Navigation: Overview >> Working Group on Finite State Machines

Working Group on Finite State Machines

Finite state machines are an indispensable tool in every game programmer's toolbox. The finite state machine (or finite state automaton) in its simplest form is defined as a set of states S, an input vocabulary I, and a transition function T(s,i) mapping a state and an input to another state. The machine has a single state designated as the start state, where execution begins, and zero or more accepting states, where execution terminates.

FSMs are often depicted graphically using flowchart-like diagrams in which states and transitions are respectively drawn as rectangles and arrows. Graphical representations of FSMs are common, the Unified Modeling Language (UML) reserves one of its nine diagram types just for state machines.

An FSM is a concise, non-linear description of how the state of an object can change over time, possibly in response to events in its environment. The implementation of FSMs in games always differs from the theoretical definition. Some code is associated with each state so that as the object's state changes, its behavior changes accordingly. Moreover, the transition function is broken up and its internal logic distributed among the states so that each state "knows" the conditions under which it should transition to a different state.

Game character behavior can be modeled (in most cases) as a sequence of different character "mental states" - a change in state is driven by the actions of the player or other characters, or possibly some feature of the game world. In an FSM-based behavior, the states describe how the character will act, and the transitions between states represent the "decisions" that the character makes about what it should do next. This "decision-action" model has the advantage of being straightforward enough to appeal to the non-programmers on the game development team (such as level designers), yet still powerful. FSMs lend themselves to being quickly sketched out during design and prototyping, and even better, they can be easily and efficiently implemented.

The FSM working group seeks to define a standard that captures the simple yet powerful way in which FSMs can be put to use. The working group has members from game development, middleware companies, and academia. Approximately 300 messages transpired last year, both on SourceForge and via direct e-mail.

Goals for a Finite State Machines Interface Standard

The goals of the FSM Working Group are to:

  1. have a unified meta description of finite state machines
  2. define an XML standard meta description of FSMs to enable interoperability of vendor packages featuring FSMs.
  3. create a standard C++ and Java API for implementing a data driven FSM described in our XML files
  4. create a best-practices guide for the many varieties of FSM implementation

Progress

  1. The group has adopted the concepts, nomenclature, and graphical notation of UML to describe finite state machines.
  2. The XML description of FSMs is in progress. Several 3rd party standards have been evaluated.
  3. We are in the process of creating requirements for a standard API and will next move on to specification.
  4. FSM working group member Dan Fu and Ryan Houlette have written a best-practices article for AI Wisdom 2; our own will take inspiration from that work.

Group Members

Current members of the working group on finite state machines:

Navigation: Overview >> Working Group on Finite State Machines