Chapter 38. Finite-State Machines

Key Topics

• Formal Definitions

• Representation and Simulation

• Control Logic

• Optimization

• Discussion

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.