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
create a GRID of cells with properties ↵
  including (fCost, gCost, hCost, parentNode, isClosed, xCoordinate, yCoordinate)
  
insert the start node into the OPEN list
  
while there are nodes inside OPEN // Main loop
  take the node inside OPEN with the smallest fCost -> CURRENT

  if CURRENT is the END node
    go back through the parents to compute the path and return. It's done
  
  remove CURRENT from the OPEN list
  set the GRID cell with the CURRENT coordinates to isClosed = true
  
  for each NEIGHBOR of CURRENT
    if NEIGHBOR is blocked by an obstacle, a closed cell or out of bounds
      move on to the next NEIGHBOR
    
    calculate the gCost for NEIGHBOR which is gCost of CURRENT + distance to NEIGHBOR ↵
      (distance 1 if in a straight line or sqrt(2) ~ 1.4 if in a diagonal)
  
    if NEIGHBOR is not in OPEN
      add it to OPEN and set the rest of its properties (hCost, fCost and parent)
    else if NEIGHBOR is in OPEN but the new gCost is smaller than the existing node
      update the gCost, fCost and parent of that node

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

Thanks for reading :)