Step 4. A* search

This program implements the A* algorithm and allows us modify it.

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

Clone and Edit the World.
  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 is A* not impressive here?

  6. Change the code to use the other heuristic.
Tweet this step: