FSM
From DmWiki
Finite state machines are a generalisation of the type of code you naturally end up writing to control simple NPCs. In today's massive games, FSMs can be over-used to a point where their structure works against the programming team. They are, however, still a very useful and important tool.
| Table of contents |
|
2 Static vs. dynamic FSMs |
A simple FSM
The best way to explain an FSM is to show some simple pseudo-code. Here is a possible FSM for a guard of some kind:
At loading time:
state = "calm"; strength = 100;
At run time:
if (state == "calm") {
wander();
if (seenNearbyEnemy()) {
if (seenByEnemy()) {
state = "attack";
}
else {
state = "ambush";
}
}
}
else if (state == "ambush") {
hide();
if (enemyClose()) {
state = "attack";
}
if (seenByEnemy()){
state = "attack";
}
}
else if (state == "attack") {
gotoEnemy();
strike();
defend();
if (enemy.strength > this.strength + 1.2) {
state = "flee";
}
}
else if (state == "flee") {
runFromEnemy();
findHealth();
if (noEnemiesNear()) {
state = "calm";
}
}
If you've written many small games before, you will probably recognise the above structure. Note that the above is for demonstration, and in real-life thought would need to be given to how long until the script runs again, if commands queue, and other similar technical aspects.
When designing an FSM, change of state is usually represented by a transition, which can have several properties on its own. Transitions connect states and show from which state the FSM is allowed to change into another state (traversing a transition).
Representation of State
It is important to note that a State Machine is all about representing State - well, duh. To cope with the problem of overly complex FSMs in games, there are several important decisions to make before writing actual code.
The State Pattern
This pattern was described in detail by Gamma, et al. It improves on the simple representation of a state (by an enumerated type or several constants) by converting it into a class. Let's start with the base class for all state classes, which must contain virtual methods for each transition in the FSM. Additionally, there are virtual enter() and exit() methods, executed when the state is entered or left.
class BaseState {
public:
virtual void seenNearbyEnemy() {}
virtual void enemyClose() {}
virtual void noEnemiesNear() {}
...
virtual void enter() {}
virtual void exit() {}
};
Note how the base class provides default implementations for all methods (doing actually nothing), so the derived state classes only have to override the methods for the transitions they are allowed to travel along. Up next is the class for our state "flee":
class FleeState : public BaseState {
public:
virtual void noEnemiesNear() {
changeState(calmState);
}
virtual void enter() {
runFromEnemy();
findHealth();
}
};
As you can see, the state is now encapsulated in its class, no more complicated if- or switch-statements. Like already mentioned, these example have educational purpose. An actual implementation in a game would not be this simple.
The changeState() method is very much straightforward:
void changeState(BaseState * state) {
currentState->exit();
currentState = state;
currentState->enter();
}
Static vs. dynamic FSMs
One big problem when writing FSMs this way is their static nature. Changes can only applied to source code, so the programmer is responsible for what the game designer ought to do. Testing is very time-consuming, as each change requires quitting the game, running the compiler, and restarting. Although there are plenty of FSM libraries like boost::fsm (now Boost.Statechart), most of them are designed to make programming FSMs easier, but the design stays static. Each and every article I read on FSMs in game programming literature deals with static ones...
It would be great to be able to represent FSMs in XML form (or even graphically in a design tool), modify them at run-time and see the changes immediately. This of course requires run-time interpretation of the FSM behaviour, which can be a bummer in case of several hundreds of enemy AIs all simulated nearly in parallel.
Interpretation vs. code generation
The solution to this problem is moving from run-time interpretation of the FSM behaviour to run-time (or off-line) code generation. After the dynamic data of the FSM representation is loaded, instead of entering a loop which runs through the state machine graph trying to find and traverse the right transitions, let a code generator do the job of converting the dynamic FSM into a static one, be it C++ code like the above or an interpreted scripting language: it will be much faster than any interpreter, as you can make many optimizations.
For more information and sample code on FSMs, see An Introduction to Finite State Machines (http://www.devmaster.net/articles/fsm_intro/).
