UP | HOME

Recursive Backtracking

Recursive backtracking a depth-first search technique for finding a path from a starting location to the goal. Although the algorithm does not necessarily find the shortest path, it will find a path (if it exists), and does not require full knowledge of the maze.

Setup

  1. The robot starts at the start. This square is marked as part of the path.
rbmaze1.svg
Figure 1: The Goal is the red square. The robot (purple circle) starts at the green square. Obstacles are Black, free space is white.

First Step

  1. The robot can't move North.
  2. The robot can move East. It moves east and marks the new square as part of the path.
rbmaze2.svg
Figure 2: State after the first step.

Continue East

  1. The robot can't move North.
  2. The robot can move East (again). It moves east and marks the new square as part of the path.
rbmaze3.svg
Figure 3: State after second step to the East

First Backtrack

  1. The robot can't move North.
  2. The robot can't move East.
  3. The robot can't move South.
  4. The robot can move West, but that is already on the path.
  5. The robot has explored all directions and not found a new free square.
  6. Therefore the current square is not on the path.
  7. The robot moves West.
rbmaze4.svg
Figure 4: With no adjacent unexplored free squares, the robot must backtrack.

Continue Moving

  1. Robot resumes from its previous time at this square.
  2. Robot has already tried moving North and East, and that failed.
  3. The Robot can move South, so it does so.
rbmaze5.svg
Figure 5: Resuming where the robot left off, it decides to move to the south.

Go South!

  1. The robot can move North, but it's been there before.
  2. The robot can't move East.
  3. The robot can move South, and does so.
rbmaze6.svg
Figure 6: Another Step to the South, followed by two steps to the east

Eastward Bound

  1. The robot can't move North, but it can move east.
  2. Repeat one more time.
rbmaze7.svg
Figure 7: After two steps, the robot has gone as far East as possible

Final Backtrack

  1. The robot cannot move in any direction without visiting an unexplored square, so it backtracks by one square.
  2. The new location has the same problem, so the robot backtracks again.
rbmaze8.svg
Figure 8: Two backtracks in a row!

Almost Home

  1. The robot has already explored North and East.
  2. The robot cannot go South.
  3. The robot can move West, so it does so.
rbmaze9.svg
Figure 9: After moving one square to the west

Goal!!!!!!!

  1. The Robot cannot move North.
  2. The Robot has already explored the East.
  3. The robot can move south, that is the goal!
  4. The robot also has a path from the start to the goal.
rbmaze10.svg
Figure 10: The robot has found the goal

Resources

  1. Recursive Backtracking

Author: Matthew Elwin.