Finite State Machines (FSM)
By ai-depot | July 8, 2002
A Finite State Machine Framework
In this section we will take a look at the implementation of finite state machines from broader perspective. We will investigate how a finite state machine can be implemented, and take a look at a framework that can facilitate multiple FSMs in a simulated real-time environment.
A single FSM on its own is of little use; therefore we need to investigate implementations from a broader view to understand where a single FSM plugs in. We will analyze portions of the finite state machine framework from the computer game Quake, in attempt to understand how to make use of the technique in a real world application.
One possible way to implement finite state machines is to have a controller of some type which acts as switch box. When the thread of execution swings around to execute code of the FSM, it is pointed at the controller which evaluates or determines the current state, usually through the use of a switch (case) statement or if-then-else statements. Once the current state is determined, the code for that state is executed, actions performed and possibly state transitions for the next time the FSM is executed. The controller may be a simple switch statement evaluating an integer, but an implementation may see the controller performing some pre-processing of inputs and triggering of state transitions before-hand.
Figure 3.1: A FSM implementation where the controller acts as a switch box to determine which state to run. The red line denotes the thread of execution.
The implementation that the programmers at id Software have chosen could almost be considered to have Object-Oriented (OO) feel (though the implementation is not OO). As mentioned before, the game world is populated by entities, and as such a generic entity structure is used as their basis. Each entity in the collection of entities is provided with some execution time by calling its “think” function. The entity is executed by the game code in what could be described as a polymorphic manner. Entities have a common interface (because they are all the same data structure), and this interface consists of function pointers which are used to execute entity specific and entity non-specific code as either action outputs or input events for the FSM.
An example; most entities are affected by damage. Damage can be inflicted by many things like a rocket projectile for example. When a damage trigger is transmitted to another entity, its pain function pointer is called, thus triggering a state transition of the effected entity into possibly a death or attack state. Key point: The damage inflicted is an input to the FSM, which may act as a trigger for a state transition.
In essence the same switch-box technique described in figure 3.1 is used, where the entities base data structure provides function pointers which act as the “switches”. When an entity is given a chance to execute its state, its “think” function pointer is called. If previously a damage input was received, the entity may have had a state transition into its “die state”. When the thread of execution runs, the objects “die state” code is then run (via a polymorphic call of the entities think function), removing the entity instance from the game world.
Rather than further explain using theory, let�s take a look at a practical example from the game Quake. A dog is a simple monster that wishes�s to attack the player or any other monster that angers it, much like the previously seen Shambler monster.
Figure 3.2: Finite State Representation of states, actions, transitions and input events for a Dog monster in Quake.
Figure 3.2 shows the four main states of a Dog monster from Quake. Superimposed over that are the main actions performed in each of those states. Some map directly to functions, others map to chains of function calls. The representation clearly shows the five main input event actions with dark borders which are called as outputs of other finite state machines. There are two types of actions displayed, the gray background represents the dog monster specific code, and the white represent framework code used by all monsters.
The figure is a good diagrammatical tool for showing what monster specific code needs to be written and where it fits into the framework. It is not a complete representation, for example, in regard to the code executed after spawning, there are other “swim” and “fly” start actions used by some monsters that can swim and fly as opposed to our walking dog. Also there is a third attack sub-state called “slide attack” which is not relevant to the dog monster.
It can be seen that although the design of a FSM on paper may be clear cut and seem easy to implement, when it comes to implementing a larger number of them, such as all the monsters in a computer game, it is easy and probably necessary to blur the boundaries of the states. In figure 3.2 we do not see well defined functions representing states as may have been expected, instead functions are shared by states and FSMs. In this example it is clear that core actions have been decomposed and their functionality abstracted to be incorporated into the framework to be used by all monsters of the game. It is a nice approach for speed of execution, maintainability and code reuse, but poor due to a moderate level of complexity (time must be invested to trace the execution path).
The finite machine is provided with execution time through its think function. It evaluates inputs from its inputs from of the game world, but can directly receive specific events as input from the output of actions performed by other FSMs. These include a touch, use, pain and die events. These events can trigger state changes of the effected finite machine, for example, as seen in Figure 3.2 a touch input event is a collision determined by the game as it advances the game physics. When received in the above example, and if the dog monster has a valid “touch” sensor function specified (which may not always be the case), it will run the code in that function and possibly have a transition to its missile attack sub state or to its attack state for a revaluation of its attack sub-states.
It is becoming clear that a FSM in this domain is very useful as a control mechanism and when used on a larger scale as seen, it is powerful. This example shows that a FSM framework can provide the ability for a simple multi-agent system, where each FSM system could be considered an agent (intelligent; uses AI techniques, autonomous; acts independently). The FSMs have sensor functions implemented specifically to handle expected events, and also has effector functions which are simply the actions performed in the game world.
Tags: none
Category: tutorial |
