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

This sounds like a job for the Bresenham line algorithm. You can use that to count the number of segments to get from A to B, and that will tell you the path distance.

Answer 3

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)

Answer 4

If you want the straight-line distance:

double dy = y2 - y1;
double dx = x2 - x1;
// if the height is odd
if ((int)dy & 1){
    // whether the upper x coord is displaced left or right
    // depends on whether the y1 coordinate is odd
    dx += ((y1 & 1) ? -0.5 : 0.5);
}
double dis = sqrt(dx*dx + dy*dy);

What I'm trying to say is, if dy is even, it's just a rectangular space. If dy is odd, the position of the upper right corner is 1/2 unit to the left or to the right.

Answer 5

If you define the different hexagons as a graph, you can get the shortest path from node A to node B. Since the distance from the hexagon centers is constant, set that as the edge weight.

This will probably be inefficient for large fields though.

Answer 6

A straight forward answer for this question is not possible. The answer of this question is very much related to how you organize your tiles in the memory. I use odd-q vertical layout and with the following matlab code gives me the right answer always.

function f = offset_distance(x1,y1,x2,y2)
    ac = offset_to_cube(x1,y1);
    bc = offset_to_cube(x2,y2);
    f = cube_distance(ac, bc);
end

function f = offset_to_cube(row,col)
    %x = col - (row - (row&1)) / 2;
    x = col - (row - mod(row,2)) / 2;
    z = row;
    y = -x-z;
    f = [x,z,y];
end

function f= cube_distance(p1,p2)
    a = abs( p1(1,1) - p2(1,1));
    b = abs( p1(1,2) - p2(1,2));
    c = abs( p1(1,3) - p2(1,3));
    f =  max([a,b,c]);
end

Here is a matlab testing code

sx = 6;
sy = 1;
for i = 0:7
    for j = 0:5
        k = offset_distance(sx,sy,i,j);
        disp(['(',num2str(sx),',',num2str(sy),')->(',num2str(i),',',num2str(j),')=',num2str(k)])
    end
end

For mathematical details of this solution visit: http://www.redblobgames.com/grids/hexagons/ . You can get a full hextile library at: http://www.redblobgames.com/grids/hexagons/implementation.html