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.

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.

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

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

Handling Complexity in the Halo 2 AI

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

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.

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.

Quote: Original post by DrEvil
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.

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?

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.

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...