Finite State Machine Implementation
Arne Olav Hallingstad4th February 2010
Home
Introduction
I recently came over a problem that would benefit from using a state machine. Unfortunately i had no generic state machine implementation I could use for the task so I decided to create one for this problem, and any future projects that might need one.Finite State Machine Goals
There's several requirements that can be made, but I've focused on these, with the highest priority first:
- Performance - Low memory usage by the FSM itself. - Generic imlpementation for easy intergration
Objects that want to use the FSM will need to derive from it. This may allow the states in the state machine to use the object directly, but in my implementation I decided that each state is its own class and so will need to use an owner pointer to access the FSM owner object.
The other approach is that each state has a a set of functions (enter/run/exit/etcetera) in the FSM class (or classes deriving from the FSM class). This is probably better for smaller state machines because of better locality to FSM owner (which is often used heavily by the states to define their behavior). There's less overhead in creating a class for each state, just add some functions. Once defined they can access member variables without using an owner pointer. Once you're past having a few states, the size of the class builds up.
It depends on how you value the different approaches, by keeping each state in its own class it is very easy to quickly get an overview over the full extent of each state. All member variables on a state object should never be duplicated across several states (at that point you might as well make an utility class for common operations or use functions on the owner).
State Machine Declaration
Any classes that may imlement a state machine should derive from aoFSM:
/*
===============================================================================
aoFSM
Finite state machine base class
===============================================================================
*/
class aoFSM {
public:
typedef void (aoFSM::*fsmFuncPtr_t)();
struct fsmStateInfo_t {
fsmFuncPtr_t initFuncPtr;
fsmFuncPtr_t enterFuncPtr;
fsmFuncPtr_t runFuncPtr;
int ident;
const char* identStr;
bool initialState;
};
aoFSM( fsmStateInfo_t _states[] ) {
fsmCurStateIndex = -1;
fsmNextStateIndex = -1;
fsmStates = _states;
}
// init fsm
void InitFSM() {
printf( "Initializing state machine '%s'\n", GetFSMName() );
fsmNumStates = 0;
bool set = false;
while ( fsmStates[ fsmNumStates ].ident >= 0 ) {
((*this).*(fsmStates[ fsmNumStates ].initFuncPtr))();
if ( fsmStates[ fsmNumStates ].initialState ) {
assert( !set );
set |= true;
fsmNextStateIndex = fsmNumStates;
printf( "...state '%s' (initial state)\n", fsmStates[ fsmNumStates ].identStr );
} else {
printf( "...state '%s'\n", fsmStates[ fsmNumStates ].identStr );
}
fsmNumStates++;
}
printf( "Successfully initialized %i fsmStates\n", fsmNumStates );
}
// run fsm
void Run() {
bool changed = fsmCurStateIndex != fsmNextStateIndex;
fsmCurStateIndex = fsmNextStateIndex;
if ( changed ) {
((*this).*(fsmStates[ fsmCurStateIndex ].enterFuncPtr))();
}
((*this).*(fsmStates[ fsmCurStateIndex ].runFuncPtr))();
}
// set next state
void NextState( int ident ) {
assert( ident >= 0 && ident < fsmNumStates );
fsmNextStateIndex = ident;
}
virtual const char* GetFSMName() const { return "unknown"; }
private:
int fsmCurStateIndex;
int fsmNextStateIndex;
fsmStateInfo_t* fsmStates;
int fsmNumStates;
};
There's no template usage at all and no virtual functions, use of defines are needed in the class wanting to use a FSM.
The state machine itself keeps a pointer to a list of possible states with the fsmStates member, index of the current state, next state and number of states in this table. Therefore state machine itself take up 4 integers or 16 bytes.
struct fsmStateInfo_t {
fsmFuncPtr_t initFuncPtr;
fsmFuncPtr_t enterFuncPtr;
fsmFuncPtr_t runFuncPtr;
int ident;
const char* identStr;
bool initialState;
};
For each state comes an additional 5 integers and one byte for a total of 21 bytes.
There's 3 important functions in the FSM:
- InitFSM() - Initialize the states and find the initial state to run - Run() - run a tick in the FSM - NextState() - allows for setting the next state to enter on the next tick
Defines Used by Implementing Class
#define FSM_PROTOTYPE( fsmClassName, ... ) \
static fsmStateInfo_t fsmStates[]; \
enum fsmStates_t { FSM_STATE_INVALID = -1, __VA_ARGS__, FSM_STATE_NUM }; \
virtual const char* GetFSMName() const { return #fsmClassName; }
#define FSM_STATE( nameOfStateClass ) \
nameOfStateClass fsm##nameOfStateClass; \
void FSMInit_##nameOfStateClass() { fsm##nameOfStateClass.Init( this ); } \
void FSMEnter_##nameOfStateClass() { fsm##nameOfStateClass.Enter(); } \
void FSMRun_##nameOfStateClass() { fsm##nameOfStateClass.Run(); } \
friend class nameOfStateClass;
#define FSM_STATE_DECL_BEGIN( fsmClassName ) \
fsmClassName::fsmStateInfo_t fsmClassName::fsmStates[] = {
#define FSM_STATE_DECL_INITIAL( fsmClassName, stateClassName, Ident ) \
{ ( void ( aoFSM::* )( void ) )( &fsmClassName;::FSMInit_##stateClassName ), \
( void ( aoFSM::* )( void ) )( &fsmClassName;::FSMEnter_##stateClassName ), \
( void ( aoFSM::* )( void ) )( &fsmClassName;::FSMRun_##stateClassName ), \
Ident, \
#Ident, \
true },
#define FSM_STATE_DECL( fsmClassName, stateClassName, Ident ) \
{ ( void ( aoFSM::* )( void ) )( &fsmClassName;::FSMInit_##stateClassName ), \
( void ( aoFSM::* )( void ) )( &fsmClassName;::FSMEnter_##stateClassName ), \
( void ( aoFSM::* )( void ) )( &fsmClassName;::FSMRun_##stateClassName ), \
Ident, \
#Ident, \
false },
#define FSM_STATE_DECL_END \
{ NULL, NULL, NULL, -1, NULL, false }, \
};
These are explained in more detail in the example use below.
Derived Class Declaration
An example implementation of a weapon state machine, with:
- an init state for creating the model, loading sounds, setting bullet type, firing rate, etcetera. - A raise state for playing the raise animation when activating the weapon. - Similarly a lower state when activating another weapon. - Idle loop state while not firing. - Reload state when clip needs to be reloaded. - Firing state while firing weapon
class aoWeaponStateInit {
public:
void Init( aoWeapon* owner );
void Enter();
void Run();
private:
aoWeapon* owner;
};
... and similar for each state declared
class aoWeapon: public aoFSM {
public:
aoWeapon() : aoFSM( fsmStates ) {}
private:
FSM_PROTOTYPE( aoWeapon,
STATE_INIT,
STATE_RAISE,
STATE_LOWER,
STATE_IDLE,
STATE_FIRING,
STATE_RELOAD )
// states
FSM_STATE( aoWeaponStateInit )
FSM_STATE( aoWeaponStateRaising )
FSM_STATE( aoWeaponStateLowering )
FSM_STATE( aoWeaponStateIdle )
FSM_STATE( aoWeaponStateFiring )
FSM_STATE( aoWeaponStateReloading )
private:
string reloadNow;
int ammo;
int clipAmmo;
};
Implementing the state machine, the class is required to use a FSM_PROTOTYPE macro and at least one FSM_STATE macro.
The FSM_PROTOTYPE macro is variadic which means beyond the first class name parameter, any number of state names may be defined. When wanting to set a new next state, these names are used.
For each state a FSM_STATE macro should be used that stores the data and functions required by the FSM base class.
Weapon Definition
Shows one of the states implemented and the base weapon definition.
/*
========================
aoWeaponStateIdle::Init
========================
*/
void aoWeaponStateIdle::Init( aoWeapon* _owner ) {
owner = _owner;
}
/*
========================
aoWeaponStateIdle::Enter
========================
*/
void aoWeaponStateIdle::Enter() {
tickDuration = 8;
ticks = 0;
}
/*
========================
aoWeaponStateIdle::Run
========================
*/
void aoWeaponStateIdle::Run() {
printf( "aoWeaponStateIdle::Run: Idle weapon tick %i of %i\n", ticks, tickDuration );
if ( ticks >= tickDuration ) {
owner->NextState( aoWeapon::STATE_LOWER );
}
ticks++;
}
// fsm declaration
FSM_STATE_DECL_BEGIN( aoWeapon )
FSM_STATE_DECL_INITIAL( aoWeapon, aoWeaponStateInit, STATE_INIT )
FSM_STATE_DECL( aoWeapon, aoWeaponStateRaising, STATE_RAISE )
FSM_STATE_DECL( aoWeapon, aoWeaponStateLowering, STATE_LOWER )
FSM_STATE_DECL( aoWeapon, aoWeaponStateIdle, STATE_IDLE )
FSM_STATE_DECL( aoWeapon, aoWeaponStateFiring, STATE_FIRING )
FSM_STATE_DECL( aoWeapon, aoWeaponStateReloading, STATE_RELOAD )
FSM_STATE_DECL_END
aoWeapon weapon;
int main( int argc, char* argv[] ) {
weapon.InitFSM();
while ( true ) {
weapon.Run();
Sleep( 500 );
}
return 0;
}
The Init() function is called when the FSM is initialized for all states registered with the state machine. The Enter() function is run on the state class that is about to become the current state. Run() is run for every tick until the state calls NextState on the owner.
FSM_STATE_DECL_INITIAL macro sets the default state to run when the state machine first runs. FSM_STATE_DECL is similar to except it won't be the default state. These macros tie the easily readable state names on the right to the state classes (second parameter) for the state machine derived class aoWeapon (first parameter).
Initialize the state machine by calling weapon.InitFSM() and start running it by calling weapon.Run().
Running
Output for the state machine test application:
Initializing state machine 'aoWeapon' ...state 'STATE_INIT' (initial state) ...state 'STATE_RAISE' ...state 'STATE_LOWER' ...state 'STATE_IDLE' ...state 'STATE_FIRING' ...state 'STATE_RELOAD' Successfully initialized 6 fsmStates -> STATE_INIT Let's give som ammo and go to idle immediately ammo: 60 clip ammo: 30 STATE_INIT -> STATE_RAISE aoWeaponStateRaising::Run: raising weapon tick 0 of 4 aoWeaponStateRaising::Run: raising weapon tick 1 of 4 aoWeaponStateRaising::Run: raising weapon tick 2 of 4 aoWeaponStateRaising::Run: raising weapon tick 3 of 4 aoWeaponStateRaising::Run: raising weapon tick 4 of 4 STATE_RAISE -> STATE_IDLE aoWeaponStateIdle::Run: Idle weapon tick 0 of 8 aoWeaponStateIdle::Run: Idle weapon tick 1 of 8 aoWeaponStateIdle::Run: Idle weapon tick 2 of 8 aoWeaponStateIdle::Run: Idle weapon tick 3 of 8 aoWeaponStateIdle::Run: Idle weapon tick 4 of 8 aoWeaponStateIdle::Run: Idle weapon tick 5 of 8 aoWeaponStateIdle::Run: Idle weapon tick 6 of 8 aoWeaponStateIdle::Run: Idle weapon tick 7 of 8 aoWeaponStateIdle::Run: Idle weapon tick 8 of 8 STATE_IDLE -> STATE_LOWER aoWeaponStateLowering::Run: lowering weapon tick 0 of 4 aoWeaponStateLowering::Run: lowering weapon tick 1 of 4 aoWeaponStateLowering::Run: lowering weapon tick 2 of 4 aoWeaponStateLowering::Run: lowering weapon tick 3 of 4 aoWeaponStateLowering::Run: lowering weapon tick 4 of 4
No State Exit Function?
By not having an exit function automatically called you're forced to do any cleanup/function calls right before telling the state machine to set a new state.
If you do different things before exiting a state depending on the reason for exiting the state you have a choice of either using a bunch of branching code (bad for readability and performance) in the exit function for all of these cases, or more cleanly (in my opinion) a non branching code right before the particular code (and reason for exiting) that sets a new state.
It's also easier to debug because if you exit one state to enter another one and there's only one function call in the old state that sets that particular new state you can easily see any cleanup/function calls together with the call to set the next state.
If something outside of the state would like to change the state, it should not be allowed to do so! Nothing but the state itself should come to the conclusion that a new state is needed. The state should be able to query or be notified about any information making it exit to another state.
A states Enter() function will be called before calling the Run() function so it may reset its state as needed.
Further Work
It would be interesting to create another FSM class which runs state functions declared on the class deriving from the FSM class. Running state functions on the derived class itself should be better suited for smaller state machines.
Evaluate implementations with features such as:
- Support for nested state machines. - Support for burying/unburying states. - "Concurrently" (single threaded) running state machines which may need some level of inter-communications (particularly individual state machines controlling AI movement, sensing, reaction, etcetera). - Notification or event system for sending data to the active state.
Conclusion
We've shown a state machine implementation which will call init/enter/exit functions on classes registered with the state machine. The state machine can take human readable state names and set the associated state class as the current state. State machine may pprint current and next state on state transitions.
