Part 4: Storing the Maze

First Thoughts

Any robot that hopes to solve a maze must somehow keep track of where it has been and then perform some algorithm to decide on how to eliminate travel down unproductive pathways. This section talks about how to store, and later modify all of the turns made while traversing the maze.

Let's start with a simple maze and some definitions so we are speaking the same language.

Here is a simple maze. The robot is at the start and is required to find the "End of Maze".

Simple line maze

First, we will traverse the maze in English, then transform our English words to an abbreviated code that will be easy to store.

Left-Hand Rule and Right-Hand Rule Defined

Mazes of this type are best solved by using either the left or right-hand rule. Look at the black lines in the maze above and pretend you are a very teeny-tiny person and the black line represents a passageway that is walled in. First, you place your left hand on the wall at the starting point. Then you start walking, keeping your left hand touching the wall to your left. Whenever you reach an intersection, keep your hand on the wall and make the turn.. With this algorithm, here is your path through the maze above.

  1. Walk down the first path to Intersection A, and go Straight.
  2. Walk to the end of the path at Dead-End B. Keeping your left hand on the wall forces you to do a U-Turn.
  3. Return to Intersection A and go Left.
  4. Continue to Intersection C and go Left.
  5. Take a mandatory Left turn towards Dead-End D
  6. At dead-end D, make a U-Turn
  7. Return to Intersection C and turn Left.
  8. Continue to dead-end E and make a U-Turn.
  9. Return again to Intersection C and go Left.
  10. Make a mandatory Left turn and go towards Intersection F.
  11. Continue to Intersection F and go Left.
  12. Reach the end of the maze at H.

Notice that Dead-End G is never reached using the left hand rule.

Also notice I used the term "mandatory turn" several times above. I will talk more about turns where there is only one possible choice later.

Compress the path

Now, most microprocessors have extremely limited memory, so storing the actions using words or phrases like "Go Left", "Go Straight" take up too much storage. Since there are only four possible actions, and they all start with a different letter, lets reduce the actions to:

The entire trip described above can be reduced to this string:

SULLLULULLL

Now, if you look at the maze, you can deduce that the "correct" path to complete the maze in the shortest time is: RRLL, so somehow, after (or during) the first trip through the maze, the sequence of turns needs to be converted from SULLLULULLL to RRLL. That algorithm is explained in great detail in a paper I wrote to explain the algorithm. (Hint: Any time the robot has to make a U-Turn, then the previous turn was incorrect and needs to be modified.) Go to this link to see the paper on the details: Line Maze Algorithm in .PDF format.

How to Store the Turns

Notice that I used the letters L, R, U, S to specify the turns. You could just as easily use numbers, such as:

Either method works depending on just how your microcontroller can store the information. Storing the numbers to specify turns is OK, but most systems require a byte to do this. If you want to use less than a byte to store each turn, then you will need something that will store the four possible turns in character or binary form.

Here are some examples of how I've stored turns in a microcontroller:

Full Bytes

In any system with enough memory to use one byte, here are three alternatives...

Turn ASCII Characters Numbers Degrees
Left Turn L 0 270
Right Turn R 1 90
U-Turn U 2 180
Go Straight S 3 0

In systems where the variable type nibble (4 bits) is allowed, you can save space by using numbers and storing each turn in one nibble.

Arrays Vs. Strings

Either arrays or strings will hold your series of turns. The one you use should depend on your programming ability with either. Use the one you are comfortable with. Both methods require you convert a bad turn sequence into a correct sequence.

Look at the set of turns LUL. In any maze where you take a left turn, then have to make a U-Turn, then take a left, the first left was a bad choice. The way to correct this is by converting "LUL" to "S", or in other words, you should go Straight at that intersection next time. So, let's try this particular combination with an array and with a string.

With An Array

Use a pointer (ptr) to keep rtrack of where the last number was placed.

Turns(0) = L

Turns(1) = U

Turns(2) = L, and ptr would be 2.

After each turn, we need to see if the next-to-last turn was a "U", so we can modify the turn for the next run. So our code wouild look something like this...

If Turns(ptr - 1) = "U" Then