CODEWITHSUNDEEP
javascripta-star
Oliver Barnwell
Oliver Barnwell

Reputation: 491

A-Star Algorithm: Slow Implementation

I am working on an implementation of the A-Star algorithm in javascript. It works, however it takes a very large amount of time to create a path between two very close together points: (1,1) to (6,6) it takes several seconds. I would like to know what mistakes I have made in the algorithm and how to resolve these.

My code:

Node.prototype.genNeighbours = function() {
    var right = new Node(this.x + 1, this.y);
    var left = new Node(this.x - 1, this.y);
    var top = new Node(this.x, this.y + 1);
    var bottom = new Node(this.x, this.y - 1);
    this.neighbours = [right, left, top, bottom];
}

AStar.prototype.getSmallestNode = function(openarr) {
    var comp = 0;
    for(var i = 0; i < openarr.length; i++) {
        if(openarr[i].f < openarr[comp].f) comp = i
    }
    return comp;
}

AStar.prototype.calculateRoute = function(start, dest, arr){
var open = new Array();
var closed = new Array();

start.g = 0;
start.h = this.manhattanDistance(start.x, dest.x, start.y, dest.y);
start.f = start.h;
start.genNeighbours();
open.push(start);
while(open.length > 0) {
    var currentNode = null;
    this.getSmallestNode(open);
    currentNode = open[0];
    if(this.equals(currentNode,dest)) return currentNode;
    currentNode.genNeighbours();
    var iOfCurr = open.indexOf(currentNode);
    open.splice(iOfCurr, 1);
    closed.push(currentNode);
    for(var i = 0; i < currentNode.neighbours.length; i++) {
        var neighbour = currentNode.neighbours[i];
        if(neighbour == null) continue;
        var newG = currentNode.g + 1;
        if(newG < neighbour.g) {
            var iOfNeigh = open.indexOf(neighbour);
            var iiOfNeigh = closed.indexOf(neighbour);
            open.splice(iOfNeigh, 1);
            closed.splice(iiOfNeigh,1);
        }
        if(open.indexOf(neighbour) == -1 && closed.indexOf(neighbour) == -1) {
            neighbour.g = newG;
            neighbour.h = this.manhattanDistance(neighbour.x, dest.x, neighbour.y, dest.y);
            neighbour.f = neighbour.g + neighbour.h;
            neighbour.parent = currentNode;
            open.push(neighbour);
        }
    }

}
}

Edit: I've now resolved the problem. It was due to the fact that I was just calling: open.sort(); which wasn't sorting the nodes by their 'f' value. I wrote a custom function and now the algorithm runs quickly.

Upvotes: 1

Views: 1081

Answers (1)

Bergi
Bergi

Reputation: 664876

A few mistakes I've spotted:

  • Your set of open nodes is not structured in any way so that retrieving the one with the minimal distance is easy. The usual choice for this is to use a priority queue, but inserting new nodes in a sorted order (instead of open.push(neighbour)) should suffice (at first).
  • in your getSmallestNode function, you may start the loop at index 1
  • you are calling getSmallestNode(), but not using its results at all. You're only taking currentNode = open[0]; every time (and then even searching for its position to splice it! It's 0!). With the queue, it's just currentNode = open.shift().

However, the most important thing (that could have gone most wrong) is your getNeighbors() function. It does create entirely new node objects every time it is called - ones that were unheard of before, and are not know to your algorithm (or its closed set). They may be in the same position in your grid as other nodes, but they're different objects (which are compared by reference, not by similarity). This means that indexOf will never find those new neighbors in the closed array, and they will get processed over and over (and over). I won't attempt to calculate the complexity of this implementation, but I'd guess its even worse than exponential.

Typically, the A* algorithm is executed on already existing graphs. An OOP-getNeighbors-function would return the references to the existing node objects, instead of creating new ones with the same coordinates. If you need to dynamically generate the graph, you'll need a lookup structure (two-dimensional array?) to store and retrieve already-generated nodes.

Upvotes: 1

Related Questions