The Maze Construction FAQ
=========================
Version 1.3 17th March 1998
----------------------------
This FAQ is maintained by "hexapod@netcom.com". Any additional suggestions
or related questions are welcome. Just send E-mail to the above address.
The latest copy of this FAQ can be found at the following web page:
ftp://ftp.netcom.com/pub/he/hexapod/index.html
Feel free to distribute or copy this FAQ as you please.
Questions
---------
MAZE CONSTRUCTION
=================
Q1. What is a maze?
Q2. How do I represent a maze?
Q3. How do I generate a 3D model of a maze?
Q4. How do I generate a random maze?
Q5. How can I optimise the generation of random mazes?
Q6. How can I use "equivalence" to speed up maze generation?
Q7. How can I customise the generation of a maze?
Q8. How do I save a maze to a file?
Q9. How do I convert a maze to a 3D model?
Answers
-------
Q1. What is a maze?
--------------------
A maze or labryinth is a collection of rooms or chambers which are
connected in an unstructured way. Each room has at least one pathway
which connects it to other rooms.
If a maze has N rooms, then it must have at least N-1 pathways in
order for every room to be accessible.
If more than N-1 paths ways exist, then it is possible to have pathways
which double back on themselves. These are referred to as "loops".
Mazes need not be constrained to an Euclidean system. They may
be arranged in a rectangular shape, hexagonally or even on the surface
of a sphere.
+----------------------------+ +---------------------------+
| Rectangular maze | | Hexagonal maze |
| | | |
| | | +-+ +-+ |
| +--+--+--+--+--+--+ | | / \ / \ |
| | | | | | | +-+ +-+ +-+ |
| + + + + +--+--+ | | / / \ |
| | | | | | | + +-+ +-+ + |
| +--+--+ +--+--+ + | | \ / / |
| | | | | +-+ +-+ +-+ |
| +--+--+--+ +--+ + | | / / \ \ |
| | | | | | + +-+ +-+ + |
| + +--+--+--+ | | | | \ \ / |
| | | | | | | +-+ +-+ +-+ |
| +--+--+--+--+--+--+ | | \ / \ / |
| | | +-+ +-+ |
| | | |
+----------------------------+ +---------------------------+
A maze may also have an exit, a special path which leads out of the
maze and completes the game, or which even leads to another maze.
Q2. How do I represent a maze?
-------------------------------
For two and three dimensional mazes, the most efficient method of
data representation is through the use of integer arrays. Each
possible direction is represented by a predefined integer bit eg.
+----------------------------------------------------------------+
| |
| North = 0x01 Bit 0 North (0x01) |
| East = 0x02 1 #---# |
| South = 0x04 2 | | |
| West = 0x08 4 West(0x08) | | East (0x02) |
| Up = 0x10 8 | | |
| Down = 0x20 16 #---# |
| South (0x04) |
| |
+----------------------------------------------------------------+
However, it is important to remember whether each bit set to one
represents a pathway which is accessible or blocked. In the following
examples, any bit which is non-zero represents a pathway which is
accessible.
Thus, a value of 0x01 represents a dead-end with an East exit,
and a value of 0x3F represents a room with every possible exit
available:
For a two dimensional maze, 16 different possible combinations of
room exist:
+--------------------------------------------+
| |
| 0x0 0x01 0x02 0x03 0x04 0x05 0x06 0x07 |
| |
| +-+ + + +-+ + + +-+ + + +-+ + + |
| | | | | | | | | | | | | |
| +-+ +-+ +-+ +-+ + + + + + + + + |
| |
| |
| 0x08 0x09 0x0A 0x0B 0x0C 0x0D 0x0E 0x0F |
| |
| +-+ + + +-+ + + +-+ + + +-+ + + |
| | | | | |
| +-+ +-+ +-+ +-+ + + + + + + + + |
| |
+--------------------------------------------+
A 3D maze will require a 3-dimensional array of integer data. However,
in order to implement dynamic memory allocation, it is more convenient
to use a one-dimensional linear array and handle the indexing through
the use of utility functions.
A simple data structure to represented a maze is shown below:
----------------------------------------------
typedef unsigned char MAZEROOM;
typedef struct maze_st
{
int m_width; // Width of the maze in rooms
int m_height; // Height of the maze in rooms
int m_depth; // Depth of the maze in rooms
int m_floornum; // Number of rooms per floor (width *height)
MAZEROOM *m_data; // List of rooms
} MAZE;
// Room indexing macro
#define MAZE_INDEX( M X, Y, Z \
return( ( (Z)*maze->m_floornum+ (Y) *maze.width + (X) )
----------------------------------------------
Q3. How do I generate a 3D model of a maze?
--------------------------------------------
In order to generate a random maze represented as a 3D model, three
stages of processing are performed:
1. Getting parameters of the maze (width, height, depth, corridor length )
2 Generating the random maze using the data representation
3. Converting the data representation to a 3D model
Stage 1 is fairly straightforward. The required dimensions of the maze
can be either pre-defined or selected from the game.
Stage 2 performs all of the hard work. It must generate the random maze
using the desired data representation, and save the connection data for
use by stage 3.
Stage 3 is also fairly straightforward. At the very minimum it only needs
to process each room one at a time and generate a set of polygons.
However, it may be necessary to convert the model into a BSP tree. In
any case this is an application problem rather than a maze generation
problem.
Q4. How do I generate a random maze?
------------------------------------
Assuming that the size of the maze are known and that an integer array
has been allocated and cleared, the next stage is to actually generate
the maze.
There are several algorithms which can be used to do this. These are
arranged in order of complexity:
o Single link at a time
o Single direction at a time
o Keep going in a spiral
o keep going in a zig-zag
For a three-dimensional maze with dimensions width W, height H and
depth D, WxHxD-1 links are required.
For all methods, the first pathway is generated at random.
The "single link at a time" method requires that one room which is
presently connected to another room is selected randomly and attached
to an adjacent room which has not yet been connected.
The "single direction at a time" method, operates similar to the "single
link" method, except that once a link has been made, the previously
unattached room is used as the starting point for the next link and
the process continues until no more links can be made in that direction.
The "keep going in a spiral" method, operates identical to the "single
direction at a time" except that it attempts to change direction whenever
the current direction is blocked. For 3D mazes, an anticlockwise search
pattern followed by a move upwards or downwards can generate some
interesting patterns (Borg cubes :)
The "zig-zag" method, operates similar to the "single direction at a time"
method, except that it always changes direction after each link has been
made. The direction always oscillates between two paths eg. North and East.
If the current direction is blocked, a new path is chosen.
Q5. How can I optimise the generation of random mazes?
-------------------------------------------------------
One speedup is to maintain a list of unvisited rooms - this need only
store a linear index ID for each room. As each room is visited, the ID
is removed from this list. Processing continues until this list is empty.
Q6. How can I use "equivalence" to speed up maze generation?
-------------------------------------------------------------
Another speedup is to use "equivalence". Using this method, each room
maintains a corridor group ID, indicating which corridor group it
belongs to. A separate integer array indicates when this corridor group
has made a connection to another corridor group.
This array stores the lowest group ID number of all the corridors that
can be reached from rooms which belong to that group. eg.
+--+ +--+ +--+
| 1|==| 2|==| 2| In this 3x3 maze, a negative ID indicates that the
+--+ +--+ +--+ room is not connected.
||
+--+ +--+ +--+ Corridors #2 and #4 are connected to corridor #1
| 1| | 3|==| 3|
+--+ +--+ +--+ Corridor #3 is not connected to any other corridor.
||
+--+ +--+ +--+
| 4|==| 4| |-1| A corridor of #-1 indicates the room is not connected.
+--+ +--+ +--+
The equivalence array is as follows:
Corridor ID Equivalent (EID)
1 1
2 1
3 3
4 1
Rooms can be generated totally at random, without having to worry about
whether rooms are already connected or not. The list is updated according
to the following rules:
o Both rooms are unconnected - A new corridor ID is generated and added
to the array - this is saved into both rooms. When a new corridor group
is created, its EID is set to its ID number.
o One room is connected - The unconnected room inherits the group ID from
the connected room. No change is made to the array.
o Both rooms are connected - A check has to be performed to make sure
that the two corridors are not already connected.
The EID of each room is examined to see if it is equal to the corridor
ID. If not, then the EID is read and used as the CID. This is repeated
until they match ie.
corr_id = get_room_id( x, y, z )
orig_id = corr_id
equiv_id = equiv_array[CID]
while ( equiv_id != corr_id )
corr_id = equiv_id
equiv_id = equiv_array[corr_id]
endwhile
Once this is done for both rooms, a comparison can be made between
the two rooms. If the two EID's match, then the rooms are already
connected.
If not, the two rooms are connected together and the EID for the room
with the highest corridor ID is set to the lowest of the two final
EID's. Generation of the maze then continues.
Q7. How can I customise the generation of a maze?
--------------------------------------------------
The mazes generated are guaranteed to prevent any cycles or loops, where
a player may keep going round in circles. However, this may be required
in order to make a game more entertaining. This feature can be
implemented simply by adding more links at random.
Note that no paths lead out of the maze - this may be changed if
required to allow "escape from the maze" type games.
Q8. How do I save a maze to a file?
------------------------------------
Once the maze has been generated, the next stage is to convert it into
an ASCII or binary data file so that it can be used by other
applications.
The best way to save the data is to use direction labels, which
determine which directions are available in any room of the maze.
The dimensions of the maze also have to be saved eg. width, height
and depth.
Each room can be saved either as an integer value, or by ASCII letters
which represent each direction that can be travelled.
For example a 3x3x1 maze might be save as follows:
+------------------+
| |
| #maze 3 3 1 |
| #data SE WE WS |
| #deta NE WS S |
| #data E WNE WN |
| |
+------------------+
Q9. How do I convert a maze to a 3D model?
-------------------------------------------
Now that the shape of the maze is known, the next stage is to convert it
into a polygonal model. The simplest way of building up the model is to
convert each room into a suitable piece of geometry.
Given N bits, there are 2^N different type of polygon model that can be
defined eg. For 4 bits, there are 16 types of room ie:
+------------------------------------------+
| |
| 0 1 2 3 4 5 6 7 |
| +-+ + + +-+ + + +-+ + + +-+ + + |
| | | | | | | | | | | | | |
| +-+ +-+ +-+ +-+ + + + + + + + + |
| |
| 8 9 10 11 12 13 14 15 |
| +-+ + + +-+ + + +-+ + + +-+ + + |
| | | | | |
| +-+ +-+ +-+ +-+ + + + + + + + + |
| |
+------------------------------------------+
This extends to 32 differnt types if all six directions are available.
The simplest method of representation is to use a single cube for each
room. In this case a single missing face represents an open path-way.
The complexity of the maze geometry only depends on the available
rendering engine. A basic model using cubes need only use a maximum of
six polygons per room. More complex models may use cylinders and
spheres to give the maze an abstract look.
It is also possible to use more than one 3D model to represent rooms
with the same combination of pathways. By selecting between these on a
random basis, it is possible to enhance the variery of the environment.