Finite State Machines (FSM)
By ai-depot | July 8, 2002
Practical Analysis
A Practical Analysis of FSM within the domain of first-person shooter (FPS) computer game
The intent of this section is to use a computer game to illustrate the conceptual workings of a FSM based on a practical rather than theoretical implementation. I will not attempt to provide insight into how the computer game works or even many specifics (code) of the implementation in the computer game. The FSMs discussed in this section have been coded, tested and released in production code, providing real world examples, within the domain of a first person computer game.
This section will provide two examples of finite state machines from a first-person computer game created by id Software [6] called Quake [7]. The reason I chose this product as the basis for the analysis was due the fact that game engine code has been released publicly under the GNU General Public License (GPL) [8] [9]. The other reason for this decision was because at the time the game was released, it was cutting-edge and had its code licensed by other company�s that produced further highly-popular titles such as Unreal and Half-Life, thus proving the success of the original product.
We are going to start with the analysis of something very simple. We will see that even through mapping the states of a simple projectile like a rocket, we can learn more about the very nature of FSM. I make no claim at being an expert in regard to Quake game code (this was my first excursion through it), so forgive me if my interpretations based on code do not directly map.
A rocket in Quake is a projectile fired from the Rocket Launcher weapon/item which may be possessed and operated by a human player.
Figure 2.1: State transition representation of a rocket projectile from Quake.
Rather than restricting myself and confusing the reader by using a formal notation as mentioned in the first section of this document, the finite state machine has been represented using an approach very similar to a State Transition Diagram. The blue boxes are the states, the orange the triggers and the arrows are the state transitions. The black boxes show the entry point and exit points of the system.
The diagram shows the full life cycle of the rocket projectile within the game. It is interesting to note that the projectile is spawned into existence as the product of an action of another FSM, namely that of the “rocket launcher” from its “fire” action. When the projectile instance dies it is removed from the game, and no longer exists.
This representation is a subjective interpretation of code. Another valid representation may break the “touch state” down further into touch and explode states. Personally I view explode as an action or effect performed by the rocket object in its touch state.
Another interesting note is that when the projectile is in its touch state, one of its effectors is to attempt to damage whatever it is touching. If it succeeds in damaging another entity in the game world, the damage action becomes an input which can trigger a state change of the effected entity into another state.
Quake makes extensive use of FSMs as a control mechanism governing the entities that exist in the game world. This has been provided by an interesting framework which is tightly related to the way FSM work in the computer game. For further discussion of this framework, please see section three.
Let�s take a look at a slightly more advanced FSM from Quake. A Shambler is a big bad monster entity from the single player component of Quake. Its mission in life is to kill the player, once it is aware of the player.
Figure 2.2: State transition representation of a Shambler monster from Quake.
Like the rocket projectile, this entity has an initial state (spawn state), and the system ends when the entity dies (die state). There are only four identified main states, but the Shambler is a good example that illustrates the ability to have a hierarchy of sub-states. Though the sub-states in this example could be considered actions of the “attack state”, they are also sub-states because the monster can only perform one (or be in one) of them per execution of the attack state.
When in the attack state, the Shambler instance makes a decision based on evaluated inputs whether to perform a melee (close up) or missile (long distance) style of attack on its goal. Upon selecting a melee type attack (melee attack state), the inputs are further evaluated, along with a random number to select a melee attack type (smash with both arms, smash with left arm or smash with right arm).
The use of a random number in the selection of a melee attack sub-state adds a level of unpredictability to the selection. Each level in the hierarchy could be considered a sub-finite state machine of the greater monster entity, and in this case the sub-FSM of the melee attack state could be classified as non-deterministic.
It is important to understand the use of layered or hierarchical finite state machines, because when used as seen in the Shambler monster it allows far more complex behaviors. This technique is heavily used in Quake by all entities in the game world. Because of this, a lot of code has been abstracted to be easily be used in many different places, actions such as movement, visibility assessments and so on.
This example has been greatly simplified to make it more readable. An example of this is in the triggers which cause the state transitions. When a state transition occurs from “Attack State” to “Idle State”, the trigger has been simplified as “lost goal”. It is true that the transition occurs due to the loss of the goal entity, but a goal can be lost by the Shambler in a number of ways evaluated at different points in the code, including time-out and damage from another entity.
Another key point regarding this example is the use of goals as the primary motivator for the FSM. This technique has not been discussed, though it is an example of the power and flexibility of FSM as a control technique. As well as possessing a hierarchy of finite state machines, the high level FSM is driven by the entities desire to locate a goal, and attack its goal. The goal is usually a human player or even another monster in the game world. It should be noted that whilst the monster is in its idle state, as well as just standing around it is also looking for goals to walk to (for roaming).
Quake did not provide the best single player experience imaginable, though it was and still is fun and addictive, both key attributes of the games success. It is good example, and a good learning tool that can show the power of both very simple finite state machines such as the rocket projectile, and slightly more complex FSM made up of a hierarchy of FSM and motivated by goals, such as the Shambler monster.
Tags: none
Category: tutorial |
