A^* on Ancient Brain

A program to show the A^* algorithm seeking a goal using a heuristic estimate of distance from goal.
Finds shortest (or joint shortest) path.
Goal: Find optimal path from top LHS corner to bottom RHS corner.

Click to run World: A star at Ancient Brain.

• Credit:
  • This is a modified port of 05_astar from AI course by Daniel Shiffman.
  • See his videos parts one and two and three.

• Two versions: Are diagonal moves allowed or not? (See boolean "diagonal" in the code.)
• Heuristic for World with diagonal moves allowed: 2D distance to the goal. This is always optimistic.
• Heuristic for World with no diagonal moves allowed: Distance across plus distance down. This is always optimistic.

• See code.
• Modified to give randomised world size and randomised wall density.
• Modified to give easy turn diagonal on/off, and different heuristics for diagonal v. non-diagonal.

• Black - wall
• Green - open list - squares known but not yet checked
• Pink - closed list - squares examined
• Dark red - a joint shortest path