🗺 Fast path planning for 2D grids
Clone or download
Latest commit 4aa05fd May 18, 2016
Permalink
Failed to load latest commit information.
bench Fix easystar.js benchmarks May 18, 2016
demo fix up mouse interactions Apr 29, 2015
example add example Apr 28, 2015
img add logo Apr 29, 2015
lib remove logging Apr 29, 2015
test fix up bug with duplicate corners Apr 25, 2015
viz fix up benchmark page Apr 30, 2015
www added comparison to jps Apr 30, 2015
.gitignore . Apr 19, 2015
.npmignore add items to npm ignore Apr 29, 2015
LICENSE . Apr 19, 2015
README.md maybe less confusing way to write time complexity Apr 30, 2015
package.json Fix easystar.js benchmarks May 18, 2016

README.md

A fast path planner for grids.

Example

var ndarray = require('ndarray')
var createPlanner = require('l1-path-finder')


//Create a maze as an ndarray
var maze = ndarray([
  0, 1, 0, 0, 0, 0, 0,
  0, 1, 0, 1, 0, 0, 0,
  0, 1, 0, 1, 1, 1, 0,
  0, 1, 0, 1, 0, 0, 0,
  0, 1, 0, 1, 0, 0, 0,
  0, 1, 0, 1, 0, 0, 0,
  0, 1, 0, 1, 0, 1, 1,
  0, 0, 0, 1, 0, 0, 0,
], [8, 7])

//Create path planner
var planner = createPlanner(maze)

//Find path
var path = []
var dist = planner.search(0,0,  7,6,  path)

//Log output
console.log('path length=', dist)
console.log('path = ', path)

Output:

path length= 31
path =  [ 0, 0, 7, 0, 7, 2, 0, 2, 0, 4, 1, 4, 1, 6, 3, 6, 5, 6, 5, 4, 7, 4, 7, 6 ]

Install

This module works in any node-flavored CommonJS environment, including node.js, iojs and browserify. You can install it using the npm package manager with the following command:

npm i l1-path-finder

The input to the library is in the form of an ndarray. For more information on this data type, check out the SciJS project.

API

var createPlanner = require('l1-path-finder')

var planner = createPlanner(grid)

The default method from the package is a constructor which creates a path planner.

  • grid is a 2D ndarray. 0 or false-y values correspond to empty cells and non-zero or true-thy values correspond to impassable obstacles

Returns A new planner object which you can use to answer queries about the path.

Time Complexity O(grid.shape[0]*grid.shape[1] + n log(n)) where n is the number of concave corners in the grid.

Space Complexity O(n sqrt(log(n)))

var dist = planner.search(srcX, srcY, dstX, dstY[, path])

Executes a path search on the grid.

  • srcX, srcY are the coordinates of the start of the path (source)
  • dstX, dstY are the coordiantes of the end of the path (target)
  • path is an optional array which receives the result of the path

Returns The distance from the source to the target

Time Complexity Worst case O(n sqrt(log(n)³) ), but in practice much less usually

Benchmarks

l1-path-finder is probably the fastest JavaScript library for finding paths on uniform cost grids. Here is a chart showing some typical comparisons (log-scale):

You can try out some of the benchmarks in your browser here, or you can run them locally by cloning this repo. Data is taken from the grid path planning challenge benchmark.

It is also pretty competitive with C++ libraries for path searching. The following chart shows the performance of l1-path-finder compared to Warthog, which is a state of the art implementation of the popular "jump point search" algorithm:

Notes and references

  • The algorithm implemented in this module is based on the following result by Clarkson et al:
  • This data structure is asymptotically faster than naive grid based algorithms like Jump Point Search or simple A*/Dijkstra based searches.
  • All memory is preallocated. At run time, searches trigger no garbage collection or other memory allocations.
  • The heap data structure used in this implementation is a pairing heap based on the following paper:
  • Box stabbing queries are implemented using rank queries.
  • The graph search uses landmarks to speed up A*, based on the technique in the following paper:
  • For more information on A* searching, check out Amit Patel's pages

License

(c) 2015 Mikola Lysenko. MIT License