Generic graph search using A* or Dijkstra.
npm install wayfinderThis 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.
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.
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.
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.
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.
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 thekey option.
All three of these options are required.
Given a node, return its neighbours in an Array.
The node to find a path from.
Given a node, return true if this is a goal node. Otherwise,
return false.
These options can be omitted.
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.
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.
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".
This is only ever called on nodes which are neighbours.
By default, this always returns 1.
By default, distanceLess(a, b) === a < b;
By default, addDistances(a, b) === a + b;
By default, this is 0.
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.
Construct a non-blocking Wayfinder with the given options. Nothing
will be calculated until you call iterate().
This starts false, and becomes true when the search is finished,
whether or not a path was found.
The path that was found, or null if there is no path.
Do one iteration of calculations. Call this repeatedly until "finished"
is true.
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.