A*

Typescript + Javascript Pathfinding algorithm library.

- Install
- Usage
- Options
- Weight
- Documentation
- License

Install

``bash
npm install astarjs --save
`

Usage

`typescript
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

`typescript

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

`typescript

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

$3

`typescript

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]];
*
/
`

$3

`typescript

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:

`typescript
.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:

`typescript
.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

`typescript
.setWalkable(0, 1, 2);
`

In that case, the library will treat this as

`typescript
.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

`typescript

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

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

`typescript
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

`typescript

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

$3

| 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.|

$3

| 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.|

$3

| 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. |

$3

| 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. |

$3

| 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