Maze Files

No, not where to put it when you need the garage floor back…

One of the more useful properties of the maze is its size. At 256 cells, the whole thing was clearly designed to be convenient for microcontrollers. A single byte can be used to tell you which cell you are in and an array of 256 bytes can hold all you need to know about the maze.

For your micromouse controller, it is most convenient to use a single bit to indicate the presence or absence of a wall in the maze. Four bits per cell is easiest although you need only store two walls per cell if space is tight since the walls are all shared.

The most obvious solution is to arrange the bits like this:

 

----WSEN

 

Using the binary bit value for each wall position, we have:

NORTH = 1
EAST = 2
SOUTH = 4
WEST = 8

Now any combination of walls in a cell can be represented by a number in the range 0 to 15. Thus, the start cell would contain the value 14 which is 0x0E in hex or 00001110 in binary.

Adding and removing walls is a simple process of using bitwise and and or operations to directly manipulate the wall data. This is safer that adding and subtracting. In fact – don’t do it by adding and subtracting – you will be asking for trouble somewhere along the line.

Say you want to add a wall to the North of cell 23. The operation would be something like this:

cell[23] = cell[23] or NORTH

Remember that whenever you add a wall to a cell, there is a corresponding wall in the neighbouring cell. The mouse generally does not remove walls from its map so you always modify the neighbouring cell. There is no need to worry about what happens at the map edges. the Northern row of cells all have a North wall and the Southern row of cells all have a South wall.

Make sure that the index that you keep for the cell number is an unsigned byte. That way, you can refer to the cell above as cell+16. This will always work. For example, cell 250 is on the top row. 250+16=266. Since the index is an unsigned byte, the value will wrap around to give you cell 10 on the bottom row.

Here is a code fragment for adding walls which should illustrate the idea (it is in no particular language):

addwall(cell,direction)
  maze[cell] = maze[cell] or direction
  if (direction = NORTH){
     cell = cell+16
     maze[cell] = maze[cell] or SOUTH
     }
  if (direction = EAST){
     cell = cell+1
     maze[cell] = maze[cell] or WEST
     }
  if (direction = SOUTH){
     cell = cell+240
     maze[cell] = maze[cell] or NORTH
     }
  if (direction = WEST){
     cell = cell+255
     maze[cell] = maze[cell] or EAST
     }
end

In assembly language this is very compact and quick.

On your PC, you can save this as a binary file, 256 bytes long, on disk. Your mouse can transmit a 256 byte block representing the maze to your monitor program.

One variation which can make things convenient is to use this bit pattern for the walls:

-W-S-E-N

The advantage of this is that two rotate instructions have the effect of taking a quarter turn. This makes it easy to translate between the local view seen by the mouse and the world view of the maze solver.

You have used four bits to stare mapping information. What are you going to do with all those extra bits?

One option is to use them to store other flags. You might choose to remember whether a cell has been visited or to keep a ‘no entry’ flag to save looking at dead ends. Your maze solving routine might use these bits to indicate a direction for the speed run. I am sure you will come up with other uses.