Overview / Usage

There are basically 2 steps. The first is to drive through the maze and find the end of it. The second is to optimize that path so your robot can travel back through the maze, but do it perfectly without going down any dead ends.

I use a technique called the left hand on the wall. Imagine you are in a maze and you keep your left hand on the edge of the wall at all times. Doing this would eventually get you out of a non-looping maze. This instructable will only deal with mazes that do not loop back on themselves.

This left hand on wall algorithm can be simplified as follows:

• If you can turn left then go ahead and turn left,
• else if you can continue driving straight then drive straight,
• else if you can turn right then turn right.
• If you are at a dead end then turn around.

The robot has to make these decisions when at an intersection. An intersection is any point on the maze where you have the opportunity to turn. If the robot comes across an opportunity to turn and does not turn then this is considered going straight. Each move was taken at an intersection or when turning around has to be stored.

The optimisation follows the principle of traversing the entire maze at once using any traversal algorithm like Breadth First Search or Depth First Search which includes backtracking form the dead ends and recording everything in the Stack Data Structure. The data obtained from the backtracking is used as a reference for path optimisation.