ContentsDownload source
and binaries of TorqMaze 0.02 (C#) [^]
Download source
and binaries of TorqMaze 0.01 (C#) [^]
Maze created with TorqMaze 0.02 If you have any questions
or comments about this article: mail me [^].
Introduction
How can we build mazes fast and efficiently?
How can we find a way through a maze fast and efficiently?
I've dediced to spend a few days for these problems and this short article is
the outcome of my research.
Top  Maze generation
Maze generation algorithm is very intuitive. We start from a layout that has walls
between all cells. I will call such layout a foundation layout or just
a foundation. An algorithm consists in walking through the foundation and deciding
whether a wall could be removed. That's why it is really fast, it works in linear
time.
Let's make a fast summary. The algorithm:
- walks through the foundation layout in a random way
- at each step it decides if the wall that separates cells can be removed
Top Walking through the foundation layout in a random way
This could be easily achieved with simple recursion:
walk_layout( x, y )
{
if ( visited( x, y ) ) return;
create_random_permutation( p )_of_a_set_0_3
call_with_the_sequence_determined_by_p
{
walk_layout( x-1, y );
walk_layout( x+1, y );
walk_layout( x, y-1 );
walk_layout( x, y+1 );
}
}
This, alas, will not work for big foundations because the stack is limited. In practice,
with C# I failed to create a 64x64 maze because I got an obvious exception "Stack
overflow".
I solved this problem with iterative version of this algorithm. It required to implement
a stack that would be used while walking to store the current position and a value
saying which directions had been already tried.
For example, if we are in cell (4, 5) and we walk to cell (4, 6) then we push to
stack (4, 5, directions | direction.E).
If we reach a cell and we see that all directions were already checked, we just
pop the state from the stack and try different ways for this state.
Top Removing walls while walking through the foundation
The second problem with maze generation is the necessity to check if two cells are
already connected. It is important because every two cells should be connectned
with exactly one path. If source and destination cells are connected then the algorithm
aborts to remove the wall between them.
In practice this is not so simple to check if there is already a path between two
cells. Naive implementation would analyze whole maze generated to this moment!
I've decided to use a version of an algorithm said to be by Robert E. Tarjan. I
found a paper about it but it still looked quite messy and unnecessary complicated.
I've decided to simplify it.
This is the idea: in addidional table (called table of bases) we store the
information on connections between cells. We will refer this table by a cell index
( index(X, Y) = maze_width * Y + X ) and the table will hold two types of data:
- the number -1 - means that the cell is a tail of a chain of connected cells
- positive number - means a pointer, a number of next cell in a chain you
have to refer
Let's connect three cells (0, 0), (0, 1) and (0, 2) into one chain. We count the
indexes:
index(0, 0)=0, index(0, 1)=1, index(0, 2)=2The table of bases
will look like this:
[0] : -1
[1] : 0
[2] : 1
...
To compute the base cell of any given cell, we compute its index and then
we search the table of bases until we reach the tail (code from TorqMaze 0.01):
int base_cell( int tIndex )
{
int index = tIndex;
while ( maze_base[ index ] >= 0 )
{
index = maze_base[ index ];
}
return index;
}
Then if we would like to check if two cells C1 i C2 are conencted we just compute
thier base cells. If base cells are equal then C1 and C2 are in the same chain.
This is because two separated chains can be merged together to form a new chain.
We do this by changing the base pointer of one chain:
void merge( int index1, int index2 )
{
// merge both lists
int base1 = base_cell( index1 );
int base2 = base_cell( index2 );
maze_base[ base2 ] = base1;
}
For example two separated chains
[0] : -1
[1] : 0
[2] : 1
and
[3] : -1
[4] : 3
[5] : 4
will be merged as:
[0] : -1
[1] : 0
[2] : 1
[3] : 0
[4] : 3
[5] : 4
Notice that base_cell() for each cell in this chain is equal to 0 and this means
that all cells are in one chain.
Top Combining of maze walking with removing of walls
Both parts of the maze algorithm are done in one pass. I remove a wall if it does
not produce a cycle in the maze. I store the wall info in special data structures.
Interface of TorqMaze 0.01
Top Path finding
There are a lot of tricky algorithms for path finding in mazes. I will present
one of the most reliable but quite memory demanding (it requires a temporary table
as big as the maze)
The algorithm is quite simple. I will provide an example:
In that temporary tablie (let's call it mazePath) we will build an image
of the path between source and destination point. At the beginning we'll fill the
table with -1.
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
We start by putting the value of 0 into the source point.
| 0 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
Then we do an i-step until we reach the destination point:
- all points that are neighbours to points filled in previous step and are
not filled yet should be filled with the value of i only if we follow
the maze (we are not allowed to go through the walls)
The interpretation is simple - in i -step we mark fields that are reachable
with ... i steps. Let's look at the example:
| 0 |
1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| 0 |
1 |
-1 |
-1 |
| -1 |
2 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
| 0 |
1 |
-1 |
-1 |
| 3 |
2 |
3 |
-1 |
| -1 |
3 |
-1 |
-1 |
| -1 |
-1 |
-1 |
-1 |
...we can reach 3 fields in 3 steps...
...
| 0 |
1 |
-1 |
-1 |
| 3 |
2 |
3 |
-1 |
| 4 |
3 |
8 |
-1 |
| 5 |
6 |
7 |
8 |
...and we reach the dest point in 8 steps!
At this time the first part of the algorithm is finished. The only thing that
we have to do is to build the path. To do it we follow the consecutive numbers from
8 to 0, starting at the destination point and ending at start point. The path is
ready.
All the details of the implementation can be found in the source of TorqMaze
0.02. As the excercise, you should try this algorithm with more complicated
mazes.
Top
About
Wiktor Zychla
Click here if you want to know more about
Wiktor Zychla.
Other articles that may interest you
|