My next game has players rescuing metal bands stranded in a forest, trying to get the best possible photos. It’s a puzzle game. The key game mechanic is drawing paths on a hex map to connect destinations. I need to refer to hex cells and figure out their neighbouring cells.
This article is about the layout of a hex grid and finding neighbours.
Layout
Unlike a standard grid, where a simple x,y position can identify any cell, a hex map presents options and inconsistency.
The first choice is pointing the hexes vertically or horizontally.
While this may seem inconsequential, it has significant implications for the rest of the addressing. For my game, I started with horizontal, then switched to vertical, as it matched some assets I found. I will switch back to horizontal, as I find it has a better layout in landscape screens.
Cell Address
We need to pick an addressing scheme for the cells: a way to refer to each cell in the map. x and y coordinates are sufficient to address every cell in an infinite map, but how do we map that into the actual hexes? As the cells as staggered, we need to decide which ones constitute a row, and which ones are a column. Here are some reasonable choices.
One choice or the other doesn’t impact the following calculations much. Or rather, it definitely impacts how we find neighbours, but it doesn’t change the complexity of the code. The rest of this article, and my game for now, is using the left one.
For more options, check out Hexagonal Grids. They have plenty of alternatives, depending on your needs.
Neighbours
To find the neighbours of a hex, we need to refer to the sides of the hex. There are six of them, so let’s number them 0…5. It doesn’t matter from which edge we start, but unless we’re insane, we’ll increase the number around the perimeter. To me, it felt natural to start with 0 at the bottom, as it felt close to the indexing origin.
I’ve put the numbers inside the hex, as they’re the side numbers for this hex. Each cell of course has the same numbers, but the abut sides do not. Though they always come in pairs.
- Side 0 touches Side 3
- Side 1 touches Side 4
- Side 2 touches Side 5
This aspect isn’t so interesting for this article, but will become relevant for path finding later.
Think about this step carefully. It would take a lot of effort to change. From path-finding, to assets naming, and rendering, changing the numbering implies a change everywhere. Basically, once I get the first assets made, I’ve committed to my layout.
Cell Address of Neighbour
Armed with a cell address and neighbour index, we can find the addresses of neighbouring cells. Unfortunately, unlike a square grid, we can’t just increment or decrement the x or y value. This is where things get interesting.
Let’s look at the layout I’m currently using again.
Let’s consider the cell at 1,2. Here is a list of all its neighbours, and how to calculate them relatively:
- Side-0,
0,1: subtract 1 from “x” and “y” - Side-1,
0,2: subtract 1 from “x” - Side-2,
0,3: subtract 1 from “x”, add 1 to “y” - Side-3,
1,3: add 1 to “y” - Side-4,
2,2: add 1 to “x” - Side-5,
1,1: subtract 1 from “y”
Now, let’s consider the cell at 1,1. Here are its neighbours:
- Side-0,
1,0: subtract 1 from “y” - Side-1,
0,1: subtract 1 from “x” - Side-2,
1,2: add 1 to “y” - Side-3,
2,2: add 1 to “x” and “y” - Side-4,
2,1: add 1 to “x” - Side-5,
2,0: add 1 to “x”, subtract 1 from “y”
The pattern looks similar, but the additions and subtractions neither line up. Only sides 1 and 4 are the same — they have neighbours in the same row.
So what’s different? It is the staggering of the hexes and forcing them into an “x” and “y” index. Look back at the layout. Regardless of the one chosen, we can see either the row or column is offset from a square-grid layout.How we calculate the neighbours depends on which row the source cell is on.
For my layout, this is a simple test. The odd y’s get the first neighbour calculation, and the even y’s get the second neighbour calculation.
This complication arises from mapping a 6-neighbour system into a 4-neighbour indexing space. There might be indexing schemes follow a more regular pattern, but would they be useful in doing a game world layout? If you have any, please send them to me.
In the end, it doesn’t matter much. While the pattern looks complex, it’s relatively easy to code. Here’s the combined C# code from my game. It’s called GetNeighboursVert as it’s for the vertical hex cell layout. I’ll switch back to horizontal when I get the new graphics.
static public Position[] GetNeighboursVert(Position a) { var isOdd = a.y % 2 == 1; var r0 = isOdd ? new Position(a.x, a.y-1) : new Position(a.x-1, a.y-1); var r1 = new Position(a.x-1, a.y); var r2 = isOdd ? new Position(a.x, a.y+1) : new Position(a.x-1, a.y+1); var r3 = isOdd ? new Position(a.x+1, a.y+1) : new Position(a.x, a.y+1); var r4 = new Position(a.x+1, a.y); var r5 = isOdd ? new Position(a.x+1, a.y-1) : new Position(a.x, a.y-1); return new Position[]{r0,r1,r2,r3,r4,r5}; }
Layout Ambivalent
In the game I’ve mostly abstracted away the notion of a hex-grid, and even indexing. I have a type called Position. It holds an x and y value, but most of the code doesn’t care what is in there. It’s an opaque indexing value used to get cell data. My code is ambivalent about how neighbours are calculated: it simply passes this opaque Position to the getNeighbours function.
Despite being a hex-based game, most of my code doesn’t actually care about the hex-based layout. It can arbitrarily work on any layout system. For example:
- UI Selection: When a player selects a cell, I highlight it and its neighbours. The state code for each cell neither cares where it is visually, or how it is connected to its neighbours. Perhaps they are edge-to-edge (the real situation), or perhaps there’s a wormhole across the galaxy. The cell doesn’t care.
- Path Finding: The algorithm to determine if paths connect to locations also doesn’t need to know about the layout. It keeps an open list of positions, and traverses the path network, oblivious to how those paths visually relate to the cells.
One place that does care is the visual layout. It calculates the true position based on a hex grid. Placement of roads and rivers also depends on the hex layout, as they need to be rotated to match the borders.
Moving On
That’s it for indexing and neighbours. I mentioned path finding briefly, and I’ll write a followup about why I need that, and how it is done.
