A*
Typescript + Javascript Pathfinding algorithm library.
Install
npm install astarjs --save
Usage
; ; ;pathFindingManager.setWalkable0 // or this.pathFindingManager.setWalkable(0, 10, 11); .setEnd4 .setStart3; ;/*returns0: {col: 5, row: 4}1: {col: 5, row: 5}2: {col: 5, row: 6}3: {col: 5, row: 7}*/
or
; ; ;pathFindingManager.setWalkable0; // or this.pathFindingManager.setWalkable(0, 10, 11); pathFindingManager.setEnd;pathFindingManager.setStart; ;/*returns0: {col: 5, row: 4}1: {col: 5, row: 5}2: {col: 5, row: 6}3: {col: 5, row: 7}*/
Running the example
Run the following commands to run the example:
npm installnpm start
Options
From version 1.0.0 on, user can choose the algorithm Heuristic between MANHATTAN and DIAGONAL. See the differences and how to configure it bellow.
Heuristic
Heuristic.MANHATTAN
; ; ;pathFindingManager.setWalkable0 .setEnd .setStart;; /** bestPath = {col: 2, row: 6}, {col: 3, row: 6}, {col: 3, row: 5}, {col: 3, row: 4},* {col: 4, row: 4}, {col: 5, row: 4}, {col: 5, row: 3}, {col: 5, row: 2}]** E -> End* S -> Start* # -> Path* * [[0, 0, 2, 2, 2, 0],* [0, 0, 0, 0, 0, 0],* [0, 0, 0, 0, 0, E],* [0, 0, 0, 0, 0, #],* [0, 3, 0, #, #, #],* [1, 2, 0, #, 2, 0],* [2, 0, S, #, 0, 2]];* * */
Heuristic.DIAGONAL
DO NOT allow diagonal
; ; ;pathFindingManager.setWalkable0 .setEnd .setStart;; /** bestPath = [{col: 2, row: 6}, {col: 3, row: 5}, {col: 3, row: 4},* {col: 4, row: 3}, {col: 5, row: 2}]** E -> End* S -> Start* # -> Path* * [[0, 0, 2, 2, 2, 0],* [0, 0, 0, 0, 0, 0],* [0, 0, 0, 0, 0, E],* [0, 0, 0, 0, #, 0],* [0, 3, 0, #, 0, 0],* [1, 2, 0, #, 2, 0],* [2, 0, S, 0, 0, 2]];* * */
Allow diagonal
; ; ;pathFindingManager.setWalkable0 .setEnd .setStart;; /** bestPath = [{col: 2, row: 6}, {col: 3, row: 5}, {col: 4, row: 4},* {col: 5, row: 3}, {col: 5, row: 2}]** E -> End* S -> Start* # -> Path* * [[0, 0, 2, 2, 2, 0],* [0, 0, 0, 0, 0, 0],* [0, 0, 0, 0, 0, E],* [0, 0, 0, 0, 0, #],* [0, 3, 0, 0, #, 0],* [1, 2, 0, #, 2, 0],* [2, 0, S, 0, 0, 2]];* * */
Weight
From version 1.1.0 on, user can setup weight for walkable tiles. To setup it use setWalkable method as bellow:
.setWalkable0,,;
Tiles with unspecified weight will use the default value of 0.
Example with walkable tiles weight
; ; ; pfManager.setWalkable,.setEnd3.setStart2;;
or
pfManager.setWalkable0,.setEnd3.setStart2;
or
pfManager.setWalkable,.setEnd3.setStart2; /** bestPath = [{col: 0, row: 0}, {col: 1, row: 0}, {col: 2, row: 0}, {col: 3, row: 0}, {col: 4, row: 0}, {col: 4, row: 1}, {col: 4, row: 2}, {col: 4, row: 3}, {col: 4, row: 4}, {col: 4, row: 5}, {col: 5, row: 5}, {col: 5, row: 6}]** E -> End* S -> Start* # -> Path* * [[2, #, #, #, #, 0],* [0, 0, 1, 1, #, 0],* [0, 0, 1, 1, #, 0],* [0, 0, 1, 1, #, 0],* [0, 0, 1, 1, #, 0],* [0, 0, 0, 0, #, 0],* [0, 0, 0, 0, #, 3]];* * */
Example with same map as above but without walkable tiles weight
; ; ; pfManager.setWalkable0,1.setEnd3.setStart2;; /** bestPath = [{col: 0, row: 0}, {col: 0, row: 1}, {col: 0, row: 2}, {col: 1, row: 2}, {col: 2, row: 2}, {col: 2, row: 3}, {col: 3, row: 3}, {col: 3, row: 4}, {col: 4, row: 4}, {col: 4, row: 5}, {col: 5, row: 5}, {col: 5, row: 6}]** E -> End* S -> Start* # -> Path* * [[2, 0, 0, 0, 0, 0],* [#, 0, 1, 1, 0, 0],* [#, #, #, 1, 0, 0],* [0, 0, #, #, 0, 0],* [0, 0, 1, #, #, 0],* [0, 0, 0, 0, #, #],* [0, 0, 0, 0, 0, 3]];* * */
Documentation
PathFinding
new PathFinding(options)
Name | Type | Description |
---|---|---|
options | Object | Optional pathfinding algorithm options |
options?:{heuristic:Heuristic, allowDiagonal?:boolean} | Name | Type | Default | Description |
---|---|---|---|---|
heuristic | Heuristic | Heuristic.MANHATTAN | Optional Type of heuristic used for the pathfinding algorithm. Choose between Heuristic.MANHATTAN and Heuristic.DIAGONAL. |
|
allowDiagonal | boolean | false | Optional When using Heuristic.DIAGONAL, user can force path on the diagonal direction even if the adjacents tiles are non-walkable. |
setWalkable(...args:(number|WalkableTile)[])
Name | Type | Description |
---|---|---|
arg | Array | An array of numbers and/or WalkableTile type. WalkableTile:{type:number, weight:number}, weight is the percentage that a tile is "heaviest" than the default weight. |
setStart(start:number|{row:number, col:number})
Name | Type | Description |
---|---|---|
start | Object/number | A number that represents the start point on map or the start point using the row/col position format. |
setEnd(end:number|{row:number, col:number})
Name | Type | Description |
---|---|---|
end | Object/number | A number that represents the end point on map or the end point using the row/col position format. |
find(map: number[][]): {col:number,row:number}[]
Name | Type | Description |
---|---|---|
map | Array | An two dimensional Array of numbers. Returns an array of objects {col:number,row:number}, where the first array position is the start point and the last array position is the end point. |