Manhattan Distance between tiles in a hexagonal grid

Question

For a square grid the euclidean distance between tile A and B is:

distance = sqrt(sqr(x1-x2)) + sqr(y1-y2))

For an actor constrained to move along a square grid, the Manhattan Distance is a better measure of actual distance we must travel:

manhattanDistance = abs(x1-x2) + abs(y1-y2))

How do I get the manhattan distance between two tiles in a hexagonal grid as illustrated with the red and blue lines below?

Answer 1

I once set up a hexagonal coordinate system in a game so that the y-axis was at a 60-degree angle to the x-axis. This avoids the odd-even row distinction.

_{(source: althenia.net)}

The distance in this coordinate system is:

dx = x1 - x0 dy = y1 - y0  if sign(dx) == sign(dy)     abs(dx + dy) else     max(abs(dx), abs(dy)) 

You can convert (x', y) from your coordinate system to (x, y) in this one using:

x = x' - floor(y/2) 

So dx becomes:

dx = x1' - x0' - floor(y1/2) + floor(y0/2) 

Careful with rounding when implementing this using integer division. In C for int y floor(y/2) is (y%2 ? y-1 : y)/2.

Answer 2

I assume that you want the Euclidean distance in the plane between the centers of two tiles that are identified as you showed in the figure. I think this can be derived from the figure. For any x and y, the vector from the center of tile (x, y) to the center of tile (x + dx, y) is (dx, 0). The vector from the center of tile (x, y) and (x, y + dy) is (-dy / 2, dy*sqrt(3) / 2). A simple vector addition gives a vector of (dx - (dy / 2), dy * sqrt(3) / 2) between (x, y) and (x + dx, y + dy) for any x, y, dx, and dy. The total distance is then the norm of the vector: sqrt((dx - (dy / 2)) ^ 2 + 3 * dy * dy / 4)