Feb 7, 2010

Line of sight on a hexagonal grid

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. 1st quadrant algorithm

We will start with drawing a 1st 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 1st 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 1st 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 1st quadrant algorithm becomes:

Example 1. 1st 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, 1st 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 1st 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.

5 comments:

  1. This page is extremely helpful for a project that i am working on.

    ReplyDelete
  2. You say that:

    Xsign ← 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 bx-ax = 0-0 = 0. Should sign(0) be 1 or -1?

    ReplyDelete
    Replies
    1. @Anonymous:

      sign(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 line-of-sight algorithm the choice of sign(0) doesn't matter, see also the Note in section 2.1: http://zvold.blogspot.ch/2010/02/line-of-sight-on-hexagonal-grid.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)

      Delete
    2. I have problem with that "if (ε >= 0)": in my game it take (0, 0)→(1, 0)→(2, 0)...
      I don't know why :(

      Delete
    3. Cool stuff! I'm not a math whiz so this is a bit over my head I'm afraid...

      I 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 hodge-podge 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.

      Delete

Google+ Badge