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 Node
s
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
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
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:
addDistances(a, b)
equals addDistances(b, a)
addDistances(a, zeroDistance)
equals a
distanceLess(a, b)
→ !distanceLess(b, a)
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
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.