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, step-by-step.
First of all, let us grok the basics of the algorithm on rectangular grid. Consider the following example of
drawing of a 1st quadrant, horizontally-biased 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 up-right. 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 negative-slope lines as well as
vertically-biased 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 vertically-biased and horizontally-biased lines separately.
Similarly to rectangular case, if we consider only the 1st quadrant (i.e. 0°≤α<90°), then a line is horizontally-biased when we only have to choose between R and UR hexes while drawing the line from left to right. In other
words, in the 1st quadrant, 0°≤α<60° defines horizontally-biased line,
and 60°≤α<90° defines vertically-biased line (for which we will choose between
UL and UR hexes while drawing upwards).
In the above picture, X-axis and Y-axis have different scales. Using these units of measurement, checking
for a line to be horizontally-biased is simple. If (i0,j0) is a
starting hex in hexagonal coords, and (i1,j1) - ending hex,
then line is horizontally-biased if ΔY<2*ΔX. Where ΔY=j1-j0, 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 horizontally-biased and vertically-biased lines (i.e.
α=60°).
Here is a way to calculate 2*ΔX:
2*ΔX = 2*(i1-i0)+abs(j1 mod 2)-abs(j0 mod 2)
where (i0,j0) and (i1,j1) 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 horizontally-biased using integer-only, no-division math.
Let's try to draw a line between (0,0) and (3,1)
step-by-step and devise a general algorithm for it in the process. First, I'd like to choose hexagon side as
new unit of measurement:
This re-scales 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 Xold and Yold, and note
that transformation to new measurement units is Xnew=Xold*sqrt(3), Ynew=Yold*1.5, we can get same result by using ΔX and ΔY from 3.2 (marking them ΔXold and ΔYold):
k = ΔYnew/ΔXnew = (ΔYold*1.5)/(ΔXold*sqrt(3)) = (ΔYold/ΔXold) * (sqrt(3)/2) = sqrt(3) * ΔYold / (2*ΔXold)
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 h-biased 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)*ΔYold/(2*ΔXold) * sqrt(3)/2 = (3*ΔYold)/(4*ΔXold)
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*ΔXold), and introduce new variable
ε'=ε*(4*ΔXold). Then the algorithm for horizontally-biased lines in
1st quarter becomes:
Example 2. Bresenham's line algorithm for h-biased lines, 1st quadrant
current hex ← start hex
color current hex
ε' ← 0 // step 0
while current hex ≠ end hex
ε' ← ε' + 3*ΔYold // steps 1,3,5,7 "move out by increasing ε=ε+k*s"
if ε' > 2*ΔXold then // steps 1a,3a,5a,7a "decide by comparing ε>0.5"
current hex ← get UP_RIGHT hex
ε' ← ε' - 3*2*ΔXold // step 4 "adjust ε after UR move, ε=ε-1.5"
else
current hex ← get RIGHT hex
ε' ← ε' + 3*ΔYold // 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*ΔXold using only integer math, and ΔYold is of course just (jend-jstart), where j is the 2nd
hexagonal coordinate.
Thus, the algorithm above requires only integer math, and doesn't use division.
Ok, now to the vertically-biased 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 1st quadrant, we will choose
between UL and UR hexes while drawing upwards:
In the picture above, we're drawing a vertically-biased line from hex (0,0) to hex
(0,3). Similarly to the rectangular grid and horizontally-biased 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=ΔXold/ΔYold, 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. Non-integer algorithm for v-biased lines, 1st quadrant
current hex ← start hex
color current hex
ε ← 0
while current hex ≠ end hex
ε ← ε + ΔXold/ΔYold
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*ΔYold, and introduce
new variable ε'=ε*2*ΔYold. This will once again get us integer-only, no-division algorithm:
Example 4. Bresenham's line algorithm for v-biased lines, 1st quadrant
current hex ← start hex
color current hex
ε' ← 0
while current hex ≠ end hex
ε' ← ε' + 2*ΔXold
if ε' > 0 then
current hex ← get UP_RIGHT hex
ε' ← ε' - ΔYold
else
current hex ← get UP_LEFT hex
ε' ← ε' + ΔYold
end if
color current hex
end while
So far, we have only considered the 1st quadrant. Due to symmetry, drawing of the lines in the
remaining 3 quadrants can be performed using exactly same algorithms (for both h-biased and v-biased 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, green-ish sectors hold all vertically-biased lines, and red-ish ones hold all horizontally-biased lines.
For example, when we're drawing a horizontally-biased line in a red sector, we can "imagine" that we are
drawing mirrored (over X or Y or both axes) line in the
1st 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
h-biased lines:
Example 5. Bresenham's line algorithm for h-biased lines, all quadrants
2*ΔXold ← get doubled X delta between end hex and start hex ΔYold ← get Y delta between end hex and start hex Xsign ← sign(ΔXold) // -1 or +1 Ysign ← sign(ΔYold) // -1 or +1 δY ← 3*abs(ΔYold) δX ← 3*abs(2*ΔXold) current hex ← start hex color current hex ε ← 0 while current hex ≠ end hex ε ← ε + δY if ε > abs(2*ΔXold) then current hex ← get DIRS[Xsign][Ysign] hex ε ← ε - δX else current hex ← get DIRS[0][Xsign] 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 vertically-biased lines can be constructed in a similar way:
Example 6. Bresenham's line algorithm for v-biased lines, all quadrants
2*ΔXold ← get doubled X delta between end hex and start hex ΔYold ← get Y delta between end hex and start hex Xsign ← sign(ΔXold) // -1 or +1 Ysign ← sign(ΔYold) // -1 or +1 δY ← abs(ΔYold) δX ← abs(2*ΔXold) current hex ← start hex color current hex ε ← 0 while current hex ≠ end hex ε ← ε + δX if ε > 0 then current hex ← get DIRS[Xsign][Ysign] hex ε ← ε - δY else current hex ← get DIRS[-Xsign][Ysign] 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 line-drawing 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://www-cs-students.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.arges-systems.com/articles/39/line-of-sight-in-hex-grid
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.
ReplyDeleteThis book can be used to demonstrate to children that the more descriptive language they use in their writing the more vivid it becomes. http://bz5tg9ifet.dip.jp http://5wfidapzun.dip.jp http://ehhcl4q3rp.dip.jp
ReplyDelete