State Machine Hell

I know "all programs are state machines" and blah blah blah but isn't there something better than this recurring idiom:

void Update()
{
  switch( myState )
  {
    case DoingTheFirstThing:
       ...
    case DoingTheSecondThing:
       ...
    case DoingTheLastThing:
       ...
  }
}

To me, these state machines are spaghetti code:  even less readable than a function laced with gotos.  Taking each state and making it a class makes it even worse - now I have to go digging through half a dozen source files to figure out what the code does.  I've done both many times, of course, and always been mystified by my code later.

What's the alternative?  Threads?  Although the code reads cleaner it can't possibly worth the issues multithreading introduces.

I've got nothing, and I'm still grudgingly doing it as above.  Anyone?

Comments

[Jeremy]

Threads do make it easier, but not full-blown preemptive threads. You really want co-routines which a cooperatively scheduled when they need to do something and give up the CPU quickly when they're done. That way you can encode the state in the current instruction+local vars, and its all a bit easier to understand.

You can do it with regular threads if you're really strict about how you interact with the threads (most likely, message-passing only). But regular C/C#/Java threads are pretty heavyweight, and you wouldn't want to model the state of 1000's of thingies with threads.

Language/runtime support really helps here: you could do it in Erlang, for example, since you can create tens or hundreds of thousands of threads to maintain your state without much effort.

[Nathan McKenzie]

What I've been doing a lot of recently is stuff like this:

myGuy = new Entity();
myGuy.name = "Jerry";
myGuy.age = 0;
myGuy.update = delegate( Entity self )
{
// do thing
// do more things
if( self.age > whatever )
{
self.update = delegate( Entity self )
{
// do thing
// do other thing
if( transition2_test < whatever )
{
self.update = delegate( Entity self )
{
// do last set of things
}
}
}
}

The upsides to such an approach, I think, are that the nesting makes the order of events, and the causes of transition, pretty clear (particularly when one of the stages is essentially PauseForATransitionEffectForHalfSecond(), which comes up a lot). The delegate update is essentially replacing the enums you have listed, but their nesting sort of obviates the need for labeling the things and makes the flow more structured. If it gets much more complicated, you can extract the update functions and name them, too. I really like that it keeps everything in one place for editing and comprehension.

The biggest downside I've found to this approach is that, while it's extremely convenient for simple situations, it can get out of hand if you start finding your logic growing more complicated. It's tempting to just keep shoving stuff in there until it's completely unreadable... but then, maybe that applies to the switch/enum case as well. Hairy logic is hairy logic.

Additionally, whereas your version of update can have common code before or after the switch statement, this version of update would require manual duplication of such functionality in each version of update. Alternatively, this might be a separate, new sub-update field, I guess.

It also depends on whether adding a delegate allocates memory or not, of course.

This style of programming can also really hurt the eyes of OO purists, I think.

The biggest thing I do like about it, though, speaking of OO, is that it doesn't clutter the interface of a class with tons of tiny named functions that aren't meant to be reusable functionality.

Are there any other critiques to this kind of approach? I've been using it a lot recently in my own stuff, but I do have to admit that much of its charm is that I haven't really worked in functional-oriented languages before, so I'm having fun just watching the results of using a new toy.

[Nathan McKenzie]

Ugh! My poor, flattened code!

Perhaps that will teach me to preview before posting...

Anyway, my code should have looked like this, more or less:

myGuy = new Entity();
myGuy.name = "Jerry";
myGuy.age = 0;
myGuy.update = delegate( Entity self )
{
...// do thing
...// do more things
...if( self.age > whatever )
...{
......self.update = delegate( Entity self )
......{
.........// do thing
.........// do other thing
.........if( transition2_test < whatever )
.........{
............self.update = delegate( Entity self )
............{
...............// do last set of things
............}
.........}
......}
...}
}

[Max Battcher]

One simple optimization to the "big-ass switch" problem is to move switch cases into individual function calls... I think in many cases it is more readable to have a bunch of UpdateForState1(), UpdateForHungryState(), UpdateWhenHappy(), or whatever functions then all of that same code nested in a switch. Then your big switch is just a simple function dispatcher. Which leads to more complicated ideas involving writing an actual generic custom function dispatcher that are much easier to do in dynamic languages than static ones like C/C++/C#.

[Aras Pranckevicius]

Like said already, coroutines FTW. Below are pretty much what you can write in Unity (JavaScript, compiled to .NET bytecode, with some syntax magic to make yields easier. In C# coroutines are more ugly).

function Patrol() {
..while(true) {
....if( LowHealth() )
......RunAway();
....else if( EnemyNear() )
......Attack();
....else
......MoveSomewhere();
....yield; // done for this update loop!
..}
}

function Attack() {
..while( !LowHealth() && EnemyNear() ) {
....DoTheAttack();
....// done with this update, and wait a bit
....yield WaitForSeconds( attackRate );
..}
..// return to whatever invoked us
}

[Poo Bear]

I had the same problem on all my lua scripts on my last game. This time I'm using non-preemptive corroutines and it's really flattened the code out nicely without any threading headaches.

//master thread class
for each script
if( script[i].resume() == FINISHED )
delete script

//a script
main()
//do some stuff
while( !ready() ) coroutine.yield()
//do some other stuff
while( on_route() ) coroutine.yield()
//do more stuff
while( talking() ) coroutine.yield()
//do last bit of stuff
return done
end

[kert]

Look around in other patterns, theres a solution there. You tried state pattern and it didnt work for you ( although i fail to understand why ), maybe Observers/signals/slots would help you. Boost::signals has a really neat demo with it.

[OnyxRaven]

If you set up your states as well known strings, you could easily use a command/factory pattern here. sorry for my crappy syntax but i've not written C++ in a while.

void update() {
Command obj = StateFactory::get(myState);
if (obj) {
bool result = obj->execute(stateinfo);
}
}

then you just have a StateFactory that can grab the correct class to execute ... each of your states can then be a full blown class.

This incurs a little bit of overhead by calling more functions, and allocating new Command memory, but much of that can be optimized nicely.

[Jeff Ward]

There are two ways I tend to do this. The first is to use classes and use what I call a "state stack". Basically, I have an IGameState or IObjectState interface, and have each state for a the game or object in a different class. Yes, it makes a lot of objects / files, but for states that require a lot of code, that's okay. You should have them in seperate files anyway. The "state stack" is a system where you can either push, pop, or exchange state classes. By doing this, you can actually push temporary states on to the stack and then rejoin the old state just by poping it off later, or you can actually pass messages from the top state down if the top state can't handle it. I've yet to use this in a really large, complicated system, but hopefully I'll find time to soon.

The other option I use is to have a Hash table of game states that contains a hash table of delegates. Basically, when you pass a message to an object it grabs the hash table for its current state, then grabs the delegate for the message and executes it. To make this look pretty I made methods like so:

protected void State( State newState, Delegate codeToExecute ) {
..this.CurrentState = newState;
..this.StateHash.add(newState, new HashTable());
..codeToExecute();
}

protected void OnMessage( Message msg, Delegate codeToExecute ) {
..HashTable messageHash = this.StateHash[this.CurrentState];
..messageHash.add(msg, codeToExecute);
}

public void StateMachine() {
..State( FirstState, delegate() {
....OnMessage( Message1, delegate() {
......// Code
....});
..State( FirstState, delegate() {
....OnMessage( Message2, delegate() {
......// Code
....});
..});
}

Then you just call "StateMachine" before you actually do anything in your code. I first did this when I integrated Ruby into a small engine, and it worked well. It might have been particularly good for Ruby, though, because the code there was a bit cleaner. The benefit to this, though, is that you can add messages and states pretty easily, and the code stays pretty clean. You can even add OnEnter, OnExit, and OnUpdate portions just be reserving messages for those three. It's really quite cool.

[kert]

CodeProject has a nice illustrated example, direct link wont work but google on "codeproject directx state pattern" will turn it up

I dont see whats wrong with approach like that, all the code goes exactly where it belongs. It can be improved on of course.

[Stern]

Anyone checked out Adam Dunkels' protothreads? There's a neat example of a switch-case state machine recoded with protothreads on the project webpage.

[Mike]

In the last piece of code I wrote that had the state pattern, I did put each state in its own class, but I also took the radical decision to put all the states in one source file. I navigate the file with the class browser. Most of the states have small amounts of code and there are only 5 possible messages, of which 2 almost always take default handling which is done in a superclass.

State machines generally have a set of possible states and a set of possible messages. If every cell in the state, message matrix is handled by unique code then you have two layers of switch statements. If you use coroutines instead, you still, in the limit, have messages*states pieces of code to navigate, but the coroutine idiom allows you to pretend it's just one function. Goody! I'll take member functions over that any day.

[Brandon Bloom]

You can simulate fibers (microthreads, protothreads, whatever you like to call them) quite well with C# generator functions.

"Full" implementation and sample usage all in other 100 lines:
http://pastebin.com/f33e6da7c

Generator functions allocate, but here the created enumerator object is saved in the manager. You will not occur any per-frame garbage.

[Ian Dallas]

One option for creating readable state machines is to write them in a domain specific language.

I've had very good luck using the open source State Machine Compiler project: http://smc.sourceforge.net.

SMC can generate code in many different languages -- C++, C#, Ruby, etc.

Writing in a domain specific language is a great way to extract out the state transition logic (guard conditions, etc) from the state execution logic. I think it's also much easier to make tweaks to the state machine when it's all contained in one, short file.

[Ian Dallas]

One option for creating readable state machines is to write them in a domain specific language.

I've had very good luck using the open source State Machine Compiler project: http://smc.sourceforge.net.

SMC can generate code in many different languages -- C++, C#, Ruby, etc.

Writing in a domain specific language is a great way to extract out the state transition logic (guard conditions, etc) from the state execution logic. I think it's also much easier to make tweaks to the state machine when it's all contained in one, short file.

[Matthew Wegner]

Coroutines are magical, especially for linear sequences. In Unity's* scripting environment you can just do:

// do something

yield WaitForSeconds(2.5);

// do something else

yield FindEnemyTarget();

// do something (fire? run away?);

yield WaitForSeconds(2.0);

And slap the whole thing in a never-ending while loop or whatever.

* Unity is an engine with Mono scripting in C#, JavaScript, and Boo: http://unity3d.com

[raigan]

I'm surprised that some are using switch statements, I've always had to resort to more heavy-handed solutions (class-per-state) out of necessity, because some states inevitably require pre/post phases rather than just Update(), and things get ugly. Am I missing something?

[Simon Cooke]

Actually, scratch that... that Generator function link is exactly what the doctor ordered...

http://pastebin.com/f33e6da7c

[David Cuccia]

Isn't this what Windows Workflow is supposed to help solve? It's a state machine domain specific language that's process and thread agile.

[Simon Cooke]

I don't know if you'd trust the code it generates for games though - it's designed for business logic. I wouldn't put bets on it being spectacularly optimal - and the architectural framework may be too much overhead. Of course, I could be wrong.

[Dave Mark]

Steve Rabin put together a decent FSM class for the book "AI Game Programming Wisdom". It condenses a lot of the extra code in those switch statements down via macros. The functionality is the same but it is far more readable.

[teamonkey]

If you can jump back and forward to different states I've found it's much better to use decision trees. That is, each loop you detect which state you should be in and then see if this is any different to the last state you were in. Compared that to the "big switch" where you jump into the case determined last time round, then within that detect which state you should be in next time.

It's a bit of an alien way to think about state machines, but it becomes crystal clear when working out the logic on paper and I find it cuts down on state transition bugs and produces more solid code.

Other than that, use a big transition table of functions for the states and transitions (easier to do in a scripting language or functional language like F#; C#'s delegates are a bit messy). You can then use a graphical tool to make it easier to maintain the table.

[Charlie Tangora]

GOAL (the lisplike that the Jak games were written in) actually had a "suspend" function for game objects - what it did, effectively, was save off the stack and registers in a little buffer then longjmp out to a known point in the game object setup code. The next frame, it wouldn't call the object's update directly, it'd restore the stack and then longjmp back into the suspend function. Then suspend would return, and the calling object would generally be fooled into thinking nothing untoward had happened.

So you could get coroutine-like behavior. In GOAL syntax:

;;do some stuff
(while (not (ready)) suspend)
;;do some other stuff
(while (on_route) suspend)
;;do more stuff
(while (talking) suspend)

Our feeling was that it would be possible to get this working in a C/C++ environment, although it would mean some very strange code. We haven't done it yet, though. I'd be very interested to see someone try it.

[Kriss Daniels]

You want to be using Lua + coroutines or something similar but you wont find me recommending any of the similar options :)

Also your video downloads are like from the 90s, if you fear the quality of icky flash at least use stage6.

[Rafael]

This is a very old post but im wandering, what solutions did you get?
These solutions posted doesnt seem better than the spaghetti code,
I am thinking just like you did and I could use a few ideias.

[Jamie]

Hey Rafael - the answer is I still use the big-ass switch statements (sometimes broken into functions, sometimes not) - with it in the back of my head that I'll refactor if it gets out of control, but since I've written that post I've never felt the need to refactor any of the fsm's I've made. TSTTCPW, I guess.

[Rafael]

hey man,
i read this article and i thought this is awesome way to do state machines. What that make me think like this is the use of enter and exit methods.
well, read if you want, its about state pattern and I recomend.

[Rafael]

this is the article
http://www.ai-junkie.com/architecture/state_driven/tut_state1.html
forgot to post

[David Cuccia]

Abandoned my state machine infatuation for a few years and just came back to it. Some C#-related items I came across this evening (seems that the performance of Windows Workflow has increased dramatically since WF 1.0):

http://stackoverflow.com/questions/1517196/how-to-write-state-machines-with-c

http://stackoverflow.com/questions/1617894/whats-the-bestwhen-performance-matters-way-to-implement-a-state-machine-in-c

http://code.google.com/p/stateless/

http://wf.codeplex.com/wikipage?title=Microsoft.Activities.StateMachine

[Jorge]

So easy with Quest3d!
http://support.quest3d.com/index.php?title=Chapter_3.8:_Finite_State_Machine