Chapter 38. FiniteState Machines
Key Topics
Finitestate machines are a model of computation with a limited amount of memory known as a state. Each machine has only a finite number of possible states (for instance, wander or patrol). A transition function determines how the state changes over time, according to the inputs to the finitestate machine. There are two different categories of state machines.
Finitestate automata (FSA) do not generate any output until a terminal state is reached. They can be used to recognize patterns (for instance, interpret enemy actions) or classifying sequences (for instance, determining a strategy). Finitestate machines provide an output every time an input symbol is consumed. They can be used to model the state of thought of nonplayer characters (NPCs), such as their current task and how they need to react to the situation (that is, sequential control).
The game AI designer who crafts behaviors manually generally creates finitestate systems. Because they are so intuitive and simple to implement, they are the most widely used form of AI used in games. Not only are they widely applicable, they are also very efficient.
This chapter covers the following topics:
The theory behind finitestate automata The differences in representation between Mealy and Moore machines, and variations of finitestate techniques The array and graphbased representations Finitestate systems as a control technique that can be used to drive the behaviors of NPCs The problems with procedural implementations of finitestate techniques The benefits and pitfalls of the finitestate machine as a technique for game AI development
The theory in this chapter is not only used to provide behavioral control for an example animat, but also to model the emotions in the preceding chapter.
