First demo of Ariane, a JS pathfinder

May 16, 2009  |  , ,

Here is the first demo of Ariane, my JavaScript pathfinding tool.

What’s a pathfinder?

Well, I’m currently making an awesome JavaScript game. In this game, the engine will have to handle the movements of dozens of characters on a map. Now, if I want these creatures to act in a realistic way, there is a bunch of thing I need to simulate to make them believable.

First, they should be able to think, or at least give the impression that they are thinking. This includes the ability to solve philosophical questions such as: should I run frantically to the player and try to eat his brain, or should I not? (spoiler: yes. zombies.)

But now that the decision has been taken, our creature needs to actually find a way to the player. This is trickier than it looks, and this is Ariane’s job, called pathfinding (another tool is under construction for the decision-making part).

The simplest way to solve this problem would be for our creature to move directly toward the player, and to try to go around any eventual obstacle. While this solution could be adequate for an undead, there are situations where a bit more intelligence is expected.

So how do we solve this problem?

We’re going to use what is called the A* algorithm (pronounced “A star”). This magic formula allows us to find a shortest path from point A to point B on our map, avoiding any obstacles in the way.

Below is a cool animation from Wikipedia on this subject.
a* algorithm

Ok, I didn’t understand it either.

More seriously, Ariane uses an efficient implementation of this algorithm to quickly compute any reasonably-long path. I’ve also implemented two useful features: parallel processing (multiple characters can “think” at the same time) and path priorities (eg to make enemies on the player field of view more reactive than the one far away).

What am I seeing in the demo?

Here we ask Ariane to compute two paths: from the top left to bottom right (in blue), and from the bottom left to the top right (in green). The points appearing on the map are the locations being analyzed.

The paths are avoidings both the red walls and the grey noise to simulate a life-like situation (the noise could represents eg trees in a forest).

The computation may seem slow, but the map displayed is a scaled down version of the actual game map. The idea is to find a path on a smaller map – which is faster, and then to scale it up to the real size. The scale being x15, the game map in the demo would be 6000×6000 px.

More info on pathfinding

If you’re interested in learning more about pathfinding, here are the two main resources from which I’ve learned everything: this article from is an excellent introduction, and Amit’s A* pages are also a very good reference, although more advanced.


  1. “While this solution could be adequate for an undead”

    Lol, that’s pretty much what I did in Z-War. (Made it ages ago, my coding practices and use of canvas have improved since then :P )

    Also I might use some of this code in Deepcommand if I ever get back to working on it :)

  2. Wow Z-war is really cool :D I don’t understand why it didn’t get more attention?

    Maybe you should make a page where the map is started at once, without sounds, and at a lot easier level, then try to submit it again to Digg/Reddit/etc… (maybe even at Chrome Experiments?)

    I mean, most people just want to try the actual game, maybe the current start page is a bit too confusing?

    Also where did you left your work on DeepCommand? I’d be curious to see how it looks.
    Especially the multiplayer part, are you planning on using Comet?
    I’d really like to implement a coop mode on my game but haven’t found any good solution yet.

  3. Yeah good idea – I’ll give that a try :)

    And I’m using binary sockets via Flash which might be considered cheating but meh :P

    I had it at the stage where multiple game lobbies could be created, chat channels etc. and synchronised building and resources ingame. The next big step was pathfinding and vehicle movement, which is where I sort of gave up :P

    I’ll stick up some screenshots later if I can remember how to fire up the server daemon :)

  4. Love the demo :)

    Have you considered increasing the cost of squares the closer they are to walls?

Leave a Reply