occasionally useful ruby, ubuntu, etc

2Sep/108

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

Comments (8) Trackbacks (0)
  1. Hello,

    Can you give an example of a js file that uses crow algorithms WITH all needed references? Do I have to include the closure library somewhere? Is it possible to avoid it? If I don’t inlcude it I can’t a “goog undefined” error. Is there any way to just include the crow library without any compilations etc. (just as easy as including jquery with one line)?

    Thanks in advance
    Yannis

    • Hi Yannis,
      Thanks for checking out Crow! Crow shouldn’t need any other references outside of the given files — though, I should clarify a little. You can’t just download the source and use that straight, you have to either download the source and “build” it properly (using rake), or you have to download a version from the Downloads section of github and use one of the contained files. Though, the Downloads is moderately out of date right now…haven’t updated since Sept 7, and I’ve been working on it almost daily. So, if you hold off a bit I’ll upload a 0.4 version.

      Crow does depend on Google Closure, but those dependencies are self-contained inside the built files. If you’re using a built file, you should already have them. For an example, you can check out the online test suite. To get it to use the non-minified version of files just hit the Enable Debug Mode button near the bottom.

      Let me know if you have more issues. I appreciate any and all feedback! Yes, it is very “alpha”, but it should still be usable.

      Thanks,
      Max

  2. Hi Max,

    First some feedback: I was planning to use JGraphT (Java) in the server, for a small utility I’m working on that needs a graph and a shortest path algorithhm when I realized that there was no need to send my (possibly large) data in the server and get the shortest path back. I searched for a javascript library and I can tell you that yours looks like the best solution publicly available at the moment. I found many “graph” javascript libraries out there but almost all are about visualisations and not about math graphs and algorithms.
    (small suggestion, btw: add a simple visualisation in your library, you can even use one of the available libraries for it).

    Ok, added the reference to crow.mini.js to my project and it seems to be ok now. Maybe you should mention it explicitly in your basic usage page for the poor souls that are not yet familiar with the idea of compiled javascript.

    Thanks again, I’ll keep watching your page.
    Yannis

    • Thanks Yannis, I’m tracking your suggestion here: http://github.com/nanodeath/CrowLib/issues/issue/5.

      Can you elaborate on what you mean by visualization? In the online test suite I already have a couple examples, on the dunesAndDemise (click from the Watch A Test dropdown), fogOfWar (after you hit Design and Play), and perfGraph (after you hit Run One-Pass) pages. The former two require canvas to render, and the latter requires CSS3 content support. Though, as I enumerate those out, I realize they’re not completely obvious…still, was that what you meant, or did you mean something different?

      I’ll take a look around JGraphT, see if there are any feature misses in my library that I could add.

      Thanks!

      • I haven’t checked everything in the library yet, maybe you have it already.
        I was thinking of something like this (from http://www.graphdracula.net/):

        var renderer = new Graph.Renderer.Raphael(‘canvas’, g, 400, 300);
        renderer.draw();

        where g is a graph object.

        Is it possible to do somehing similar with crow?

        Have a nice day!

  3. Hey Max,
    Glad to have found your library. Do the already-built download files have support for ConnectedNode?

  4. Great work! Glad to see you’re working on this.


Leave a comment


No trackbacks yet.