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?

Solution 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.

Solution 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)

Solution 3

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.

Solution 4

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

Solution 5

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.

View more solutions

Comments

[Chris Pfohl]

I'm not sure your question makes sense. Do you mean, how do you measure the length of the red or blue lines?

[Svante]

The question does not look sensible because it describes a euclidean distance in a square lattice, but seems to ask for a manhattan distance on a hexagonal lattice.

[Coyod]

sorry for the confusion, i mean how many moves from A to B by one of shortest paths.

[Svante]

Does it make sense for a floating-point number to be "even"? Is bit-and a valid way to check the evenness of a floating-point number?

[Mike Dunlavey]

@Svante: Good point. I put in a cast. The only reason I put in the double was because 1/2 could enter the picture.

[Svante]

I was just composing a similar answer, so +1. However, "integer division" is not correct for the coordinate transformation. y/2 needs to be floor (y / 2), where / produces a rational and floor rounds towards negative infinity.

[aaz]

@Svante – Thanks. This is do-what-I-want pseudocode, which is, of course, rounding down :)

[Svante]

floating-point numbers are usually a bad substitute for rationals. Are you sure that (int)1.0 is 1 in whatever compiler you intend to use? What if it is (int)0.999999 or (int)1.00000001? If you absolutely must use floating-point numbers, produce them as late as possible.

[Mike Dunlavey]

@Svante: Good point again. You can assume that floating point is exact for integers, but it's still probably not a good idea to depend on it. In this case it would have been more prudent to work with half-integers. I just didn't want to make the code any more confusing.

[Svante]

Thanks for your consideration. My idea would be not to have any implementation details in pseudocode, i.e., no types, no casts, no bit fiddling, no inexact functions, and = denotes equality, not assignment.

[Coyod]

Thank you, aaz. That's exactly what i need.

[nugget]

If you flip the y-axis, you need to change "abs(dx + dy)" to "abs(dx) + abs(dy)". (This also works if the y-axis stays the same, so it is also a more general algorithm.)

[Fylke]

@SorenJohnson It's not enough to change the abs(dx + dy), you also need to change the if statement to sign(dx) != sign(dy) (this just bit me, that's how I know...) Also, in case anyone is wondering, sign() is a function that returns -1 if the number is negative, zero if it's zero and 1 if it's positive.

[Randy L]

pretty cool. this model demonstrates that the coordinate space in a hex grid is similar to a square grid, except any cell is adjacent to 6 cells instead of 4 in the square grid. love me some geometry in my computer science.

[lxg]

Please refer to this paper: E. D. Luczak and A. Rosenfeld, “Distance on a Hexagonal Grid,” IEEE Trans. Comput., vol. C–25, no. 5, pp. 532–533, May 1976.