occasionally useful ruby, ubuntu, etc

Announcing Crow, a path-finding library in Javascript

Over the past few weeks I've been building out a clean and fast path-finding library in Javascript with a particular gaming site in mind, and I'm pretty happy with where it's at right now. If you're interested in at least one of: API design, Google Closure library, Google Closure compiler, or QUnit, then hit the jump for more. In the future, I'll cover Javascript (and object-oriented patterns), path-finding (breadth-first search, Dijkstra's algorithm, and A*), rake, games, and the embedded Sinatra+Bundler.

API Design

I wanted a way that users could quickly and easily calculate the shortest path through a graph with minimum complexity and code. To that end, I came up with the following design. First thing is you create a node class that extends crow.BaseNode and implements getX() and getY() (for positioning); and distanceAlgorithm (for calculating distance between adjacent nodes). I try to make this as obvious as possible -- if any of these requirements aren't met, an exception is thrown instructing the developer to override these "abstract" methods. Two possible distanceAlgorithms are given out of the box, too -- a Pythagoras version and a Manhattan variant.

After this, the developer instantiates a crow.Graph object, adds instances of their node that represent the walkable path, and then run findGoal with a start point and an end point. Done! Three components: writing the node subclass, initializing a graph instance, and then querying it.

This design also affords flexibility to you. You can instantiate nodes in whatever way you want with whatever properties you want, so long as it implements the required methods. Besides distanceAlgorithm (which just returns a scalar given a dx and a dy), you can choose to implement distanceTo instead, which gives you full control over calculating the distance between two nodes. With this, you can implement a multitude of things, from varyingly difficult terrain (going from a Grass node to a Grass node has a different distance than a Grass node to a Sand node, perhaps, if the sand slows the unit down) to impassible terrain (distance to a Wall node is Infinity, for example, which will block the path). Lastly, you have full control over which algorithm actually runs (force dijkstra's with a well-placed algoritm:"dijkstra"), or you can define your own. I also have a suite of tests, some of which are interactive, to demonstrate what's possible with the API.

I also plan on implementing some more complicated algorithms you may not have heard of, including Lifelong Planning A* (pdf link) and D* Lite (pdf link). However, both are a fair bit more complicated than A*, and whether I implement them hinges primarily on whether I can understand linked papers, and secondarily on whether I think they're an important tool in the pathfinder toolbox.

Google Closure

Initially, I only needed Google Closure for a priority queue implementation for A*, but soon after I decided to use it to manage all my dependencies for me, and I don't regret that decision in the slightest. The script that sorts out dependencies is a little slow, but otherwise it does a great job. I'm also using the library's event system, which is a little kludgier when you don't need/want references to DOM elements, but the (deprecated?) event object I'm using actually works pretty well.

Lastly, I'm using the Advanced Compilations mode of the compiler to generate the final output, which runs about 20% faster in Chrome than non-minified. It's a little finicky mainly in that you must label your constructors or it issues warnings, and any interfaces you want to expose to non-Closure compiled code have to be specially treated. Still, forcing you to document your code isn't the worst thing in the world.

QUnit

QUnit is, of course, still fun and easy for testing Javascript (with a little help from jQuery). However, there are two special notes I'd like to point out.

Dynamically generating tests

Actually generating tests is a little tricky, especially if you're inside a for loop. This is because of the way closures work and the fact that executing QUnit's test() doesn't immediately execute the test. If your iterator index is variable i, for instance, and you call test inside a for loop and use i, then by the time the test actually executes, they'll all have the same i value! That's no good at all. Instead, I did something like this:

Basically, create a method, and then pass the current iterated object into that method. The method doesn't have to be defined in the middle of your for loop, but if you want access to other variables in that same scope, it doesn't hurt (too much).

Custom compare methods

Unfortunately, creating custom compare methods doesn't seem to be a well-supported use case of QUnit. For example, if I want to compare every element of array a and array b, and make sure elements in the same location in each array have matching values for .getX() and .getY(), I basically have to iterate over every element and call equals on every coordinate pair. This isn't terrible, but it clutters up the tests and provides misleading numbers. Before too long, some of my test cases have dozens of tests inside them! I realize I could try to mimic what equals (or same) does, but it accesses private APIs. I'd like it if there was simply a way to hook into the equals method to provide some custom logic easily, or perhaps make my own equalsNodeArray method that used public APIs, but I don't think QUnit really supports that yet. I'll just have to live with the inflated test count numbers, for now.

The Code

You thought I forgot the code, didn't you? Well...I did. So here you go: github repo. If you just want to check out the cool interactive test suite, head over to my sinatra port.

Other topics

That's enough for today! In the next post, I'll dig into some of the Ruby aspects behind the project (rake and embedded Sinatra).