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.
The Multi-State Mazes Core Library provides STL-like concepts whose models (C++ classes) fulfill the requirements outlined above.
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. 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.
SphereFSMBuilder
. 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.
Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.