Path finding on any graph
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.
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.
Infinityif no such edge exists.
changeevent 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
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.