Hex Grids

From StoneHome

Contents

Hex grids are a critical component of many games, especially tactical and logistical games and games with unit engagement. Many game designers rely on hex grids for various reasons including visual appeal, unit movement simplification, a solved corner-step distance problem and superior flanking behavior. There are many grids to be chosen from, including triangular grids, super/sub grids, irregular grids and various approaches to 3D and heightmapped 2D.

Hex grids are also frequently a difficult point for novice coders, and often an extremely frustrating issue, given their superficial simplicity. They're actually not so hard, once you've broken them into their discrete problems, and tackled them one at a time. So, let's do some hex grid work: storage, rendering, and simple algorithms (A*, ray-cast and shadow-cast line of sight, and so on.)

Hex grids come in a variety of flavors. Let's start by making our choices clear.

Orientation

Like any board shape, the hex can be spun on its center to reveal a "different" board. With a square grid, there are two immediately obvious sensible orientations: straight and diagonal. Similarly, with hexes, there are two sensible orientations. That said, they're difficult to name because of a curiosity about their geometry: the board, if measured by the distance from the center of the middle tile to an "outer edge" by tile traversal (ie, not a straight line), describes a hex. (Below you see two radius 4 hex grids.) A radius-N hex grid is itself hexagonal, but in the opposed orientation to the center tile; therefore, if there's a horizontal edge to the hex, then there will be a vertical edge to the grid, and vice versa. I choose to name them by grid orientation, not tile orientation; a horizontally-aligned grid is a grid on which one can move horizontally.

Image:exHexGridVert.gif
Vertically Aligned Grid
Image:exHexGridHoriz.gif
Horizontally Aligned Grid

Horizontally Aligned

Horizontally aligned grids account for the majority of hex-based board games, presumably because a hex board that fills a rectangle will have two staggered edges, and making those the short edges is aesthetically more pleasing. The orientation of the board does not affect the game in any way.

Vertically Aligned

Vertically aligned grids have a very slight advantage. It happens that there's a lucky and visually appealing tiling for vertically aligned grids of hexes to be drawn, such that the hexes are drawn with an isometric depth and can overlay one another, using only two grids of square image tiles (such as console game system background layers). Whereas that probably sounds like a bunch of mumble right now, by the end of the document it should be clear that in the case of limited gaming platforms this is an exceedingly neat and powerful little cheapo technique. We'll go with vertically aligned grids for this tutorial; changing to a horizontally aligned renderer isn't hard, but it's a pain in the ass to describe the system in vague terms to account for either, so let's just pick one for the time being. So, not because it's better for the game or for general practice, not out of aesthetics, but in order to support a cute hack that saves us some rendering time, it's vertical.

Coordinate Systems

There are a bunch of approaches to coordinate systems for hex grids. I've had to make up names for them; sorry that they suck. You get to name the next ones, 'kay?

Image:HorizStagger.gif
Horizontally staggered
vertical grid
Image:VertStagger.gif
Vertically staggered
horizontal grid

Staggered

Staggering is probably the most common amateur method for handling hexagon boards. It's relatively straightforward and easy to implement, as long as a programmer follows the one-location implementation rule (because the staggers can be placed in various ways, handling stagger placement in multiple locations is an invitation to disaster.)

Still, staggering isn't nessecary, and implies a minor logic overhead, given that which two nearby hexes against the grain are in the same row varies from column to column, so there's a bit of branching and a bit of simple mask logic implied. Not a big deal for simple games, like Abalone, Halma (Chinese Checkers,) hex adaptations of Othello, Attaxx, Connect-4, et cetera. However, hen dealing with heavy-duty use of the underlying map, such as A* / Dijkstra's Walk, other pathfinding, areafinding, shadowcasting and raycasting algorithms, especially on big maps (say, Civ3 on hex), one is best advised to spend a little time to avoid the overhead. Luckily, a better answer isn't hard to find, as long as you're aware of other missteps.

Image:HorizInterlace.gif
Horizontally interlaced
vertical grid
Image:VertInterlace.gif
Vertically interlaced
horizontal grid

Interlaced

Interlaced is another, even stranger way to handle hex grids. One also sees it occasionally in 2d isometric systems (it's worth noting that one major commercial game uses this system, so there may be an underlying trick with which I'm not yet familiar. I do hope it's not about onscreen placement, as it doesn't save anyone any time.)

Interlacing involves tracking half the cells in the against-grain axis per span, and doubling the number of spans to compensate with the intermediary cells (much like doubling the vertical raster and skipping horizontal lines, the technique underlying interlaced video.) Examples to either side show the doubled rasters as thin green lines (hey, nobody said I was an artist.) This is even more of a pain in the butt to get correct reliably if not defined in exactly one place, and unless implemented in a very crafty fashion involves around twice as much overhead as staggering. Interlacing in my opinion is not a good approach (unless, again, there's some underlying trick that I'm not aware of in the large commercial game's implementation;) if you're not willing to distort as with trapezoidal (below,) use staggering, not interlacing.

Flattened 3D

Image:Hex3D.png
Hex mapped to 3D

I very much dislike this approach, but some smart people use it, so I'll mention it and link to it in passing then not say much more. Much as hex can be mapped to a 2d grid, it can also be mapped to a 3d grid. Fill each hex with three distributed radial corner lines, and you get the standard-issue cube orientation optical illusion. From that perspective, each hex is a cube, and the hex map is actually a diagonal surface of cubes described by m=1 in all three axes (just like a Q*Bert board, when you work with a horizontally-aligned hex grid.)

Therefore, from that perspective, in cubespace calling Z the visual vertical axis, X the axis pointing inwards and to the right, and Y the axis pointing inward and to the left, then you can develop a coordinate system (x,y,z) where X refers to Northeast/Southwest movement, Y to Northwest/Southeast, and Z to North/South. There are two curious upshots to this system. One is that movement is described axially, meaning that a movement along two axes (such as a knight in chess) is automagically added together as part of looking up the cell. The other is that cells do not have canonical locations. (1,1,0), (2,0,1), (0,2,-1), (3,-1,2) and (5,-3,4) are the same hex. This leads to various bizarre properties about reflection that may have some significant use, but which I do not care to fathom. Some people work very naturally in this system. I do not. Let us never speak of this again.

It's worth realizing that this can't be a storage coordinate system, but rather only a location coordinate system, because of the lack of canonical locations; there needs to be some function to translate the coordinaates into unique positions in storage, and every lookup needs translation into this underlying system, which can be expensive. This system is very natural for a small class of idealized hex games, of the likes of Halma, Stern-Halma (Chinese Checkers,) Abalone, and so forth, because one can simply make reference to locations by adding to the coordinate systems along all three synthetic axes. However, much like with the other two already-discussed systems (but much moreso) this system implies a significant amount of overhead and shouldn't be used when large board-intensive searches, such as A*, pathfinding and area selection need to be carried out.

Trapezoidal

This coordinate system is based on the observation that a hex grid can be seen as a distrorted square grid, and is therefore actually a standard 2d grid and can be stored as such. This is a very fast solution, though implementing it in a general fashion is sometimes a bit of a hassle the first time around. Luckily, you've got a tutorial on hand, so, let's go.