Implementation of A* Pathfinding in Javascript

I’ve been meaning to release my self-contained implementation of A* pathfinding for a while now, but it took me forever to get around to cleaning up the codebase and stuff. Anyways, once I did tidy it up, I decided to release it. Hopefully somebody out there will find it useful.

Here’s a demo of it in action:

Click anywhere to start a path, then click again to complete it. As you can see, my implementation is pretty quick. Although I haven’t measured its performance, strictly speaking, it can calculate a 850 or so unit long path with a barely visible delay (and I suspect even that delay is largely due to ‘s rendering performance–it really drops after you hit about nine million pixels, or 360,000 tiles). The algorithm uses a custom ordered array so it is pretty speedy.

Why use AStar.js?

If you’re interested in A* pathfinding, there are a few other pathfinding packages for Javascript. However, most of them require several Javascript libraries and/or complex inter-dependencies. To use my module, you only need to include one file–astar.js, and there are no external dependancies.

Getting started with AStar.js

Once you’ve included astar.js, you need to create an instance of the AStar pathfinding tool before you can start calculating your path. To create an instance of AStar, you need to provide your map data, the map’s height, the map’s width, and a function to tell whether or not a particular node is blocked.

Say your map data looks like this:

var map = [
[0, 1, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 0],
];

You’d initialize your AStar object like this:

astar = new AStar(map, 7, 7, function(data, x, y) {
return {
blocks: data[x][y]
}
});

The anonymous function you pass in takes three parameters; an inside reference to the data you passed in previously, the node’s x coordinate, and the node’s y coordinate. All it needs to return is an object with a boolean property, blocks, indicating whether or not the node in question is walkable. I may end up extending it to take values that let you determine the terrain cost of each node, but for now either a node is blocks movement or it doesn’t. In the case of the example, a “0” indicates unwalkable terrain and a “1” indicates walkable terrain. That’s why, in this example,  just returning the value at the specified node works.

Once you’ve initialized the AStar module, all it takes is a single line of code to get a path:

var path = astar.path(start_x, start_y, end_x, end_y);

AStar.path() returns an array containing the nodes found for the path specified, containing the starting and ending points. Each node is represented as an object with x and y values.

Demos and downloading AStar.js

You can find the link to the demo in the article here. I also put up a pathfinding stress test for fun; turns out that calculating an ~850 node long path takes about 200 ms (be warned, the linked page may take a while to load).

You can download AStar.js in an uncompressed format here (there’s also a minified version available). I hope somebody finds this helpful, and as always, be sure to let me know if I made any typos or errors in this article! (don’t forget to subscribe to my RSS feed, too)

View Source

8 thoughts on “Implementation of A* Pathfinding in Javascript”

    1. admin says:

      Hey, I’ve looked at ROT.js before and while it isn’t exactly my cup of tea (I prefer to work from scratch or my own existing codebase), it seems really useful. I see you have all the basic stuff needed to set up a pretty nice RL in Javascript, and I like the way you do everything by callbacks. Nice work! I’ll have to write an article on it at some point.

  1. Robert says:

    Haha holy s*** @ the demo. When I first started html5 I looked to see if there was an Astar pathfinding library to use, of course there were quite a few to choose from. I decided I’d use http://buildnewgames.com/astar/ when I got to it but your demo looks too awesome to pass by =]. I’ll definitely be using it, thanks!I came here from your stackoverflow page. You helped me yesterday with a question about massive amounts of variables. I ended up reading a lot into it before starting and was wondering if by any chance you’d be willing to look over it quick and let me know what you think? I also had a question about it too if you wouldn’t mind. Anyway if you are interested feel free to email me, thanks for all your help

    1. admin says:

      Thank you. I’ve always had an interest in A* pathfinding and have actually written a few different versions of it. This is my best so far, I think. Hopefully it’ll help. :]Oh, yeah, that was an interesting question. I was thinking about it today, and almost ended up writing a post on the subject. I still might! Anyways, I’ll shoot you an email when I get the chance. Good luck!

  2. Kyle Newsome says:

    Hey, thanks for making this, it was a huge help to me. I actually needed a Python version of A* and wasn’t satisfied with what appeared to be available so I ended up converting your JS code entirely into python and it works like a charm.I’d be happy to share and credit you somewhere, though I’m not sure where is best. I’d paste it right here but don’t wanna mess with the comments flow.

    Cheers@kylnew

    1. admin says:

      Awesome! Glad it proved to be of use. :) I don’t know where you could stick it… maybe a Gist? (gist.github.com)Elliot@unosoid

  3. Muzboz says:

    Awesome, awesome, awesome. :)

    1. admin says:

      Thanks! :)