Exact A * search heuristic for isometric maps?

Question

I wrote an implementation of the A * search algorithm. The problem is that the heuristic I'm using right now works exactly on square grids. Since my map is isometric, heuristics do not take into account the actual location of the map and, therefore, the distance between the cells.

Update: After extensive registration and analysis (read how spending a lot of time trying to understand platitudes), I came to the conclusion that my current heuristic works quite well, with one small exception: the end result is the opposite for real direct and diagonal movement.

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const { int diagonal = std::min(abs(coord.x-goal->position.x), abs(coord.y-goal->position.y)); int straight = (abs(coord.x-goal->position.x) + abs(coord.y-goal->position.y)); return 14 * diagonal + 10 * (straight - 2 * diagonal); } 

This means that the direct movement, which really costs sqrt(2) times more than the diagonal movement on the isometric map, is calculated as diagonal. The question arises: how can I change the current heuristic so that it gives the correct results for the isometric layout? Just replacing diagonal with straight and vice versa will fail.

Answer 1

You can try to convert from isometric coordinates to the square grid coordinate for all calculations.

Let's say that 0.0 remains the root of the map. 0.1 remains unchanged; 1.2 becomes 0.2; 1.3 - 0.3; 2.3 turns into 1.4; 3.3 is 2.5; 0.2 turns into -1.1; etc. This brings you back to the square grid, so the coordinates and heuristic should work again.

Y coordinate becomes Y + source X offset (3.3 for x = 2, so it becomes 2.5); finding the source X is mathematically more difficult.

[Mindflow; ignore] Isometric coordinates at Y = 0 are accurate for source X. Thus, to calculate source X you need to "move left / up Y times", which should clear the change Y / 2; rounded down, at the X coordinate ... roughly speaking, the square coordinates will be:

 sourceX = X - Y/2 sourceY = Y + sourceX 

Where sourceX and sourceY are the coordinates in a normal square grid; and Y / 2 is integer arithmetic / rounded down.

So, theoretically, it becomes:

 double DistanceToEnd(Point at, Point end) { Point squareStart = squarify(at); Point squareEnd = squarify(end); int dx=squareStart.X-squareEnd.X; int dy=squareStart.Y-squareEnd.Y; return Math.Sqrt(dx*dx+dy*dy); } Point squarify(Point p1) { return new Point(p1.X-p1.Y/2, p1.Y+(p1.X-p1.Y/2)); } 

Update based on new bits of the question:

Assuming you are trying to get the distance (3.2; 3.3) (distance (2.3; 3.3) = distance (3.1; 3.3)); the following should work: (translated from C #, typos are not guaranteed to be absent)

 inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const { int cx=coord.x - coord.y/2; int cy=coord.y + cx; int gx=goal->position.x - goal->position.y/2; int gy=goal->position.y + gx; int diagonal = std::min(abs(cx-gx), abs(cy-gy)); int straight = (abs(cx-gx) + abs(cy-gy)); return 14 * diagonal + 10 * (straight - 2 * diagonal); } 

EDIT: Fixed a terrible typo .... again.

Answer 2

Amit here calculates the "Manhattan distances for hexagons." Its code is in C ++, and I cannot vouch for it, but Amit is the name that I heard before for developing the game.

The Manhattan distance for hexagons must be suitable for proper heuristics.

Edit: Canceled hyperlink syntax, screaming.