Hex maps. Every wargamer knows them. Expert D&D players broke out of their dual-axis world during their Isle of Dread campaign to use these six-sided monsters. Here’s a close up of one:
Hex maps, it is claimed, offer a more natural choice of direction for players who want to model open air terrain than the good old graph-paper, cartesian plane, 2 perpendicular axes maps. Graph paper maps do match up well to the four cardinal points of a compass, which is nice. Even better for programmers, these kinds of maps are easily represented with 2 dimensional arrays, a data structure that even grumpy old C supports!
And it’s easy to find the neighboring squares in this kind of map. Consider a coordinate system whose origin (0,0) is the upper most left corner of a grid. Going to the right adds to the x coordinate, while going left subtracts from it. Similarly, going down to the bottom of the grid adds to the y coordinate, but going up lessens the y value. If the starting square can be thought of as being at the coordinate (x,y), then neighbors can be found at predictable offsets:
- Northern neighbor: (x, y-1)
- Eastern neighbor: (x+1, y)
- Southern neighbor: (x, y+1)
- Western neighbor: (x-1, y)
It’s easy to extrapolate how you could find the diagonal squares too if you wanted to, but that’s not desirable for wargamers. There are at most only four equidistant neighbors for any given square on the graph paper map. Sure, you could include the four squares pointed to by the diagonals of the square, but these are more distant from the center of the square than the neighbors at the cardinal points. And that makes wargamers mad! How can you accurately plot the range of your 18th century dutch cannon using only the cardinal compass points?! Hex maps offer up to six equidistant neighbors for any given hex. And that means more accurate pathing for cannon fire. Super!
But how do you model a map in which each element has six neighbors? You could make a linked list of structures that contain pointers to each of their neighbors. But that’s not a particularly natural fit and would cause a great deal of programming overhead to populate and search. Is there a way to get all the benefits of a hex map into a 2D array implementation? Yes, there is but you need to to think about a hex map in a certain way.
Look at Figure 1 again, but try to see the map as three columns of hexes stacked on top of each other. Notice that although the first column (with hexes A and D) are horizontally aligned with the last column (with hexes C and F) but the the middle column (with hexes B, E and G) is a bit offset. This is an important detail that will affect our hex map model. We can order these hexes from left to right, top to bottom if we take into account the offset columns that happen every other time. That is, all the odd number columns are offset from the even numbered ones. We can make a horizontal row by starting with a left-most hex. Then, find the “northeastern” neighbor in the odd row. To find the horizontal neighbor of that hex, look to its “southeastern” side. In Figure 1, the first horizontal row is marked out as hexes A, B and C. Continue this alternation until you hit the last column of hexes.
Once we have a predictable sorting order for our hexes, we can use a 2D array to model this map. Why bother with a 2D for a linear list? The answer is that a 2D array naturally maps to the way computer screens are represented in most drawing libraries. 2D arrays also fit easily into an SQL database system. So, even though the thing we want could be represented in a number of ways, there’s a lot of convenience to be had in thinking of (x,y) coordinates. So given a hex coordinate, how can we determine its neighbors in a 2D array? The answer is: it depends!
It depends on whether the hex is in a odd numbered column or an even numbered one. Consult the two tables below. I look for neighboring hexes in a clockwise direction starting at the top of the hex (which would be the northern neighbor).
Figure 3: Calculating Neighbors for Hexes in Even Columns
Figure 4: Calculating Neighbors for Hexes in Odd Columns
And for the purposes of this discussion, column 0 counts as even. Does your brain hurt a little? Mine too. Let’s make this more concrete.
Using Figure 1, let’s create a 2D array that maps the hexes in the right order.
|0||A (0,0)||B (1,0)||C (2,0)|
|1||D (0,1)||E (1,1)||F (2,1)|
Figure 5: Mapping a Hex Map into a 2D Array
I have included the coordinates of the hex in this table for easier reference. Let’s walk through our algorithm to find all the neighbors of each point.
|A (0,0)||(0,-1)||D (1,0)||E (1,1)||B (0,1)||(-1, 1)||(-1,0)|
|B (1,0)||(1,-1)||(2,-1)||C (2,0)||E (1,1)||A (0,0)||(0,-1)|
|C (2,0)||(2,-1)||(3,0)||(3,1)||F (2,1)||E (1,1)||B (1,0)|
|D (0,1)||A (0,0)||E (1,1)||(1,2)||(0,2)||(-1, 2)||(-1,1)|
|E (1,1)||B (1,0)||C (2,0)||E (2,1)||G (1,2)||B (0,1)||A (0,0)|
|F (2,1)||C (2,0)||(3,1)||(3,2)||(2,2)||G (1,2)||E (1,1)|
Whew! That’s quite a table of mind-numbing numbers! What this table is attempting to show is the neighboring hexes for each hex appearing in the left-hand column. Computations which result in a valid location are shown with that area’s label. Computations that produce bum results are shown in italics, just to give you some idea how the edge cases work.
Now that you can easily find the neighbors of any hex, you can implement any of the class of algorithms designed to calculate shortest path, distance, etc. Of particular note, A* pathfinding and shortest distance routines should fall out nicely once you wrap the neighbor calculations into some kind of function.
Which is an exercise I leave for the reader. I realize that modeling hex maps is a solved problem, but I worked this stuff out for myself. Thinking of these sorts of things keeps me off the streets and high on life.
UPDATE: Other people are interested in hex maps too.