## 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[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.

#### 7 comments:

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

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?

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)

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

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.

3. whats is k?

4. hi, in vertical line is not working. Example: (0, 4) - (0, 8)