October 07, 2004
A Maze Mapping Algorithm
A Maze Mapping Algorithm
Andy Michalicek,
PAReX, November 26, 2003
This is one of several maze mapping techniques you can find
in the literature. The advantage of this one is that it requires just a
small amount of memory. Also, mapping of the maze defines the return path
that will be used in the competition, without requiring extra software.
In this approach, the maze is treated as a collection of
squares or cells. In each cell, we will be recording where the walls are,
and a history of where we move. Because the PAReX competition maze consists
of multiples of 4’x 4’ sections, with walls placed on 12”
boundaries, a 12”x12” cell is a natural choice. For a maze that
is 4’x4’, sixteen bytes of storage are needed (4 x 4 = 16). For
a maze that is 8’x8’, 64 bytes are needed. The maze then is
mapped as a two dimensional array of bytes.
Recording the Cell Wall Configuration
We will use N, E, S, and W as absolute directions. We
can do this even if those directions are not the true compass directions, as an
assumed convenience. We will assume that when the robot starts out, it is
facing north. We will talk of the robot moving Forward (F), right (R), or
left (L), where F is to move forward to the next cell, and R and L is to turn
right or left and then move to the next cell in that direction. The robot
needs to keep track of its heading, because walls within a cell are recorded per
the side of the cell they are located: north, east, south, or west.
In addition to physical walls, the robot will deal with
virtual walls. A robot does not distinguish between a physical and virtual
wall when choosing which way to travel, both are valid blocks to its
movement. This comes into play where it has traveled along one path in a
maze, has hit a dead end, and has had to backtrack. It will treat that path
as if virtual walls existed, and not travel from that cell in that direction
again.
As the robot moves through the maze, it analyzes the wall
layout and records it in its map. It stores this in one byte per cell, where
two bits are assigned to each wall. For each cell in the map the four walls
are coded as follows:
| Code |
Binary |
Meaning |
| 0 |
00 |
Untraveled |
| 1 |
01 |
Traveled |
| 2 |
10 |
Not Used |
| 3 |
11 |
Don’t Go There |
‘Untraveled’ means that the robot has not traveled
there. ‘Traveled’ says that the robot has already moved in that
direction. ‘Don’t Go There’ can either mean that a wall is
there, or that the robot has gone there already, but at some point ran into a
dead end, and had to back track, and so it will never want to go there
again. When entering a new cell, the robot will only have to look forward,
to the right, and to the left. It will assume that in the direction behind
it, it can mark the wall with a code of 1, for ‘Traveled’.
When the walls are analyzed and stored in the map, the robot does so using absolute
directions of N, E, S, or W, rather than forward, left or right. This is because
‘forward’ for the robot can be any absolute direction at different time
while searching through the maze. The storage pattern for each cell is as
follows:
| North |
East | South | West |
xx xx xx xx = 8 bits
In the starting square, it is facing North, and there are
three walls located at east, south, and west, so it would record the starting
square as:
00(N) 11(E) 11(S) 11(W) = 00 11 11
11 binary = 0333 quad
So at the start, the heading is N, and Map(0,0) = 0 3 3 3.
Movement Algorithm
For the PAReX maze competition, there are two modes: Search,
and Return. In search, we are looking through the maze for a tennis ball,
mapping the maze as we go. In return, we have found the tennis ball and want to
take the most direct path back to the start.
We are now ready to start walking
through the maze. Since there is a PAReX rule that the maze will be laid out in
a tree structure without any cross-over paths, we can follow each branch of the
maze till we find the tennis ball, or follow it to a dead end. If we find a dead
end, we will backtrack to where we can start down another path. While we are
backtracking, we will insert virtual walls behind us in the map so that we
‘Don’t Travel There’ again, just as if walls existed in those
spots.
For convenience, we are referring to
the passageway where a wall could exist as a wall. Below you will find the
phrase “the wall the robot will travel through” or the phrase
“the wall the robot just came through” not to mean the robot can
pass through walls, but to mean the passageway where a wall would have existed.
This was done for readability (of the author if nobody else).
Search Mode
In this mode, movement is always to a ‘0’ unless
backtracking, in which case movement is to a ‘1’.
| 1. |
Record the front, right, and left walls into the map. |
| 2. |
Check F, R, and L for a wall code of value 0. If F is 0, go there.
Else if R is 0, go there. Else if L is 0, go there. The choice to
look at R before L was arbitrary. If there are no 0 codes, find the
‘1’ and move there. This indicates you are backtracking.
There will be only one ‘1’. |
| 3. |
Before the actual move in a ‘0’ direction, the wall the
robot will travel through is changed from a 0 to a 1. Update the map. |
| 4. |
Move to the new cell and update the current heading and location. |
| 5. |
After arriving at a new cell, if the wall code behind the robot is a
‘0’, it is changed to a 1 (been there). If it is a
‘1’, it is changed to a 3 (virtual wall). Update the map. |
| 6. |
If three walls exist, then a dead end has been found, and the robot must
backtrack. Turn around and go back to the previous cell. |
| 7. |
Repeat until the tennis ball is found. Normally we would now tap the ball to
displace it, then enter Return mode. |
Return Mode
For the PAReX maze, the search mode
ends and the return mode begins when the tennis ball is found. We now look for
‘1’s, instead of ‘0’s, of which there should be only one
per cell. We know we have returned home when all four walls are
‘3’.
1. All cells should only have one ‘1’. The other two
walls can be either a ‘0’ or a ‘3’. Move
in the direction of the ‘1’.
2. Update the current heading and location.
3. In the new cell’s map, the wall the robot just came
through is marked with a code of 3. Update the map.
4. Repeat until all four walls are ‘3’s. Extra points
are earned at this point if the robot indicates it knows that it has returned to
the start. Update the map.
Example
In the example, the location of the robot will be indicated with: (x,y), where
(x,y) is the current location. At the beginning of the search phase, this will
read (0,0).
We will assume that the robot starts off in the south-west
corner of an 3’x3’ maze, and is facing north. Cells are numbered
from 0 to 2 for north-south, and 0 to 2 for east-west. The starting cell
location is therefore (0,0). The current heading is north (N). There are walls:
on the right (R), which is east (E); behind, which is south (S); and to the left
(L), which is west (W), and so Map(0,0) = 0 3 3 3.
As a part of starting out, since it would have been done as the last step of the
previous move, we assign a code of 3 (wall) to the location behind us. Now we
can move.
Sample maze:
Walking through the maze:
Step 1
| Location |
(0,0) = 0 3 3 3 |
| Mode |
Search |
| Heading |
North |
| Decision |
Forward |
|
The robot starts out in cell (0,0), facing north. The first motion will be
forward. The south wall has been set to 3 as an initial condition.
|
|
Step 2
| Location |
(1,0) = 0 0 1 3 |
| Mode |
Search |
| Heading |
North |
| Decision |
Forward |
|
Now in (1,0), the robot is still facing north. The north wall of (0,0)
has been set to 1, and the south wall of (1,0) has been set to 1.
The robot chooses to go forward.
|
|
Step 3
| Location |
(2,0) = 3 0 1 3 |
| Mode |
Search |
| Heading |
North |
| Decision |
Right |
|
Now in cell (2,0), the north wall of (1,0) has been set to 1 and the south wall
of (2,0) has been set to 1.Only one ‘0’ exists, and the robot turns
right.
|
|
Step 4
| Location |
(2,1) = 3 3 3 1 |
| Mode |
Backtrack |
| Heading |
West |
| Decision |
Back |
|
Dead end. The robot turns around and backtracks, The west wall is
‘1’, so it goes that way.
|
|
Step 5
| Location |
(2,0) = 3 3 1 3 |
| Mode |
Backtrack |
| Heading |
West |
| Decision |
Left |
|
In (2,0), the robot has set the wall (east) it has just come through to a 3. It
is still in Backtrack mode, so it follows the ‘1’ code of the south
wall, and turns left.
|
|
Step 6
| Location |
(1,0) = 3 0 1 3 |
| Mode |
Search |
| Heading |
South |
| Decision |
Left |
|
In (1,0), a code of 0 is found in the east wall, so the robot switches from
backtrack to search. The north wall code of (1,0) has been set to a 3.
|
|
Step 7
| Location |
(1,1) = 3 0 3 1 |
| Mode |
Search |
| Heading |
East |
| Decision |
Forward |
|
Searching again, the east wall of (1,0) has been set to a ‘1’, and
the west wall of (1,1) has been set to a ‘1’. Continue forward.
|
|
Step 8
| Location |
(1,2) = 0 3 0 1 |
| Mode |
Search |
| Heading |
East |
| Decision |
Right |
|
Still in search mode, the east wall of (1,1) has been set to a ‘1’,
and the west wall of (1,2) has been set to a ‘1’.
|
|
Step 9
| Location |
(0,2) = 1 3 3 0 |
| Mode |
Search |
| Heading |
South |
| Decision |
Right |
|
Still in search mode.
|
|
Step 10
| Location |
(0,1) = 3 1 3 3 |
| Mode |
Backtrack |
| Heading |
West |
| Decision |
Back |
|
Another deadend, so backtrack.
|
|
Step 11
| Location |
(0,2) = 1 3 3 3 |
| Mode |
Backtrack |
| Heading |
East |
| Decision |
Left |
Step 12
| Location |
(1,2) = 0 3 3 1 |
| Mode |
Search |
| Heading |
North |
| Decision |
Forward |
|
Another code of ‘0’, so another branch starts here. Switch from
backtrack to search mode.
|
|
Mode: Return Home
| Step 13 |
|
| Location |
(2,2) = 3 3 1 3 |
| Heading |
North |
| Decision |
Back |
| |
| Step 14 |
|
| Location |
(1,0) = 0 0 1 3 |
| Heading |
South |
| Decision |
Right |
| |
| Step 15 |
|
| Location |
(1,0) = 0 0 1 3 |
| Heading |
West |
| Decision |
Forward |
Step 16
| Location |
(1,0) = 0 0 1 3 |
| Heading |
West |
| Decision |
Right |
| |
| Step 17 Completed |
|
| Location |
(1,0) = 0 0 1 3 |
| Mode |
Complete |
| Heading |
South |
| Decision |
Stopped |
|
Back to the starting square. Note the four '3's in the start cell, and that the
other cells have a single '1'. All '1's lead back to the start.
|
|
Posted by Kelly Small at October 7, 2004 10:06 PM
