Is my implementation of A* wrong?

Posted by Bloodyaugust on Game Development See other posts from Game Development or by Bloodyaugust
Published on 2012-08-29T07:25:52Z Indexed on 2012/08/29 9:50 UTC
Read the original article Hit count: 211

Filed under:
|

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.

WAT

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.

© Game Development or respective owner

Related posts about JavaScript

Related posts about path-finding