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.