Accurate A* search heuristic for isometric maps?

Question

I have written an implementation of the A* search algorithm. The problem is that the heuristic I'm currently using only works accurately on square grids. As my map is isometric, the heuristic doesn't take into account actual the layout of the map and thus, the distance between cells.

Update: After extensive logging and analysis (read as spending lots of time trying to figure out a banality), I have come to the conclusion that my current heuristic works quite well, with one little exception: the end result is reversed for real straight 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 a straight move, which really costs sqrt(2) times more than a diagonal move on an isometric map, is calculated to be the that of a diagonal one. The question is: how can I modify my current heuristic so it will produce correct results for an isometric layout? Simply replacing diagonal with straight and vice versa will not work.

Answer 1

One thing to try would be converting from isometric coordinates to a square grid coordinate set for all calculations.

Say that 0,0 stays the root of the map. 0,1 stays the same, 1,2 becomes 0,2; 1,3 becomes 0,3; 2,3 becomes 1,4; 3,3 becomes 2,5; 0,2 becomes -1,1; etc. This puts you back into a square grid such that the coordinates and heuristics should work again.

Y coordinate becomes Y+sourceX offset (3,3 is at x=2; so becomes 2,5); finding sourceX mathmatically is proving itself more difficult.

[Stream of consciousness; ignore] Isometric coordinates at Y=0 are accurate for source X. So, to calculate source X you need to 'move left/up Y times' which should net a change of Y/2; rounded down, in the X coordinate.... roughly suggesting that the square coordinates would 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, in theory, this 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 question:

Assuming that you are trying to get distance(3,2; 3,3) < (distance(2,3; 3,3) = distance(3,1; 3,3)); the following should work: (translated from C#; typos not guaranteed to be non present)

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 horrible typo.... again.