A* Search Algorithm in JavaScript (Updated)

See the updated pathfinding demo of A* Search in JavaScript.

Get all the updated source code from github.

When I first wrote the A* Search in JavaScript article I knew there were some things that could make the pathfinding faster. I didn't know realize that it would be this much faster. Here are my (totally unscientific) results:

Observed Speed of A* Search on Chrome 6.0.472.55 on OS X
# rows	original	updated
100	700-2500ms (wildly variant)	5-10ms
50	160ms	5-10ms
15	0-5ms	0-2ms

Here's What Changed

I got some feedback about using a heap or a priority queue instead of a list (basically keep the open items in sorted order the whole time so we can just grab it off of the top instead of needing to traverse the whole list every time. As predicted, this makes a huge difference as the number of nodes goes up, but may actually be a little slower for a very low number of nodes because of the overhead of keeping them sorted. I found a binary heap implementation from http://eloquentjavascript.net/appendix2.html and put it in.

Also, I realized two places that I was traversing lists that could be avoided. Getting rid of extra traversals (especially ones that ran inside nested loops) made a very big difference in performance.

I was keeping all of the nodes inside a closed list, which required traversing that list every time to see if it was already closed. This was replaced with a simple bit on the node to track if it had been closed.
I was checking to see if a node was visited already by seeing if it was in the open list. This was replaced by a simple bit to see if it had been visited.

Old Pseudocode

push startNode onto openList
while(openList is not empty) {
  currentNode = find lowest f in openList
  if currentNode is final, return the successful path
  push currentNode onto closedList and remove from openList
  foreach neighbor of currentNode {
    if neighbor is not in openList {
      save g, h, and f then save the current parent
      add neighbor to openList
    }
    if neighbor is in openList but the current g is better than previous g {
      save g and f, then save the current parent
    }
  }
}

Updated Pseudocode (* lines have changed)

* push startNode onto openHeap
while(openList is not empty) {
  * currentNode = pop from openHeap
  if currentNode is final, return the successful path
  * set currentNode as closed
  foreach neighbor of currentNode {
    * if neighbor is not set visited {
      * save g, h, and f then save the current parent and set visited
      * add neighbor to openHeap
    }
    if neighbor is in openList but the current g is better than previous g {
      save g and f, then save the current parent
      * reset position in openHeap (since f changed)
    }
  }
}

I also did some general cleanup, getting rid of dependancies on the demo, and I split out the code so that the search function can be used standalone (taking a two dimensional array as a parameter), so if someone just wanted the optimized astar search, you could call it like so:

<script type='text/javascript' src='astar.js'></script>
<script type='text/javascript'>
var graph = new Graph([
  [1,1,1,1], // 1 is open, 0 is wall
  [0,1,1,0],
  [0,0,1,1]
]);
var start = graph.nodes[0][0];
var end = graph.nodes[1][2];
var result = astar.search(graph.nodes, start, end);
// result is an array containing the shortest path
</script>

What Could Make It Better?

Last time I posted about this, I got a lot of feedback (mostly about how slow it was). If anyone reading this knows of anything that could make it better, let me know.

Source Code (direct links)

astar.js |

graph.js |

demo.js |

astar-list.js (old implementation with open and closed values swapped)

Comments

Stark Says:

October 4th, 2010 at 5:57 am

Brian, big thanks for your work!

Brian Grinstead » Blog Archive » A* Search Algorithm in JavaScript Says:

October 4th, 2010 at 6:43 am

[…] that this code has been updated. I have an updated blog post detailing what […]

codergamer Says:

January 13th, 2011 at 7:34 am

I tried to implement something like this.But I discouraged too early.Thanks to your work.
I can now improve my engine.
Great work! thanks and keep it up.
Best regards Codergamer

Age of empire browser versie (poc) | svenn.d Says:

February 22nd, 2011 at 10:26 am

[…] gebruikt, de villagers mogen niet door objecten heen lopen toch ?! Ik heb hier gekozen voor het A*pathfinding algoritme. Een bijkomstig probleem is dat het pathfinding iedere stap moet herhaald worden, gezien het pad […]

felix Says:

May 11th, 2011 at 4:36 pm

Hi again :)
now i made a 8 direction a* javascrpt function .. yours helped me alot!

so here is what i think that may be better in yours :

– instead of checkeing everytime the openheap size for open nodes you may check a small integer variable .. so if you open a new node do ++ if you close one — …

– you may add a different node value support .. if wall value = 10 a node with 0 will be better then one with 5… see http://ronco.packagecloud.com/path/ ;)

– you may try my version of a BinaryHeap .. i dont know whitch is faster

 
// c is the array with the nodes sorted from its cost
 
//k is a list of c's keys
 
//in this example the nodes total cost must be in node.c
 
var openlist = [c:[],k:[]];
 
 
//add a node
// if p is true the node will be added to highest priority of nodes this the same cost
 
openlist = addToOpenList(node,openlist,p);
 
//remove it
 
openlist = removeFromOpenListt(node,openlist);
 
 
// to get the next node use
 
nextnode = cn = openlistt.c[Math.min.apply(Math,openlist.k)][0];
 
// the two functions
 
        function addToOpenList(node,actl,p){
		if(!actl.c[node.c]){
			actl.c[node.c] = new Array(node);
			actl.k.push(node.c);
		}else if(!p){
			actl.c[node.c].push(node);
		}else{
			actl.c[node.c].splice(0,0,node);
		}
		return actl;
	}
 
	function removeFromOpenList(node,actl){
		var key = 0;
		for(var i=0,al=actl.c[node.c].length;i=0;i--){
				if(actl.k[i] ==node.c){
					actl.k.splice(i,1);
					break;
				}
			}
		}
		return actl;
	}

felix Says:

May 11th, 2011 at 4:42 pm

oh damn sorry for this dubble post but i paste the wrong remove function .. it shuld be:

	function removeFromOpenList(node,actl){
		var key = 0;
		for(var i=0,al=actl.c[node.c].length;i=0;i--){
				if(actl.k[i] ==node.c){
					actl.k.splice(i,1);
					break;
				}
			}
		}
		return actl;
	}

Brian Says:

May 11th, 2011 at 7:46 pm

Thanks Felix!
Nice demo – I really like the idea of giving different nodes weights. I am also interested in optimizations, I will have to look through your source to see if we can speed it up and add in the 8 directions. All the source is here: https://github.com/bgrins/javascript-astar.

fatmanx Says:

December 15th, 2011 at 8:48 am

In order to have nice diagonal straight lines between two nodes on a blank table (and other situations as well) I added this to astar.js in the neighbors method:

 
        if(grid[x-1] &amp;&amp; grid[x-1][y-1] &amp;&amp; ( (grid[x] &amp;&amp; grid[x][y-1] &amp;&amp; !grid[x][y-1].isWall()) || (grid[x-1] &amp;&amp; grid[x-1][y] &amp;&amp; !grid[x-1][y].isWall()) )  ) {
            ret.push(grid[x-1][y-1]);
        }
        if(grid[x+1] &amp;&amp; grid[x+1][y-1] &amp;&amp; ( (grid[x] &amp;&amp; grid[x][y-1] &amp;&amp; !grid[x][y-1].isWall()) || (grid[x+1] &amp;&amp; grid[x+1][y] &amp;&amp; !grid[x+1][y].isWall()) )  ) {
            ret.push(grid[x+1][y-1]);
        }
        if(grid[x-1] &amp;&amp; grid[x-1][y+1] &amp;&amp; ( (grid[x] &amp;&amp; grid[x][y+1] &amp;&amp; !grid[x][y+1].isWall()) || (grid[x-1] &amp;&amp; grid[x-1][y] &amp;&amp; !grid[x-1][y].isWall()) )  ) {
            ret.push(grid[x-1][y+1]);
        }
        if(grid[x+1] &amp;&amp; grid[x+1][y+1] &amp;&amp; ( (grid[x] &amp;&amp; grid[x][y+1] &amp;&amp; !grid[x][y+1].isWall()) || (grid[x+1] &amp;&amp; grid[x+1][y] &amp;&amp; !grid[x+1][y].isWall()) )  ) {
            ret.push(grid[x+1][y+1]);
        }

The code will push the diagonal nodes too into the neighbors vector if the said node has at least one neighbor that is not wall (you may change this to whatever you like, I thought it finds more natural paths this way)
Enjoy!

NinjaSudo Says:

March 21st, 2012 at 11:02 pm

I found this version of the JavaScript A* implementation. http://devpro.it/examples/astar/index2.html

Seems to have quite the efficient approach the codes a bit harder to read and it’s not super portable. What do you think?

rarecoins Says:

April 29th, 2012 at 1:09 am

Much Thanks!…

Thanks for taking the time to provide us all with the info!…

JavaScript – for loop does not correctly allocate the x and y Says:

May 6th, 2012 at 2:14 pm

[…] using a A* pathfinding script in a simple JavaScript 2D (canvas) game. I broke my game down to a SSCCE. Anyway, my game is 15 […]

Neel Says:

May 20th, 2012 at 1:42 pm

Hi Brian, this is awesome! In a game I’m working on, different kinds of tiles have different movement costs (i.e. water’s cost is 2, so moving over a water tile costs as much as moving over 2 normal tiles.) How would I implement that using your astar code?

Brian Says:

May 21st, 2012 at 5:44 am

Neel,
This is a problem we have been talking about over on the Github project. See this issue: https://github.com/bgrins/javascript-astar/issues/3 and this post: http://www.briangrinstead.com/blog/astar-graph-search-variable-costs.

The basic gist is that you need to mark the cost on each node, and the algorithm should take care of the rest. See this line: https://github.com/bgrins/javascript-astar/blob/master/astar.js#L14. There are a couple of different ways you can handle this. Either by creating a second graph that contains cost data only, or changing the semantics of the original graph to make WALL = 0, and anything else = COST. See the post for more details. I need some feedback from people implementing this algorithm about what is the best way to handle this so I can get this functionality into trunk. Let me know what you think!

8 great A* pathfinding resources | Hey, Javascript! Says:

May 25th, 2012 at 1:55 pm

[…] 7) Brian Grinstead’s Javascript implementation […]

Kieve Chua Says:

October 19th, 2012 at 9:08 pm

Thanks for the great work!
Some newbie question here, is it possible for a* search to have more than 8 nodes?
For my case, I need to search a path that possible to have more than 8 nodes, wondering is a* the best algorithm for this case …

Gabriel Says:

April 12th, 2013 at 6:33 am

Hi
I tried using your code in one of my projects (a planner for a maze-like thing where the shortest path through it will be highlighted).

I do not seem to be able to use your code standalone, even your snippet (https://gist.github.com/bgrins/581352) does not do anything if i just use this on my page (astar.js and graph.js are correctly in the same folder as the html-file and also imported).

If I run this gist in the console on your demo page, it works as intended, but if I run it on my page the result is always an empty array.

See this JSFiddle: http://jsfiddle.net/Utmqr/

What is missing? :)
Thanks for your help.

Brian Says:

April 12th, 2013 at 8:03 am

Gabriel,
Doh! We had made a switch to make ‘0’ a wall and ‘1’ an open path. This makes it easier to do weighted nodes, as ‘2’ could be twice as far to travel for obstacles and whatnot. Unfortunately, I had not updated the gist. See this jsFiddle: http://jsfiddle.net/Utmqr/2/, and the gist is now up to date as well: https://gist.github.com/bgrins/581352.

Gabriel Says:

April 12th, 2013 at 9:16 am

Hi Brian

Thanks for the quick reply and the clarification.

This is really nice, thanks for sharing this implementation :)

PeteA Says:

May 2nd, 2013 at 10:23 am

Was just thinking if this could be modified so that it took a ‘height’ parameter and the cost associated was based on the current tile height vs the one you’re moving to. Could be a fraction of the cost value, so 1.2 would be cost 1 with a height 2… However that may just vastly complicate things!

Brian Says:

May 2nd, 2013 at 10:42 am

Regarding allowing variable height / widths, that is definitely an interesting idea! It does seem like it could complicate things when trying to allow diagonal movement, but it would be cool. If you want to play around with it you could add a new vertical cost here in the init function: https://github.com/bgrins/javascript-astar/blob/master/astar.js#L14 then determine which cost to apply to the gScore here: https://github.com/bgrins/javascript-astar/blob/master/astar.js#L67. You could also store the vertical cost as a separate grid as opposed to a fraction, but I think you could probably get it to work either way.

Rachel Says:

May 31st, 2013 at 1:50 pm

Hi

Great code.

2 Questions:

How can I make the path line stay viable

How can I automatically make the path display when I pass an “end” value?

Thanks

Dean H. Says:

December 23rd, 2013 at 9:43 am

Brian, my use case is a grid of city streets where streets have different speed limits. I was considering using the astar.js code, but in order for it work correctly, I think cost should be a property of the edges rather than the nodes. Do you see another way to go about it?

tieTYT Says:

February 22nd, 2014 at 8:11 pm

There are some inconsistencies here that really confuse me. You have a comment that says: // 0 is open, 1 is wall

But if you look at https://github.com/bgrins/javascript-astar you have another comment that says: // Weight can easily be added by increasing the values within the graph, and where 0 is infinite (a wall)

Though it may be obvious to you, I wish you’d explicitly spell out the syntax to pass into new Graph. Specifically, where is node (0,0)?

Brian Says:

February 23rd, 2014 at 2:08 pm

Thanks for the heads up. The 0/1 format changed since the original post and the current implementation to allow for different weights on the graph – I wrote more about this here: http://www.briangrinstead.com/blog/astar-graph-search-variable-costs. I’ve updated this post to be more clear.

The format is visually laid out in code the same as the graph would be laid out on the screen. So the first element in the first array would be node (0, 0), while the last element in the last array would be the bottom right node in the graph.

brenton Says:

May 17th, 2014 at 3:10 am

Thanks for this. The option of a weighted graph Woot!!! – you must have been reading my mind before I even thought of things. Now I can do things like work out the best path through mud or on land or near enemies or away from them or congested traffic or back roads

Salute.

Erik Walle Says:

March 8th, 2015 at 10:51 pm

Hey buddy, I found a bug in your code. You mark nodes dirty when they are explored, but around lines 59 and 74, you make other node changes:

59 start.h = heuristic(start, end);
75 currentNode.closed = true;

This may not show for a while, but eventually you’ll find a state where you cannot reuse the graph. My fix is just to mark those nodes dirty after those operations.
Took me a few hours to find that. :\

Pathfinding on tile mapElvarion Says:

April 7th, 2015 at 7:09 am

[…] A* processing. As a base for the A* and Graph classes I used very good implementation of it by Brian Grinstead. I do not like the Graph class implementation, actually, as far it uses huge amount of memory and […]

Eric Says:

February 17th, 2016 at 4:16 pm

This is a great project! I’ve been using it as a base for finding the best paths between coordinates of different heights, and the cost function was easy to play around with. It was also pretty easy to visualize your demo grid in 3D as a height map: https://www.youtube.com/watch?v=NaG9Ne3Y_do

Christoph D Says:

May 31st, 2016 at 11:35 am

@Erik Walle: took me also some hours :-)

currentNode.closed = true;
graph.markDirty(currentNode); // I added this line – now it works like charm

akbar rosidianto Says:

June 14th, 2016 at 8:13 am

how if i use that your works for non grid ?
i want to use it for my graph

Brian Grinstead