l1-path-finder is a fast path planner for grids

GitHub Install Usage Theory Benchmarks References

Install

You can install l1-path-finder using

:

> npm install l1-path-finder

It works great with

!

Usage

Given a binary ndarray encoding a grid, calling l1-path-finder constructs a data structure for shortest path queries.

You can then query the planner by calling .search(), which computes the shortest path between a pair of points. That's it!

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)

Theory

l1-path-finder is based on sound computer science:

Instead of searching cell-by-cell, l1-path-finder preprocesses the grid to extract a visibility graph.
Extra vertices are added to reduce the number of edges from O(n²) to O(n √ log(n)). [1]
Preprocessing is fast, taking at most O(n log(n)) time.
Searching is done using A^* with landmarks, which runs in O(n log(n)^3/2) in the worst case. [2]
The visit queue is implemented using a pairing heap, which gives constant time insertion and fast updates. [3]

Click to interact

Left click to place blocks
Right click to set path
Purple lines = visibility graph
Yellow circle = landmark
Teal circle = corner point
Purple circle = Steiner point
Visited nodes are colored by distance to goal

Benchmarks

l1-path-finder is also extremely fast in practice.

On the grid path planning challenge [4] data set, it outperforms all other JavaScript path planning libraries by orders of magnitude:

The JavaScript implementation of l1-path-finder is even competitive with state of the art native C++ codes.

The following chart is a comparison to the Dan Harabor's implementation of jump point search [5]:

To see for yourself, you can run a limited interactive benchmark right in your browser:

BENCHMARK

References

K. Clarkson, S. Kapoor, P. Vaidya. (1987) "Rectilinear shortest paths through polygonal obstacles in O(n log²(n)) time" Proceedings of the third annual Symposium on Computational Geometry (SoCG).
A. Goldberg, H. Kaplan, R. Werneck. (2007) "Better landmarks within reach" Lecture notes in computer science, Volume 4525.
M. Fredman, R. Sedgewick, D. Sleator, R. Tarjan. (1986) "The pairing heap: A new form of self-adjusting heap" Algorithmica 1
N. Sturtevant. (2012) "Benchmarks for grid-based path finding" Transactions on Computational Intelligence and AI in Games
D. Harabor, A. Grastein. (2011) "Online graph pruning for pathfinding on grid maps" In Proceedings of the 25th National Conference on Artificial Intelligence (AAAI).
A. Patel. (2015) "Amit Patel's path finding notes"
0fps blog post (COMING SOON)

Acknowledgements

Thanks to Amit Patel for many useful conversations on path finding. Also, Hugh S. Kennedy, Matt DesLauriers and Elija Insua for feedback on design.