Alex Rivera | Logout

Manhattan Distance between tiles in a hexagonal grid

Asked 2011-02-22T22:30:23.457
23

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?

enter image description here

algorithm path distance hexagonal-tiles
Edit
Report

1 Answer

2

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.

answered 2011-02-22T22:44:08.877

Your Answer