FSM Builder Concept

An FSM Builder fulfills the requirements imposed by the sgdk::IndexTypeFSM. class template for initializing a finite state machine, so that it can be used to simulate the navigation of a maze.

Notation

FSM_Builder is a type that models the FSM Builder concept.
fsm_builder is an object of type FSM_Builder.

Associated Types

Name Expression Description

State index type FSM_Builder::StateIndex The type that represents the index of a vertex in the underlying maze graph.

Input index type FSM_Builder::InputIndex The type that represents the index of an edge in the underlying maze graph.

Maze graph type FSM_Builder::MazeGraph The type of the underlying maze graph.

Pattern type FSM_Builder::Pattern The type of the underlying Pattern.

Cell type FSM_Builder::Cell The type of the cells in the underlying pattern.

Edge direction type FSM_Builder::Direction A type for representing the course or bearing that is followed when traversing an edge in the underlying pattern's internal graph.

Argument validation policy FSM_Builder::ArgumentValidationPolicy The Argument Validation Policy that determines how this FSM_Builder will accept or reject the arguments to its initialization.

Name	Expression	Description
State index type	`FSM_Builder::StateIndex`	The type that represents the index of a vertex in the underlying maze graph.
Input index type	`FSM_Builder::InputIndex`	The type that represents the index of an edge in the underlying maze graph.
Maze graph type	`FSM_Builder::MazeGraph`	The type of the underlying maze graph.
Pattern type	`FSM_Builder::Pattern`	The type of the underlying Pattern.
Cell type	`FSM_Builder::Cell`	The type of the cells in the underlying pattern.
Edge direction type	`FSM_Builder::Direction`	A type for representing the course or bearing that is followed when traversing an edge in the underlying pattern's internal graph.
Argument validation policy	`FSM_Builder::ArgumentValidationPolicy`	The Argument Validation Policy that determines how this `FSM_Builder` will accept or reject the arguments to its initialization.

Valid Expressions

The following expressions must be valid.

Name Expression Type Requirements Return Type

Initialization fsm_builder.initialize(model-specific arguments) This function must be able to accept arguments by name. bool

Pattern access fsm_builder.getPattern() const FSM_Builder::Pattern&

Maze graph access fsm_builder.getMazeGraph() const FSM_Builder::MazeGraph&

Readiness fsm_builder.isReady() bool

Transition function building fsm_builder.buildTransitionFunction(transition_function) transition_function must be an instance of sgdk::IndexTypeTransitionFunction. void

Source state access fsm_builder.getSourceState() FSM_Builder::StateIndex

Target state access fsm_builder.getTargetState() FSM_Builder::StateIndex

Solvability fsm_builder.hasSolutionFromState(state) state must be convertible to FSM_Builder::StateIndex. bool

Solution access fsm_builder.getCorrectInput(state) state must be convertible to FSM_Builder::StateIndex. FSM_Builder::InputIndex

Cell access fsm_builder.getStateCell(state) state must be convertible to FSM_Builder::StateIndex. const FSM_Builder::Cell&

Direction from state fsm_builder.getStateDirection(state) state must be convertible to FSM_Builder::StateIndex. FSM_Builder::Direction

Name	Expression	Type Requirements	Return Type
Initialization	`fsm_builder.initialize(`model-specific arguments`)`	This function must be able to accept arguments by name.	`bool`
Pattern access	`fsm_builder.getPattern()`		`const FSM_Builder::Pattern&`
Maze graph access	`fsm_builder.getMazeGraph()`		`const FSM_Builder::MazeGraph&`
Readiness	`fsm_builder.isReady()`		`bool`
Transition function building	`fsm_builder.buildTransitionFunction(transition_function)`	`transition_function` must be an instance of `sgdk::IndexTypeTransitionFunction`.	`void`
Source state access	`fsm_builder.getSourceState()`		`FSM_Builder::StateIndex`
Target state access	`fsm_builder.getTargetState()`		`FSM_Builder::StateIndex`
Solvability	`fsm_builder.hasSolutionFromState(state)`	`state` must be convertible to `FSM_Builder::StateIndex`.	`bool`
Solution access	`fsm_builder.getCorrectInput(state)`	`state` must be convertible to `FSM_Builder::StateIndex`.	`FSM_Builder::InputIndex`
Cell access	`fsm_builder.getStateCell(state)`	`state` must be convertible to `FSM_Builder::StateIndex`.	`const FSM_Builder::Cell&`
Direction from state	`fsm_builder.getStateDirection(state)`	`state` must be convertible to `FSM_Builder::StateIndex`.	`FSM_Builder::Direction`

Expression Semantics

Name Expression Precondition Semantics Postcondition

Initialization fsm_builder.initialize(model-specific arguments) If the argument validation policy in effect accepts the specified arguments, initializes this FSM_Builder and its underlying pattern, then returns true; otherwise, returns false. The parameters to be recognized are model-specific; consult the documentation for that model for details. fsm_builder.isReady() == true if and only if either this or a previous fsm_builder.initialize() call has returned true. Enforcing this postcondition allows applications to recover gracefully from a failed attempt at initialization.

Pattern access fsm_builder.getPattern() Returns a const reference to the underlying pattern.

Maze graph access fsm_builder.getMazeGraph() Returns a const reference to the underlying maze graph.

Readiness fsm_builder.isReady() Returns true if and only if this FSM_Builder is initialized and can itself be used to initialize a finite state machine by building the finite state machine's transition function, false otherwise.

Transition function building fsm_builder.buildTransitionFunction(transition_function) Builds the specified transition function according to the structure of the underlying maze graph and its property maps.

Source state access fsm_builder.getSourceState() FSM_Builder::StateIndex Returns the finite state machine's source state.

Target state access fsm_builder.getTargetState() Returns the finite state machine's target state.

Solvability fsm_builder.hasSolutionFromState(state) 0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph()) Returns true if and only if it is possible for the finite state machine to reach the target state from the specified state, false otherwise.

Solution access fsm_builder.getCorrectInput(state) 0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph()) If fsm_builder.hasSolutionFromState(state) == true, returns the input that brings the finite state machine one step closer to its target state; otherwise, returns the number of possible inputs.

Cell access fsm_builder.getStateCell(state) 0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph()) Returns the cell that the maze graph's cell index map pairs the specified state with.

Direction from state fsm_builder.getStateDirection(state)

The Maze Maker last used to initialize fsm_builder must have built a last-visited map that is stored in the maze graph.

0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph())

Returns the direction from the last-visited cell to the cell that the maze graph's cell index map pairs the specified state with.

Name	Expression	Precondition	Semantics	Postcondition
Initialization	`fsm_builder.initialize(`model-specific arguments`)`		If the argument validation policy in effect accepts the specified arguments, initializes this `FSM_Builder` and its underlying pattern, then returns `true`; otherwise, returns `false`. The parameters to be recognized are model-specific; consult the documentation for that model for details.	`fsm_builder.isReady() == true` if and only if either this or a previous `fsm_builder.initialize()` call has returned `true`. Enforcing this postcondition allows applications to recover gracefully from a failed attempt at initialization.
Pattern access	`fsm_builder.getPattern()`		Returns a const reference to the underlying pattern.
Maze graph access	`fsm_builder.getMazeGraph()`		Returns a const reference to the underlying maze graph.
Readiness	`fsm_builder.isReady()`		Returns `true` if and only if this `FSM_Builder` is initialized and can itself be used to initialize a finite state machine by building the finite state machine's transition function, `false` otherwise.
Transition function building	`fsm_builder.buildTransitionFunction(transition_function)`		Builds the specified transition function according to the structure of the underlying maze graph and its property maps.
Source state access	`fsm_builder.getSourceState()`		`FSM_Builder::StateIndex`	Returns the finite state machine's source state.
Target state access	`fsm_builder.getTargetState()`		Returns the finite state machine's target state.
Solvability	`fsm_builder.hasSolutionFromState(state)`	`0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph())`	Returns `true` if and only if it is possible for the finite state machine to reach the target state from the specified state, `false` otherwise.
Solution access	`fsm_builder.getCorrectInput(state)`	`0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph())`	If `fsm_builder.hasSolutionFromState(state) == true`, returns the input that brings the finite state machine one step closer to its target state; otherwise, returns the number of possible inputs.
Cell access	`fsm_builder.getStateCell(state)`	`0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph())`	Returns the cell that the maze graph's cell index map pairs the specified state with.
Direction from state	`fsm_builder.getStateDirection(state)`	The Maze Maker last used to initialize `fsm_builder` must have built a last-visited map that is stored in the maze graph. `0 <= state && state < boost::num_vertices(fsm_builder.getMazeGraph())`	Returns the direction from the last-visited cell to the cell that the maze graph's cell index map pairs the specified state with.

Invariants and Runtime Complexity Guarantees

Runtime complexity is measured in turms of cell and connection count within the underlying pattern unless otherwise specified. The following invariants must hold.

Name Invariants Runtime complexity

Initialization Deterministic polynomial time

Pattern access Amortized constant time

Maze graph access Amortized constant time

Readiness Amortized constant time

Transition function building Linear time with respect to the number of states (unless a next-state input maker is used, in which case the time complexity is quadratic)

Source state access Amortized constant time

Target state access Amortized constant time

Solvability Linear time with respect to the number of states

Solution access Linear time with respect to the number of possible inputs

Cell access Amortized constant time

Direction from state Amortized constant time

Name	Invariants	Runtime complexity
Initialization		Deterministic polynomial time
Pattern access		Amortized constant time
Maze graph access		Amortized constant time
Readiness		Amortized constant time
Transition function building		Linear time with respect to the number of states (unless a next-state input maker is used, in which case the time complexity is quadratic)
Source state access		Amortized constant time
Target state access		Amortized constant time
Solvability		Linear time with respect to the number of states
Solution access		Linear time with respect to the number of possible inputs
Cell access		Amortized constant time
Direction from state		Amortized constant time

Models

The following class templates deriving from FSMBuilder:

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