lowlighter/astar is a JavaScript project with 33 stars. πΊοΈ A JavaScript implementation of A* algorithm.
Snapshot summary built from the project's own GitHub metadata β there's no written TopGit review yet. The page will update automatically when a full review is published.
WHY NO REVIEW YET
TopGit writes full reviews for the most-starred, most-requested repositories. This page is a snapshot until then β see the READ ME tab for the original README in full.
If you're using a custom data structure, you'll need to convert it into a Graph struture. Don't worry, it's quite easy.
Assume your datas look like this :
let a = {id:"pallet-town", gym:null}
let b = {id:"viridian-city", gym:"Earth badge"}
let c = {id:"cinnabar-island", gym:"Volcano badge"}
First, start by creating a new Graph and some nodes :
let graph = new Astar.Graph()
a = new Astar.Node(a.id, a) //Datas are synchronized :
b = new Astar.Node(b.id, b) //b.gym = "Earth badge"
c = new Astar.Node(c.id, c) //c.gym = "Volcano badge"
Then you'll need to override Graph.id(id) method because graphs instances only use numbers as identifiers.
//Override graph.id method
graph.id = function (name) {
return ["pallet-town", "viridian-city", "cinnabar-island"].indexOf(name)
}
//This way, graph.id will be compatible with any id type
graph.id("pallet-town") //Return 0
Finally link different nodes :
graph.edge(a, b, 1, 2) //Going from a to b cost 1 whereas going from b to a cost 2
graph.edge(a, c, 1, null) //Going from a to b cost 1 whereas it's not possible to go from b to a
Create a graph from an array structure
For conveniency, it's possible to create directly a graph from an array structure without specific order :
YX Order
let map = [
[0, 1, 0],
[0, 1, 1],
[0, 0, 0],
]
XY Order
let map = []
for (let x = 0; x < 3; x++) { map[x] = []
for (let y = 0; y < 3; y++) {
map[x][y] = Math.random() > 0.5
} }
Create a configuration
To create a new Configuration, just type the following code :
let astar = new Astar.Configuration(map)
If you want to specify options, you can pass a second argument to instanciation :
let graph = new Astar.Configuration(map, {
order:"yx", //Access order for 2D Array
torus:false, //Tell if 2D Array is wrapped on itself
diagonals:true, //Tell if diagonals moves are allowed (2D Array)
cutting:false, //Tell if diagonals moves between two blocking squares are allowed (2D Array)
heuristic:"euclidian", //Heuristic function name
cost(a, b) { return b == 1 ? null : 1 }, //Cost function definition
thread:"./bin/lowlight.astar.min.js", //If script's source is specified, multi-threading will be enabled
})
If you want to reuse same map but with different option, just create instance with multiple options objects.
let graph = new Astar.Configuration(map, layer1, layer2, layer3)
Cost function
Cost function takes will be called with two Node instances : source node and destination node.
It must returns a number or null.
While it's possible to use Infinity and negatives values, it isn't advised because it can leads to suspicious behaviours.
Most of the time, you'll only need the second argument, but you may want to use the first one to detect transitions.
For example, going from plains to mountains may cost 2 whereas going from mountains to mountains may cost only 1.
let cost = function(a, b) {
if (b === "sea") { return null }
if (b === "plains") { return 1 }
if ((a === "mountains")&&(b === "mountains")) { return 1 }
if ((a === "plains")&&(b === "mountains")) { return 2 }
return null
}
Heuristic function
By default, only two-dimensional heuristic functions are defined.
The first two arguments are source node and destination node (remember that you can store anything in a node instance).
The third one is optional and may be specified as heuristicOptions in astar.path method.
Computing a path
To compute a path, you'll just need to pass a start node and a goal node.
let path = astar.path({x:0, y:0}, {x:2, y:2})
If multi-threading option is enabled, you'll be need to specify a callback function.
Note that if you're using a multiple layers graph, you may specify the layer you want to use, the default one being 0.
astar.path({x:0, y:0}, {x:2, y:2}, {layer:1})
Using Jump Search Point (JPS)
A* JPS is pruning rules to avoid node exploration expansion.
This means that it's generally much faster than classic A*, however, it comes with a major drawback : movement costs must be uniform.
You may specify that you want to use jps in options when computing a path :
astar.path({x:0, y:0}, {x:2, y:2}, {jps:true})
Nota Bene : This only works for two-dimensionals grid.
Using static graphs
If your graph is static, you can set the static option to prevent useless computations.
Before computing a path, it'll do a connectivity test to check if a path exists before computing one.
astar.path({x:0, y:0}, {x:2, y:2}, {static:true})
You can also use it on dynamics graphs, but don't forget to rebuild connectivity by calling graph.connectivity() method each time you edit it.
Project content
/bin
Live and dev scrripts files
/src
Source files
/demo
Demo and codes examples
/docs
Documentation
Rebuild project and expanding the library
You'll need to run the following command the first time to install dependencies.
npm install
Then to rebuild project, just run the following command :
npm run build
This will update /bin files with included /src files.
Although package.json (which contains "source" and "output" paths) are preconfigured, you may need to reconfigure them if you're planning to expand this library.
To include a file just use the following syntax in the "source" file :
/* #include <path/to/file.js> */
File minification is performed with Babel minify.
Documentation is generated with JSDoc 3.
Although package.json (which contains "jsdoc_source", "jsdoc_output", "jsdoc_config" and "jsdoc_readme") and docs/categories.json are preconfigured, you may need to reconfigure them if you're planning to expand this library.
The most recent commit recorded on lowlighter/astar was 5.3 years ago, based on the GitHub push timestamp. The repository has 3 forks β one of the better signals of community interest.
How many stars does lowlighter/astar have?
lowlighter/astar has 33 GitHub stars β refresh the page for the live number, or check github.com/lowlighter/astar. TopGit mirrors GitHub's count but does not claim minute-by-minute accuracy.
What language is lowlighter/astar written in?
lowlighter/astar is written primarily in JavaScript. GitHub's language field is based on the largest share of bytes in the default branch.
What topics is lowlighter/astar associated with?
GitHub's repository topics for lowlighter/astar: "astar", "astar-algorithm", "astar-pathfinding", "pathfinding", "pathfinding-algorithm", "pathfinding-library". TopGit's editorial category is open-source.
Where do I read more about lowlighter/astar?
This TopGit page is a snapshot β the READ ME tab shows the project's own README content (links stripped, images preserved). The GitHub repository at github.com/lowlighter/astar is the definitive source.
Read full README in the tab above.
Still deciding about astar?
One click hands the question to an AI along with this page β see what it says about astar.