Summary

There are two different subtypes of finite state techniques:

• Finite-state automata, used to recognize or accept sequences of input symbols by producing one output.

• Finite-state machines, capable of transducing an input stream into the corresponding outputs. Mealy and Moore machines are particular variations on the representation.

The essence of finite-state models is the transition function. There are different ways to represent and simulate it in practice:

• An array can be used as a lookup to find the next state based on the current state and the input.

• A directed graph allows the next state to be looked up as a link from the current state using the input symbol.

The graph-based implementation scales better with the number of states, and tends to perform more efficiently. Simple declarative models of the theory can be used as decision-making components, but procedural approaches are more convenient for control problems:

• Each transition is represented as a function that returns true if the state should change.

• Each state has an update procedure that is used to perform the corresponding actions.

Occasionally, there are problems with the procedural approach, notably loss of information and ambiguity in the transitions—which can result in unforeseen bugs in the behaviors. These can be resolved with a simple priority queue of messages if necessary.

Finite-state machines are one of the most suitable AI techniques for game AI development. That said, they have some conceptual problems that cannot be resolved by clever implementation. Chapters 40 and 41 discuss nondeterministic machines, probabilistic finite-state machines, fuzzy-state machines, and hierarchical-state machines. These remedy most of the other problems associated with finite-state machines.

The next chapter applies finite-state machines to modeling emotions, and provides a few examples of how to use finite-state machines in practice.

Practical Demo Fizzer is an animat that uses finite-state machines as an implementation of its deathmatch behaviors. Although the design is not particularly complex, Fizzer shows how behaviors can be crafted explicitly by a designer. Scaling up the capabilities of this animat is particularly challenging because of the rapid increase in complexity.