A-Star-Algorithm-Path-Finding 🔎

A* path finding algorithm implemented in p5.js

Formulae ℹ️

  f(n) = g(n) + h(n)

• F of N is the total cost from node to the Goal.
• G of N is the cost of the start node to the N.
• H of N is a heuristic function that estimates the cost of the cheapest path from N to the goal.

A* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended. The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal.

Here the grid has been 25 X 25 cubes. Green nodes represents nodes which are available and can be searched. Red nodes represents nodes which has been visited and is closed. Black nodes represents object or obstacles in the way. Whenever path is found the shortest way from nodes are represented in blue.

Pseudo-Code 🧮

  OpenSet = [];
  ClosedSet = [];
  Add start node to OpenNodes;
  
  loop()
    currentNode = node in OpenSet with the lowest f(n) / f_cost
    remove currentNode from OpenSet
    add currentNode to ClosedSet
    
    if currentNode is the end node
      Congragulation you have found the path.
      return;
      
    foreach neighbour of the currentNode 
      if neighbour is not traversable or neighbour is in ClosedSet
        skip to the next neighbour
        
      if new path to the neighbour is shorter or is not improved 
        set f(n) / f_cost of neighbour 
        set parent of neighbour to current 
        
      if neighbour is not in OpenSet
        add neighbour to Open Set
    

Here is example of completed paths with Starting Node of 0,0 and End node of 25,25 (Very top-left corner to very bottom-right corner)

Here is an example if there no path was found from start node to end node