« How Much Planning - High Level Concepts? | Main | Manager In A Strange Land: Theory of Drag, Part 1 »

December 13, 2007

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

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

Your Information

(Name is required. Email address will not be displayed with the comment.)

Jamie's Bragging Rights

  • Spider-Man 2
    The best superhero games of all time Game Informer
    Top five games of all time Yahtzee Croshaw
    Top five superhero games of all time MSNBC
    Top 100 PS2 games of all time Official Playstation 2 Magazine
    1001 Games You Must Play Before You Die Nomination for Excellence in Gameplay Engineering Academy of Interactive Arts & Sciences
  • Schizoid
    Penny Arcade PAX 10 Award
    Nominated for XBLA Best Original Game
    Nominated for XBLA Best Co-Op Game