Table of Contents
In the description of the Bresenham
linedrawing algorithm one aspect remained not covered  what if we need to find every hexagon intersecting
with the line. You can see the difference between linedrawing algorithm and "line of sight" algorithm in the
picture above, where hex (4,0)
is visited only in the latter case.
Such an algorithm might be useful, for example, in a game where a unit fires a projectile along a line, and
the projectile needs to hit every object it encounters while moving by the line. For example, it would be a pity
if a firebat's flame, fired from (0,0)
to (7,1)
, missed a
zergling sitting at (4,0)
.
The following sections describe how the line of sight building algorithm can be implemented in a very similary to linedrawing algorithm fashion. Reading the Bresenham algorithm post beforehand might greatly aid understanding of what follows.
We will start with drawing a 1^{st} quadrant line, using a coordinate system where hexagon side is the unit.
There are 6
directions on a grid, and we're going to need 4 of them (UL
, UR
, R
, DR
) for the 1^{st} quadrant
case. Now, let's start drawing a line, choosing intersecting hexes, and keeping track of a deviation of a real
line from the center of the current hex (just like it is done in the Bresenham algorithm for horizontallybiased lines in the 1^{st} quarter).
During this process, the following four cases are possible:
In the picture above, after we did a move to the UP_RIGHT
from (0,0)
to (0,1)
, ε
exceeds 1.0
value, indicating that the next move should certainly be UP_LEFT
.
Note, that since the α
here is close to 90
, the °
k=ΔY/ΔX
is huge (this is a verticallybiased line), but we're still drawing it like it's a horizontallybiased one. So, ε
changes a lot in just a single step, but we
won't miss any hexes since occasional UP_LEFT
movements are tracked.
Now, first portion of the algorithm would look like this:
... if (ε > 1.0) current hex ← get UP_LEFT hex ε ← ε  k*s  1.5 // s = sqrt(3)/2 else ... end if
Note
In fact, (ε > 1.0)
better be (ε >= 1.0)
if you
want lines like (0,0)
 (0,2)
to be "truly" intersecting,
i.e. covering both (0,1)
and (1,1)
hexes.
When ε
is less than 1.0
after the latest move, we ought
to do the next move, and choose from 3 remaining variants (we can't move UP_LEFT
here, because every move only increases X
coord):
From the picture above, it should be obvious that UP_RIGHT
move occurs when
is greater than ε
0.5
. So, we
extend our algorithm to this:
... if (ε >= 1.0) current hex ← get UP_LEFT hex ε ← ε  k*s  1.5 // s = sqrt(3)/2 else ε ← ε + k*s if (ε > 0.5) current hex ← get UP_RIGHT hex ε ← ε  1.5 else ... // handle remaining RIGHT and DOWN_RIGHT cases end if end if
Looking at the picture above, we see that DOWN_RIGHT
move happens when ε
is less than 0.5
, and remaining case is moving RIGHT
(not shown in the picture):
... if (ε >= 1.0) current hex ← get UP_LEFT hex ε ← ε  k*s  1.5 // s = sqrt(3)/2 else ε ← ε + k*s if (ε > 0.5) current hex ← get UP_RIGHT hex ε ← ε  1.5 else if (ε < 0.5) current hex ← get DOWN_RIGHT hex ε ← ε + 1.5 else current hex ← get RIGHT hex ε ← ε + k*s // when moving RIGHT, no need to add/sub 1.5, since we remain on the same horizontal end if end if end if
Now, if we remember the definition of k, complete 1^{st} quadrant algorithm becomes:
Example 1. 1^{st} quadrant LOS algorithm
current hex ← start hex color current hex ε ← 0 while current hex ≠ end hex if (ε >= 1.0) current hex ← get UP_LEFT hex ε ← ε  (3*ΔY_{old})/(4*ΔX_{old})  1.5 else ε ← ε + (3*ΔY_{old})/(4*ΔX_{old}) if (ε > 0.5) current hex ← get UP_RIGHT hex ε ← ε  1.5 else if (ε < 0.5) current hex ← get DOWN_RIGHT hex ε ← ε + 1.5 else current hex ← get RIGHT hex ε ← ε + (3*ΔY_{old})/(4*ΔX_{old}) end if end if end if color current hex end while
Multiplying everything by the factor of 4*ΔX_{old}
, and introducing
ε_{new} = ε_{old}*4*ΔX_{old}
, we have:
Example 2. Integeronly, nodivision, 1^{st} quadrant LOS algorithm
current hex ← start hex color current hex ε ← 0 // or ε ← 2*2*ΔX_{old} while current hex ≠ end hex if (ε >= 2*2*ΔX_{old}) // or ε > 0 current hex ← get UP_LEFT hex ε ← ε  3*ΔY_{old}  3*2*ΔX_{old} else ε ← ε + 3*ΔY_{old} if (ε > 2*ΔX_{old}) // or ε > 2*ΔX_{old} current hex ← get UP_RIGHT hex ε ← ε  3*2*ΔX_{old} else if (ε < 2*ΔX_{old}) // or ε < 3*2*ΔX_{old} current hex ← get DOWN_RIGHT hex ε ← ε + 3*2*ΔX_{old} else current hex ← get RIGHT hex ε ← ε + 3*ΔY_{old} end if end if end if color current hex end while
Note
It's possible to freely choose initial value of ε
as long as every inequation in
the algorithm gets adjusted. I find the algorithm to be better readable when 4*ΔX_{old}
is chosen as a starting value for ε
(see comments
above).
Having 1^{st} quadrant covered, we can exploit the symmetry and extend the algorithm to the full 2d plane:
Example 3. All quadrants LOS algorithm
2*ΔX_{old} ← get doubled X delta between end hex and start hex ΔY_{old} ← get Y delta between end hex and start hex X_{sign} ← sign(ΔX_{old}) // 1 or +1 Y_{sign} ← sign(ΔY_{old}) // 1 or +1 δY ← abs(ΔY_{old}) δX ← abs(2*ΔX_{old}) current hex ← start hex color current hex ε ← 2*δX while current hex ≠ end hex if (ε >= 0) current hex ← get DIRS[X_{sign}][Y_{sign}] hex // UP_LEFT for 1^{st} quadrant ε ← ε  3*δY  3*δX else ε ← ε + 3*δY if (ε > δX) current hex ← get DIRS[X_{sign}][Y_{sign}] hex // UP_RIGHT for 1^{st} quadrant ε ← ε  3*δX else if (ε < 3*δX) current hex ← get DIRS[X_{sign}][Y_{sign}] hex // DOWN_RIGHT for 1^{st} quadrant ε ← ε + 3*δX else current hex ← get DIRS[0][X_{sign}] hex // RIGHT for 1^{st} quadrant ε ← ε + 3*δY end if end if end if color current hex end while
Where DIRS
table is the familiar magic table:
Table 1. DIRS[i][j]
table used in the algorithm
above
i=1 
i=0 
i=+1 

j=1 
DOWN_LEFT 
LEFT 
DOWN_RIGHT 
j=+1 
UP_LEFT 
RIGHT 
UP_RIGHT 

Another explanation of LOS algorithm (as well as Bresenham's line algorithm). There is also a very good introduction to hexagonal grids, coordinates on it, and other algorithms, like FOV (field of view) building.

Amit's Game Programming Information
List of hexagonal grids related resources.
This page is extremely helpful for a project that i am working on.
ReplyDeleteYou say that:
ReplyDeleteXsign ← sign(ΔXold) // 1 or +1
Ysign ← sign(ΔYold) // 1 or +1
But if you want to test from a=(0,0) to b=(0,4) then bxax = 00 = 0. Should sign(0) be 1 or 1?
@Anonymous:
Deletesign(0) can be either +1 or 1. There're 2 possibilities to build vertical line from (0, 0) to (0, 4):
1) (0, 0)→(0, 1)→(0, 2)→(0, 3)→(0, 4)
2) (0, 0)→(1, 1)→(0, 2)→(1, 3)→(0, 4)
Your sign(0) choice simply selects one of these possibilities.
But, for lineofsight algorithm the choice of sign(0) doesn't matter, see also the Note in section 2.1: http://zvold.blogspot.ch/2010/02/lineofsightonhexagonalgrid.html#id2838157
That is, because of "if (ε >= 0)", we'll just get all hexes covered: (0, 0)→(1, 1)→(0, 1)→(0, 2)→(1, 3)→(0, 3)→(0, 4)
I have problem with that "if (ε >= 0)": in my game it take (0, 0)→(1, 0)→(2, 0)...
DeleteI don't know why :(
Cool stuff! I'm not a math whiz so this is a bit over my head I'm afraid...
DeleteI wrote a computer version of "Hold the Line" and this part of the engine by far took the longest, and tbh, I'm not entirely happy with it. It's a hodgepodge of code found off the web w/ my changes specific to the game. I need to look at it again to both understand it *and* improve it.
I will use this posting as a reference when I get to it.
whats is k?
ReplyDelete