Different FSM patterns - your experience?

This topic is 3999 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Just a quick poll for preferences and experiences: I have been using a design pattern that, while having a "state" class that helps me process state changes, the states themselves are actually an enumerated type in the actual agent class itself. Therefore, all the logic for any given state and/or the transitions is, of course, also in the agent class itself. I have also seen (but not used) a design pattern where each different state is its own class (inheritted from a generic "state" class). The agent simply carries a pointer to the object of its current state. I won't put my opinions or observations here yet. I don't want to cant the replies in a particular direction. I would like, however, to see if any of you have used both types - and what you see as the advantages and disadvantages of them both. For those that have used only one, please feel free to respond as well with your perception of the situation.

Share on other sites
I personally like to split behaviors into seperate classes by seperating the states. It's much easier to extend them and add new ones this way, though it's a bit of a pain to then have each state need a pointer back to the agent.

Share on other sites
Good timing for your question Dave... I've been wrestling with an FSM design and integration issue these past few weeks and perhaps some of the answers people give might help me out!

From my own experiences, the different approaches have paralleled my OO programming development. I used to build agents that did not explicitly implement a FSM to manage their logic. The logic was just built into the agent design. There was typically an interface layer (sensors and actuators) and an internal agent function that produced the mapping from sensors to actions. The FSM was implicit in that agent function. This worked reasonably well for single agents and robots I was playing with, but as soon as I moved toward multi-agent simulations and game environments, I found myself duplicating work between agents.

Once I'd started reading some of the Game AI literature I came around to the idea of explicitly designing the FSM class to handle the logic processing. Eventually I took up the state design pattern that is quite prevalent today and encoded states as classes. However, I've come to find problems with that recently. You can't do it in infinite state spaces (for obvious reasons), so if your domain is continuous and not easily discretised, you end up either going back to implicit FSM design, or you take a different tack; encoding agent behaviours as 'states' and then determing the outcome of behaviours depending on the current domain state. This becomes most useful when the outcomes of the agents behaviour depend on the external environment state. I've subsequently noticed that many examples in the game AI literature actually do this.

At the moment I'm tackling a generic behavioural machine class that incorporates parameterised behaviours. An example of the use of such a machine would be in high level behavioural description of an aircraft. You can define behaviours like turn, climb, descend, land, takeoff, etc., which given parameters become commands. The parameters change the execution of the behaviour depending on factors internal and external to the agent.

My final conclusion? I tend to favour the state-as-class design pattern. It's easier to handle things like logging, easier to manage the extension of the state space and ultimately I believe it makes you think more clearly about state flow logic, because you can separate out the logic of flow control.

Cheers,

Timkin

Share on other sites
As a follow up. I've modelled my state machine very heavily on this design:

Handling Complexity in the Halo 2 AI

Share on other sites
I had a scripted FSM but since reading Game Programming AI by Example I really like the goal driven approach, where goals are composed of small tasks and are pushed onto a stack. Each possible high level goal calculates a desirability for the task and the highest scoring goal is performed. When a goal is completed or failed the agent then continues will goals which are on the stack. So an enitity may have been tracking to a position and came under attack. It would then be decided either to fight or flee .... after the instance if the entity is still alive it would continue on with the task set before the conflict if it is still valid.

I recommend a read of the book it is really good. The FSM section of the book is available online.
http://www.ai-junkie.com/architecture/state_driven/tut_state1.html

Share on other sites
I've written FSMs using switch statements and using virtual functions. Each idiom has strengths.

In my opinion, for smaller FSMs where the states have more differences than commonalities, there's little reason to go with the OO approach. The "game state" FSM of an application is a good example of this. Most of the time with AI, though, this pattern emerges accidentally, as a boolean variable or two grow into a more complicated state space. So I do think this idiom is overused.

In situations where there are "things about" the state, the OO approach really comes into its own. As an example, I use a state machine to maintain the current action of a character. In addition to doing whatever it needs to do, I can determine under what circumstances the action can be interrupted, and other useful properties. Doing this without classes would require parallel switch statements, which are an absolute pain in the ass to maintain.

Share on other sites
Before this FSM I used the Goal queue stuff as described in Game Programming AI by Example. It's pretty good, but after some time I got tired of its limitations. The seperation of goals from evaluators becomes a pain. Any complex evaluation of the goal you do in the evaluator that results in specific parameters of the goals you have to cache in the evaluator, and pass it to the goal, or re-do the work in the goals ReplanSubgoals. Also, if your goals are data driven and need parameters from script or such, you need to cache that in your evaluator as well, also passing it to the goal on creation, since goals are created constantly and pretty often. It would be inefficient to pull their parameters from script or whatever in their ReplanSubgoals function.

Overall it's a nice system, but the above problems had me re-thinking using it, and either replacing or modifying it to consolidate the desirability calculations as part of a more persistent goal class, which turns out is what the Halo2 article is about and more. Additionally, I'm doing low level states that are run simultaneously with high level states, which is part of the FSM design as well, so another bonus over the goal approach. For example, there is a low level FollowPath function that is responsible for moving the agent along a path. I prefer this method greatly over a queue of tens or hundreds of Goto goals, whose seperation into different class instances really serves little purpose imo.

Share on other sites
Quote:
 Original post by DrEvilI prefer this method greatly over a queue of tens or hundreds of Goto goals, whose seperation into different class instances really serves little purpose imo.

I don't think any sane person would actually implement a long sequence of waypoints on a path as instances of a 'waypoint class', or at least they wouldn't once they had more than a few waypoints along a path. Of course, there is a natural mapping between that and a path following behaviour through the specification of a path class that can respond to agent queries about coordinate locations along the path (which the agent may steer toward, or move through, etc).

One thing I'd like to hear feedback on (so long as it doesn't hijack the thread from IFs original intent) is this prevalence of state machines as 'behavioural machines'. I read through the Gamasutra article linked above and noted that the Halo 2 HFSM was another example of this design pattern. This, at least to me, appears to be a perversion of the classic FSM, but one that is quite relevant and useful in game AI design, which is often concerned with designing actors that instantiate gameplay requirements. Do others find it useful to work/think/design in this behaviour space and if so, why? If you do, how are you positioned with regards to the original question in this thread: do you prefer to encode such behaviours within the agent, or in a separated machine+logic idiom?

Share on other sites
There are really two things here: the actual states of the machine, and the actions/operations/events that can occur. If you think about this, to encode a state machine with n states and m actions, you would need n*m functions. So that's the root: in a system that dispatches on states (switch, for example), you have to modify m different pieces of code to add a single state. In a system that dispatches on actions (virtual methods, for example), you need to change n pieces of code to add a single action.

There's no real getting around it. If you are lucky, you have some intuition about your problem domain and you can pick the style that suits it best.

I'm not a Gamasutra member, so I can't read the link. While the theory of FSM's is interesting, I really doubt game AI programmers use them for this reason. Really, people use FSMs because they allow you to specify behavior using a simple causal framework. It encapsulates the if-then-else decision making process that everybody is familiar with.

Share on other sites
Funny that Mat's book came up - that is where I first saw the idea of state-as-class. I was startled by it at first but I can see where it has benefits. Reading that and poring through his code was what caused me to ask the question in the first place. (note that I am not discussing his goal stack idea here)

However, I had also used Steve Rabin's FSM class from Game AI Wisdom (it was also in a Gems book). He has a very easy way of setting up a sequence of FSM states using what are (behind the scenes) actually macros. It makes it very easy to identify your states and have logic for "on enter" "on update" and "on exit". It's easy to read and program. But... it means that all your transition and action logic is in that one function (and it gets lengthy when you have a lot of states) or for readability you have to split it out to other functions that are called from inside that State function. Now you have started to scatter what was once a very streamlined collection of stuff. *shrug*

Again, benefits to both...

Share on other sites
Quote:
 Original post by The Reindeer EffectI'm not a Gamasutra member, so I can't read the link.
Holy crap... why not? It's free, dude!

Share on other sites
Quote:
 Original post by TimkinOne thing I'd like to hear feedback on (so long as it doesn't hijack the thread from IFs original intent) is this prevalence of state machines as 'behavioural machines'. I read through the Gamasutra article linked above and noted that the Halo 2 HFSM was another example of this design pattern. This, at least to me, appears to be a perversion of the classic FSM, but one that is quite relevant and useful in game AI design, which is often concerned with designing actors that instantiate gameplay requirements. Do others find it useful to work/think/design in this behaviour space and if so, why?

In games, I don't think I've ever seen a state machine used to represent the overall environmental states or anything like that. They've always been used purely to represent one sub-state of the game, usually the current behaviour of an actor.

Why? I think it's because you start off thinking about developing AI for the actor, and that becomes classified into several separate behaviours, which tend to lead from one to the other, and a FSM is a natural representation of that.

I think that modelling the more general domain of a game with state machines never gets considered because almost all the important data is continuous. Personally I can't think of many overall game situations in my experience that could be adequately modelled with a FSM.

Quote:
 If you do, how are you positioned with regards to the original question in this thread: do you prefer to encode such behaviours within the agent, or in a separated machine+logic idiom?

In our current project, all behaviour is within the agent, though the external game environment, and behavioural state transitions are done by the agent as a result of processing its own implicit state and that of the environment. But it's sometimes practical to have a State hierarchy of objects that act on an Actor hierarchy which can give some useful separation and re-use.

Share on other sites
I think part of the disconnect may be the difference between the 'State' design pattern and the mathematically inspired FSM concept. The State design pattern is much more general and flexible.

In my experience, most game AI is written with a focus on behaviors. Designers know what they want to see in game and they typically think in behaviors. State systems are nice as they provide a way to encapsulate behavior and the additional state it requires.

Thinking about this a bit more, there are two interesting ramifications:

1) In doing this, we are encoding a production system in a state machine along with the functionality/data for the AI to act.

2) Using states this way is very close to a strategy pattern. We think of most AI 'behavior states' as highly differentiated, but in practice each state is an alternate 'thing for the AI to do' (typically with the same interface). If we ignore the functionality provided by each behavior state and look at it abstractly, it might end up closer to a strategy pattern.

Coming full circle for the OP, I've used both approaches. In general, encapsulation of data and functionality is good. It can cause implementation issues if you don't refactor logic out into reusable chunks, but it generally scales well.

You also might want to consider a more data driven approach. I think a few of the AI Wisdom books have examples, but the idea is to move the transition definitions out of code entirely. Depending on who is using the system, this might be worth evalating.

Share on other sites
Kylotan and BrianL: I definitely agree with both of you on this. I think you've nailed the issue precisely (and it seems to fit my intuition). There are two fundamentally different types of games as I see it: those that engage the player as an actor and those that challenge the player to manipulate the game state without having to be a part of it. The latter is most notably evident in puzzles games; the former in genres such as FPS and RPG.

Of the genres that depict players as actors, my intuition is that it is only natural and correct to design gameplay in terms of interactions between actors and interactions with an environment. This leads, as both of you noted, to thinking in terms of behaviours. We often start off with a high level behavioural descriptor (such as kill enemy) and then break this down via decision heirarchies into implementable actions that we hope will achieve the goal. This is essentially a planning process, where we end up with a 'state machine' that implements the conditional logic of plan execution that we require to deal with a dynamic game. Thus, our state machine actually represents a policy (universal/conditional plan).

I do think you find more classical implementations of FSMs depicting actual game states in traditional game genres like puzzle games. Game trees, for example, are just an expansion of a state machine along a subset of finite depth path sequences.

So what does this mean for Dave's original question? I suspect it gets down to issues of extensibility and reusability. Both the state-as-class pattern and the internal, conditional logic pattern (e.g., compiler macros) have issues with extensibility (they each trade off opposing aspects to make the other more efficient) but the state-as-class pattern seems to me at least to admit reusability more cleanly. Ideally, I think there is only one golden rule to follow and that is that it should be easy to code and easy to understand and that it should improve design and production process efficiency, rather than hinder it. If your choice does that, then I don't see a problem with it! ;)

Cheers,

Timkin

Share on other sites
I thought I would post some snippets for a visual.

Steve Rabin's FSM class as used in one of my classes. In this case, Class CGate inherits from StateMachine but otherwise all states and logic are kept in CGate:

// H file //////////////////////////////////////class CGate : public CFacility, public StateMachinepublic:        virtual bool States( StateMachineEvent event, int state );// CPP file //////////////////////////////////bool CGate::States(StateMachineEvent event, int state){smBeginStateMachine	///////////////////////////////	smState(GTS_UNLEASED)		smOnEnter			gFields.SetDirtyFlag(mField, true);		///////////////////////////////	smState(GTS_OPEN)		smOnEnter			gFields.SetDirtyFlag(mField, true);							///////////////////////////////	smState(GTS_OCCUPIED)		smOnEnter			gFields.SetDirtyFlag(mField, true);			//printf("Gate %s at %d is occupied\n",mName, mField);		smOnExit			mAircraft = NULL;	///////////////////////////////	smState(GTS_TURNING)		smOnEnter			gFields.SetDirtyFlag(mField, true);			//printf("Gate %s at %d is turning\n",mName, mField);			short minutes = CalcTurnTime();			mNextStateTime = gGameData.GetTime() + replCHighTimeSpan(0,0,minutes,0);		smOnUpdate			if (TimeToChangeState()) {				SetState(GTS_OPEN);			}	///////////////////////////////	smState(GTS_BROKEN)		smOnEnter			gFields.SetDirtyFlag(mField, true);smEndStateMachine}

Mat Buckland's method where an agent has a pointer to other states:
class MinersWife : public BaseGameEntity{private:  StateMachine<MinersWife>* m_pStateMachine;  {    //set up the state machine    m_pStateMachine = new StateMachine<MinersWife>(this);    m_pStateMachine->SetCurrentState(DoHouseWork::Instance());    m_pStateMachine->SetGlobalState(WifesGlobalState::Instance());  }  ~MinersWife(){delete m_pStateMachine;}  StateMachine<MinersWife>* GetFSM()const{return m_pStateMachine;}};/// in another file titled "Miner's wife owned states"class WifesGlobalState : public State<MinersWife>{  private:    WifesGlobalState(){}  //copy ctor and assignment should be private  WifesGlobalState(const WifesGlobalState&);  WifesGlobalState& operator=(const WifesGlobalState&); public:  //this is a singleton  static WifesGlobalState* Instance();    virtual void Enter(MinersWife* wife){}  virtual void Execute(MinersWife* wife);  virtual void Exit(MinersWife* wife){}  virtual bool OnMessage(MinersWife* wife, const Telegram& msg);};//------------------------------------------------------------------------////------------------------------------------------------------------------class DoHouseWork : public State<MinersWife>{private:  DoHouseWork(){}    //copy ctor and assignment should be private  DoHouseWork(const DoHouseWork&);  DoHouseWork& operator=(const DoHouseWork&);public:  //this is a singleton  static DoHouseWork* Instance();    virtual void Enter(MinersWife* wife);  virtual void Execute(MinersWife* wife);  virtual void Exit(MinersWife* wife);    virtual bool OnMessage(MinersWife* wife, const Telegram& msg);};//------------------------------------------------------------------------////------------------------------------------------------------------------class VisitBathroom : public State<MinersWife>{private:    VisitBathroom(){}  //copy ctor and assignment should be private  VisitBathroom(const VisitBathroom&);  VisitBathroom& operator=(const VisitBathroom&); public:  //this is a singleton  static VisitBathroom* Instance();    virtual void Enter(MinersWife* wife);  virtual void Execute(MinersWife* wife);  virtual void Exit(MinersWife* wife);  virtual bool OnMessage(MinersWife* wife, const Telegram& msg);};//------------------------------------------------------------------------////------------------------------------------------------------------------class CookStew : public State<MinersWife>{private:    CookStew(){}  //copy ctor and assignment should be private  CookStew(const CookStew&);  CookStew& operator=(const CookStew&); public:  //this is a singleton  static CookStew* Instance();    virtual void Enter(MinersWife* wife);  virtual void Execute(MinersWife* wife);  virtual void Exit(MinersWife* wife);  virtual bool OnMessage(MinersWife* wife, const Telegram& msg);};

Share on other sites
Quote:
 Original post by dmailI had a scripted FSM but since reading Game Programming AI by Example I really like the goal driven approach, where goals are composed of small tasks and are pushed onto a stack. Each possible high level goal calculates a desirability for the task and the highest scoring goal is performed. When a goal is completed or failed the agent then continues will goals which are on the stack. So an enitity may have been tracking to a position and came under attack. It would then be decided either to fight or flee .... after the instance if the entity is still alive it would continue on with the task set before the conflict if it is still valid. I recommend a read of the book it is really good. The FSM section of the book is available online. http://www.ai-junkie.com/architecture/state_driven/tut_state1.html

This works very well in many cases. I've used it before in retail games, and works really well, and is very expandible. AI stacks are sooo useful.

Share on other sites
Quote:
 Original post by KylotanPersonally I can't think of many overall game situations in my experience that could be adequately modelled with a FSM.

The only ones i've experienced have been turn based games. Even then though the physics is running continuously.