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.

  1. 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.
  2. 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.

astar.js
graph.js
demo.js

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

Comments

  1. Stark Says:

    Brian, big thanks for your work!

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

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

  3. codergamer Says:

    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

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

    […] 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 […]

  5. felix Says:

    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;
    	}
  6. felix Says:

    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;
    	}
  7. Brian Says:

    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.

  8. fatmanx Says:

    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!

  9. NinjaSudo Says:

    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?

  10. rarecoins Says:

    Much Thanks!…

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

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

    […] 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 […]

  12. Neel Says:

    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?

  13. Brian Says:

    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!

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

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

  15. Kieve Chua Says:

    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 …

  16. Gabriel Says:

    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.

  17. Brian Says:

    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.

  18. Gabriel Says:

    Hi Brian

    Thanks for the quick reply and the clarification.

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

  19. PeteA Says:

    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!

  20. Brian Says:

    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.

  21. Rachel Says:

    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

  22. Dean H. Says:

    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?

  23. tieTYT Says:

    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)?

  24. Brian Says:

    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.

  25. brenton Says:

    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.

  26. Erik Walle Says:

    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. :\

  27. Pathfinding on tile mapElvarion Says:

    […] 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 […]

  28. Eric Says:

    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

  29. Christoph D Says:

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

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

  30. akbar rosidianto Says:

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

Comments are closed. Please contact me instead.