Table of Contents
There is a lot of comprehensive resources available regarding Bresenham's line algorithm on a rectangular grid. Hexagonal grids case, however, is rarely described in a friendly to a beginner way. This article is an attempt on explaining the hexagonal grids case, with pictures and verbose explanations.
We will start with a brief look at the classic algorithm, then introduce hexagonal grid, coordinate system, and build Bresenham's line drawing algorithm for it, stepbystep.
First of all, let us grok the basics of the algorithm on rectangular grid. Consider the following example of
drawing of a 1^{st} quadrant, horizontallybiased line (i.e. 0°≤α<45°
) from
point (0,0)
to point (3,2)
in cartesian coordinates:
To draw a line, we move "current" pixel to the right pixel by pixel, and determine which one of two adjacent
pixels to fill: (1) a pixel to the right or (2) a diagonal pixel to the upright. To do this, we keep track of a
deviation from the ideal line for each step, shown on the picture asε_{n}
(index n denotes subsequent values of ε
). Deviation increases to the value
of k=ΔY/ΔX
for every "horizontal" step, and as soon as it exceeds 0.5
(half the pixel size), we know we should make a "diagonal" step (and decrease ε
by 1.0
, naturally).
Now, despite k
can be fractional, it is actually possible to perform all
calculations in integer math and without division, by applying a simple trick (namely, taking 2*ΔX
as a unit). Also, it should be obvious that drawing of negativeslope lines as well as
verticallybiased ones is essentially similar. More details could be found, for example, here. Or just keep reading,
since we are going to dig into all this for hexagonal grid case.
On a hexagonal grid, the algorithm is very similar. All calculations will still be performed in cartesian
coords, but we will scale X
and Y
axes differently.
Let's choose some grid orientation and a simple coordinate system on a hexagonal grid, just to introduce common terminology for addressing hexes.
In the picture above, a set of hexes having the same X coordinate is highlighted. This also introduces 6 directions on the grid.
Now, since hexagonal grids have different type of symmetry than rectangular ones, we will consider verticallybiased and horizontallybiased lines separately.
Similarly to rectangular case, if we consider only the 1^{st} quadrant (i.e. 0°≤α<90°
), then a line is horizontallybiased when we only have to choose between R
and UR
hexes while drawing the line from left to right. In other
words, in the 1^{st} quadrant, 0°≤α<60°
defines horizontallybiased line,
and 60°≤α<90°
defines verticallybiased line (for which we will choose between
UL
and UR
hexes while drawing upwards).
In the above picture, Xaxis and Yaxis have different scales. Using these units of measurement, checking
for a line to be horizontallybiased is simple. If (i_{0},j_{0})
is a
starting hex in hexagonal coords, and (i_{1},j_{1})
 ending hex,
then line is horizontallybiased if ΔY<2*ΔX
. Where ΔY=j_{1}j_{0}
, and ΔX
is cartesian distance between
start and end hexes. Both ΔY
and 2*ΔX
are always integer.
Blue line is an example of border case between horizontallybiased and verticallybiased lines (i.e.
α=60°
).
Here is a way to calculate 2*ΔX
:
2*ΔX = 2*(i1i0)+abs(j1 mod 2)abs(j0 mod 2)
where (i_{0},j_{0})
and (i_{1},j_{1})
are start and end hexes in hexagonal coords, abs()
returns absolute value.
Note
Now, given start and end points in hexagonal coords, we can determine if a line is horizontallybiased using integeronly, nodivision math.
Let's try to draw a line between (0,0)
and (3,1)
stepbystep and devise a general algorithm for it in the process. First, I'd like to choose hexagon side as
new unit of measurement:
This rescales both X
and Y
axes differently. For the
blue line in the picture above, in this new coordinates we have:
k = tan(α) = 1.5 / (3.5 * sqrt(3)) = sqrt(3)/7
Or, if we name axes from section
3.2 as X_{old}
and Y_{old}
, and note
that transformation to new measurement units is X_{new}=X_{old}*sqrt(3)
, Y_{new}=Y_{old}*1.5
, we can get same result by using ΔX
and ΔY
from 3.2 (marking them ΔX_{old}
and ΔY_{old}
):
k = ΔY_{new}/ΔX_{new} = (ΔY_{old}*1.5)/(ΔX_{old}*sqrt(3)) = (ΔY_{old}/ΔX_{old}) * (sqrt(3)/2) = sqrt(3) * ΔY_{old} / (2*ΔX_{old})
Now, we will start by filling pixel (0,0)
, and move to the right by the step
s=sqrt(3)/2
at a time. On each step we choose which pixel to fill in, R
or UR
, and keep track of deviation ε
of
pixelized line from the ideal line (again, index n
of ε_{n}
in the picture shows subsequent changes of ε
):
Example 1. Steps to build hbiased line from (0,0) to (3,1)
0) ε_{0}=0, color current pixel (0,0) 1) move out: ε_{1}=ε_{0}+k*s 1a) decide where to move: ε_{1}<=0.5, so we will move to the R hex 2) color hex (1,0), and increase ε once more: ε_{2}=ε_{1}+k*s. Now hex (1,0) is the current one 3) move out: ε_{3}=ε_{2}+k*s 3a) decide where to move: ε_{3}>0.5, so we will move to the UR hex 4) color hex (1,1), and adjust ε accordingly: ε_{4}=ε_{3}1.5. Now hex (1,1) is current, and ε is negative (thus shown in red) 5) move out: ε_{5}=ε_{4}+k*s, ε is still negative (and will remain such till the final hex) 5a) decide where to move: ε_{5}<=0.5, hence R hex is next 6) color hex (2,1), and increase ε once more: ε_{6}=ε_{5}+k*s. Now hex (2,1) is current 7) move out: ε_{7}=ε_{6}+k*s 7a) decide where to move: ε_{7}<=0.5, hence R hex is next 8) color hex (3,1), and we are done
As a check, if we perform ε=ε+k*s after the last step, we should get 0.0
.
Indeed:
ε_{final}=ε_{begin} + 7*k*sqrt(3)/2  1.5 = 0 + 7 * (sqrt(3)/7) * (sqrt(3)/2)  3/2 = 0
All this doesn't look like integer math at all, so let's make the following observation:
k*s = k * sqrt(3)/2 = sqrt(3)*ΔY_{old}/(2*ΔX_{old}) * sqrt(3)/2 = (3*ΔY_{old})/(4*ΔX_{old})
So, k*s
can be calculated purely in integer, but we also do not want division.
Since everything we need to choose between R and UR is merely ε
, let's multiply
every formula in question by (4*ΔX_{old})
, and introduce new variable
ε'=ε*(4*ΔX_{old})
. Then the algorithm for horizontallybiased lines in
1^{st} quarter becomes:
Example 2. Bresenham's line algorithm for hbiased lines, 1^{st} quadrant
current hex ← start hex color current hex ε' ← 0 // step 0 while current hex ≠ end hex ε' ← ε' + 3*ΔY_{old} // steps 1,3,5,7 "move out by increasing ε=ε+k*s" if ε' > 2*ΔX_{old} then // steps 1a,3a,5a,7a "decide by comparing ε>0.5" current hex ← get UP_RIGHT hex ε' ← ε'  3*2*ΔX_{old} // step 4 "adjust ε after UR move, ε=ε1.5" else current hex ← get RIGHT hex ε' ← ε' + 3*ΔY_{old} // steps 2,6 "adjust ε after R move, ε=ε+k*s" end if color current hex // steps 2,4,6,8 "color current hex" end while
Note
We know how to calculate 2*ΔX_{old}
using only integer math, and ΔY_{old}
is of course just (j_{end}j_{start})
, where j
is the 2^{nd}
hexagonal coordinate.
Thus, the algorithm above requires only integer math, and doesn't use division.
Ok, now to the verticallybiased lines. Things are simpler if we go back to original coordinates
introduced in section 3.2 (i.e. unit
of measurement is the diameter of hex's inscribed circle). For the 1^{st} quadrant, we will choose
between UL
and UR
hexes while drawing upwards:
In the picture above, we're drawing a verticallybiased line from hex (0,0)
to hex
(0,3)
. Similarly to the rectangular grid and horizontallybiased lines on a hexagonal grid cases, we keep track of
a deviation ε_{n}
on each step n
. Red color means
that ε
is negative. On each step, we increase ε
by
k*s
, where k=ΔX_{old}/ΔY_{old}
, and
s=1
(moving in Y
direction), then decide between
UL
and UR
hexes, and adjust ε
by adding/substracting 0.5
.
That is, the algorithm would be very similar to the previous one:
Example 3. Noninteger algorithm for vbiased lines, 1^{st} quadrant
current hex ← start hex color current hex ε ← 0 while current hex ≠ end hex ε ← ε + ΔX_{old}/ΔY_{old} if ε > 0 then current hex ← get UP_RIGHT hex ε ← ε  1/2 else current hex ← get UP_LEFT hex ε ← ε + 1/2 end if color current hex end while
Again, let's multiply everything in the algorithm above by the factor of 2*ΔY_{old}, and introduce
new variable ε'=ε*2*ΔY_{old}. This will once again get us integeronly, nodivision algorithm:
Example 4. Bresenham's line algorithm for vbiased lines, 1^{st} quadrant
current hex ← start hex color current hex ε' ← 0 while current hex ≠ end hex ε' ← ε' + 2*ΔX_{old} if ε' > 0 then current hex ← get UP_RIGHT hex ε' ← ε'  ΔY_{old} else current hex ← get UP_LEFT hex ε' ← ε' + ΔY_{old} end if color current hex end while
So far, we have only considered the 1^{st} quadrant. Due to symmetry, drawing of the lines in the
remaining 3 quadrants can be performed using exactly same algorithms (for both hbiased and vbiased lines) but operating on absolute values
of ΔX
and ΔY
, and choosing directions to move on each
step accordingly. Consider the following picture of four quadrants:
In the picture above, greenish sectors hold all verticallybiased lines, and redish ones hold all horizontallybiased lines.
For example, when we're drawing a horizontallybiased line in a red sector, we can "imagine" that we are
drawing mirrored (over X
or Y
or both axes) line in the
1^{st} quadrant. We will assign ΔX
and ΔY
their
absolute values and track ε deviation as we have done previously, but use not original R/UR
directions to move, but modify them accordingly. Here is one possible way to implement unified algorithm for
hbiased lines:
Example 5. Bresenham's line algorithm for hbiased lines, all quadrants
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 ← 3*abs(ΔY_{old}) δX ← 3*abs(2*ΔX_{old}) current hex ← start hex color current hex ε ← 0 while current hex ≠ end hex ε ← ε + δY if ε > abs(2*ΔX_{old}) then current hex ← get DIRS[X_{sign}][Y_{sign}] hex ε ← ε  δX else current hex ← get DIRS[0][X_{sign}] hex ε ← ε + δY end if color current hex end while
It uses 2d table named DIRS
to choose appropriate hexagonal directions:
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 
Note
While using a table is more illustrative, it might be wiser (from the performance point of view) to implement separate functions for each quadrant. But performance measurements of various methods to move around on a hex grid is a different topic...
Unified algorithm for verticallybiased lines can be constructed in a similar way:
Example 6. Bresenham's line algorithm for vbiased lines, all quadrants
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 ε ← 0 while current hex ≠ end hex ε ← ε + δX if ε > 0 then current hex ← get DIRS[X_{sign}][Y_{sign}] hex ε ← ε  δY else current hex ← get DIRS[X_{sign}][Y_{sign}] hex ε ← ε + δY end if color current hex end while

http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html
Excellent illustrative explanation of Bresenham linedrawing algorithm on a rectangular grid. Covers negative slopes, every quadrant and everything.

http://www.falloutsoftware.com/tutorials/dd/dd4.htm
Another nice tutorial with source code.

http://wwwcsstudents.stanford.edu/~amitp/Articles/HexLOS.html
Another explanation of Bresenham's line algorithm (line of sight), together with a very good introduction to hexagonal grids, coordinates on it, and other algorithms, like FOV (field of view) building.

http://www.argessystems.com/articles/39/lineofsightinhexgrid
Short comment on a seemingly different approach to line building.

Amit's Game Programming Information
List of hexagonal grids related resources.
This helped me out quite considerably in exactly the areas I was struggling with  thanks a bunch!
ReplyDeleteThanks you very much! You make it just simple as in rectangle coordinate.
ReplyDeleteThe notation choice for the variable 2*ΔXold led to quite a bit of confusion for me. Readers can easily skip past the note which describes how this variable is calculated and assume it is literally "Two times ΔXold" which results in confounding errors in the algorithm because the column offset (staggered pattern) is not being accounted for.
ReplyDelete