A * Error implementing Pathfinding
I seem to have a bug in the following A * pathfinding implementation that I have implemented based on the psuedocode found here .
function NodeList() {
this.nodes = [];
this.add = function(givenNode) {
for(var i = 0; i<this.nodes.length; i++) {
if(this.nodes[i].f <= givenNode.f) {
this.nodes.splice(i, 0, givenNode);
return;
}
}
this.nodes.push(givenNode);
}
this.pop = function() {
return this.nodes.splice(this.nodes.length-1, 1)[0];
}
this.getNode = function(givenNode) {
for (var i = 0; i < this.nodes.length; i++) {
if (this.nodes[i].pos.x == givenNode.pos.x && this.nodes[i].pos.y == givenNode.pos.y) {
return this.nodes.splice(i, 1)[0];
}
}
return -1;
}
this.hasNode = function(givenNode) {
for (var i = 0; i < this.nodes.length; i++) {
if (this.nodes[i].pos.x == givenNode.pos.x && this.nodes[i].pos.y == givenNode.pos.y) {
return true;
}
}
return false;
}
this.length = function() {
return this.nodes.length;
}
}
function PathNode(pos, f, g, h) {
this.pos = pos;
this.f = f;
this.g = g;
this.h = h;
}
function FindPath(start, goal) {
var x_array = [0, -1, -1, -1, 0, 1, 1, 1];
var y_array = [1, 1, 0, -1, -1, -1, 0, 1];
var open_list = new NodeList();
open_list.add(new PathNode(start, start.Manhattan(goal) * 10, 0, start.Manhattan(goal) * 10));
var closed_list = new NodeList();
while(open_list.length() > 0) {
var currentNode = open_list.pop();
if(currentNode.pos.x == goal.x && currentNode.pos.y == goal.y) {
var path = [];
var curNode = currentNode;
while(true) {
path.push(curNode);
curNode = curNode.parent;
if(curNode == undefined) break;
}
return(path);
}
closed_list.add(currentNode);
for(var i=0; i<8; i++) {
var neighbor = new PathNode(new Vector2(currentNode.pos.x + x_array[i], currentNode.pos.y + y_array[i]), 0, 0, 0);
if(map.tiles[neighbor.pos.x][neighbor.pos.y].blocked == true) {
canContinue = false;
}
for(var j=0; j<objects.length; j++) {
if(objects[j].blocks == true && objects[j].position.x == neighbor.pos.x && objects[j].position.y == neighbor.pos.y) canContinue = false;
}
if(closed_list.hasNode(neighbor)) continue;
if(!canContinue) continue;
if(open_list.hasNode(neighbor)) { // if open_list contains neighbor, do this:
neighbor = open_list.getNode(neighbor);
neighbor.parent == currentNode;
neighbor.g = currentNode.g + 10;
neighbor.h = neighbor.pos.Manhattan(goal) * 10;
neighbor.f = neighbor.g + neighbor.h;
open_list.add(neighbor);
} else { // otherwise it not on the open list, do this:
if(neighbor.g < currentNode.g) {
neighbor.parent = currentNode;
neighbor.g = currentNode.g + 10;
neighbor.f = neighbor.g + neighbor.h;
}
open_list.add(neighbor);
}
}
}
}
I must be doing something wrong because the code spirals into an infinite loop and the browser crashes whenever I run it. Can anyone please point out my error?
source to share
I'll update this answer with dots when I find them.
-
First of all, I see no way to avoid the outer loop in your Environment. You have console.log instead of the return statement you have in your example posted here.
console.log(path);
insteadreturn path;
-
You are not checking the closed list for nodes that have been closed. So, once you have assessed the state of a node in the open list, it has moved to the closed list, but you are not doing anything with that list. There is nothing to prevent you from adding a closed-list node to an open-ended list again. You are checking the open list only to prevent the same node from being added more than once. (Although your example code posted here shows that you are)
The combination of these things looks like it will produce the same path infinitely many times.
It's also easy to point out that your example code is incorrectly deferred, so it looks like this code is not inside a neighbor checking loop.
source to share