Chapter 40. Nondeterministic State Machines

Key Topics

• Overview

• Fuzzy-State Machines

• Nondeterministic State Machines

• Probabilistic State Machines

There are various types of extensions to finite-state machines. These range from nondeterministic models (with ambiguous transitions) to probabilistic models (each transition has a probability), including fuzzy models (where every state is a fuzzy variable).

There are few changes to be made to finite-state machines to support these variations. The representation is still graphlike, and the data structures remain very similar.

Each extension to finite-state machines has its own advantage. Nondeterministic models greatly simplify the modeling of large finite-state machines and the combining of smaller ones together. Probabilistic models can be used to analyze the likelihood of obtaining different sequences, or even to generate stochastic output sequences. Fuzzy models combine the advantages of fuzzy logic with finite-state machines; partial degrees of truth on the inputs and state values are supported, and smooth outputs can be generated.

In games, this can simplify the development of nonplayer character (NPC) behaviors, as well as improve the final results by making the outputs less predictable and with smoother transitions.

In the nondeterministic case, it's best to convert the machines to deterministic ones before simulation. For probabilistic models, the simulation of the finite-state machines is updated to take into account the changes in representation. Each transition is just chosen stochastically.

For the fuzzy system, the finite-state machines can be trivially converted to a set of rules and fuzzy variables. Therefore, the same fuzzy engine can be used to simulate the fuzzy state machine.