Author: Koryn Grant
Copyright: 1998 Koryn Grant
Date: 10 June 1998
MazeGeneratorLib is a static library (on PowerPC/680x0) that creates mazes. The
interface to the library comprises 5 simple procedure calls for initialising the
internal data structures, setting the options, creating the maze, retrieving the
data and cleaning up. The mazes created are such that any two rooms in the maze are
guaranteed to be connected by one and only one path. The maze creation engine is
reasonably flexible, allowing the height, width and depth of the maze to be chosen
as well as the type of connections allowed between rooms. By default the allowed
directions are n, s, e, w, ne, nw, se, sw, up and down. These can be restricted to
the 4 cardinals, with a further feature being the ability to restrict connections
between XY, XZ or YZ planes. Once the maze has been created extra walls can be removed
at random in order to make the maze more open. To compile the MazeGeneratorLib from
the sources requires MyAssertions from Peter Lewis' PNL Libraries, available from
http://www.stairways.com/ , and KGLists,
available from Pascal Central http://www.pascal-central.com/
MazeGeneratorLib is written with CodeWarrior. Project files are included for CWPro3
(Maze Generator.µ) and CWPro2 (Maze Generator.old.µ). Source code and
a text listing of the project files (Maze Generator.µ.text) are included for
use with other environments.
In a nutshell, the maze is created by starting with every room completely sealed
off, then knocking out walls until all rooms are connected.
To be more precise, at any stage the maze is modelled by sets of rooms - two rooms
A and B are in the same set if there is a path in the maze from room A to room B.
Removing the wall between two rooms is equivalent to taking the union of the sets
containing them. Initially each room is in a set by itself, the goal being to end
up with every room in a single set. A first draft of the algorithm used is the following:
The important point about step 2 is that the wall chosen has to be "removable".
This means that it must not be a boundary wall (one leading to a room outside the
maze), it must not lead to a room in the same set as the randomly chosen room (this
guarantees that there can only be one path between rooms) and it must satisfy any
constraints imposed by the options selected for the maze. (The first two restrictions
on "removable" walls are always imposed, and so in the following discussion
I won't mention them again.)
The easiest constraint to satisfy is that on diagonal connections between rooms.
If diagonal connections are not permitted, then the algorithm above is unchanged;
however, a "removable" wall is considered to be one that connects rooms
in a north/south, east/west or up/down direction.
Slightly more difficult are the constraints (if imposed) on connections between
XY, XZ or YZ planes. For example, suppose the desired maze was to be 3x3x3, constructed
in such a way that it consisted of three 3x3 mazes stacked on top of each other with
only one up/down connection between floors. (This corresponds to setting ZConnections
to 1.) In this situation a wall that connects two rooms up/down is not considered
to be "removable" in the above algorithm, and the termination condition
must be altered to
When there are only three sets left these represent the three floors of the maze,
and all that remains is to knock out one wall connecting floors one & two, and
another connecting floors two & three:
Now there is only one set left, and at this stage any extra walls can be removed
to make the maze more open.
Here's a second draft of the algorithm that the MazeGenerator libraries use:
This is still a draft, because the algorithm as described above has a major flaw.
Exercise for the reader: determine what the flaw is and how to fix it. (The MazeGenerator
libraries use a slight modification of the above algorithm that eliminates the flaw.)
Internally the maze creation engine is written in Object Pascal, with the sets
of rooms implemented as singly-linked lists. The reason I chose to use an OO style
rather than straight procedural Pascal is that I already have an OO implementation
of singly-linked lists (used heavily in SlashMUD)
which has been thoroughly stress-tested. Using this meant that I could sub-class
my existing list objects, thus reusing my SlashMUD
code, and concentrate on coding the algorithm.
Although an hour to create a thousand-room maze may seem slow, this is a huge
maze. For my purposes (creating mazes for SlashMUD),
MazeGeneratorLib is sufficiently fast on my 6100/66. I have personally gotten lost
in the first maze I connected to the SlashMUD example area, which was 4x4x4 with
no diagonal directions. Using a 10x10x10 would all but guarantee that players would
never find their way out. Not that I'm in any way, shape or form suggesting that
this is a bad thing...
Download Maze Generator