Basic Usage

Basic Usage

Whenever you use Crow, you'll always be performing three steps: creating a GridNode or ConnectedNode subclass, populating a Graph instance, and finally invoking an algorithm. Let's cover these in the most basic way possible.

Creating a GridNode subclass

crow.GridNode is the Javascript class you'll need to extend with your own node class in order for your nodes to be recognized as nodes. It contains logic that you will usually need to override in order for the class to work. Let's see how this is done:

	// Here we have the constructor -- you can make it whatever you want, actually, so long as 
	// you can get an x- and y-coordinate out of it later
	var MyNode = function(arr){
		crow.GridNode.apply(this, arguments);
	};
	
	// Now we're extending the crow.GridNode class.  This will be the archetype of all MyNodes that are created.
	MyNode.prototype = new crow.GridNode();
	
	////////////////////////////////////////////////////////////////////////////
	/// The rest of this example describes OPTIONAL code that you can write! ///
	/// Your node will work just fine without them!                          ///
	////////////////////////////////////////////////////////////////////////////
	
	// These two accessors are how we get the position of the node.
	// By default, getX and getY return the "x" and "y" property of the node.
	// If these properties don't exist, you'll need to override these methods.
	// The implementation you see below is the same as the default in crow.GridNode.
	MyNode.prototype.getX = function(){ return this.x; };
	MyNode.prototype.getY = function(){ return this.y; };
	
	// This defines the distance algorithm as the Manhattan distance algorithm (which is simply x2 - x1 + y2 - y1).
	// You can also choose `pythagoras` in place of `manhattan`, to use pythagorean theorem instead.
	// The default distanceAlgorithm is Manhattan, so I could have left this line out.
	MyNode.prototype.distanceAlgorithm = crow.GraphUtil.distance.manhattan;

And that's it! That's one of the simplest node classes you can implement;

Not using a standard grid plane?

If you instead want to place nodes in "space" and connect them arbitrarily using fixed distances, you'll want to extend crow.ConnectedNode instead of crow.GridNode. The first argument to your constructor should be a unique identifier of the node instead of a position, and then you can call connectTo(otherNode, distance) on your node instance to join it to other nodes. Unless you implement distanceToGoal, however, only Dijkstra's will work for you.

Populating an instance of the Graph class

Now that we have our node, we must make a Graph and add the nodes to it.

	// Instantiating a graph...
	var graph = new crow.Graph();
	
	// Adding some nodes to it...
	graph.addNode(new MyNode([0, 0]));
	graph.addNode(new MyNode([1, 0]));
	graph.addNode(new MyNode([1, 1]));

And you're done!

Tip: Adding nodes manually gets old fast. So there's a helper that you can use:

	// Here we have a one-dimensional array with strings in each slot.  What character is in each
	// slot (X vs -) has no special meaning except for what we define in the callback following this array.
	// The only requirement is that this array be a one-dimensional array of strings.  It's
	// also recommended that each string have the same length, but this is not strictly required.
	var graphArray = [
		"XX",
		"-X"
	];
	
	// crow.Graph.fromArray iterates over every element of the provided graph array and passes it into
	// the callback in the form of an x-coordinate of the point, the y-coordinate, and the one-character
	// string at that point.
	var graph = crow.Graph.fromArray(graphArray, function(xCoordinate, yCoordinate, valueAtCoordinate){
		if(valueAtCoordinate == "X"){
			return new MyNode([xCoordinate, yCoordinate]);
		}
	});
	
	// If you're still unclear how this works, note that the callback gets called with the following arguments:
	// callback(0, 0, "X") // returns new MyNode([0, 0]); which is added to the graph
	// callback(1, 0, "X") // returns new MyNode([1, 0]); which is added to the graph
	// callback(0, 1, "-") // returns a falsey value (undefined), so the graph isn't modified
	// callback(1, 1, "X") // returns new MyNode([1, 1]); which is added to the graph

Calling the algorithm

Finally you have to query the graph to get a result! There are many ways to do this, of course, but here are a couple:

	// Shortest path from 0,0 to 1,1 using Dijkstra's:
	var path = graph.findGoal({start: graph.getNode(0, 0), goal: graph.getNode(1, 1)});
	
	// If you'd like to use the usually-better A*:
	path = graph.findGoal({start: graph.getNode(0, 0), goal: graph.getNode(1, 1), algorithm: "a*"});
        // when you're done with the path, be sure to bake it, otherwise whenever you invalidate the graph, this path will always signaled to regenerate...
        path.bake();
	
	// If you don't want shortest path, but rather a breadth-first search from a starting point looking for nodes with a trait:
	var bfsNodes = graph.getNodes({start: graph.getNode(0, 0), filter: function(node){
			return node.x == node.y;
		}
	});
	// bfsNodes will now contain nodes reachable from 0,0 that are along the diagonal, i.e. [0,0], [1,1], [2,2], etc.

The path object returned by findGoal is an instance of crow.algorithm.Path has many useful properties, including nodes for the nodes that were actually found (including start and goal), found for whether the algorithm was actually successful, and length for the total distance from start to goal (which can be different from the number of nodes, since distances between adjacent nodes isn't necessarily 0).

Conclusion

Hopefully this is enough to get you started. When you find yourself wanting more, check out some of the other articles!