a-star-search

A special case of best-first graph search that uses heuristics to improve speed. Define your 2D grid then add any blocked coordinates to the environment that must be avoided when generating the shortest path. Written in CoffeeScript.

Stats

StarsIssuesVersionUpdatedCreatedSize
a-star-search
510.1.134 years ago7 years agoMinified + gzip package size for a-star-search in KB

Readme

A* Search

A special case of best-first graph search that uses heuristics to improve speed. Define your 2D grid then add any blocked coordinates to the environment that must be avoided when generating the shortest path. Written in CoffeeScript.

Usage

Add a-star-search to your package.json and run $ npm install

Require aStar in your app and define the parameters of your 2D grid:

aStar = require 'a-star-search'
startLocation = {xAxis: 1, yAxis: 1}
destination = {xAxis: 4, yAxis: 1}
environment = {blockedLocations: [{xAxis: 2, yAxis: 1}, {xAxis: 2, yAxis: 2}, {xAxis: 2, yAxis: 3}], worldSize: {xAxis: 10, yAxis: 10}}

Call the run method passing in the parameters defined above:

aStar.run(startLocation, destination, environment)

This returns the following shortest path:

[
 {xAxis: 1, yAxis: 1, gCost: 0, hCost: 30, fCost: 30, parent: {xAxis: 1, yAxis: 1}},
 {xAxis: 2, yAxis: 0, gCost: 14, hCost: 30, fCost: 44, parent: {xAxis: 1, yAxis: 1}},
 {xAxis: 3, yAxis: 1, gCost: 28, hCost: 10, fCost: 38, parent: {xAxis: 2, yAxis: 0}},
 {xAxis: 4, yAxis: 1, gCost: 38, hCost: 0, fCost: 38, parent: {xAxis: 3, yAxis: 1}}
]

Visual representation:

y
10 . . . . . . . . . . .
 9 . . . . . . . . . . .
 8 . . . . . . . . . . .
 7 . . . . . . . . . . .
 6 . . . . . . . . . . .
 5 . . . . . . . . . . .
 4 . . . . . . . . . . .
 3 . . b . . . . . . . .
 2 . . b . . . . . . . .
 1 . x b x X . . . . . .
 0 . . x . . . . . . . .
   0 1 2 3 4 5 6 7 8 9 10 x

Running the test suite

$ npm install
$ NODE_ENV=development jasmine-node spec/aStarSpec.js
References

http://www.policyalmanac.org/games/aStarTutorial.htm

http://en.wikipedia.org/wiki/A*

http://en.wikipedia.org/wiki/List_of_algorithms

If you find any bugs or have a feature request, please open an issue on github!

The npm package download data comes from npm's download counts api and package details come from npms.io.