A* search algorithm in JavaScript

Implementing the A* algorithm in JavaScript to be used in games and other scenarios.

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest known heuristic cost, keeping a sorted priority queue of alternate path segments along the way.

I already implemented the A* for C#. Therefore I only had to port the code from C# to JavaScript, which turned out to be no problem at all with extended knowledge of both languages.

One of the things that is special about my implementation is that I am using the proposed object oriented JavaScript approach (as described in the Mario5 article). This creates an implementation of A* that can be easily extended or modified.

The final code consists of several classes, where some of them have originated from structures in C#. Since JavaScript does only know objects and primitives, the concept of a structure cannot be applied here. However, if one keeps in mind that every object is passed as a reference, we can extend our basic model with a clone() method. This way we can get copies of the corresponding structures.

/* This is actually a structure */
var PathFinderNode = Class.extend({
    init: function() {
        this.F = 0;
        this.G = 0;
        this.H = 0;
        this.X = 0;
        this.Y = 0;
        this.PX = 0;
        this.PY = 0;
    },
    clone: function() {
        var me = this;
        var you = new PathFinderNode();
        you.F = me.F;
        you.G = me.G;
        you.H = me.H;
        you.X = me.X;
        you.Y = me.Y;
        you.PX = me.PX;
        you.PY = me.PY;
        return you;
    }
});

Another thing that is not possible is the usage of template classes. We could now extend our object oriented approach with such a feature, or we do only extend the constructor of the classes, which should have template features.

var PriorityQueueB = Class.extend({
    init: function(comparer, type) {
        this.type = type;/* this is the T */
        this.innerList = [];
        this.comparer = comparer;
    },
     /* ... */
});

Since the constructor of a class is an object, too, we can pass it around (like any other function). So in this case we can create such a dynamic type just by calling new this.type().

Enumerations are among the easiest things to port. In JavaScript we can just create an object and name the properties. Here is a proper enumeration:

var PathFinderNodeType = {
    Start   : 1,
    End     : 2,
    Open    : 4,
    Close   : 8,
    Current : 16,
    Path    : 32
};

Some people might argue that this does not fit the enumeration (a collection of constants) from other languages, but since JavaScript is a scripting language with variables only (the const keyword should not be used - the IE does not even support it), it is quite obvious that there is no such thing as a collection of constants.

Finally we have a Maze class that is responsible for the game board information. Here we can access the following functions:

var Maze = Class.extend({
    init: function(size, start, end) {
        /* ... */
    },
    isPointInGrid: function(point) {
        /* ... */
    },
    tryBuild: function(point) {
        /* ... */
    },
    tryRemove: function(point) {
        /* ... */
    },
    getPath: function(mazeStrategy) {
        /* ... */
    },
    getPathAir: function() {
        /* ... */
    },
    calculate: function(mazeStrategy) {
        /* ... */
    }
});

This one makes use of the PathFinder class. This is the actual implementation of the A* search algorithm.

var PathFinder = Class.extend({
    init: function(grid) {
        /* ... */
    },
    reset: function() {
        /* ... */
    },
    findPath: function(start, end) {
        var me = this;
        var parentNode = new PathFinderNode();
        var found = false;
        var gridX = me.grid.length;
        var gridY = me.grid[0].length;
        me.stop = false;
        me.stopped = false;
        me.reset();
        var direction = me.diagonals ? [[0, -1], [1, 0], [0, 1], [-1, 0], [1, -1], [1, 1], [-1, 1], [-1, -1]] : [[0, -1], [1, 0], [0, 1], [-1, 0]];
	var ndiag = me.diagonals ? 8 : 4;

        parentNode.G = 0;
        parentNode.H = me.heuristicEstimate;
        parentNode.F = parentNode.G + parentNode.H;
        parentNode.X = start.X;
        parentNode.Y = start.Y;
        parentNode.PX = parentNode.X;
        parentNode.PY = parentNode.Y;
        me.open.push(parentNode);

        while(me.open.count() > 0 && !me.stop) {
            parentNode = me.open.pop();

            if (parentNode.X === end.X && parentNode.Y === end.Y) {
                me.close.push(parentNode);
                found = true;
                break;
            }

            if (me.close.length > me.searchLimit) {
                me.stopped = true;
                return;
            }

            if (me.punishChangeDirection)
                me.horiz = (parentNode.X - parentNode.PX); 

            for (var i = 0; i < ndiag; i++) {
                var newNode = new PathFinderNode();
                newNode.X = parentNode.X + direction[i][0];
                newNode.Y = parentNode.Y + direction[i][1];

                if (newNode.X < 0 || newNode.Y < 0 || newNode.X >= gridX || newNode.Y >= gridY)
                    continue;

                var newG = 0;

                if (me.heavyDiagonals && i > 3)
                    newG = parentNode.G + parseInt(me.grid[newNode.X][newNode.Y] * 2.41);
                else
                    newG = parentNode.G + this.grid[newNode.X][newNode.Y];

                if (newG === parentNode.G)
                    continue;

                if (me.punishChangeDirection) {
                    if (newNode.X - parentNode.X) {
                        if (!me.horiz)
                            newG += 20;
                    }

                    if (newNode.Y - parentNode.Y) {
                        if (me.horiz)
                            newG += 20;
                    }
                }

                var foundInOpenIndex = -1;

                for(var j = 0, n = me.open.count(); j < n; j++) {
                    if (me.open.get(j).X === newNode.X && me.open.get(j).Y === newNode.Y) {
                        foundInOpenIndex = j;
                        break;
                    }
                }

                if (foundInOpenIndex !== -1 && me.open.get(foundInOpenIndex).G <= newG)
                    continue;

                var foundInCloseIndex = -1;

                for(var j = 0, n = me.close.length; j < n; j++) {
                    if (me.close[j].X === newNode.X && me.close[j].Y === newNode.Y) {
                        foundInCloseIndex = j;
                        break;
                    }
                }

                if (foundInCloseIndex !== -1 && (me.reopenCloseNodes || me.close[foundInCloseIndex].G <= newG))
                    continue;

                newNode.PX = parentNode.X;
                newNode.PY = parentNode.Y;
                newNode.G = newG;

                switch(me.formula) {
                    case MazeStrategy.MaxDXDY:
                        newNode.H = me.heuristicEstimate * (Math.max(Math.abs(newNode.X - end.X), Math.abs(newNode.Y - end.Y)));
                        break;

                    case MazeStrategy.DiagonalShortCut:
                        var h_diagonal = Math.min(Math.abs(newNode.X - end.X), Math.abs(newNode.Y - end.Y));
                        var h_straight = (Math.abs(newNode.X - end.X) + Math.abs(newNode.Y - end.Y));
                        newNode.H = (me.heuristicEstimate * 2) * h_diagonal + me.heuristicEstimate * (h_straight - 2 * h_diagonal);
                        break;

                    case MazeStrategy.Euclidean:
                        newNode.H = parseInt(me.heuristicEstimate * Math.sqrt(Math.pow((newNode.X - end.X) , 2) + Math.pow((newNode.Y - end.Y), 2)));
                        break;

                    case MazeStrategy.EuclideanNoSQR:
                        newNode.H = parseInt(me.heuristicEstimate * (Math.pow((newNode.X - end.X) , 2) + Math.pow((newNode.Y - end.Y), 2)));
                        break;

                    case MazeStrategy.Custom1:
                        var dxy = new Point(Math.abs(end.X - newNode.X), Math.abs(end.Y - newNode.Y));
                        var Orthogonal = Math.abs(dxy.X - dxy.Y);
                        var Diagonal = Math.abs(((dxy.X + dxy.Y) - Orthogonal) / 2);
                        newNode.H = me.heuristicEstimate * (Diagonal + Orthogonal + dxy.X + dxy.Y);
                        break;
						
                    case MazeStrategy.Manhattan:
                    default:
                        newNode.H = me.heuristicEstimate * (Math.abs(newNode.X - end.X) + Math.abs(newNode.Y - end.Y));
                        break;
                }

                if (me.tieBreaker) {
                    var dx1 = parentNode.X - end.X;
                    var dy1 = parentNode.Y - end.Y;
                    var dx2 = start.X - end.X;
                    var dy2 = start.Y - end.Y;
                    var cross = Math.abs(dx1 * dy2 - dx2 * dy1);
                    newNode.H = parseInt(newNode.H + cross * 0.001);
                }

                newNode.F = newNode.G + newNode.H;
                me.open.push(newNode);
            }

            me.close.push(parentNode);
        }

        if (found) {
            var fNode = me.close[me.close.length - 1].clone();

            for(var i = me.close.length - 1; i >= 0; i--) {
                if ((fNode.PX === me.close[i].X && fNode.PY === me.close[i].Y) || i === me.close.Count - 1)
                    fNode = me.close[i].clone();
                else
                    me.close.splice(i, 1);
            }

            me.stopped = true;
            return me.close;
        }

        me.stopped = true;
    }
});

A demo of the A* star implementation can be found on my homepage. You can also download the complete source code below.

Download astar.zip (37 kB)

Created . Last updated .

References

Sharing is caring!