Step 4. A^* search

Video

World

A star
"A Star" algorithm to find shortest path through maze.

Notes

• A^* seeks a goal using a heuristic estimate of distance from goal.
• It will find the shortest (or joint shortest) path.
• Goal here: Find optimal path from top LHS corner to bottom RHS corner.
• Reload for a new problem.
• Sometimes there is no path.

Credits

• This is a modified port of 05_astar from AI course by Daniel Shiffman.
• See his videos parts one and two and three.
• Modified to give randomised world size and randomised wall density.
• Modified to give a switch to say if diagonal moves are allowed or not.
• Modified to use different heuristics for diagonal v. non-diagonal.

Look at code

• See code.
• Two versions: Are diagonal moves allowed or not? See boolean "diagonal".
• 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.

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

Exercise

1. Change the various customisable values.
2. Change the speed. See the "frameRate" line.
3. Change open and closed colours to white.
4. Change it to no walls at all, diagonal.

5. Change it to no walls, no diagonal.
   Question: Why does it look so strange? Is it really finding the shortest path?

6. Change the code to use the other heuristic.