wayfinder v0.1.5

About

This is a library to find the shortest path between a starting node and any of a set of goal nodes within a graph.

It aims to be generic and applicable to a wide variety of problems. See the unit tests for inspiration.

What's a graph? I just want to write video games

A graph is a data structure. It consists of a set of nodes, and a set of edges connecting them. Your game world can almost certainly be described as a graph; see the "maze" examples in the unit tests to see how to use Wayfinder on a simple 2D maze.

Basic Usage

var Wayfinder = require('wayfinder');

// Blocking API
var path = Wayfinder.findPath(options);

// Nonblocking API
var wayfinder = new Wayfinder(options);
while (!wayfinder.finished)
    wayfinder.iterate();
var path = wayfinder.path;

For more in-depth examples, see the unit tests.

Path Type

The return type of Wayfinder.findPath and the type of wayfinder.path is either null, if no path could be found, or an Array of Nodes representing the path. The first node will always be the start node, and the last node will be the goal node that was found. The nodes in between will be ordered along the path from start to goal.

Options

The Wayfinder constructor and the findPath function both take as their only argument an options object. This object is used to configure the behaviour of the pathfinder.

The options object should be an ordinary JavaScript object, with option names as keys. For example:

Wayfinder.findPath({
    start: myStartNode,
    neighbours: function (node) { ... },
    goal: function (node) { ... }
});

The possible options are documented below.

Graph Options

The first three options describe your graph. The search will start at the start node, and find the shortest path to a goal node, which means any node where goal(node) == true. The path is found by examining the start node's neighbours, then the neighbours of each of those nodes, and so on until a goal node is reached.

The Node type as referenced in these definitions can be anything you like. Wayfinder doesn't make any assumptions about what it can or can't do with your nodes, and it will never modify them. However, it does use the strict equality operator (===) to determine whether two nodes are the same node or not. To change this, override the key option.

All three of these options are required.

neighbours

• Type: Function(Node) → Array of Node

Given a node, return its neighbours in an Array.

start

• Type: Node

The node to find a path from.

goal

• Type: Function(Node) → Boolean

Given a node, return true if this is a goal node. Otherwise, return false.

Optimization Options

These options can be omitted.

heuristic

• Type: Function(Node) → Distance

This should return an estimate for the distance between this node and the nearest goal node.

By default, this always returns zeroDistance, which by default is 0.

Providing a heuristic function means you are using the A* algorithm. If you omit it, you are using Dijkstra's algorithm.

If you do provide a heuristic, then as long as the heuristic always underestimates true distance to the goal, the algorithm will always find the shortest path to the goal. (Here, "underestimate" means that heuristic(x) <= trueDistance(x)).

For example, if you are searching a physical space, a heuristic function returning the straight-line distance to the goal will always be an underestimate. The actual distance may be longer (if there are obstacles to be avoided) but cannot logically be shorter.

If the heuristic sometimes overestimates the true distance, you will not necessarily find the shortest path, but heuristic functions returning higher values make the algorithm run faster, so if you value speed more than correctness, you may want to overestimate.

See Wikipedia for more information about the heuristic function.

key

• Type: Function(Node) → *

Wayfinder considers two nodes to be the same node if key(node1) === key(node2).

By default, key(node) === node.

If your neighbours function constructs new JavaScript objects, you might want to implement key unless you want a potentially infinite graph.

Distance Options

The next group of options concerns distances between nodes. All of these options can be omitted.

It's common to need to override "distance". The other distance options can usually be left alone unless you want to use a type other than JavaScript's Number to measure distances.

If you do decide to override the distance arithmetic functions, be aware that Wayfinder expects them to follow the following invariants:

1. addDistances(a, b) equals addDistances(b, a)
2. addDistances(a, zeroDistance) equals a
3. distanceLess(a, b) → !distanceLess(b, a)
4. distanceLess(a, b), distanceLess(b, c) → distanceLess(a, c)

(where a equals b means !distanceLess(a, b) && !distanceLess(b, a)).

Some authors refer to "distance" as "cost".

distance

• Type: Function(Node, Node) → Distance

This is only ever called on nodes which are neighbours.

By default, this always returns 1.

distanceLess

• Type: Function(Distance, Distance) → Boolean

By default, distanceLess(a, b) === a < b;

addDistances

• Type: Function(Distance, Distance) → Distance

By default, addDistances(a, b) === a + b;

zeroDistance

• Type: Distance

By default, this is 0.

distanceIsInfinite

• Type: Function(Distance) → Boolean

By default, only the constant Infinity maps to a true value here.

If the distance between a node and the start node is infinite, Wayfinder will stop looking for paths through that node.

If you return an infinite distance from the distance(a, b) function, then a and b will be treated as if they weren't neighbours at all.

API Reference

new Wayfinder(Options)

Construct a non-blocking Wayfinder with the given options. Nothing will be calculated until you call iterate().

Wayfinder#finished :: Boolean

This starts false, and becomes true when the search is finished, whether or not a path was found.

Wayfinder#path :: Path or null

The path that was found, or null if there is no path.

Wayfinder.prototype.iterate()

Do one iteration of calculations. Call this repeatedly until "finished" is true.

Wayfinder.findPath(Options) → Path or null

Find a path synchronously.

This won't return until a path is found or it is proven that one doesn't exist, so if you use this function on an infinite graph, you could lock up your JavaScript interpreter.