A* algorithm works OK, but not perfectly. What's wrong?
- by Bart van Heukelom
This is my grid of nodes:
I'm moving an object around on it using the A* pathfinding algorithm. It generally works OK, but it sometimes acts wrongly:
When moving from 3 to 1, it correctly goes via 2. When going from 1 to 3 however, it goes via 4.
When moving between 3 and 5, it goes via 4 in either direction instead of the shorter way via 6
What can be wrong? Here's my code (AS3):
public static function getPath(from:Point, to:Point, grid:NodeGrid):PointLine {
// get target node
var target:NodeGridNode = grid.getClosestNodeObj(to.x, to.y);
var backtrace:Map = new Map();
var openList:LinkedSet = new LinkedSet();
var closedList:LinkedSet = new LinkedSet();
// begin with first node
openList.add(grid.getClosestNodeObj(from.x, from.y));
// start A*
var curNode:NodeGridNode;
while (openList.size != 0) {
// pick a new current node
if (openList.size == 1) {
curNode = NodeGridNode(openList.first);
}
else {
// find cheapest node in open list
var minScore:Number = Number.MAX_VALUE;
var minNext:NodeGridNode;
openList.iterate(function(next:NodeGridNode, i:int):int {
var score:Number = curNode.distanceTo(next) + next.distanceTo(target);
if (score < minScore) {
minScore = score;
minNext = next;
return LinkedSet.BREAK;
}
return 0;
});
curNode = minNext;
}
// have not reached
if (curNode == target) break;
else {
// move to closed
openList.remove(curNode);
closedList.add(curNode);
// put connected nodes on open list
for each (var adjNode:NodeGridNode in curNode.connects) {
if (!openList.contains(adjNode) && !closedList.contains(adjNode)) {
openList.add(adjNode);
backtrace.put(adjNode, curNode);
}
}
}
}
// make path
var pathPoints:Vector.<Point> = new Vector.<Point>();
pathPoints.push(to);
while(curNode != null) {
pathPoints.unshift(curNode.location);
curNode = backtrace.read(curNode);
}
pathPoints.unshift(from);
return new PointLine(pathPoints);
}
NodeGridNode::distanceTo()
public function distanceTo(o:NodeGridNode):Number {
var dx:Number = location.x - o.location.x;
var dy:Number = location.y - o.location.y;
return Math.sqrt(dx*dx + dy*dy);
}
