Koryn's Units
Koryn Grant, Macintosh Developer



pascalflavouredmac picture

Maze Generator

Author: Koryn Grant
Copyright: 1998 Koryn Grant
Email: koryn@kagi.com
Date: 10 June 1998

Summary

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/ .

Environment

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.

The algorithm

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:

  1. Put each room in a set by itself.
  2. Pick a room at random, and pick a random wall within that room.
  3. If this wall is "removable" then remove it, and join the sets containing the two rooms which had that wall. If the wall is not "removable", proceed to step 4.
  4. Repeat from step 2 until only one set remains.

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

  1. Repeat from step 2 until only three sets remain.

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:

  1. Knock out walls to satisfy any constraints on connections between XY, XZ or YZ planes.

Now there is only one set left, and at this stage any extra walls can be removed to make the maze more open.

  1. Knock out the specified number of extra walls to be removed at random.

Here's a second draft of the algorithm that the MazeGenerator libraries use:

  1. Put each room in a set by itself.
  2. Pick a room at random, and pick a random wall within that room.
  3. If this wall is "removable" then remove it, and join the sets containing the two rooms which had that wall. If the wall is not "removable", proceed to step 4.
  4. If there are no constraints on connections between planes then repeat from step 2 until only one set remains. Otherwise, repeat from step 2 until the number of remaining sets is equal to the dimension of the direction in which the constraints apply (think about it :)
  5. If necessary, knock out walls to satisfy any constraints on connections between XY, XZ or YZ planes.
  6. Knock out the specified number of extra walls to be removed at random.

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.)

Implementation

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.

The files

Maze options

Timings

Final comments

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...

Credits

Download Maze Generator



Copyright ©1998 Koryn Grant.