Pathing randomly fails after first search. Pathfinder doesn't reset closed nodes after search is complete.

[manthrax]

Subsequent searches on the same grid/graph will fail, since "closed" nodes are left over from the previous search.

Here is a fixed version of the "astar" method that saves off, and restores the closed nodes flags, before the path is returned.

`
var astar = {
/**
* Perform an A* Search on a graph given a start and end node.
* @param {Graph} graph
* @param {GridNode} start
* @param {GridNode} end
* @param {Object} [options]
* @param {bool} [options.closest] Specifies whether to return the
path to the closest node if the target is unreachable.
* @param {Function} [options.heuristic] Heuristic function (see
* astar.heuristics).
*/
search: function(graph, start, end, options) {
graph.cleanDirty();
options = options || {};
var heuristic = options.heuristic || astar.heuristics.manhattan,
closest = options.closest || false;

    var openHeap = getHeap(),
        closestNode = start; // set the start node to be the closest if required
    var closedList = [];
    start.h = heuristic(start, end);

    openHeap.push(start);

    while(openHeap.size() > 0) {

        // Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
        var currentNode = openHeap.pop();

        // End case -- result has been found, return the traced path.
        if(currentNode === end) {
            while(closedList.length>0)closedList.pop().closed = false;
            return pathTo(currentNode);
        }

        // Normal case -- move currentNode from open to closed, process each of its neighbors.
        currentNode.closed = true;
        closedList.push(currentNode);

        // Find all neighbors for the current node.
        var neighbors = graph.neighbors(currentNode);

        for (var i = 0, il = neighbors.length; i < il; ++i) {
            var neighbor = neighbors[i];

            if (neighbor.closed || neighbor.isWall()) {
                // Not a valid node to process, skip to next neighbor.
                continue;
            }

            // The g score is the shortest distance from start to current node.
            // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
            var gScore = currentNode.g + neighbor.getCost(currentNode),
                beenVisited = neighbor.visited;

            if (!beenVisited || gScore < neighbor.g) {

                // Found an optimal (so far) path to this node.  Take score for node to see how good it is.
                neighbor.visited = true;
                neighbor.parent = currentNode;
                neighbor.h = neighbor.h || heuristic(neighbor, end);
                neighbor.g = gScore;
                neighbor.f = neighbor.g + neighbor.h;
                graph.markDirty(neighbor);
                if (closest) {
                    // If the neighbour is closer than the current closestNode or if it's equally close but has
                    // a cheaper path than the current closest node then it becomes the closest node
                    if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) {
                        closestNode = neighbor;
                    }
                }

                if (!beenVisited) {
                    // Pushing to heap will put it in proper place based on the 'f' value.
                    openHeap.push(neighbor);
                }
                else {
                    // Already seen the node, but since it has been rescored we need to reorder it in the heap
                    openHeap.rescoreElement(neighbor);
                }
            }
        }
    }
    while(closedList.length>0)closedList.pop().closed = false;

    if (closest) {
        return pathTo(closestNode);
    }

    // No result was found - empty array signifies failure to find path.
    return [];
},
// See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
heuristics: {
    manhattan: function(pos0, pos1) {
        var d1 = Math.abs(pos1.x - pos0.x);
        var d2 = Math.abs(pos1.y - pos0.y);
        return d1 + d2;
    },
    diagonal: function(pos0, pos1) {
        var D = 1;
        var D2 = Math.sqrt(2);
        var d1 = Math.abs(pos1.x - pos0.x);
        var d2 = Math.abs(pos1.y - pos0.y);
        return (D * (d1 + d2)) + ((D2 - (2 * D)) * Math.min(d1, d2));
    }
},
cleanNode:function(node){
    node.f = 0;
    node.g = 0;
    node.h = 0;
    node.visited = false;
    node.closed = false;
    node.parent = null;
}

};
`

[paperjack93]

Thank you, I was wondering WTF was going on.

[Je1te]

This was very helpful.

[seamuskills]

I'm having this problem but I'm using a script tag with a link to the script. is there any way to reset the closed nodes outside the script?

[tukkek]

Since no-one-else seems to have done it over the years, I've created a fork with this fix: https://github.com/tukkek/a-star.

The performance improvement from being able to re-use the graph is massive. I estimate it's on the order of 100-times-faster or more on a project with a very-large-graph but I haven't actually bench-marked it.

I have also created a pull-request, more out-of-respect for Brian than in any hope of it actually being merged: #81. ¯\_(ツ)_/¯

Thank you for sharing your fix @manthrax!