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
- 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:
addDistances(a, b)
equalsaddDistances(b, a)
addDistances(a, zeroDistance)
equalsa
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
- 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.