Chapter 38. Finite-State Machines
Finite-state 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 finite-state machine. There are two different categories of state machines.
Finite-state 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).
Finite-state 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 finite-state 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 finite-state automata
The differences in representation between Mealy and Moore machines, and variations of finite-state techniques
The array- and graph-based representations
Finite-state systems as a control technique that can be used to drive the behaviors of NPCs
The problems with procedural implementations of finite-state techniques
The benefits and pitfalls of the finite-state 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.