Path Finding algorithms

• A* Search

  A* is an informed search algorithm that uses a heuristic function to evaluate nodes by combining the cost of reaching the node (G cost), with an estimate of the cost required to reach to end point (H cost) to give us the F cost. A* explores the most promising nodes first and guarantees optimal pathfinding.

  
• Breadth First Search

  Like A*, BFS guarantees the shortest path between two points by exploring all the nodes at the current depth from the start point before moving on to the nodes at the next depth. BFS uses a queue to keep track of nodes to be explored, which ensures that nodes are visited in the order they are discovered.

  
• Depth First Search

  Unlike the previous two algorithms, DFS only guarantees a path between two points if it exists by exploring as far as possible along along each path before backtracking. DFS uses a stack to keep track of nodes to be explored which means it visits nodes in the order they were added to the stack.

  
• Random Search

  This algorithm is very similar to DFS, in which it guarantees a path between two points by using a stack to explore nodes. However, instead of the adding each node visited to the stack in the same order, it randomizes the order that the nodes are inserted. This produces a unique and chaotic exploration with each search.