# Deriving a formula for hex neighbors

from Red Blob Games

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.

Email me , or tweet @redblobgames, or comment: