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.
This Post Has 9 Comments
Leave a Reply
This site uses Akismet to reduce spam. Learn how your comment data is processed.
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
Hi Peteh
sory My English is not good
Please help me:
– I don’t understand line 3 of text instruction:
“”””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””
– 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.
“””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””
=> In line 3: I don’t understand, why we know value in cell neighbour while mose not go in cell that? So value in Array is anticipated?
+ When i creat a Array (ex: 8*8): values each cell of Array is set before?
I see Your Code: #define NUMCELLS 256
– So Array is {0,0,0…..0,0,0} (255 byte)? when mose not yet go in a cell, how can mose know value in cell that?
– I see instruction set value Array: http://www.swallow.co.uk/dash/maze2.gif
=> Is that value i must set befor in Array (256 byte)?
And:
– code your instruction:
___________________________________
#define NORTH 1
#define EAST 2
#define SOUTH 4
#define WEST 8
#define VISITED 16
#define ONROUTE 32
____________________________________________
-=> I don’t understand why you used 1,2,4 ,8, 16 and 32 for value variables . without use value other
please forword email thanhnl05@gmail.com
THank you very much!
The entire maze is flooded even if the mouse has not visited each cell. For cells that the mouse has not yet seen, you can assume that it has no walls. In this way, every cell holds a distance from the goal. When the mouse does enter that cell, it can use the information to help it decide where to move next.
The best thing is to write some test code to run on a PC and you will soon see what needs to be done.
The values shown for each wall simply allow you to use a single byte of storage to represent all the wall information for a cell. For example, a cell with walls in the West, East and South positions would have a wall value of 2+4+8 = 14 stored in it. Simple bitmasks let you examine the presence or absence of a wall.
Thanks for your help.
Can you hint for me a few good software make a maze and simulation in this or soft you are using? thanks you!
you should probably see what a Google search comes up with. There is not much. The examples you find are likely to be written for web display in Java or javascript but they may give you some ideas.
really, you need to write this yourself. All the mouse and maze related code can then be used directly in your own mouse.
You could also go to github.com or code.google.com and search for micromouse there.
Hi Peter
I understood base flood fill augorithm, but i can’t understand when Mose moved to goal, It go to back by route other is to DISCOVER cells not travel, then find slower route. So when go back, how flood fill augorithm change?? is value change all the cells??? are we use array other for times go back?
Thanks you!
When you return, you set the target cell to be the start rather than the goal. The flood naturally produces different values and these will almost certainly take the mouse on a different path as it returns.
After going to and from the goal a number of times, there will come a point where the route calculated no longer passes through any unknown walls. Then the best route has been found and you can start the speed runs.
thanks Peter for help.
But I understand: what is value of cell start (destination -> start). Is start = 0, destination = ? ? can you talk detail or more? Thanks you so much