Maze Maker Concept

A Maze Maker has the job of building a maze graph on top of a Pattern.

Notation

MM is a type that models the Maze Maker concept.

Associated Types

Name Expression Description

Default policy MazeMakerTraits<MM>::DefaultPolicy If a Maze Maker can have more than one behavior with respect to maze making--without violating the characteristics that the other associated types convey--then this type determines which behavior to execute if no other policy is specified.

Random inputs required MazeMakerTraits<MM>::RequiresRandomInputs A Boolean Constant indicating whether or not an FSM Builder needs to randomize its inputs for each state before using this Maze Maker.

Restart on dead end MazeMakerTraits<MM>::RestartsOnDeadEnd A Boolean Constant indicating whether or not an FSM Builder needs to replace the dead-end states with the starting state after using this Maze Maker.

Last-visited map built MazeMakerTraits<MM>::BuildsLastVisitedMap A Boolean Constant indicating whether or not an FSM Builder can use the last-visited map stored in the maze graph after using this Maze Maker. If the value of this constant is false, then this Maze Maker cannot be used together with an FSM Input Maker that requires a last-visited map.

Name	Expression	Description
Default policy	`MazeMakerTraits<MM>::DefaultPolicy`	If a Maze Maker can have more than one behavior with respect to maze making--without violating the characteristics that the other associated types convey--then this type determines which behavior to execute if no other policy is specified.
Random inputs required	`MazeMakerTraits<MM>::RequiresRandomInputs`	A Boolean Constant indicating whether or not an FSM Builder needs to randomize its inputs for each state before using this Maze Maker.
Restart on dead end	`MazeMakerTraits<MM>::RestartsOnDeadEnd`	A Boolean Constant indicating whether or not an FSM Builder needs to replace the dead-end states with the starting state after using this Maze Maker.
Last-visited map built	`MazeMakerTraits<MM>::BuildsLastVisitedMap`	A Boolean Constant indicating whether or not an FSM Builder can use the last-visited map stored in the maze graph after using this Maze Maker. If the value of this constant is `false`, then this Maze Maker cannot be used together with an FSM Input Maker that requires a last-visited map.

Valid Expressions

The following expressions must be valid.

Name Expression Type Requirements Return Type

Maze making MM::makeMaze(maze, pattern, rng_engine, policy)

maze must be a reference to a MazeStruct object.

pattern must be a const reference to a Pattern object.

rng_engine must be a reference to a Random Number Generator Engine object.

policy must be a const reference to an instance of a maze policy class.

void

Name	Expression	Type Requirements	Return Type
Maze making	`MM::makeMaze(maze, pattern, rng_engine, policy)`	maze must be a reference to a `MazeStruct` object. pattern must be a const reference to a Pattern object. rng_engine must be a reference to a Random Number Generator Engine object. policy must be a const reference to an instance of a maze policy class.	`void`

Expression Semantics

Name Expression Precondition Semantics Postcondition

Maze making MM::makeMaze(maze, pattern, rng_engine, policy)

The results will be stored in the maze object.

If a Maze Maker can have more than one behavior with respect to maze making--without violating the characteristics that its associated types convey--then the policy object determines which behavior to execute; otherwise, it will be ignored.

Name	Expression	Precondition	Semantics	Postcondition
Maze making	`MM::makeMaze(maze, pattern, rng_engine, policy)`		The results will be stored in the maze object. If a Maze Maker can have more than one behavior with respect to maze making--without violating the characteristics that its associated types convey--then the policy object determines which behavior to execute; otherwise, it will be ignored.

Invariants and Runtime Complexity Guarantees

Runtime complexity is measured in turms of cell and connection count. The following invariants must hold.

Name Invariants Runtime complexity

Maze making Deterministic polynomial time

Name	Invariants	Runtime complexity
Maze making		Deterministic polynomial time

Models

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