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.

#### Incoming search terms:

- MicroMouse Algorithm (15)
- flood fill algorithm micromouse (1)
- line maze solver micromouse (1)
- micromouseonline floodfill (1)

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