+2  A: 

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.

CoderTao
I need to fix the heuristic, not the algorithm itself, and doing this would require a complete change of the system.
Electro
Ultimately this should only change the Heuristic; if you try the heuristic for distance remaining as distance(squareCoords(current), squareCoords(dest)); you shouldn't need to make any other changes in the system.
CoderTao
Two things:A) there's a typoB) it's not giving me any better paths than my current heuristic, for a good reason: it's not taking into account diagonal movement
Electro
I take no responsibility for awful spelling. That said; what do you mean 'its not taking into account diagonal movement'? An explicit example of what it is doing on your end would be useful.
CoderTao
It's not making any diagonal moves whatsoever, unless you are moving to a tile which is adjacent.
Electro
New heuristic is not working at all. Algorithm stalls.
Electro
That... doesn't make alot of sense. There shouldn't be a case where the algorithm would outright stall.... at some point it should exhaust all possibilities and give up; but it shouldn't be stalling.
CoderTao
Well, that's what I meant. But it takes some time to do that.
Electro
Okay; yet another horrible typo was probably present. I suspect I should have posted the C# code; gy=position.y + cy should have been gy=position.y+gx
CoderTao
Well, it's not *exactly* what I had in mind, but thanks!
Electro
A: 

Amit here computes the "manhattan distances for hexagons". Its C++ code, and I can't vouch for it, but Amit is a name I've heard before for game development.

The manhattan distance for hexagons should be suitable for a proper heuristic.

Edit: reversed the syntax for hyperlinking, whoops.

Agor
Unfortunately, tiles on a hexagonal grid only move in 6 directions, and the cost of moving is equal for every direction, so I can't use this.
Electro
My god, I completely misread your question. Somehow isometric became hexagonal. Sorry about that.
Agor