State Machines in Programs


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:

We will represent a state machine by a directed graph where the states are the nodes and the transitions the edges.

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:

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
    /* @param stateValue identifier of this state */
    BaseState( int stateValue ): stateId_( stateValue ) {}; 

And a function to read this identifier:
int getStateId() const { return stateId_; };
    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:
    /// @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:

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:

/// State with special functions, which will be called from GraphicStateMachine on special events.
class GraphicState
	: public BaseState
    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_
GraphicStateMachine::msgProc( GuiEvent::Event ge )
  return static_cast<GraphicState*>(actState_)->msgProc( ge );
GraphicStateMachine::keyboardProc( KeyEvent::Event ke )
  static_cast<GraphicState*>(actState_)->keyboardProc( ke );
// renders the actual display, via onFrameRender of actState_
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:

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
   ** 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 ); 
	 case GameStates::simpleIntro:
	   return new SimpleIntroState( GameStates::simpleIntro, graphEng );
    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:
GameEngineImpl::registerState( int stateId )
  assert( stateMachine_ );
  stateMachine_->registerState( StateFactory::New( stateId, graphEng_, &confPars_ ) );


So let me shortly summarize the benefits of a state machine as the basis of most programs: By this modular developement will be strongly supported and many problems of common programs are avoided.

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.

On entering of the global state (Almanac State) we just initiliaze the corresponding state machine (Almanac State Machine) and while in this state the current state of the Almanac State Machine is our program state. So we still have only one final state at any given time. In this case the state of the Almanac State Machine is embedded in the Almanac State.

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.



Bei Problemen mit diesen Internetseiten schreiben sie bitte eine Email an mich!