Path finding on any graph


Explor is a general-purpose, asynchronous, dynamic path planning library for JavaScript, providing a high-level API for planning and walking paths on any graph. Special attention has been given to applications in Artificial Intelligence and Networking.

The release of Explor v1.0.0 is planned for August 2015.

A demo app is included at demo/index.html. It uses Explor to build a bot that can find its way around obstacles to reach a goal. The demo can be run in "static" and "dynamic" modes. In static mode, the bot knows ahead of time the location of every obstacle, and determines the shortest path to the goal. In dynamic mode, the bot has no knowledge of the obstacles and dynamically readjusts its path as it learns of the environment. At the same time, in both modes, the demo animates the path finding calculations to demonstrate the benefits of various heuristics and algorithms.

I would love input and feedback on API design. If you are interested in this library, how would you like to use it?

Also, I'm looking for a documentation generator that outputs like the Lo-Dash docs. Does such a generator exist in pure JS?

The primary concepts of Explor are those of Graphs, Planners, and Explorers.

Graphs are exactly what you expect: collections of nodes connected by edges of possibly varying length. Graphs can be used to intuitively represent spatial information and data sets with complex relationships. Planners are tools used to plan paths through graphs. Explor includes planners implementing A* and D* Lite to find the shortest path between two nodes, and it is easy to write planners for other needs. Explorers are the primary actors on graphs. They walk the graph, using Planners to choose paths and can intelligently readjust if the graph changes, even in the middle of a walk. Thus Explorers can be used as smarter iterators for your graph, or as tools for implementing AIs (think robots in a maze).

Calculating paths can be an expensive task. To avoid blocking, Explor executes planning asynchronously. These methods return Promises, objects that represent the eventual result of the asynchronous calculation. All promises in Explor follow the Promises/A+ spec. For more details on Promises, checkout the official spec and this awesome tutorial from HTML5 Rocks.

Explorers are the main interface of Explor, using Planners to walk Graphs.

  • new Explorer(graph, start, goal, [planner, [options]])
    • Constructs an explorer that walks a graph from start to goal.
  • Explorer.prototype.step() → Promise
    • Moves the explorer to the next node on the path.
    • Returns a promise resolving to the path after the step.
  • Explorer.prototype.walk([callback]) → Promise
    • Walks the explorer to the goal.
    • Take a function to be applied to each node during the walk.
    • Returns a promise that resolves at the end of the walk.

Explor works with any graph implementing this small interface. There is no imposed interface on the nodes of a graph, giving implementers the freedom to define graphs in ways that are meaningful and optimized for their application.

Explor separates the concepts of keys and nodes: keys refer to nodes. Keys, like nodes, can take any form relevant to the graph, and any node may have multiple keys. The only restriction is that nodes be keys to themselves. This key-node dicotomy lets the graph implementer define a literal notation for keys that can be used throughout Explor.

  • graph.get(key) → Node
    • Returns the node for a given key. Since nodes can be any object, this method effectively normalizes a given key. All nodes MUST be keys to themselves. The mapping from keys to nodes is defined solely by this method.
  • graph.getSuccessors(node) → Array of Nodes
    • Gets all nodes reachable from node.
  • graph.getPredecessors(node) → Array of Nodes
    • Gets all nodes that can reach node.
  • graph.getEdge(from, to) → Number
    • Returns the length of the edge between two nodes, from and to.
    • Returns Infinity if no such edge exists.
  • graph.clone() → Graph
    • Returns a shallow clone of the graph.
  • Event: change
    • If the graph is dynamic, it must be an EventEmitter and emit a change event whenever is is updated.

Below is a list of included Graph implementations. See the wiki for details.

  • explor/graphs/graph - The canonical implementation. It lets you use any object for nodes.
  • explor/graphs/simple-plane - An infinite 8-connected graph, i.e. a plane, where nodes are either walkable or obstacles.

Planners compute paths through graphs between two nodes. Planners must inherit the base planner from explor/lib/planners/planner.

  • planner.plan(graph, start, goal) → Promise
    • Plans a path between two nodes.
    • Returns a promise for the list of nodes on the path from start to goal.

Below is a list of included Planner implementations. See the wiki for details.

  • explor/planners/astar - Finds the shortest path using the A* algorithm.
  • explor/planners/dstar - Finds the shortest path using the D* Lite algorithm, with good performance for frequently changing graphs.