npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

wayfinder

v0.1.5

Published

Generic graph search using A* or Dijkstra.

Downloads

1

Readme

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.