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 x + y + z = 0 constraint.

For each of the six directions, we have Δx, Δy, Δz. The key idea here is that we’ll start with q, r coordinates from the offset grid, convert them into cube coordinates x, y, z, then add  Δx, Δy, Δz, then convert back into offset coordinates q, r. 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 above section:

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

# convert even-q offset to cube
x = q
z = r - (q + (q&1)) / 2
y = -x - z

I’m only going to show this for a single direction, northeast, with Δx = +1, Δy = 0, Δz = -1:

# (1) convert even-q offset to cube coords:
x = q
y = -x - z
z = r - (q + (q&1)) / 2

# (2) apply Δx, Δy, Δz:
x' = x + 1
y' = y
z' = z - 1

# (3) substitute eq (1) into eq (2):
x' = q + 1
y' = -x - z
z' = r - (q + (q&1)) / 2 - 1

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

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

So that’s it! We’ve worked through some math and it simplifies down to q' = q + 1 and r' = r - (q&1). (For this case, y 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.