Line of sight on a hexagonal grid

Table of Contents

1. Introduction

2. 1^st quadrant algorithm

2.1. Moving UP_LEFT

2.2. Moving UP_RIGHT

2.3. Moving DOWN_RIGHT or RIGHT

2.4. Going integer-only

3. Remaining quadrants

4. Further reading

1. Introduction

In the description of the Bresenham line-drawing algorithm one aspect remained not covered - what if we need to find every hexagon intersecting with the line. You can see the difference between line-drawing 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 line-drawing algorithm fashion. Reading the Bresenham algorithm post beforehand might greatly aid understanding of what follows.

2. 1^st quadrant algorithm

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 horizontally-biased lines in the 1^st quarter).

During this process, the following four cases are possible:

2.1. Moving UP_LEFT

Figure 2. Moving UP_LEFT from (0,1) to (0,2)

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 vertically-biased line), but we're still drawing it like it's a horizontally-biased 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):

2.2. Moving UP_RIGHT

Figure 3. Moving UP_RIGHT from (0,1) to (1,2)

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

2.3. Moving DOWN_RIGHT or RIGHT

Figure 4. Moving DOWN_RIGHT from (2,1) to (3,0)

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

2.4. Going integer-only

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*ΔYold)/(4*ΔXold) - 1.5
  else
    ε ← ε + (3*ΔYold)/(4*ΔXold)
    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*ΔYold)/(4*ΔXold)
      end if
    end if
  end if
  color current hex
end while

Multiplying everything by the factor of 4*ΔXold, and introducing εnew = εold*4*ΔXold, we have:

Example 2. Integer-only, no-division, 1^st quadrant LOS algorithm

current hex ← start hex
color current hex
ε ← 0                                           // or ε ← -2*2*ΔXold
while current hex ≠ end hex
  if (ε >= 2*2*ΔXold)                            // or ε > 0
    current hex ← get UP_LEFT hex
    ε ← ε - 3*ΔYold - 3*2*ΔXold
  else
    ε ← ε + 3*ΔYold
    if (ε > 2*ΔXold)                            // or ε > -2*ΔXold
      current hex ← get UP_RIGHT hex
      ε ← ε - 3*2*ΔXold
    else
      if (ε < -2*ΔXold)                         // or ε < -3*2*ΔXold
        current hex ← get DOWN_RIGHT hex
        ε ← ε + 3*2*ΔXold
      else
        current hex ← get RIGHT hex
        ε ← ε + 3*ΔYold
      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*ΔXold is chosen as a starting value for ε (see comments above).

3. Remaining quadrants

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*Δ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
ε ← -2*δX
while current hex ≠ end hex
  if (ε >= 0)
    current hex ← get DIRS[-Xsign][Ysign] hex                  // UP_LEFT for 1st quadrant
    ε ← ε - 3*δY - 3*δX
  else
    ε ← ε + 3*δY
    if (ε > -δX)
      current hex ← get DIRS[Xsign][Ysign] hex                 // UP_RIGHT for 1st quadrant
      ε ← ε - 3*δX
    else
      if (ε < -3*δX)
        current hex ← get DIRS[Xsign][-Ysign] hex              // DOWN_RIGHT for 1st quadrant
        ε ← ε + 3*δX
      else
        current hex ← get DIRS[0][Xsign] hex                  // RIGHT for 1st 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

4. Further reading

• Clark Verbrugge’s Hex Grids

  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.