Is my implementation of A* wrong?
- by Bloodyaugust
I've implemented the A* algorithm in my program. However, it would seem to be functioning incorrectly at times. Below is a screenshot of one such time.
The obviously shorter line is to go immediately right at the second to last row. Instead, they move down, around the tower, and continue to their destination (bottom right from top left). Below is my actual code implementation:
nodeMap.prototype.findPath = function(p1, p2) {
var openList = [];
var closedList = [];
var nodes = this.nodes;
for (var i = 0; i < nodes.length; i++) { //reset heuristics and parents for nodes
var curNode = nodes[i];
curNode.f = 0;
curNode.g = 0;
curNode.h = 0;
curNode.parent = null;
if (curNode.pathable === false) {
closedList.push(curNode);
}
}
openList.push(this.getNode(p1));
while(openList.length > 0) {
// Grab the lowest f(x) to process next
var lowInd = 0;
for(i=0; i<openList.length; i++) {
if(openList[i].f < openList[lowInd].f) {
lowInd = i;
}
}
var currentNode = openList[lowInd];
if (currentNode === this.getNode(p2)) {
var curr = currentNode;
var ret = [];
while(curr.parent) {
ret.push(curr);
curr = curr.parent;
}
return ret.reverse();
}
closedList.push(currentNode);
for (i = 0; i < openList.length; i++) { //remove currentNode from openList
if (openList[i] === currentNode) {
openList.splice(i, 1);
break;
}
}
for (i = 0; i < currentNode.neighbors.length; i++) {
if(closedList.indexOf(currentNode.neighbors[i]) !== -1 ) {
continue;
}
if (currentNode.neighbors[i].isPathable === false) {
closedList.push(currentNode.neighbors[i]);
continue;
}
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
var gScoreIsBest = false;
if (openList.indexOf(currentNode.neighbors[i]) === -1) {
//save g, h, and f then save the current parent
gScoreIsBest = true;
currentNode.neighbors[i].h = currentNode.neighbors[i].heuristic(this.getNode(p2));
openList.push(currentNode.neighbors[i]);
}
else if (gScore < currentNode.neighbors[i].g) { //current g better than previous g
gScoreIsBest = true;
}
if (gScoreIsBest) {
currentNode.neighbors[i].parent = currentNode;
currentNode.neighbors[i].g = gScore;
currentNode.neighbors[i].f = currentNode.neighbors[i].g + currentNode.neighbors[i].h;
}
}
}
return false;
}
Towers block pathability. Is there perhaps something I am missing here, or does A* not always find the shortest path in a situation such as this? Thanks in advance for any help.
