Check out the demo here.

## Introduction

The A-Star Pathfinding algorithm finds the shortest path in between 2 points while avoiding obstacles.

## Resources

To understand how the algorithm works, I highly recommend the following video by Sebastian Lague:

## Explanations

### The basic logic is pretty straightforward:

For each cell around the start node, calculate 3 properties:

- The distance from the start node - commonly called
`G Cost`

- The distance from to the end node - commonly called
`H Cost`

- The sum of the two - commonly called
`F Cost = G Cost + H Cost`

Then pick the node with the lowest `F Cost`

amongst all the nodes and start the process again. When finding the next node to use as a pivot, consider the newly calculated nodes and the previous ones as well.

If there is a path, it should eventually be reached. Otherwise eject !

### The part that is a bit trickier:

The distance from the start for a new Node A is equal to the distance in between Node A and its parent + the distance in between that parent and the start node __and not the absolute distance from the start node.__

This is important as otherwise, obstacles would not be taken into account.

This has 2 consequences:

- When computing a new node, the parent node needs to be saved as well. This will form a linked list of sorts that will save the whole path information from the start.
- When looking at the neighbooring nodes, always check the already computed nodes as well and see if a smaller
`G Cost`

can be found__through the current node__. If that is the case, the`G Cost`

,`F Cost`

and parent need to be updated for that neighbooring node with the new best path information.

When using the app I have created, you can hover over the cells to checkout the different properties that were computed.

## Pseudo Code based on my implementation

create an OPEN list that will hold the computed nodes |

The TypeScript implementation is available here and the full code is available on GitHub

Thanks for reading :)