State Machine

Started by
3 comments, last by JoshM 18 years, 8 months ago
Lately I've been thinking about how to implement a robust and easy to use state machine. My context is in controlling UI flow and state, but I'd like it to be something general that could be used for AI states or input states or... whatever. I'm interested in everybody's opinion of what I've got so far. Would you use it? Where does it break down? Why is it annoying? Etc. The thing that sucks most is that each state is responsible for moving to the following state. A "real" state machine would have this encoded into the machine description as well as what states are valid from each state... but I'm more interested in a practical and easy-to-debug than a "proper" state machine and I can't think of a better name for what I'm doing here. I do plan to try and come up with a way to predefine state flow and valid states, but I'm not sure yet how to do it or how it will fit with this, if at all. I just *really* hate the classic "big case statement" or using giant arrays and enums and such. Here is StateMachine.h (The backslashes are botched, so I used "(backslash)")

// StateHandler
// Holds pointers to an object's methods and provides a bottleneck for 
//  calling them.
template< typename THost >
class StateHandler
{
private:
	typedef void(THost::*Callback)();
	Callback mEnter;
	Callback mUpdate;
	Callback mExit;

public:
	void Set( Callback enter, Callback update, Callback exit )
	{
		assert( enter && update && exit );
		mEnter = enter;
		mUpdate = update;
		mExit = exit;
	}
	void Enter( THost* host )	{ assert( host ); (host->*mEnter)(); }
	void Update( THost* host )	{ assert( host ); (host->*mUpdate)(); }
	void Exit( THost* host )	{ assert( host ); (host->*mExit)(); }
};


// StateMachine
// Maintains a pointer an instance of THost, and a pointer to a StateHandler 
//  instance that is used to call methods on the host.
// It is invalid for the StateHandler object to contain a NULL pointer,
//  and must be initialized with a StateHandler that calls empty functions if
//  that behavior is desired.  This is to avoid all the bugs and branching
//  that comes with NULL pointers.
template< typename THost >
class StateMachine
{
private:
	StateHandler< THost >*	mStateHandler;
	THost*			mHost;

public:
	StateMachine( StateHandler< THost >& initState ) 
	: mHost( 0 ),
	  mStateHandler( &initState )
	{}

	void SetHost( THost* host )
	{
		assert( host );
		mHost = host;
	}

	// Calls the Update method for the StateHandler.
	void Update()
	{
		assert( mHost );
		assert( mStateHandler );
		mStateHandler->Update( mHost );
	}
	
	// Changes states, calling Exit on the current state before changing and 
	// calling Enter on the new state after changing.
	void Goto( StateHandler< THost >& s )
	{
		assert( mHost );
		assert( mStateHandler );
		assert( &s );
		mStateHandler->Exit( mHost );
		mStateHandler = &s;
		mStateHandler->Enter( mHost );
	}
};

// These macros are used to easily and cleanly set up a host class
// to use a state machine.
#define STUB_STATE_HANDLER_FUNCS( STATENAME )	(backslash)
	void enter ## STATENAME (){}		(backslash)
	void update ## STATENAME (){}		(backslash)
	void exit ## STATENAME (){}

#define DECLARE_STATE_HANDLER_FUNCS( STATENAME )(backslash)
	void enter ## STATENAME ();		(backslash)
	void update ## STATENAME ();		(backslash)
	void exit ## STATENAME ();

#define SET_STATE_HANDLER( CLASS, STATENAME )	(backslash)
	mState ## STATENAME.Set(		(backslash)
	& CLASS ::enter ## STATENAME,	(backslash)
	& CLASS ::update ## STATENAME,	(backslash)
	& CLASS ::exit ## STATENAME );






Here is an example of how it would be used:

class TestScreen : public AbstractScreen
{
	StateMachine< TestScreen > mStateMachine;
	StateHandler< TestScreen > 
		mStateNothing, 
		mStateStart, 
		mStateIdle, 
		mStateStop;
	
	STUB_STATE_HANDLER_FUNCS( Nothing );
	STUB_STATE_HANDLER_FUNCS( Start );
	STUB_STATE_HANDLER_FUNCS( Idle );
	STUB_STATE_HANDLER_FUNCS( Stop );

public:

	TestScreen();
	virtual ~TestScreen()	{}
	virtual void Start()	{ mStateMachine.Goto( mStateStart ); }
	virtual void Stop()	{ mStateMachine.Goto( mStateStop ); }
	virtual void Suspend()	{}
	virtual void Resume()	{}
	virtual void Update()	{ mStateMachine.Update(); }
};

...

TestScreen::TestScreen()
: mStateMachine( mStateNothing )
{
	mStateMachine.SetHost( this );
	SET_STATE_HANDLER( TestScreen, Nothing );
	SET_STATE_HANDLER( TestScreen, Start );
	SET_STATE_HANDLER( TestScreen, Idle );
	SET_STATE_HANDLER( TestScreen, Stop );
}




Advertisement
It's very difficult to make generic state-machine code. I wouldn't want the virtual call overhead here, which is the same thing as a member function pointer dereference.

If you stay on this track, I would just go fully OOP and make an interface for IState & IStateMachine:
struct IState
{
virtual ~IState() {}
virtual void Enter(IStateMachine*)=0;
virtual void Update(IStateMachine*)=0;
virtual void Exit(IStateMachine*)=0;
};

struct IStateMachine
{
virtual ~IStateMachine() {}
virtual void QueueNextState(IState*)=0;
virtual void Reset()=0;
//...?
};

But that can be a good deal of overhead for a state-machine.

If you wanted to get serious about re-usable state-machine code in C++, I'd look into a policy base meta-template implementation either using Loki or boost::mpl. The more common approach today is to use a tool that generates C or C++ code.
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
Quote:Original post by Shannon Barber
It's very difficult to make generic state-machine code.

Ok, I'm glad that it's not just me then :)

Quote:I wouldn't want the virtual call overhead here, which is the same thing as a member function pointer dereference.

I see now that one of the assumptions I'm making in my design is that there won't be an overabundance of states, and that state transitions wouldn't be common enough to cause any kind of cpu/mem hit. But you're right - it isn't ideal. Then again, if you've just got a huge case statement then you've got the overhead of a huge jump table also. And I figured that encapsulating the member function pointers into a discreet chunk of ram would be much more cache-friendly than having a massive vtable? Does that make sense or is my head full of FUD?

Quote:If you stay on this track, I would just go fully OOP and make an interface for IState & IStateMachine:

The problem with this approach is that the classes that implement IState are not "part" of any other class. Which makes it very difficult to use the state machine to control any kind of private process that you don't necessarily want to expose via public members and accessors/mutators. There are OO ways around that limitation, but at that point you've just caused a considerable amount of bloat and complication without really gaining anything it seems.

Quote:If you wanted to get serious about re-usable state-machine code in C++, I'd look into a policy base meta-template implementation either using Loki or boost::mpl.


I like the idea of using policies to define behavior for transitions, handling null states, etc. But I'm not yet to the point in the design where I'm ready to think about maximizing reusability. I just want it to be reasonable at this point, not perfect.

Again, meta-templates could possibly present a very run-time efficient implementation, but complications include:
1) Executable bloat that could possibly ruin cache performance and defeat the purpose of avoiding method pointers/vtable.
2) The cost of integrating a state machine for aggregation or inheritence by any class could include a LOT of really ugly code. I use macros in my example, but it would be totally reasonable to not use them - the code would still be readable. Meta-template setups for a state machine could get very complex and impossible to debug IMO.
In general, the meta-template approach is fun but ultimately a pain to debug and often ends up offloading a bunch of complexity onto the client classes, which in turn increases chances for bugs to creep in. I also wouldn't expect meta-templates to be very friendly with the SNSystems compiler for PS2 etc.

Quote:The more common approach today is to use a tool that generates C or C++ code.

Could you give me some pointers on where to find tools like this? Or is it mostly a homebrew kind of thing?

Thanks!
Quote:Original post by JoshM
Quote:Original post by Shannon Barber
It's very difficult to make generic state-machine code.

Ok, I'm glad that it's not just me then :)

Quote:I wouldn't want the virtual call overhead here, which is the same thing as a member function pointer dereference.

I see now that one of the assumptions I'm making in my design is that there won't be an overabundance of states, and that state transitions wouldn't be common enough to cause any kind of cpu/mem hit. But you're right - it isn't ideal. Then again, if you've just got a huge case statement then you've got the overhead of a huge jump table also. And I figured that encapsulating the member function pointers into a discreet chunk of ram would be much more cache-friendly than having a massive vtable? Does that make sense or is my head full of FUD?


Size matters not :) If there's tons of states, then sure the jump table will be big, but so will the tables of your triple-indirected functions (member pointers/virtual functions). If we're concerned about cache think about that a minute; one continuous table vs. 3 tables. Three indirections is begging for a cache miss.

Quote:
Quote:If you stay on this track, I would just go fully OOP and make an interface for IState & IStateMachine:

The problem with this approach is that the classes that implement IState are not "part" of any other class. Which makes it very difficult to use the state machine to control any kind of private process that you don't necessarily want to expose via public members and accessors/mutators. There are OO ways around that limitation, but at that point you've just caused a considerable amount of bloat and complication without really gaining anything it seems.


I can see the desire for member-function pointer, then the state-handling functions are part of the state-machine. There's no need to pass a pointer to the state-machine then, it's already passed in as 'this'.

If you use a template you can sorta do both:
template<class StateMachine>struct State{	virtual ~State() {}	virtual void Enter(StateMachine*)=0;	virtual void Update(StateMachine*)=0;	virtual void Exit(StateMachine*)=0;};struct StateMachine;struct State1 : State<StateMachine>{	virtual void Enter(StateMachine*){}	virtual void Update(StateMachine*){}	virtual void Exit(StateMachine*){}};struct State2 : State<StateMachine>{	virtual void Enter(StateMachine*){}	virtual void Update(StateMachine*){}	virtual void Exit(StateMachine*){}};struct StateMachine{	StateMachine() : current_state(&state1) {}   	State1 state1;   State2 state2;	State<StateMachine>* current_state;};



Quote:
Quote:If you wanted to get serious about re-usable state-machine code in C++, I'd look into a policy base meta-template implementation either using Loki or boost::mpl.


I like the idea of using policies to define behavior for transitions, handling null states, etc. But I'm not yet to the point in the design where I'm ready to think about maximizing reusability. I just want it to be reasonable at this point, not perfect.

Again, meta-templates could possibly present a very run-time efficient implementation, but complications include:
1) Executable bloat that could possibly ruin cache performance and defeat the purpose of avoiding method pointers/vtable.
2) The cost of integrating a state machine for aggregation or inheritence by any class could include a LOT of really ugly code. I use macros in my example, but it would be totally reasonable to not use them - the code would still be readable. Meta-template setups for a state machine could get very complex and impossible to debug IMO.
In general, the meta-template approach is fun but ultimately a pain to debug and often ends up offloading a bunch of complexity onto the client classes, which in turn increases chances for bugs to creep in. I also wouldn't expect meta-templates to be very friendly with the SNSystems compiler for PS2 etc.

1) You have to written the mpl code right, and then the opposite is the case, you create an inlining effect that eliminates alot of code bloat issues - thing you would resort to #define macros to resolve in C code.
2) The mpl is bad is this is the case, the idea is to make the meta-template complicated and the client code simple.
3) Then file bugs reports to SNSystems ;) unless they only claim an EC++ compiler.

Quote:
Quote:The more common approach today is to use a tool that generates C or C++ code.

Could you give me some pointers on where to find tools like this? Or is it mostly a homebrew kind of thing?


Almost all CASE tools do this; any UML tool that generates code will (a state diagram is part of UML).
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
Quote:Three indirections is begging for a cache miss.
Doh >:/ What was I thinking?

Quote:There's no need to pass a pointer to the state-machine then, it's already passed in as 'this'.
I don't see anywhere that was passing a pointer to the statemachine. I like the example you gave, and this was my first inclination also - but classes derive from State will know nothing about the object who's states they implement. Sure, I could just derive from StateMachine, but as soon as I want my object to have two state machines I'm screwed, right? For example, my object could need to coordinate multiple parallel tasks that each involve multiple serial steps. Maybe then I should contain those tasks into their own objects that derive from StateMachine? Hmm.

Quote:1) You have to written the mpl code right, and then the opposite is the case, you create an inlining effect that eliminates alot of code bloat issues - thing you would resort to #define macros to resolve in C code.
2) The mpl is bad is this is the case, the idea is to make the meta-template complicated and the client code simple.
3) Then file bugs reports to SNSystems ;) unless they only claim an EC++ compiler.
Ok, I'd give mpl a chance then. As far as SNSys goes - if it were only that easy... their compiler is based on an ancient version of GCC.

Quote:
Almost all CASE tools do this; any UML tool that generates code will (a state diagram is part of UML).
I've only used Visio for UML, but I don't remember any kind of code-generation. There's probably a $12,00 plugin to do it ;)

Thanks again

This topic is closed to new replies.

Advertisement