Important: This documentation covers Yarn 1 (Classic).
For Yarn 2+ docs and migration guide, see yarnpkg.com.

Package detail

astarjs

tbpisco24MIT1.1.3TypeScript support: included

Pathfinding algorithm library.

pathfinding, astar, a star, a-star, path, a*, heuristic, manhattan, diagonal

readme

A*

Typescript + Javascript Pathfinding algorithm library.

Install

npm install astarjs --save

Usage

import { PathFinding } from 'astarjs';

let map = [ [0,  0,  14, 23, 23, 0,  0,  23, 0,  0,  0,  2,  0,  0],
            [0,  0,  0,  0,  0,  0,  13, 1,  0,  0,  0,  0,  0,  13],
            [1,  23, 0,  14, 23, 0,  13, 0,  2,  0,  1,  0,  23, 2],
            [14, 0,  0,  0,  0,  23, 0,  0,  0,  2,  2,  2,  0,  0],
            [13, 0,  0,  0,  0,  3,  0,  0,  0,  0,  0,  14, 0,  0],
            [13, 0,  0,  0,  23, 0,  0,  23, 0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0,  0,  0,  23, 0,  0,  0,  0,  0],
            [0,  0,  0,  23, 0,  4,  0,  0,  0,  1,  0,  23, 0,  2]];

let pathFindingManager = new PathFinding();
pathFindingManager.setWalkable(0) // or this.pathFindingManager.setWalkable(0, 10, 11); 
                    .setEnd(4)
                    .setStart(3);

let bestPath: {col:number,row:number}[] = pathFindingManager.find(map);
/*
returns
0: {col: 5, row: 4}
1: {col: 5, row: 5}
2: {col: 5, row: 6}
3: {col: 5, row: 7}*/

or


import { PathFinding } from 'astarjs';

let map = [ [0,  0,  14, 23, 23, 0,  0,  23, 0,  0,  0,  2,  0,  0],
            [0,  0,  0,  0,  0,  0,  13, 1,  0,  0,  0,  0,  0,  13],
            [1,  23, 0,  14, 23, 0,  13, 0,  2,  0,  1,  0,  23, 2],
            [14, 0,  0,  0,  0,  23, 0,  0,  0,  2,  2,  2,  0,  0],
            [13, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  14, 0,  0],
            [13, 0,  0,  0,  23, 0,  0,  23, 0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0,  0,  0,  23, 0,  0,  0,  0,  0],
            [0,  0,  0,  23, 0,  0,  0,  0,  0,  1,  0,  23, 0,  2]];

let pathFindingManager = new PathFinding();
pathFindingManager.setWalkable(0); // or this.pathFindingManager.setWalkable(0, 10, 11); 
pathFindingManager.setEnd({col: 5, row: 7});
pathFindingManager.setStart({col: 5, row: 4});

let bestPath: {col:number,row:number}[] = pathFindingManager.find(map);
/*
returns
0: {col: 5, row: 4}
1: {col: 5, row: 5}
2: {col: 5, row: 6}
3: {col: 5, row: 7}*/

See full example here

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


import { PathFinding, Heuristic } from 'astarjs';

let map = [ [0,  0,  2,  2,  2,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  3,  0,  0,  0,  0],
            [1,  2,  0,  0,  2,  0],
            [2,  0,  0,  0,  0,  2]];

let pathFindingManager = new PathFinding({heuristic: Heuristic.MANHATTAN});
pathFindingManager.setWalkable(0)
                    .setEnd({col: 5, row: 2})
                    .setStart({col: 2, row: 6});
let bestPath = pathFindingManager.find(map);

/*
* 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


import { PathFinding, Heuristic } from 'astarjs';

let map = [ [0,  0,  2,  2,  2,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  3,  0,  0,  0,  0],
            [1,  2,  0,  0,  2,  0],
            [2,  0,  0,  0,  0,  2]];

let pathFindingManager = new PathFinding({heuristic:Heuristic.DIAGONAL});
pathFindingManager.setWalkable(0)
                    .setEnd({col: 5, row: 2})
                    .setStart({col: 2, row: 6});
let bestPath = pathFindingManager.find(map);

/*
* 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


import { PathFinding, Heuristic } from 'astarjs';

let map = [ [0,  0,  2,  2,  2,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  3,  0,  0,  0,  0],
            [1,  2,  0,  0,  2,  0],
            [2,  0,  0,  0,  0,  2]];

let pathFindingManager = new PathFinding({heuristic:Heuristic.DIAGONAL, allowDiagonal:true});
pathFindingManager.setWalkable(0)
                    .setEnd({col: 5, row: 2})
                    .setStart({col: 2, row: 6});
let bestPath = pathFindingManager.find(map);

/*
* 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:

.setWalkable({type: 1, weight:0.5},{type: 2, weight:1});

In this case, setWalkable can receive an indefinite list of arguments with the following data type:

{type:number, weight:number} or number

type here is used to differentiate between terrain types (like grass, pathway, sand, etc...) and each type can have a different weight. The weight will increase the movement cost.

Example:

.setWalkable(0, { type: 1, weight: 0.5 }, { type: 2, weight: 2 });

When you use number as argument, in this case, 0, the library will read it as { type: 0, weight: 0 }.

Here the type 0 might be something easier to walk through, like a pathway, type 1 might be grass and type 2, a slow terrain like sand.

If you are not using tiles with different movement costs, you can set just as

.setWalkable(0, 1, 2);

In that case, the library will treat this as 

.setWalkable({ type: 0, weight: 0 }, { type: 1, weight: 0 }, { type: 2, weight: 0 });

Tiles types with unspecified weight will use the default value of 0.

Example with walkable tiles weight


import { PathFinding } from 'astarjs';

let map = [ [2,  0,  1,  1,  0,  0],
        [0,  0,  1,  1,  0,  0],
        [1,  0,  1,  1,  0,  0],
        [0,  0,  1,  1,  0,  0],
        [0,  0,  1,  1,  0,  0],
        [0,  0,  0,  0,  0,  0],
        [0,  0,  0,  0,  0,  3]];

let pfManager = new PathFinding();            
pfManager.setWalkable({type: 0},{type: 1, weight:3}).setEnd(3).setStart(2);
let bestPath = pfManager.find(map);

or 

pfManager.setWalkable(0,{type: 1, weight: 3}).setEnd(3).setStart(2);

or

pfManager.setWalkable({type: 0, weight: 0},{type: 1, weight: 3}).setEnd(3).setStart(2);


/*
* bestPath = [{ col: 0, row: 0 },{ col: 0, row: 1 },{ col: 1, row: 1 },{ col: 1, row: 2 },
              { col: 1, row: 3 },{ col: 1, row: 4 },{ col: 1, row: 5 },{ col: 1, row: 6 },
              { col: 2, row: 6 },{ col: 3, row: 6 },{ col: 4, row: 6 },{ col: 5, row: 6 }]
*
* E -> End
* S -> Start
* # -> Path
* 
*  [[S,  0,  1,  1,  0,  0],
*   [#,  #,  1,  1,  0,  0],
*   [1,  #,  1,  1,  0,  0],
*   [0,  #,  1,  1,  0,  0],
*   [0,  #,  1,  1,  0,  0],
*   [0,  #,  0,  0,  0,  0],
*   [0,  #,  #,  #,  #,  E]];
* 
* 
* */

Example with same map as above but without walkable tiles weight


import { PathFinding } from 'astarjs';

let map = [ [2,  0,  1,  1,  0,  0],
            [0,  0,  1,  1,  0,  0],
            [1,  0,  1,  1,  0,  0],
            [0,  0,  1,  1,  0,  0],
            [0,  0,  1,  1,  0,  0],
            [0,  0,  0,  0,  0,  0],
            [0,  0,  0,  0,  0,  3]];

let pfManager = new PathFinding();            
pfManager.setWalkable(0,1).setEnd(3).setStart(2);
let bestPath = pfManager.find(map);

/*
* bestPath = [{ col: 0, row: 0 },{ col: 0, row: 1 },{ col: 0, row: 2 },{ col: 0, row: 3 },
              { col: 0, row: 4 },{ col: 0, row: 5 },{ col: 0, row: 6 },{ col: 1, row: 6 },
              { col: 2, row: 6 },{ col: 3, row: 6 },{ col: 4, row: 6 },{ col: 5, row: 6 }]
*
* E -> End
* S -> Start
* # -> Path
* 
*  [[S,  0,  1,  1,  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],
*   [#,  #,  #,  #,  #,  E]];
* 
* */

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 ...args A list 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.

License

MIT