Deriving a formula for hex neighbors

This is an appendix for the neighbors section of the page.

Derive offset-grid neighbor formula

First, be sure you understand the cube neighbor algorithm. There are six neighbors, and each increments one axis by 1 and decrements a different axis by 1, thus preserving the q + r + s = 0 constraint.

For each of the six directions, we have Δq, Δr, Δs. The key idea here is that we’ll start with col, row coordinates from the offset grid, convert them into cube coordinates q, r, s, then add  Δq, Δr, Δs, then convert back into offset coordinates col, row. This general principle works for all the algorithms on the page.

I’ll show how this works for a single offset grid type, “even-q”: These are the coordinate conversions for “even-q”, from the conversions section:

# convert cube to even-q offset
col = q
row = r + (q + (q&1)) / 2

# convert even-q offset to cube
q = col
r = row - (col + (col&1)) / 2
s = -q-r

I’m only going to show this for a single direction, northeast, with Δq = +1, Δr = -1, Δs = 0:

# (1) convert even-q offset to cube coords:
q = col
r = row - (col + (col&1)) / 2
s = -q-r

# (2) apply Δq, Δr, Δs:
q' = q + 1
r' = r - 1
s' = s

# (3) substitute eq (1) into eq (2):
q' = col + 1
r' = row - (col + (col&1)) / 2 - 1
s' = -q'-r'

# (4) convert back into even-q coords:
col' = q'
row' = r' + (q' + (q'&1)) / 2

# (5) substitute eq (3) into eq (4)
col' = col + 1
row' = row  - ( col + (col&1)) / 2 - 1   + (col + 1 + ((col + 1)&1)) / 2
     = row  + (-col - (col&1) - 2) / 2   + (col + 1 + (1 - (col&1))) / 2
     = row  + (-col - (col&1) - 2        +  col + 1 +  1 - (col&1))  / 2
     = row  + (   -2 * (col&1)) / 2
     = row - (col&1)

So that’s it! We’ve worked through some math and it simplifies down to col' = col + 1 and row' = row - (col&1). (For this case, s doesn’t play a role, but it does in other situations.) That’s just for one direction, and only for even-q offset grids, but that’s how it works. For those of you who are compiler/language enthusiasts, this is defining evenq_offset_neighbors(H) as map(cube_to_evenq, cube_neighbors(evenq_to_cube(H))), then inlining all that code and greatly simplifying. It’s the type of work an compiler optimizer would do for you.

You can either work through all the cases, or you can perform the conversions at runtime (which likely will be optimized out by your compiler), or you can precalculate everything and put the results into lookup tables. I used lookup tables for my last game.