A Maze of Concepts

C++ Classes for Generating Random Mazes

by Scott Robert Ladd, drawings by Maria Alvarado Ladd
1 July 2002

Index
  Defining the Spell
  Classes & Algorithms
  The Final Result
Sidebars
  Exception handling
  Interfacing to C
  Namespaces
Documentation
  libcoyote (all classes)
  maze class
  maze_renderer class
  architect class
Downloads
  libcoyotl-3.0.0.tar.gz

Ever since I first read of Merlin as a child, my goal has been to be a wizard. But unlike many childhood dreams, this one actually came true; today, I'm a conjurer, creating something from nothing, beginning with a blank page and writing arcane formulae that produce wondrous new things. I am a computer programmer, a summoner of bits and bytes, a creator of programs. Overly poetic, perhaps — but I find that a healthy dose of wonder makes coding ever so much more fascinating. If we reduce programming to its mundane aspects, we produce mundane software, I think.

Engineers construct reality by employing the forces of nature as identified by scientists; true magic — not that silly sleight-of-hand stuff, mind you — is the application of advanced technology to solving complex problems. As the incomparable Arthur C. Clarke once said: Any sufficiently advanced technology is indistinguishable from magic.

Defining the Spell

I began with an idea for an experiment: Use genetic algorithms to evolve searching skills in software organisms; such research is applicable to many applications, including web searching and data mining. I've puttered about with several such algorithms, and wanted to move to a more complicated environment.

Mazes provided an elegant environment for artificial evolution. After all, scientists have been running mice through mazes for quite some time in an effort to glean biological and psychological information; you'll also find robots negotiating mazes, in pursuit of knowledge.

An additional benefit of this project: My wife loves to solve mazes, and now I can keep her supplied to her heart's content.

Writing a program is much like developing a spell -- you start by defining what you want to accomplish. Here's the list I began with:

Portability
The maze software must be 100% portable, yet efficient. Given the requirements above, and my own views on programming languages, I chose to work in Standard C++. While the initial application runs from the command-line, nothing in the code prevents its use in a graphic application. In later installments, I'll present a Java GUI wrapper for the C++ code, and connections to other languages.
Extensibility
My primary goal is to use labyrinth navigation is a fitness test for evolving algorithms. And I wanted to print mazes for my wife and kids. Thus a "maze" is encapsulated as a generic concept; that requires an object-oriented approach, where a maze object is not task-specific.
Algorithmic flexibility
A maze can be created in a variety of ways; the technique present herein is a simple recursive algorithm, which generates challenging, twisty mazes. However, there's no need to limit the software to a single maze-generating algorithm — a future application might require minimal spanning trees, for example. So the "carving" of a maze needed to be "pluggable," through a polymorphic class.
Image creation
The software must draw a maze's image, for either printing or display. To that end, the code draws to PNG ("ping") files, using the popular libpng library of tools. After all, a good wizard only reinvents the wheel when it is absolutely necessary, and libpng is a proven set of portable tools. To keep the software flexible, rendering is external to the maze class, interrogating an object for the information needed in drawing an image. That will make it easier to add other image formats in the future.

Persistence
One more requirement is the ability to save mazes for future reuse and reprinting, using standard istream objects as the data store. Persistence is integrated directly into maze, since the class "knows" its internal structure and is thus best equipped to save and restore objects of its type.

Classes & Algorithms

To avoid name conflicts, I define all classes inside the namespace libcoyote, the standard namespace I use for my general purpose libcoyote library. The diagram at left describes the high-level structure of the maze classes.

In any object-oriented project, encapsulation and separation of function determine class structure. The design suggests a core maze class that defines the data structure of a maze -- dimensions, wall placement, and entrance and exit locations. The maze class does not include intrinsic support for rendering images or genetic algorithms; instead, it contains a generated set of tables used by algorithms implementing those features. As such, the class implements a variety of interrogation functions meant to provide read-only access to internal data.

Since several different algorithms can carve mazes with different characteristics, I saw the need for a polymorphic "architect" class, thus divorcing the carving algorithm from the data it generates. The abstract architect class is tightly bound to the maze data structures, and I defined it within the scope of maze, as a friend; it implements protected static methods that access the internal data of a maze.

The recursive_maze_architect class is a concrete implementation of architect for the depth-first carving algorithm. And while it may sound like starting my truck on a wet morning, the maze_renderer class actually generates a PNG image of a maze.

Let's look at some specific techniques I used to implement these classes.

maze & architect

The maze class is the largest in this package; each object has a width, a height, an entrance, an exit, and a two-dimensional array of cells that know the state of their four walls. The POD (plain old data, a Standard C++ term for intrinsic types) structure cell defines an object containing a four-element array of pointers to wall values; wall is an enumerated type with values for North, South, East, and West. A position structure is simply a pair of size_t values representing the row and column coordinates of a location within the maze.

The constructor dynamically allocates wall objects during maze construction, assign their pointers to adjacent cells. For example, the south wall of m_cells[0][0] is the north wall of m_cells[0][1]; both pointers reference the same wall object. Such a design makes maze generation very easy, as you'll see when we look at recursive_maze_generator.

The maze class does not implement a public constructor; instead, a pair of static member functions create maze objects from architect and istream sources. This technique hides the default constructor while providing specific creation functions that "build" on "blank" maze objects. The private constructor simply generates an empty maze, with all walls standing; the generate function creates a new maze using the constructor, and then calls a supplied architect object's create_floor_plan method to carve the pattern. The load method creates a new maze after reading dimension and wall data from an istream. By using the static creation functions (known as named constructors), I hide the maze constructor that is not suitable for public consumption.

Why incorporate persistence directly into the maze class, while separating image generation in a separate class?

Such design choices often depend more on philosophy and not on technical constraints. In my mind (a strange place, admittedly!), image generation is a read-only process that extracts information from a maze without altering it. Persistence, on the other hand, is an invasive read/write procedure that requires intimate interaction with the maze data structure.

recursive_maze_architect

The recursive back-tracking algorithm begins by selecting an "entrance" cell, opening the outside wall, and then following this recursive algorithm: Pick a random direction, and move to the adjoining cell in that direction, if you haven't visited it before. Push the previous cell location onto a stack, knock out the wall between the cell you came from and the one you're in, then move to another randomly-selected adjacent cell. Repeat the process until you reach a place that is surrounded by cells that have all already been visited. At this point, pop cells off of the stack until you find one that does have an unvisited neighbor, and start carving again. The result is a maze with a long twisty solution and lots of long dead ends.

The recursive_maze_architect class implements this algorithm in the form defined by maze::architect, by implementing the virtual function create_floor_plan. The algorithm begins by defining a set of permutations of the four directions; each time the algorithm needs to move to a new cell, it randomly selects one of these permutations and uses it to define the search order for finding an unvisited neighbor cell. I use a std::deque to track previously-visited cells. comments in the code should lead you through the carving process.

maze_renderer

Generating a PNG image from a maze requires the libpng and zlib (libz) libraries; most Linux distributions include these, and you can obtain source for these packages at their respective web sites.

maze_renderer creates monochrome PNG images from a maze; you can see three examples on this page. The nested image class encapsulates bit data generated from the maze file; the maze_renderer::render function translates that raw bit pattern into a simple PNG image, which is written to a specified file name. An argument to render defines the width of corridors; the image constructor will throw an exception if given a grid_size less than 2, since a small value would make no sense.

testmazes

The maze include a simple command-line test program that exercises the maze classes. By default, the program generates a 20-by-20 maze, writes it to a PNG image, saves the maze as a data file, restores it, and writes a second image that can be verified by comparison against the first. Command-line arguments let a user to set the size of the maze and image file names.

I write this sort of console program as a unit test, creating a suite of test programs at each stage of development. As a project grows in size, it's often necessary to retest components; unit tests provide focused, incremental environments for assuring code quality and reliability.

The Final Result

I've produced quite a few mazes with this software, and it works well in several applications. The development path for the overall project includes the implementation of other "carving" algorithms, a discussion of "random" number generators, the introduction of a generic genetic algorithm framework, and creation of the final application. Along the way, I'll be adding new sidebars, and digressing into issues like Java-C++ interoperability.

As always, I'm interested in feedback from my readers. Drop me an e-mail, and I'll develop an article where I respond to your questions and comments.

And now on to the next incantation...

- Scott