State Machines in Programs

Introduction

In this tutorial I while introduce how to use state machines to keep a program always in a well defined state.

A state machine has mainly two parts:

• states
• transitions

By using a state machine as the basis of a program, the program is in just one state at any given time. The State can only be changed by a transition.

So the state defines the complete behaviour of the program at this point of time and the programmer can avoid by this side effects and his program is always in a well defined state.

To change the state either the user (via the gui) or the program itself triggers a transition. To enforce to reach only a well defined state, transitions can be guarded, so that not all transitions are possible.

This for example allows only entrance to a given state, if all preconditions (like initiliazing of program resources) are met. The guard functions are also needed as soon as you have a multi-threaded program to garantuee exclusive access to a critical sections.

To summarize a state machine offers a program:

• avoiding of side effects
• well defined behaviour through just being in one state at any given time

BaseState and BaseStateMachine

So let's start by defining a BaseState class from which we can derive our concrete program states.

A state in this case is just identified by a number (stateId_). so we need first a simple constructor:

class BaseState { public: /* @param stateValue identifier of this state */ BaseState( int stateValue ): stateId_( stateValue ) {};

And a function to read this identifier:

int getStateId() const { return stateId_; }; private: const int stateId_; };

As the identifier should not change through program execution it is const and private.

Finally we need our guard functions. In this case one check if we are allowed to enter this state from a given other state and one to check if we can leave this state for an other state:

public: /// @result if the state could be entered virtual bool onEnter( int oldState ){ return true; }; /// @result if the state could be left virtual bool onLeave( int newState ){ return true; };

As our base state has no functionality and we don't want to define guard functions for every state, both just return true.

So now let us take a look at the state machine itself:

• We need to set an initial state. For this we have a constructor who just takes this as n parameter:

  BaseStateMachine::BaseStateMachine( BaseState* initState ) : stateMap_(), actState_( initState ) { // assert state defined assert( actState_ ); registerState( initState ); // enter initial state assert( initState->onEnter( initState->getStateId() ) ); }

  Where stateMap_ is just a std::map of stateIds (int) and states (BaseState*).
• then we need to add further states to our state machine:

  void BaseStateMachine::registerState( BaseState* st ) { stateMap_[st->getStateId()] = st; }

• next we need a way to go from one state to an other:

  bool BaseStateMachine::changeState( int newState ) { std::map::iterator stateIter = stateMap_.find( newState ); if( stateIter == stateMap_.end() ) { return false; } // if we can't leave the actState for new state...bad luck if( !actState_->onLeave( newState ) ) return false; // if we can't enter new state from last state...bad luck if( !stateIter->second->onEnter( actState_->getStateId() ) ) { // but each state should be enterable from itself... // otherwiese we have a big problem. assert( actState_->onEnter( actState_->getStateId() ) ); return false; } // new state found. actState_ = stateIter->second; return true; }

• Finally we need to free all associated memory of the state machine:

  void BaseStateMachine::releaseStates() { for( std::map::iterator stateIter = stateMap_.begin(); stateIter != stateMap_.end(); stateIter++ ) delete stateIter->second; stateMap_.clear(); } BaseStateMachine::~BaseStateMachine() { releaseStates(); }

But now one question is still open: How takes a concrete state effect in the program?

For this I will show here a concrete instance of a state machine developed for a game engine based on Direct3D.

GraphicState and GraphicStateMachine

To get events to a state we define a new GraphicState derived from BaseState with:

• a drawing Routine onFrameRender
• a msgProc to react to events like pressed buttons
• and a keyboardProc to react on pressed keys.

 
/// State with special functions, which will be called from GraphicStateMachine on special events.
class GraphicState
	: public BaseState
{
  public:
    GraphicState( int stateId, GraphicEngine* graphEng ): BaseState( stateId ), graphEng_( graphEng ) {};
    virtual ~GraphicState(){};     
    /// Method to propagate drawing events from graphicengine
    virtual void onFrameRender( double fTime, float fElapsedTime ) = 0; 		
    /// Method to propagate msgEvents from graphicengine
    virtual bool msgProc( GuiEvent::Event ge ) = 0;
    virtual void keyboardProc( KeyEvent::Event ke ) = 0;
}; 

In the same way we derive from BaseStateMachine a GraphicStateMachine with just the same functions as GraphicState and which calls the functions of the current state:

// handles message events, and calls the corresponding function of actState_ bool GraphicStateMachine::msgProc( GuiEvent::Event ge ) { return static_cast<GraphicState*>(actState_)->msgProc( ge ); } void GraphicStateMachine::keyboardProc( KeyEvent::Event ke ) { static_cast<GraphicState*>(actState_)->keyboardProc( ke ); } // renders the actual display, via onFrameRender of actState_ void GraphicStateMachine::onFrameRender( double fTime, float fElapsedTime ) { static_cast<GraphicState*>(actState_)->onFrameRender( fTime, fElapsedTime ); }

By this we call only the functions from the state machine itself, when events occur and our interface to Direct3D does not need to know, in which state we are at the time of the event.

Registering States

So finally I will introduce in a short excurse one way to easily register states:

• A state factory.

Just assign an enum for your state ids and implement a class with one or more factory functions for states:

/// Class for generating States for this game class StateFactory { public: /* ** returns a new State, for registering with the StateMachine of this game ** ** @param stateId State to create ** @param graphEng pointer for GraphicEngine, if needed by state to create ** @param confPars pointer to ConfigParser, if needed by state to create. */ static BaseState* New( int stateId, GraphicEngine* graphEng = NULL ) { switch( stateId ) { case GameStates::mainMenu: return new MainMenuState( GameStates::mainMenu, graphEng ); break; case GameStates::simpleIntro: return new SimpleIntroState( GameStates::simpleIntro, graphEng ); break; } int unkownStateForStateFactory = 0; assert( unkownStateForStateFactory ); return NULL; } };

The introduction of unknownStateForStateFactory is just one more point to garantuee that our program is always in a well defined state, as we now get an assertion as soon as we want to create a state, which is not yet implemented in the StateFactory. As all states should be normally registered at the start of the program, this asserts that we do not forget any state.

Then you can easily use this functon to register needed states to your state machine:

void GameEngineImpl::registerState( int stateId ) { assert( stateMachine_ ); stateMachine_->registerState( StateFactory::New( stateId, graphEng_, &confPars_ ) ); }

Conclusion

• the program is always in exactly one well defined state
• States can easily be guarded against entrance from other states when not all prerequisites are met.
• There are no side effects between states.

Excurse: state machines embedded in state machines

Often it is not sufficient to have just one state machine. So I will shortly show how you can embbed a state machine in a state of an other state machine.

As shown on the screen above there can be more than one level of embedding. The only limitation to this technique is that with each level your code gets a little bit harder to understand.