A* pathfinding heuristic for static nodes

Question

I'm trying to write my own A* pathfinding algorithm and have a problem; when seeking the shortest cost path the following error arises:

Where the green filled node is the start node, the red filled node is the goal node and the pink filled nodes are the actual path that the algorithm has taken.

This is of course not the shortest path and I'm certain the problem lies with my heuristic function (manhattan distance):

int Map::manhattanDistance(Node evaluatedNode, Node goalNode)
{
    int x = evaluatedNode.xCoord - goalNode.xCoord;
    int y = evaluatedNode.yCoord - goalNode.yCoord;
    if(x + y < 0)
        return (x + y) * -1;
    else
        return x + y;
}

It seems to me that manhattan distance formula is not ideal here and my question is therefore: what other distance measuring algorithm would work for me here?

EDIT: for sake of clarity, each nodes width is determined by number of nodes in row / screen width = 640 and each nodes height is determined by number of nodes in column / screen height = 480.

Answer 1

A negative cost would imply that a route is free, or more than that it discounts previous moves. It looks like you have tried to account for this by multiplying by -1 of the aggregate, however the damage has already been done. That is why the solution has used diagonals, (1 - 1) * -1 is still zero and thus is considered to be free.

I would replace the if statement with the following, which uses the magnitude of each component by applying abs against it separately:

return Math.abs(x) + Math.abs(y);