Core Library API

Source Code Dependencies

You must have the following C++ libraries installed before attempting to compile any program using this library.

Anatomy of a Maze

In most cases, we can simulate the navigation of a maze by using a finite state machine, or FSM. Each state corresponds to a room in the maze; the FSM processes an input when we attempt to leave the room. When the FSM reaches its target state, we solve the maze.

Swiss GD Knife provides a finite state machine class that we can use to simulate maze navigation. The class owns a getCurrentState() function, a processInput() function, a boolean hasReachedTargetState() function, and even a reset() function when it is necessary to start over. That leaves us two ingredients to produce: an object that builds the FSM, and a mapping from the FSM's states to the maze's rooms. The primary function of this library is to provide exactly these ingredients. The process is rather complex, so we should identify what we need to facilitate it.

  1. First, we need to know what the underlying structure of the maze is. Is it a rectangular grid? Is it a beehive? Is it even physical?
  2. Next, we need to know what type of maze we're going to make. Is it an undirected spanning tree or an arrow maze? Will it have loops, dead ends, or both? It is vital that the choice of maze and the choice of underlying structure remain independent of each other as much as possible, to ensure the greatest potential reuse of even the most traditional maze creation algorithms.
  3. Then, there is the matter of precisely how we will navigate the maze, and the user interface influences the way we send inputs to the FSM. If the maze is two-dimensional and our view is from the top down, then our inputs may correspond to cardinal points on a compass. On the other hand, if we're using a three-dimensional, first-person interface, then a set of commands like "go straight", "make a right", or "turn around" may be more appropriate.
  4. Regardless of the type of input the FSM will end up processing, certain combinations of maze type, maze structure, and endpoints may produce a degenerate maze. For example, if the maze is a no-left-turn maze and the underlying structure is a rectangular grid, then a user that enters the maze facing a direction that puts his or her right hand on a wall will either end up trapped in the maze or walk through a trivial solution path. We should validate our initialization arguments to protect the user from these occasions.

The Multi-State Mazes Core Library provides STL-like concepts whose models (C++ classes) fulfill the requirements outlined above.

Quick Recipe for a Multi-State Maze

  1. Construct a Random Number Generator Engine and a Finite State Machine.

         typedef boost::mt19937
         typedef sgdk::IndexTypeFSM<
                     boost::numeric::ublas::matrix<unsigned int>
                   , unsigned int
         RNGEngine rng_engine;
         FiniteStateMachine fsm;
  2. Pick an FSM Builder (and, if necessary, an FSM Input Maker) from the Core FSM Layer.

         typedef msmazes::ParallelepipedFSMBuilder <>
         typedef msmazes::FSMDirectionInputMaker
         Builder builder;
  3. Pick a Maze Maker from the Core Maze Layer.

         typedef msmazes::WalkthroughMazeMaker
  4. Initialize the FSM Builder using the Random Number Generator Engine, the Maze Maker, the FSM Input Maker, and some additional parameters.

         typedef Builder::Pattern
           , MazeMaker()
           , InputMaker()
           , msmazes::OrthogonalTesselationSelector()
           , Tesselation::createCell(1.0, 0.0, 0.0)
           , Tesselation::createCell(3.0, 3.0, 0.0)
           , Tesselation::createCellIncrement(1.0, 1.0, 1.0)
           , Tesselation::createCell(0.0, 1.0, 0.0)
           , Tesselation::createCell(4.0, 2.0, 0.0)

    Each FSM Builder uses a corresponding Pattern from the Core Pattern Layer, where a few of these parameters are documented more thoroughly.

  5. Initialize the FSM using the FSM Builder.

  6. You can now simulate the navigation of a maze!

         const Tesselation& parallelepiped = builder.getPattern();
         while (!fsm.hasReachedTargetState())
             unsigned int state = fsm.getCurrentState();
             renderCurrentMazeRoom(builder.getStateCell(state), parallelepiped);  // User-defined
             int input = getInputFromUser();  // User-defined
             if ((-1 < input) && (input < parallelepiped.getMaxOutDegree()))

The documentation for each model of the FSM Builder concept provides additional examples that put this recipe into action.


Multi-State Mazes isn't as fully featured as it should be. Future versions will incorporate the following features:

The following features need more research to design and implement, but are definitely worth consideration:

These lists are not exhaustive, of course; more items will be added to them as the need for them grows.


The Multi-State Mazes Core Library is distributed under the terms of the GNU General Public License. The Free Software Foundation can explain it better than I can, but basically if you want to use our code in your program, you can sell, share, or give away your software as long as your customers also have the same distribution and selling rights you received; in other words, you also need to distribute your software under this license.


Hi, I'm Cromwell D. Enage, the project admin. Let me know whether or not you find this library useful for yourself and/or for others.

Multi-State Mazes in C++ is hosted by Use the Table of Contents for navigation.