Multi-State Mazes: Core Library API

The Standard Template Library should already be part and parcel of any decent C++ compiler.

The Boost Software Libraries are a must-have for anyone aspiring to be a great C++ programmer. If you're not familiar with them, these tutorials should get you better acquainted.

Swiss GD Knife is a small set of library modules used extensively by this library.

We intend for this library to work well with any graphics suite. The program that comes with the binary distribution was compiled using the Irrlicht 3D Engine.

Anatomy of a Maze

In most cases

finite state machine

FSM

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.

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?

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.

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.

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.

The Pattern concept encapsulates the underlying structure of a maze, with each room referred to as a cell.

The Maze Maker concept encapsulates a maze algorithm.

The FSM Input Maker concept provides the input needed to transition from the current cell to the next, using the last-visited cell when necessary.

The FSM Builder concept binds them all together and is used to initialize an FSM. Each model contains a specific Pattern, and its getStateCell() function will map any of the FSM's states to a cell in that pattern. Each model takes in any Maze Maker and almost any FSM Input Maker as initialization arguments, as well as the ones that the underlying pattern may require. Finally, each model associates itself with a specific Argument Validation Policy that checks all the initialization arguments to ensure that the maze is reasonably solvable.

Quick Recipe for a Multi-State Maze

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

     typedef boost::mt19937
             RNGEngine;
     typedef sgdk::IndexTypeFSM<
                 boost::numeric::ublas::matrix<unsigned int>
               , unsigned int
             >
             FiniteStateMachine;
     RNGEngine rng_engine;
     FiniteStateMachine fsm;

Pick an FSM Builder (and, if necessary, an FSM Input Maker) from the Core FSM Layer.

     typedef msmazes::ParallelepipedFSMBuilder <>
             Builder;
     typedef msmazes::FSMDirectionInputMaker
             InputMaker;
     Builder builder;

Pick a Maze Maker from the Core Maze Layer.

     typedef msmazes::WalkthroughMazeMaker
             MazeMaker;

Initialize the FSM Builder using the Random Number Generator Engine, the Maze Maker, the FSM Input Maker, and some additional parameters.

     typedef Builder::Pattern
             Tesselation;
     builder.initialize(
         rng_engine
       , 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.

Initialize the FSM using the FSM Builder.

     fsm.initialize(builder);

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()))
         {
             fsm.processInput(input);
         }
     }

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

Limitations

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.

Core Library API

Source Code Dependencies

Anatomy of a Maze

Quick Recipe for a Multi-State Maze

Limitations

License

Contact