Overview

This chapter documents all the different variations of finite-state machines that prove useful in computer games. This includes fuzzy, nondeterministic, and stochastic state machines. Further extensions to finite-state machines—such as hierarchies—are left until the next chapter.

Before starting the explanations, it seems appropriate to make clear distinctions between the different approaches, but also try to point out similarities (see Table 40.1). This can be somewhat confusing, because the mathematical background spans over multiple domains; terminology, and even interpretation, varies from one subject to another.

Table 40.1. The Different Variations of Finite-State Computational Models and Their Relationship to Each Other

	Acceptor	Transducer
Deterministic	Finite-state automaton	Finite-state machine
Nondeterministic	Nondeterministic FSA	Nondeterministic finite-state machines
Probabilistic	Hidden Markov chain	Markov model
Fuzzy	Fuzzy FSA	Fuzzy FSM

For each of the paradigms, there are acceptors (that determine whether an input sequence is valid), recognizers (classifying an input sequence), and transducers (outputting values matching the inputs):

• Deterministic models are fully predictable and present no ambiguity when computing the results.

• Nondeterministic models are less explicitly defined; they allow ambiguous cases, but no hints are provided as to which is correct. The option that generates the right result should be chosen; the trick is to decide how to achieve this.

• Probabilistic models have probabilities associated with each of the transitions. These can be used for analysis or interpreted stochastically.

• Fuzzy models have each state represented as a fuzzy variable. The transitions can be interpreted as fuzzy rules applied over the states. Each of the fuzzy states has a degree of membership that changes throughout the simulation.

This brief overview is intended to remove any possible misinterpretation of the techniques. Everything will become clear with the following technical coverage.