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


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.


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


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.


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


Models



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