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

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