Pathfinding with the A-Star Algorithm in JavaScript

Below is a simple implementation of the A-Star (A*) pathfinding algorithm in JavaScript. To see it in action, copy the code into a .html file and open that file in a web browser that has JavaScript enabled.

UPDATE 2016/02/12 – I have updated this code to bring it more in line with the way I do things nowadays, and hopefully clarify it somewhat in the process. I am also adding a brief description of how the algorithm actually works.

The A-Star algorithm is meant to find the best path from one point in a grid to another point in that same grid. The procedure works as follows:

1. Start with a “map”, which is a grid made up of cells. Some of these cells are more difficult to traverse than others. The difficulty associated with traversing a particular cell is called its “cost”.

2. Choose a starting cell and a goal cell.

3. Create an initially empty list of map cells to be considered as part of the optimal path. When cells are added to this list, they will be sorted in order of increasing total cost. The total cost of a cell will be the sum of the known cost to traverse the path from the start cell to that cell, plus an estimate of the cost from that cell to the goal cell. The method for estimating the cost from a particular cell to the goal, in this implementation, is to subtract that cell’s position from the position of the goal cell to find the displacement, and then add the absolute value of the displacement’s X and Y components.

4. Create another initially empty list, to record cells that have already been considered.

5. Remove the first entry from the list of cells to be considered. Because of how the list is sorted, this will be the cell with the lowest total estimated cost so far. Add the cell to the list of cells that have already been considered. Note that if the list of cells to be considered is ever empty, there is no valid path between the start and end nodes.

6. If the cell is the goal cell, the path is complete. Since each node in the path contains a link to the previous node in the path, the cells in the final path can be determined by “backtracking” from the goal node all the way back to the start node.

7. If the current cell isn’t the goal node, find each of the cells adjacent to the current cell–that is, its “neighbors”. In this implementation, a cell’s neighbors will be the cells to its north, south, east, and west. Most cells, then, will have four neighbors, but cells on an edge of the map will have fewer.

8. Check each neighbor cell to see if it is already present in either the list of cells to be considered or in the list of cells that have already been considered. If the neighbor is not yet present in either list, proceed to the next step. If, however, the neighbor is indeed already present in either list, ignore it and check the next neighbor.

9. For each of the current cell’s neighbors that have not yet been considered, determine the neighbor’s total estimated cost using the procedure described in step 3. Note that the cost to move from the start cell to the current cell is already known, because either the current cell is the start cell, in which case the cost will be 0, or else the cost will have been calculated in this step during a previous iteration.

10. As each neighbor’s estimated total cost is calculated, insert it into the list of nodes to be considered, in order of increasing total estimated cost.

11. Return to step 5 and repeat steps 5-11 until a path has been determined.

UPDATE 2017/02/13 – I have modified the code a bit further. Now the user can click the map to change the goal position, and a new path will be calculated and drawn. I also made the “water” terrain infinitely difficult to cross, rather than merely very difficult, and added some complexity to the map to illustrate more varied pathfinding scenarios.

AStar


<html>
<body>
<script type="text/javascript">
 
// main
 
function pathfindingTest()
{
	var terrains =
	[
		// MapTerrain(name, codeChar, color, costToTraverse)
		new MapTerrain("plain", ".", "Green", 1),
		new MapTerrain("water", "~", "Blue", Number.POSITIVE_INFINITY),
	];
 
	var map = new Map
	(
		"Map",
		terrains,
		// neighborOffsets
		[ 
			new Coords(1, 0),
			new Coords(0, 1),
			new Coords(-1, 0),
			new Coords(0, -1),
		],
		// cellsAsStrings
		[
			"................",
			"............~~~.",
			"...~~~......~.~.",
			".....~......~...",
			".....~......~~~~",
			"..~~~~~~~~......",
			"..~......~~~....",
			"..~~~......~....",
			".........~~~....",
			".....~~~~~......",
			".....~..........",
			"...~~~....~~~~..",
			".....~....~..~..",
			".....~....~..~..",
			".....~....~~~~..",
			".....~.........."
		]	
	);
 
	var path = new Path
	(
		map,
		new Coords(4, 4), // startPos
		new Coords(9, 12) // goalPos
	);
 
	var display = new Display(new Coords(256, 256));

	Globals.Instance.initialize
	(
		display,
		map,
		path
	);
	
	Globals.Instance.update();
}
 
// extensions
 
function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.addLookups = function(keyName)
	{
		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var key = element[keyName];
			this[key] = element;
		}
 
		return this;
	}
 
	Array.prototype.insertElementAt = function(element, index)
	{
		this.splice(index, 0, element);
	}
 
	Array.prototype.insertElementSortedByKeyName = function(elementToSort, keyName)
	{
		var keyValueToSort = elementToSort[keyName];
 	
		var i;
		for (i = 0; i < this.length; i++)
		{
			var elementAlreadySorted = this[i];
			var keyValueAlreadySorted = elementAlreadySorted[keyName];
			 
			if (keyValueToSort < keyValueAlreadySorted)
			{
				break;
			}
		}
 
		this.insertElementAt(elementToSort, i);
	}
 
	Array.prototype.removeAt = function(index)
	{
		return this.splice(index, 1);
	}
}
 
// classes
 
function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.absolute = function()
	{
		this.x = Math.abs(this.x);
		this.y = Math.abs(this.y);
		return this;
	}
	 
	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;	 
		return this;
	}
	 
	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}
	 
	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}
	 
	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}
	 
	Coords.prototype.equals = function(other)
	{
		return (this.x == other.x && this.y == other.y);
	}
	
	Coords.prototype.floor = function()
	{
		this.x = Math.floor(this.x);
		this.y = Math.floor(this.y);
		return this;
	}
	 
	Coords.prototype.isInRange = function(range)
	{
		var returnValue = 
		(
			this.x >= 0
			&& this.x <= range.x
			&& this.y >= 0
			&& this.y <= range.y
		);
		 
		return returnValue;
	}
	 
	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}
	 
	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;	 
		return this;
	}
	
	Coords.prototype.overwriteWithXY = function(x, y)
	{
		this.x = x;
		this.y = y;	 
		return this;
	}
	 
	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
	 
	Coords.prototype.sumOfXAndY = function()
	{
		return this.x + this.y;
	}
}
 
function Display(sizeInPixels)
{
	this.sizeInPixels = sizeInPixels;
}
{
	Display.prototype.drawMap = function(map)
	{
		var mapSizeInCells = map.sizeInCells;
		 
		var mapCellSizeInPixels = this.sizeInPixels.clone().divide
		(
			mapSizeInCells
		);
		 
		var mapCellPos = new Coords(0, 0);
		var drawPos = new Coords(0, 0);
		 
		for (var y = 0; y < mapSizeInCells.y; y++)
		{
			mapCellPos.y = y;
			 
			for (var x = 0; x < mapSizeInCells.x; x++)
			{
				mapCellPos.x = x;
				 
				var mapCellAtPos = map.cellAtPos
				(
					mapCellPos
				);
				var terrain = mapCellAtPos.terrain;
				 
				drawPos.overwriteWith
				(
					mapCellPos
				).multiply
				(
					mapCellSizeInPixels
				);
				 
				this.graphics.fillStyle = terrain.color;
				this.graphics.fillRect
				(
					drawPos.x,
					drawPos.y,
					mapCellSizeInPixels.x,
					mapCellSizeInPixels.y
				);
			 
			}
		}
	}
 
	Display.prototype.drawPath = function(path)
	{
		var map = path.map;
		this.drawMap(map);
		 
		var mapSizeInCells = map.sizeInCells;
		var mapCellSizeInPixels = this.sizeInPixels.clone().divide
		(
			mapSizeInCells
		);
		 
		var mapCellSizeInPixelsHalf = 
		mapCellSizeInPixels.clone().divideScalar(2);
		 
		var pathNodes = path.nodes;
		 
		var pathNode = pathNodes[0];
		 
		var drawPos = new Coords();
		drawPos.overwriteWith
		(
			pathNode.cellPos
		).multiply
		(
			mapCellSizeInPixels
		).add
		(
			mapCellSizeInPixelsHalf
		);
		 
		this.graphics.strokeStyle = "Red";
		this.graphics.beginPath();
		this.graphics.moveTo(drawPos.x, drawPos.y);
		 
		for (var i = 1; i < pathNodes.length; i++)
		{
			pathNode = pathNodes[i];
			drawPos.overwriteWith
			(
				pathNode.cellPos
			).multiply
			(
				mapCellSizeInPixels
			).add
			(
				mapCellSizeInPixelsHalf
			);  
			 
			this.graphics.lineTo
			(
				drawPos.x,
				drawPos.y
			);
		}
		 
		this.graphics.stroke();
	}
	 
	Display.prototype.initialize = function()
	{ 
		var canvas = document.createElement("canvas");
		canvas.width = this.sizeInPixels.x;
		canvas.height = this.sizeInPixels.y;
		 
		this.graphics = canvas.getContext("2d");
		 
		document.body.appendChild(canvas);  
	}
}

function Globals()
{
	// do nothing
}
{
	// instance
	Globals.Instance = new Globals();
	
	// methods

	Globals.prototype.initialize = function(display, map, path)
	{
		this.display = display;
		this.map = map;
		this.path = path;

		this.display.initialize();
		this.inputHelper = new InputHelper();
		this.inputHelper.initialize();
	}
	
	Globals.prototype.update = function()
	{
		this.path.calculate();
		this.display.drawPath(this.path);
	}
}

function InputHelper()
{
	this.mouseClickPos = new Coords();
}
{
	InputHelper.prototype.initialize = function()
	{
		document.body.onmousedown = this.handleEventMouseDown.bind(this);
	}

	// events

	InputHelper.prototype.handleEventMouseDown = function(event)
	{
		this.mouseClickPos.overwriteWithXY
		(
			event.x,
			event.y
		);
		
		var map = Globals.Instance.map;
		var mapCellSizeInPixels = Globals.Instance.display.sizeInPixels.clone().divide
		(
			map.sizeInCells
		);

		var mouseClickPosInCells = this.mouseClickPos.clone().divide
		(
			mapCellSizeInPixels
		).floor();
		
		var path = Globals.Instance.path;
		path.goalPos.overwriteWith(mouseClickPosInCells);
		
		Globals.Instance.update();
	}
}
 
function Map(name, terrains, neighborOffsets, cellsAsStrings)
{
	this.name = name;
	this.terrains = terrains;
	this.neighborOffsets = neighborOffsets; 
	this.cellsAsStrings = cellsAsStrings;
	 
	this.terrains.addLookups("codeChar");
	this.sizeInCells = new Coords
	(
		this.cellsAsStrings[0].length, 
		this.cellsAsStrings.length
	);
	this.sizeInCellsMinusOnes = this.sizeInCells.clone().subtract
	(
		new Coords(1, 1)
	);
}
{
	Map.prototype.cellAtPos = function(cellPos)
	{
		var codeChar = this.cellsAsStrings[cellPos.y][cellPos.x];
		var terrain = this.terrains[codeChar];
		 
		return new MapCell(terrain);
	}
}
	 
function MapCell(terrain)
{
	this.terrain = terrain;
}
	 
function MapTerrain(name, codeChar, color, costToTraverse)
{
	this.name = name;
	this.codeChar = codeChar;
	this.color = color;
	this.costToTraverse = costToTraverse;
}
	 
function Path(map, startPos, goalPos)
{
	this.map = map;
	this.startPos = startPos;
	this.goalPos = goalPos;
}
{
	Path.prototype.calculate = function()
	{
		var nodesToConsider = this.calculate_1_InitializeListOfNodesToConsider();
		var nodesAlreadyConsidered = [];
		 
		while (nodesToConsider.length > 0)
		{
			var nodeToConsider = nodesToConsider[0];
			 
			if (nodeToConsider.cellPos.equals(this.goalPos) == true)
			{   
				this.nodes = this.calculate_3_BuildListOfNodesFromStartToGoal
				(
					nodeToConsider
				);
				break;
			}
			else
			{
				nodesToConsider.removeAt(0);
				var nodeToConsiderID = nodeToConsider.id(this.map.sizeInCells);
				nodesAlreadyConsidered[nodeToConsiderID] = nodeToConsider;
				 
				this.calculate_2_AddNeighborsToListOfNodesToConsider
				(
					nodeToConsider,
					nodesToConsider,
					nodesAlreadyConsidered
				);
			}
		}
	}
 
	Path.prototype.calculate_1_InitializeListOfNodesToConsider = function()
	{
		var nodesToConsider = [];
		 
		var displacementFromStartToGoal = new Coords();
		 
		displacementFromStartToGoal.overwriteWith
		(
			this.goalPos
		).subtract
		(
			this.startPos
		);
		 
		var costFromStartToGoalEstimated = 
			displacementFromStartToGoal.absolute().sumOfXAndY();
		 
		var startNode = new PathNode
		(
			this.startPos, // cellPos
			0, // costFromStart
			costFromStartToGoalEstimated,
			null // prev
		);
		 
		nodesToConsider.push(startNode);
		 
		return nodesToConsider;
	}
	 
	Path.prototype.calculate_2_AddNeighborsToListOfNodesToConsider = function
	(
		nodeToFindNeighborsOf,
		nodesToConsider,
		nodesAlreadyConsidered
	)
	{
		var mapSizeInCells = this.map.sizeInCells;
		 
		var nodesNeighboring = nodeToFindNeighborsOf.neighbors(this);
		 
		for (var n = 0; n < nodesNeighboring.length; n++)
		{
			var nodeNeighbor = nodesNeighboring[n];
			var nodeNeighborID = nodeNeighbor.id(mapSizeInCells);
			 
			var hasNodeNeighborNotYetBeenSeen = 
			(
				nodesAlreadyConsidered[nodeNeighborID] == null 
				&& nodesToConsider[nodeNeighborID] == null
			);
			 
			if (hasNodeNeighborNotYetBeenSeen == true)
			{
				nodesToConsider.insertElementSortedByKeyName
				(
					nodeNeighbor,
					"costToGoalEstimated"
				);
				 
				nodesToConsider[nodeNeighborID] = nodeNeighbor;
			}
		}
	}
		 
	Path.prototype.calculate_3_BuildListOfNodesFromStartToGoal = function(nodeGoal)
	{
		var returnValues = [];
		 
		var nodeCurrent = nodeGoal;
		 
		while (nodeCurrent != null)
		{
			returnValues.insertElementAt(nodeCurrent, 0);
			nodeCurrent = nodeCurrent.prev;
		}
		
		for (var i = 0; i < returnValues.length; i++)
		{
			var nodeCurrent = returnValues[i];
			if (nodeCurrent.costFromStart == Number.POSITIVE_INFINITY)
			{
				returnValues.length = i;
				break;
			}
		}
		 
		return returnValues;
	}
}
 
function PathNode(cellPos, costFromStart, costToGoalEstimated, prev)
{
	this.cellPos = cellPos;
	this.costFromStart = costFromStart;
	this.costToGoalEstimated = costToGoalEstimated;
	this.prev = prev;
}
{
	PathNode.prototype.id = function(mapSizeInCells)
	{
		var nodeToConsiderIndex = 
			this.cellPos.y 
			* mapSizeInCells.y 
			+ this.cellPos.x;
		 
		var returnValue = "_" + nodeToConsiderIndex;
		 
		return returnValue;
	}
	 
	PathNode.prototype.neighbors = function(path)
	{
		var map = path.map;
		 
		var returnValues = [];
		var mapSizeInCellsMinusOnes = map.sizeInCellsMinusOnes;
		var costToGoalTemp = new Coords();
		var neighborPos = new Coords();
		 
		var neighborOffsets = map.neighborOffsets;
		 
		for (var i = 0; i < neighborOffsets.length; i++)
		{
			var neighborOffset = neighborOffsets[i];
			 
			neighborPos.overwriteWith
			(
				this.cellPos
			).add
			(
				neighborOffset
			);
			 
			if (neighborPos.isInRange(mapSizeInCellsMinusOnes) == true)
			{
				var neighborMapCell = map.cellAtPos(neighborPos);
				var neighborTerrain = neighborMapCell.terrain;
				var neighborCostToTraverse = neighborTerrain.costToTraverse;
				 
				var neighborCostFromStart = 
					this.costFromStart 
					+ neighborCostToTraverse;
				 
				var neighborCostToGoalEstimated = 
					neighborCostToTraverse
					+ costToGoalTemp.overwriteWith
					(
						path.goalPos
					).subtract
					(
						this.cellPos
					).absolute().sumOfXAndY();
				 
				var neighborNode = new PathNode
				(
					neighborPos.clone(),
					neighborCostFromStart,
					neighborCostToGoalEstimated,
					this // prev
				);
				 
				returnValues.push(neighborNode);
			}
		}
	 
		return returnValues;
	}
}
 
// run
 
pathfindingTest();
 
</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s