Astarjs NPM | npm.io

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

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

Running the example

Run the following commands to run the example:

npm install
npm 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

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(0,{type: 1, weight:0.5},{type: 2, weight:2});

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

Example with walkable tiles weight

import { PathFinding } from 'astarjs';

let map = [ [2,  0,  0,  0,  0,  0],
			[0,  0,  1,  1,  0,  0],
			[0,  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:2}).setEnd(3).setStart(2);
let bestPath = pfManager.find(map);

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

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

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

import { PathFinding } from 'astarjs';

let map = [ [2,  0,  0,  0,  0,  0],
			[0,  0,  1,  1,  0,  0],
			[0,  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: 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.

License

MIT

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

@everything-registry/sub-chunk-1173 @zalastax/nolb-ast

4 years ago

4 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago