Solving the maze

No use having a micromouse
that can’t solve mazes. Although it seems central to the task of creating
a micromouse, actually solving the maze is possibly the easiest part of
the entire job. Here are a couple of ideas.

There are many ways to solve the kind of maze found in micromouse competitions.
A naive approach would be to follow the left or right wall in the expectation
that it will eventually lead to the goal. This is only true for some,
especially simple kinds of maze. Micromouse mazes are designed specifically
so that this is not possible. Here the goal is in the centre of the maze
and not connected to the outside of the maze by a wall. Thus, any attempt
to follow the walls will just bring you back to where you started.

Many mouse builders have their mouse follow rules that, for example,
ensure all four quadrants are searched or that turns are made preferentially
in one or another direction depending on where you are. Some of these
search algorithms can find themselves caught in loops and need special
tests to detect problems. I can’t think of a compelling reason to
search in this way. Apart from the primary goal of finding the route to
the centre which has the smallest number of steps, you might wish to at
least circle the centre to try and be sure you have not missed any longer
but quicker routes. Remember that the shortest path may well not be the fastest path for your mouse.

I believe the simplest method available to a micromouse is some variation
on the flood-fill or Bellman algorithm. The idea is to start at the goal
and fill the maze with values which represent the distance from each cell
to the goal. When the flooding reaches the starting cell then you can
stop and follow the values downhill to the goal.

The simple flooding algorithm works like this:

  • Start with an array of bytes with one byte representing each cell
    in the maze.
  • Put the value 0 into the cell that you are aiming for.
  • Go through all the cells and make sure that each one has a value that
    is just one more than its smallest accessible neighbour.
  • Repeat that last step until you have not changed the value in the
    starting cell.

Notice that there is no need to pre-initialise the map contents. This algorithm can take a considerable number of iterations. Worst case would see
you doing all 256 cells a couple of hundred times. Say that it took you
ten instructions per cell (it would be more than that I expect) and each
one takes 0.5 microseconds, you might need around 0.25 seconds to solve
the maze. In practice, the algorithm will run for as many iterations as there are cells in the longest path. This is likely to be only 20 to 50 cells and so you should be done in much less time. Even so, you don’t want to be doing that any more often than you have
to. In practice, you only have to when you come to a junction – i.e. a
cell with three or four exits. At all other times, your action is predetermined
and there is no decision to make.

To save a bit of time, a number of designers divide up their flooding
algorithm and do just a bit of it as a time delay routine. Dealing with
just one cell is a simple enough task and could be made to run in a fixed
time regardless of content. Use this as a time delay in your speed control
loop and with any luck, by the time you get to a junction, the maze has
been solved in the background. If the solver has not finished then just
finish the job while you are waiting to see which way to go.

 

One Response to Solving the maze

  1. Adam says:

    If you would like to see some of the basic maze solving algorithms in action please visit http://www.mobilerobots.pl/index.php?p=1_22_Micromouse

Leave a Reply