Check out the demo here.
The A-Star Pathfinding algorithm finds the shortest path in between 2 points while avoiding obstacles.
To understand how the algorithm works, I highly recommend the following video by Sebastian Lague:
For each cell around the start node, calculate 3 properties:
- The distance from the start node - commonly called
- The distance from to the end node - commonly called
- 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 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 Costcan be found through the current node. If that is the case, the
F Costand 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.
create an OPEN list that will hold the computed nodes
Thanks for reading :)