A* is the Algorithm for ALL paths.

Data structure. A matrix of nodes where each has:

• G = cost from start to a given node. Think “go” cost.
• H = minimum possible cost from a given node to the end.
• F = G cost + H cost. Think minimal possible “finished” cost.
• Parent node.

Algorithm:

• Add the starting node to the open list.
• Select the lowest F cost node that’s still open.
• If the selected node is the end node:
  • Back track through the parent nodes until the start. That’s the path.
  • Done!
• For each surrounding node that isn’t blocked nor closed and where the G cost is shorter with this parent or the surrounding node isn’t open:
  • Set the surrounding node’s costs.
  • Set the parent to the current node.
  • Make the node open if it isn’t already.
• Move the node to the closed list.
• Repeat until the end is reached.