# A*

Typescript + Javascript Pathfinding algorithm library.

- [Install](#Install)
- [Usage](#Usage)
- [Options](#Options)
- [Weight](#Weight)
- [Documentation](#Documentation)
- [License](#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](https://github.com/tbpisco/astarjs-example)

# 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 

### DO NOT allow diagonal

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

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

### 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](https://github.com/tbpisco/astarjs/blob/master/LICENSE)