0

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

enter image description here

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.

Improve this question
1
  • What do you expect the distance to be between (3,5) and (2,6)? Commented Jun 30, 2014 at 15:46

1 Answer 1

Reset to default
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);

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

That is the Manhattan Distance. (Your formula was just wrong).