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.
Last updated 3 years ago by hackjoy .
MIT · Repository · Bugs · Original npm · Tarball · package.json
$ cnpm install a-star-search 
SYNC missed versions from official npm registry.

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

Current Tags

  • 0.1.13                                ...           latest (3 years ago)

12 Versions

  • 0.1.13                                ...           3 years ago
  • 0.1.12                                ...           5 years ago
  • 0.1.11                                ...           6 years ago
  • 0.1.10                                ...           6 years ago
  • 0.1.9                                ...           6 years ago
  • 0.1.8                                ...           6 years ago
  • 0.1.6                                ...           6 years ago
  • 0.1.4                                ...           6 years ago
  • 0.1.3                                ...           6 years ago
  • 0.1.2                                ...           6 years ago
  • 0.1.1                                ...           6 years ago
  • 0.1.0                                ...           6 years ago
Maintainers (1)
Downloads
Today 0
This Week 0
This Month 0
Last Day 0
Last Week 0
Last Month 1
Dependencies (1)
Dev Dependencies (1)
Dependents (0)
None

Copyright 2014 - 2017 © taobao.org |