A grid of hexagons is quickly drawn on paper. In code the trouble starts with the first question: what is a cell called? A normal grid has x and y, four neighbors and a distance you can work out in your sleep. With hexagons none of that holds, and there are several ways to number the cells.
The demo shows a board of 9 by 7 hexes. A click or drag places the cursor, on the right the same cell is shown as offset, axial, cube and doubled. The six neighbors light up orange, every other cell shows its distance to the cursor. Move the mouse over a cell and you see how that number comes together.
The chips at the bottom right switch between pointy (a corner points up) and flat (a side is on top), and between odd and even. "Offset" and "Axial" put the coordinates into the cells, "Naive" shows a distance that is easy to build first and wrong. You can also move the cursor with Q W E A D Z X C or the arrow keys.
Red Blob Games has explained hex grids at length for years, with lovely interactive diagrams: Hexagonal Grids and the implementation guide that goes with it. Everything here is rebuilt in my own code, with tests. This post lays the groundwork for a few follow-ups.
Offset: the array
If you store a hex board in a two-dimensional array you end up with offset coordinates (col, row). Every second row is pushed half a cell to the right so the hexagons interlock. Which rows that is, is a matter of taste: the odd ones in odd-r, the even ones in even-r. With flat hexes it is columns that slide down (odd-q and even-q). That makes four conventions, and the demo switches between them live. The same cell has different offset numbers afterwards.
Offset is bad for calculations because the neighbors behave differently from row to row. In odd-r, going up and to the right from row 2 keeps you in the same column, from row 3 you land one column further right. So you need two neighbor tables, one per parity:
{{1, 0}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}}, // row not pushed right
{{1, 0}, {1, -1}, {0, -1}, {-1, 0}, {0, 1}, {1, 1}}, // row pushed right
These are the six steps {dcol, drow} for a pointy row without and with the shift. Flat has two more, and for even instead of odd the choice is swapped. neighborOffset is what moves the cursor in the demo when you press a key.
Axial: two axes, one step
The math is done in axial. Instead of column and row there is q (horizontal) and r (diagonally down for pointy, there is no shift anymore). The six neighbors are then the same steps in every cell:
constexpr Axial kAxialDirections[kDirections] = {{1, 0}, {1, -1}, {0, -1}, {-1, 0}, {-1, 1}, {0, 1}};
Getting to a neighbor is one addition with no case distinction:
inline Axial neighbor(Axial a, int direction) {
const Axial step = kAxialDirections[wrapDirection(direction)];
return {a.q + step.q, a.r + step.r};
}
The detour from offset to axial is written once. For pointy with odd-r:
const int shift = l.parity == Parity::Odd ? o.row - parityBit(o.row) : o.row + parityBit(o.row);
return {o.col - shift / 2, o.row};
The parity bit is subtracted from the row first (added for even-r), so the number is even and the division by 2 is exact. The demo does exactly this for the cell under the cursor: offset col 4, row 3 becomes q 3, r 3.
Cube: the third axis
Cube adds an s to q and r, and the three values always add up to zero:
inline Cube toCube(Axial a) { return {a.q, a.r, -a.q - a.r}; }
So axial is cube without s, there is nothing more to it. The demo shows the calculation in the orange line: s = -(3) - (3) = -6. The reason to carry s along anyway is the distance. The number of steps between two cells is the largest absolute value of the three differences:
inline int cubeDistance(Cube a, Cube b) { return std::max({std::abs(a.q - b.q), std::abs(a.r - b.r), std::abs(a.s - b.s)}); }
In the first frame the cursor is at (3, 3, -6) and the marked cell at (7, 1, -8). The differences are 4, -2 and -2, the largest absolute value is 4. Four steps lie between them, and the heatmap shows a 4 there too.
You can also do it straight in axial, (|dq| + |dq + dr| + |dr|) / 2 gives the same number, you just no longer see why.
Doubled
The fourth form is rare. For pointy, doubled doubles the column: col = 2q + r, row = r. The column then counts half hex widths, and only cells where col + row is even are valid. For flat the row is doubled instead.
Drawing
A hex gets onto the screen by a formula from its axial coordinates. For pointy the center is at:
return {kSqrt3 * (q + r / 2.0), 1.5 * r};
Everything is calculated for a hex size of 1 (center to corner), the demo multiplies by 30 pixels. A test checks that all six neighbors are exactly √3 away and share two corners with the cell.
To find the cell under the mouse I still take the lazy way here: the nearest center, then a check that the point really lies inside that hexagon. With 63 cells that is plenty. The formula that goes straight from pixel to hex comes in a follow-up post.
Pitfalls
The obvious distance on the offset grid is |dcol| + |drow|. The "Naive" chip turns it on and the rings around the cursor fall apart. Even the neighbors no longer all show a 1. In odd-r the cell (1, 0) is a neighbor of (0, 1), the naive value says 2. The hover card on the right shows both numbers one below the other and marks the wrong one.
The second trap hides in row % 2. In C++ -1 % 2 is -1, and row % 2 == 1 takes a negative odd row for even. With two's complement x & 1 gives the right bit for negative numbers too, which is why the test covers row -1 and column -1 separately.
Then there is mixing up odd and even: the same offset numbers sit elsewhere in odd-r and even-r, as the demo shows when you switch, because the cursor keeps its offset values.
How I test it
All conversions run in both directions for all four conventions, which catches sign errors. I compare the neighbor tables for every cell of a range against the route through axial: convert, take a step, convert back. The distance I check without the formula. A breadth-first search walks outward from the origin step by step, 217 cells within eight steps, and cubeDistance has to return for each the number of steps the search needed to reach it.
The code is in the repo at hex-koordinaten. The project Game Dev Snippets collects all demos of the series.