Articles

We have been steadily working on a game, and as such the site has been quiet. I wanted to take a short break to discuss an issue that we ran into, as the algorithm may be of assistance to others.

Here’s the situation: assume that you have a hexagonal grid, with coordinates as laid down below. I understand the coordinates are rotated 90 degrees from what a wargamer would expect, but bear with me here – this will actually simplify things.

Given these coordinates, how would you find out which hexagons lie in the line of sight between two points, say (0,3) and (3,0)?

My first impulse was to assume this was a simple case of line rasterization, and we could apply something like Bresenham’s to solve it. This in theory works fine, but Bresenham’s was originally created for pixels, which are laid out on a non-staggered grid. This means that (2,2) will always be on the same level as (1,2), which as you can see above is not the case in our example. Because of this, it assumes that as we move left and down, we will not go back to a Y coordinate that we have already passed.

Check out however the next example:

Suppose that the red line is going from (0,3) to (3,0). This means that the line starts at (0,3), moves to (1,2), goes down to (1,1). So far so good. Immediately afterwards, however, it goes back up to (2,2) before going back down to (2,1) and ending at (3,0). This is something that Bresenham’s is not prepared to deal with at all.

It seemed to be a relatively hairy problem to solve cleanly, with an option being altering the numbering of the odd columns to crowbar them into fitting what Bresehnam’s expect, but it didn’t seem clean enough. Raycasting was too lazy a choice to actually consider it. I toyed with other alternatives, including throwing a line and calculating the hex center distance to the line, but it seem didn’t like the best solution.

Eventually I hit on something that works beautifully. Instead of considering the hexes, I consider the six triangles that the hexes are made of.

Say you were to split each hex horizontally across the middle, and then cross it from each of the other opposite corners. You would end up with six triangles, three stacked on top of each other. If we renumber these triangles according to a left-right, bottom-top sequence, we can then use Bresenham’s directly on top of the coordinates to obtain the list of triangles that are touched by the line. The end rasterization would look like this:

We then evaluate which hexagons those triangles belong to, and voilá! Those are the hexagons in your line of sight.

There are also two trivial cases, where we can skip Bresenham’s: if a line is straight up, or if the Y for both coordinates is the same and both Xs are either odd or both even (a fully horizontal line).

Hopefully this will help those rare souls who find themselves dealing with hexagon-based boards.