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

l1-path-finder

v1.0.0

Published

Fast shortest path finder for grids

Downloads

177

Readme

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 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 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.

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