Game is LIVE

You can play the game where I use this algorithm here: Vocab RPG

This is a two-part series about creating an A* pathfinding algorithm in JavaScript on a grid with 4-directional movement.

The first part is about creating the algorithm in its most basic form. The second part is about improving the algorithm’s calculation speed with binary heaps.

Everything you are reading on this page is the first part of this series.

Overview

There are already many detailed posts on the internet about the A* pathfinding algorithm. So why do I write another one?

1. This guide is about writing the algorithm in JavaScript.
2. I will also show an implementation example with the Phaser 3 framework.
3. The grid loaded into the A* algorithm is created by the popular Tiled Map Editor.

The combination of these three points is quite unique and at the same time I know there is a large community that would use exactly these tools. However, the A* algorithm presented here will work just as fine without these tools. All you need to do is provide the grid and know which tiles are walkable.

So here we go!

A* Pathfinding Algorithm: The Essentials

For a very detailed explanation of the A* algorithm I suggest this website here: Amit’s A* Pages. I will focus here on the most important information only so we can build our algorithm in JavaScript.

In short, the A* algorithm finds the fastest path between two points on a tiled grid. Each tile on the grid is called a node.

The algorithm tracks the nodes in two lists: the open list and the closed list.

The open list contains all nodes that could be part of the best path and need to be examined. The closed list contains all nodes that were on the open list previously and have already been examined.

Remember that nodes are the tiles on the grid. However, we have to call them nodes (and not tiles) because we will save more information about them.

In the A* algorithm, each node must carry the following information:

• Position on the grid: x and y.
• g-value: Distance from the starting node to the current node.
• h-value: H stands for heuristic. This value is an approximate calculation of the distance between the current node and the goal node.
• f-value: The sum of the g-value and h-value. It is used to compare nodes with each other. A lower f-value is considered better.
• Parent: The parent node of the current node.

I hope the above summary was not too confusing. Hopefully, when you see the JavaScript code it becomes clearer.

Creating Nodes in JavaScript

Note that I use the values tx and ty for “tile x” and “tile y” respectively, meaning it is the position on the grid. I do this to differentiate it from the standard x and y values which are in pixels.

The heuristic value is calculated using the Manhatten Method. This method is widely accepted as very efficient on a grid with 4 directional movement – which is exactly what we are doing!

With this said, I have created a JavaScript object for the nodes as follows:

let Node = function(pos, goal, parent)
{
	'use strict';
	
	this.tx		= pos.tx;
	this.ty		= pos.ty;
	this.parent	= parent || null;
	
	// g(n) The exact cost of the path from the starting point to any vertex n
	this.g		= this.parent	?	this.parent.g + 1 : 0;
	
	// h(n) The heuristic estimated cost from vertex n to the goal
	this.h		= this.calcHeuristic(pos, goal);
	
	// f(n) = g(n) + h(n)
	this.f		= this.g + this.h;
};

Node.prototype.calcHeuristic = function(pos, goal)
{
	'use strict';
	
	const movementcost	= 1;
	
	let dx	= Math.abs(goal.tx - pos.tx);
	let dy	= Math.abs(goal.ty - pos.ty);
	
	return movementcost * (dx + dy);
};

Create a Grid as an Array

The grid for our JavaScript algorithm must be a two-dimensional array. For my example, I’ve created a simple map in the Tiled Map Editor and exported it as a JSON file.

For the game I use the Phaser 3 framework. Conveniently, Phaser 3 allows you to load this JSON file into the game and access the grid.

Here is how you load the JSON file as a tilemap into the Phaser 3 game, inside the preload scene:

// The spritesheet containing the tiles for your tilemap
this.load.image('tilemap_32px',	'tilemap_32px.png');
// The JSON file generated by the Tiled export
this.load.tilemapTiledJSON('map_1',	'map1.json');

And here is how you can access the grid array in the game:

let map = this.make.tilemap({ key: 'map_1', tileWidth: 32, tileHeight: 32 });
let tileset = map.addTilesetImage('tilemap_32px');
let layer_2 = map.createStaticLayer('objects', tileset, 0, 0);
// Grid is saved here: layer_2.layer.data

For more info about the Phaser 3 API, click here: Phaser 3 API Tilemaps
And here you can see more tilemap examples in Phaser 3: Phaser 3 Tilemaps Examples

The most important part is that we have a two-dimensional grid representing the whole tilemap. In my example (an array generated by Tiled and then imported into the Phaser 3 framework), the grid uses a value of -1 for empty tiles.

In other words, if the value is -1, we can walk on it. If it has any value of 0 or higher, there will be an object drawn that blocks the path.

The reason for this is that the value is actually the index of the frame from the spritesheet. -1 means there is nothing drawn at all. Index 0 means we draw the first frame of the spritesheet and so on.

Here is how it looks in JavaScript code:

this.grid	= layer_2.layer.data;

// Check the index value to see if it is a walkable tile
// or blocked by an object:
// this.grid[y][x].index

Last note: You are also free to create your own two-dimensional array for the grid! What’s important is that you know which values represent a walkable tile and which tiles are blocked.

Now that we have the nodes and the grid prepared, we can finally tackle the A* pathfinding algorithm!

A* Pathfinding Algorithm: The Set-Up

Let’s initiate our object representing the A* algorithm:

• As you can see, the lists are arrays.
• The start and goal will be nodes. For this purpose we instantiate the Node object we created earlier (see code above).
• The grid will be a two-dimensional array.

let Astar = function()
{
	'use strict';
	
	this.OPEN	= [];
	this.CLOSED	= [];
	
	this.START;
	this.GOAL;
	
	this.GRID;
};

Now let’s look at the first part of the findPath() method:

Astar.prototype.findPath = function(grid, start, goal)
{
	'use strict';
	
	// Init
	this.GRID		= this.cloneGrid(grid);
	
	this.START		= new Node(start, goal);
	this.GOAL		= new Node(goal, goal);
	
	this.OPEN		= [ this.START ];
	this.CLOSED		= [];
	
	// Empty grid
	if(this.GRID.length <= 0)
	{
		return [];
	}
	
	// Start and goal are the same tile
	if(this.START.tx === this.GOAL.tx && this.START.ty === this.GOAL.ty)
	{
		return [];
	}
	
	// GOAL is on a blocked tile
	if(this.GRID[this.GOAL.ty][this.GOAL.tx].index != -1)
	{
		return [];
	}

	// to be continued below...

this.START and this.GOAL are simply the start and goal nodes for which we try to find the fastest path. At the beginning, the open list contains only the start node and the closed list is empty.

We also start out by cloning the grid. Cloning the grid is important so you don't change any values in the grid that was provided. Like this we can be sure the original grid stays unaltered and as we remove examined nodes, they won't go missing from the grid.

Cloning the greed means simply looping through the two-dimensional array and saving the values in a new array:

Astar.prototype.cloneGrid = function(grid)
{
	'use strict';
	
	let clone	= [];
	
	for(let y = 0; y < grid.length; y++)
	{
		clone[y]	= [];
		
		for(let x = 0; x < grid[y].length; x++)
		{
			clone[y][x]	= grid[y][x];
		}
	}
	
	return clone;
};

A* Pathfinding Algorithm: The Loop

Below continues the findPath() method for my A* algorithm. There is a lot happening here and I will try to break it apart the best I can (please leave a comment below if something is unclear):

We have to keep examining the open list for as long as it contains nodes. Remember, the open list contains all candidates which could be part of the fastest path. That's why our while clause is: while(this.OPEN.length > 0).

Now the question is, how do we know which nodes should be added to the open list? Quite simply, all neighbor nodes of our current node! As our algorithm is for 4 directional movement, each node has up to 4 neighbors.

Remember that in our very first iteration of the loop, we have only the starting node in the open list.

Another question is how do we decide which node is the best candidate? If you remember, in the section above about the nodes we said that a node with a lower f-value is considered a better node.

In short:

1. We keep adding the neighbors of the current tile to the open list.
2. Then we keep examining all nodes in the open list and move the best node into the closed list.
3. Once our current node is the same as our goal node, we have arrived and found the path!
4. If the current node is not the goal node, and thus we have not arrived yet, we simply continue with the loop until we finally do.
5. If we examined all nodes from the open list and still haven't arrived at the goal node, it means that there is no possible path between the start and goal node.

With this said you will see how we go through this step-by-step in the code below:

	// continuing from above Astar.prototype.findPath()

	while(this.OPEN.length > 0)
	{		
		// Get best node n from OPEN
		let n	= this.getLowestFromOpen();
		
		this.removeLowestFromOpen();
		
		this.CLOSED.push(n);
		
		// n is the goal, we are done
		if(n.tx == this.GOAL.tx && n.ty == this.GOAL.ty)
		{
			this.GOAL	= n;
			break;
		}
		
		// Examine neighbors of n
		let children	= this.getNeighbors(n);
		
		for(let i = 0; i < children.length; i++)
		{
			let child	= children[i];
			
			if(this.getNodeIdxInList(this.CLOSED, child) >= 0)
			{
				continue;
			}
			
			child.g	= n.g + 1;
			child.h	= n.calcHeuristic(child, this.GOAL);
			child.f	= child.g + child.h;
			
			let idx	= this.getNodeIdxInList(this.OPEN, child);
			
			if(idx >= 0)
			{
				if(child.g > this.OPEN[idx].g)
				{
					continue;
				}
			}
			
			this.OPEN.push(child);
		}

		// to be continued below...
	}

As you noticed, there are a couple of helper methods to keep this loop well-arranged:

• this.getLowestFromOpen()
• this.removeLowestFromOpen()
• this.getNeighbors()
• this.getNodeIdxInList()

These methods are very basic JavaScript and you could easily write them yourself. However, they help understand how the A* algorithm works and I will share my code below with some key takeaways.

A* Method: getLowestFromOpen()

Please note: Using unsorted arrays for your open and closed list is not the efficient and best way to do this! The fastest calculation speed is achieved by using a binary heap data structure. However, this first post is about writing the A* pathfinding algorithm in JavaScript in the most basic way. I will improve the algorithm with binary heaps in the follow-up post.

As you know by now, the best node is the node with the lowest f-value. And where are all the candidates stored? That's right, in the open list! Hence, we loop through the open list and look at every node's f-value. Once found, we return that node. It's very straight forward.

A very important detail is this statement here: if(this.OPEN[i].f <= lowest.f). The <= operator is crucial for the workings of this A* algorithm. If you think about it, which nodes are added last to the open list? That's right, the newest ones. And the newest ones are also the closest ones to the current node that you are examining.

By using the <= operator, we decide a very important tiebreaker situation where several nodes have the same f-value. In this case, we prioritize nodes closer to our current tile and not older nodes that were added in a much earlier iteration of the loop.

If you are confused about this, feel free to leave a comment below and I'll do my best to re-phrase!

Astar.prototype.getLowestFromOpen = function()
{
	'use strict';
	
	let lowest	= this.OPEN[0];
	
	for(let i = 0; i < this.OPEN.length; i++)
	{
		if(this.OPEN[i].f <= lowest.f)
		{
			lowest	= this.OPEN[i];
		}
	}
	
	return lowest;
};

A* Method: removeLowestFromOpen()

It is crucial that when you add a node to the closed list that you remove it from the open list. As you know now, the node with the lowest f-value is the best candidate. This is the node that must be moved to the closed list and as such must be removed from the open list. The helper method below removes it for us:

Astar.prototype.removeLowestFromOpen = function()
{
	'use strict';
	
	let idx		= 0;
	let lowest	= this.OPEN[idx];
	
	for(let i = 0; i < this.OPEN.length; i++)
	{
		if(this.OPEN[i].f <= lowest.f)
		{
			idx		= i;
			lowest	= this.OPEN[i];
		}
	}
	
	this.OPEN.splice(idx, 1);
};

A* Method: getNeighbors()

This is a long method however it is very simple to understand: All we need to do is get all the neighbor nodes of the current node. Remember that we are using 4-directional movement and as such it can return maximum four neighbors.

As we are moving on a grid, we check the neighbor nodes left, right, up and down. As a reminder, tx and ty stand for tile-x and tile-y respectively. It stands for the x/y position on the grid, as opposed to the x/y position in pixels.

Also remember that in the HTML5 canvas the coordinate system expands from the origin in the top-left corner to the right and down:

• Left: tx - 1
• Right: tx + 1
• Up: ty - 1
• Down: ty + 1

Finally, we can only return neighbors that we can also walk on!

"Walkable tile" means the tile is actually on the grid (and not outside of the bounds of the grid) and that the tile not blocked by a house, tree or any other objects you want to draw in your game.

Remember from the section above about the grid: When we export a map generated with the Tiled Map Editor, an index of -1 means the tile can be walked on.

Astar.prototype.getNeighbors = function(node)
{
	'use strict';
	
	let neighbors	= [];
	
	// Left neighbor
	if(node.tx - 1 >= 0 && this.checkWalkable(node, 'left'))
	{
		let pos		= { tx: node.tx - 1, ty: node.ty };
		neighbors.push(new Node(pos, this.GOAL, node));
	}
	
	// Right neighbor
	if(node.tx + 1 < this.GRID[0].length && this.checkWalkable(node, 'right'))
	{
		let pos		= { tx: node.tx + 1, ty: node.ty };
		neighbors.push(new Node(pos, this.GOAL, node));
	}
	
	// Up neighbor
	if(node.ty - 1 >= 0 && this.checkWalkable(node, 'up'))
	{
		let pos		= { tx: node.tx, ty: node.ty - 1 };
		neighbors.push(new Node(pos, this.GOAL, node));
	}
	
	// Down neighbor
	if(node.ty + 1 < this.GRID.length && this.checkWalkable(node, 'down'))
	{
		let pos		= { tx: node.tx, ty: node.ty + 1 };
		neighbors.push(new Node(pos, this.GOAL, node));
	}
	
	// Return all neighbors
	return neighbors;
};

Astar.prototype.checkWalkable = function(n, dir)
{
	'use strict';
	
	let direction	= dir	|| '';
	let is_walkable	= true;
	
	switch(direction.toLowerCase())
	{
		case 'left':
			is_walkable	= this.GRID[n.ty][n.tx - 1].index === -1	?	true	:	false;
			break;
		case 'right':
			is_walkable	= this.GRID[n.ty][n.tx + 1].index === -1	?	true	:	false;
			break;
		case 'up':
			is_walkable	= this.GRID[n.ty - 1][n.tx].index === -1	?	true	:	false;
			break;
		case 'down':
			is_walkable	= this.GRID[n.ty + 1][n.tx].index === -1	?	true	:	false;
			break;
		default:
			is_walkable	= this.GRID[n.ty][n.tx].index === -1		?	true	:	false;
	}
	
	return is_walkable;
};

A* Method: getNodeIdxInList()

This is simply a method to check if the current node is already in the open or closed list. This step is very important because we must not add a node to either of these lists, if it's already in there!

In the loop, it is very possible that your current tile has neighbors that you have already examined. It is crucial that you check if a candidate is already in your open or closed list. If it is, then you must not add it again.

If it returns -1 it means that it was not found in the list. If it returns an index of 0 or higher, then the node is already inside the list:

Astar.prototype.getNodeIdxInList = function(arr, node)
{
	'use strict';
	
	for(let i = 0; i < arr.length; i++)
	{
		if(arr[i].tx == node.tx && arr[i].ty == node.ty)
		{
			return i;
		}
	}
	
	return -1;
};

Neighbors, Children and Parents

We are very close to finishing our A* algorithm now! Before we finalize the JavaScript code, there is one more concept you must understand: Nodes are connected with each other in a parent-child relationship. It is vital that you understand this because this is how we will find the path eventually.

As our algorithm keeps looping through the open list, adding more neighbors, and moving the best candidates into the closed list, it does something very important: defining the parent of each node.

When we get the neighbor nodes, we also set the current node as the parent of the neighbors. You are probably thinking to yourself right now that it is really not a complicated concept, however it is crucial you are aware of it nonetheless.

Finally We Found the Path

This is the third and last subsection of the findPath() method. Remember, we get out of the loop the moment our current tile equals the goal tile. And also remember that for each node we have saved its parent node. Now all we need to do is the following:

1. Start with the last node that was added to the closed list, as it equals the goal node.
2. Add this node to the path array which we will return as our result.
3. Now take the parent node and add it also to the path array.
4. Keep doing this until you arrive at the start node of the path! The start node does not have a parent because this is where it all started.

The last bit of code below is a loop doing exactly what was just described. Note that we use path.unshift() to add the nodes to the beginning of the array because we are moving backwards from the goal node to the start node.

Also note this line here: path.splice(0, 1);. The last node added to your path array will be the start node. Most likely you will not need the start node in your path because your sprite will already be standing on this tile.

	// continuing from above Astar.prototype.findPath()

	// Find path by following parents from GOAL to START
	let path	= [];
	let current	= this.GOAL;
	
	while(current)
	{
		path.unshift(current);
		
		current	= current.parent;
	}
	
	path.splice(0, 1);
	
	return path;
};

The Complete findPath() Method

Until now and to illustrate the most essential concepts, the findPath() method was split up into three parts. Below you will find the method as a whole:

Astar.prototype.findPath = function(grid, start, goal)
{
	'use strict';
	
	// Init
	this.GRID		= this.cloneGrid(grid);
	
	this.START		= new Node(start, goal);
	this.GOAL		= new Node(goal, goal);
	
	this.OPEN		= [ this.START ];
	this.CLOSED		= [];
	
	// Empty grid
	if(this.GRID.length <= 0)
	{
		return [];
	}
	
	// Start and goal are the same tile
	if(this.START.tx === this.GOAL.tx && this.START.ty === this.GOAL.ty)
	{
		return [];
	}
	
	// GOAL is on a blocked tile
	if(this.GRID[this.GOAL.ty][this.GOAL.tx].index != -1)
	{
		return [];
	}
	
	while(this.OPEN.length > 0)
	{		
		// Get best node n from OPEN
		let n	= this.getLowestFromOpen();
		
		this.removeLowestFromOpen();
		
		this.CLOSED.push(n);
		
		// n is the goal, we are done
		if(n.tx == this.GOAL.tx && n.ty == this.GOAL.ty)
		{
			this.GOAL	= n;
			break;
		}
		
		// Examine neighbors of n
		let children	= this.getNeighbors(n);
		
		for(let i = 0; i < children.length; i++)
		{
			let child	= children[i];
			
			if(this.getNodeIdxInList(this.CLOSED, child) >= 0)
			{
				continue;
			}
			
			child.g	= n.g + 1;
			child.h	= n.calcHeuristic(child, this.GOAL);
			child.f	= child.g + child.h;
			
			let idx	= this.getNodeIdxInList(this.OPEN, child);
			
			if(idx >= 0)
			{
				if(child.g > this.OPEN[idx].g)
				{
					continue;
				}
			}
			
			this.OPEN.push(child);
		}
	}
	
	// Find path by following parents from GOAL to START
	let path	= [];
	let current	= this.GOAL;
	
	while(current)
	{
		path.unshift(current);
		
		current	= current.parent;
	}
	
	path.splice(0, 1);
	
	return path;
};

Final Words

Thank you for reading until here!

Keep in mind that the algorithm presented here is not the most efficient in terms of calculation speed. Using unsorted arrays for the open and closed lists is not optimal and from what I've learned, using the binary heap data structure is much faster and is widely considered to be the best approach.

That's why in my follow-up post I will improve the current A* pathfinding algorithm with binary heap data structures. Follow me on Twitter @thejamespierce to find out when it's written and published here on my Dev Blog.

If you have open questions or feedback, please use the comments section below. I would love to hear how I can improve this article.

And now reward yourself with a little break and check out my latest game: Monster Clean-Up 🙂