Distance between 2 hexagons on hexagon grid

algorithm, c++, distance, hexagonal-tiles

Solution

First apply the transform (y, x) |-> (u, v) = (x, y + floor(x / 2)).

Now the facial adjacency looks like

 0 1 2 3
0*-*-*-*
 |\|\|\|
1*-*-*-*
 |\|\|\|
2*-*-*-*

Let the points be (u1, v1) and (u2, v2). Let du = u2 - u1 and dv = v2 - v1. The distance is

if du and dv have the same sign: max(|du|, |dv|), by using the diagonals
if du and dv have different signs: |du| + |dv|, because the diagonals are unproductive

In Python:

def dist(p1, p2):
    y1, x1 = p1
    y2, x2 = p2
    du = x2 - x1
    dv = (y2 + x2 // 2) - (y1 + x1 // 2)
    return max(abs(du), abs(dv)) if ((du >= 0 and dv >= 0) or (du < 0 and dv < 0)) else abs(du) + abs(dv)

Problem

I have a hexagon grid: with template type coordinates T. How I can calculate distance between two hexagons? For example: dist((3,3), (5,5)) = 3 dist((1,2), (1,4)) = 2

Original source

Related problems