MazeGenerator 1.0
Koryn Grant, Pascal Developer



MazeGenerator 1.0

By Koryn Grant
7 April 1998

Contents

Download
Overview
The Alogrithm
Implementation
The Files
Maze Options
Timings


Download

MazeGenerator 1.0 binary download

MazeGenerator 1.0 binhex download

Overview

MazeGeneratorLib is a shared library (on PowerPC)/library (on 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 finishing. 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.

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

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

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

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

NOTE: Click here to download the whole ball of wax.

Maze Options

Timings


Copyright ©1998 Koryn Grant

Web page by Bill Catambay
Updated: 9-Apr-1998