This is an implementation in code.org that uses A* pathfinding and a manhattan heuristic. It is grid-based so it does not yet work with graphs. It is, as always, extremely laggy but in the meantime it serves as a working A.I. system that will provide you the shortest distance from point A to point B.
One way this script can be used for games is pac-man. I have seen projects that don’t use pathfinding but instead just make the ghosts move incredibly fast directly toward the player, which means if you stand still behind a wall the ghosts wouldn’t be able to reach you.
Below is a minified version of the ‘module’.
"PATH V1.0";var path=function(){var t={};function Node(t,e){this.Traversable=true;this.Heuristic="Manhattan";this.Closed=false;this.X=t;this.Y=e}Node.prototype.CalculateHeuristic=function(t){if(this.Heuristic==="Manhattan"){return abs(this.x-t.x)+abs(this.y-t.y)}};Node.prototype.CalculateCosts=function(){var t=this.CalculateHeuristic(this.Board.Start);var e=this.CalculateHeuristic(this.Board.End);this.F=t+e;this.H=e};function Board(){this.Checked=[];this.Rows=[]}Board.prototype.BestNode=function(){var t;for(var e=0;e<this.Checked.length;e++){var r=this.Checked[e];if(!r.Closed&&(!t||r.F<=t.F&&r.H<=t.H)){t=r}}return t};Board.prototype.GetNeighbors=function(t){var e=[[0,1],[0,-1],[1,0],[-1,0]];var r=[];var s=t.X;var o=t.Y;for(var i=0;i<e.length;i++){var a=e[i];var h=this.Rows[s+a[0]];if(h&&h[o+a[1]]&&h[o+a[1]].Traversable){r.push(h[o+a[1]])}}return r};Board.prototype.ProcessNeighbors=function(t){var e=this.GetNeighbors(t);for(var r=0;r<e.length;r++){var s=e[r];s.CalculateCosts();var o=true;for(var i=0;i<this.Checked.length;i++){if(s==this.Checked[i]){o=false}}if(o){this.Checked.push(s)}if(!s.Closed&&(!s.From||s.CalculateHeuristic(t)<s.CalculateHeuristic(s.From))){s.From=t}}};Board.prototype.GetRow=function(t){if(!this.Rows[t]){this.Rows[t]=[]}return this.Rows[t]};Board.prototype.AddNode=function(t){t.Board=this;this.GetRow(t.X)[t.Y]=t};Board.prototype.Reset=function(){this.Checked=[];for(var t=0;t<this.Rows.length;t++){for(var e=0;e<this.Rows[t].length;e++){this.Rows[t][e].Closed=false;this.Rows[t][e].H=undefined;this.Rows[t][e].F=undefined;this.Rows[t][e].From=undefined}}};Board.prototype.GetPath=function(){var t=this.Start;while(t!=this.End){this.ProcessNeighbors(t);t=this.BestNode();if(t){t.Closed=true}else{return[]}}var e=[];while(t!=this.Start){e.unshift(t);t=t.From}e.unshift(t);return e};t.Node=Node;t.Board=Board;return t}();
In order to use this module, we must start by creating a board.
var board = new path.Board();
The board is empty as of now so we start filling it with nodes.
For every node, we create the node, and then add the node to the board.
// x and y are the positions of the node.
var node = new path.Node(x, y);
board.AddNode(node)
If you want the node to be an obstacle, you can set the Traversable property of the node to false (by default it is true). If you want to make the node the starting node, you set the Start propery of the board to the node. The same goes for the end node.
var start = path.Node(0, 0);
board.Start = start;
var obstacle = path.Node(0, 1);
obstacle.Traversable = false;
var end = path.Node(0, 2);
board.End = end;
board.AddNode(start);
board.AddNode(end);
board.AddNode(obstacle);
A map is always nice to make representing obstacles easier in code.
// In this example, 0 will represent blank tiles, 1 will represent obstacles, 2 will repsent the start position, and 3 will represent the end position
var map = [
[2, 0, 1],
[0, 0, 0],
[1, 0, 3],
]
With 2 nested for-loops, we iterate through every element of map and its children. Then we find out the value of the position (obstacle/no obstacle). Create and determine the type of a node with conditionals. Finally add the node to the board.
for (var y = 0; y<map.length; y++) {
for (var x = 0; x<map[y].length; x++) {
var value = map[y][x];
var node = new path.Node(x, y);
//a value of 0 is nothing special
if (value===1) {
node.Traversable=false;
} else if (value===2) {
board.Start = node;
} else if (value===3) {
board.End = node;
}
board.AddNode(node);
}
}
From here on, we can just use board.GetPath() to solve the board. If there is a solution, it will return an ordered array of all the nodes you would have to move through to reach the destination. Otherwise, it will return an empty array (GetPath will always return at least 2 nodes: start & end, if there is a solution.)
var solvedpath = board.GetPath();
There is no function in the module to draw the board. So you will have to implement it on your own. For testing purposes, the code below will draw the board with colored squares.
Green is the start; Red is the end; Grey is an obstacle; Cyan is the path to take to reach the end.
for (var x = 0; x<board.Rows.length; x++) {
for (var y = 0; y<board.Rows[x].length; y++) {
var n = board.Rows[x][y];
if (n==board.Start) {
fill("green");
} else if (n==board.End) {
fill("red");
} else if (solvedpath.indexOf(n)>=0) {
fill("cyan");
} else if (n.Traversable) {
fill("white");
} else {
fill("grey");
}
rect(x*400/map.length, y*400/map[0].length, 400/map.length, 400/map[0].length);
}
}
All these things added together makes a working pathfinding script. All the code snippets together will make a working pathfinding script. You can check that out here:
One last thing is if the start/end/obstacles change. In that case, you will need to use board.Reset() before calling board.GetPath() again.