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, theG 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 :)