Navigation: Overview >> Working Group on Finite State Machines

Working Group on Finite State Machines

To create standards interfaces for game related finite state machines - that is the mission of the ten members of this AI Interface Standards Committee's (AIISC) working group. Professions include game AI and non-game AI developers, academics, consultants and AI middleware vendors. Nick Porcino manages the work of the group in the role of its coordinator. Until now, we contributed around 180 postings to our forum.

Goals for a Finite State Machines Interface Standard

The primary goal of the finite state machines (FSM) group is to define a standard interface that facilitates integration of finite state machines with game engines. To that end, our major goals have been the following:

  1. identify how FSMs are commonly embedded in games,
  2. define a common language to describe finite state machines,
  3. define an XML description of FSMs for interoperability between tools,
  4. define a C++ API whereby FSMs can be efficiently and easily interfaced with other systems.

FSM Committee Motivation

Finite state machines are arguably the most popular technology in game AI programming today. They are conceptually simple, efficient, easily extensible, and yet powerful enough to handle a wide variety of situations.

The finite-state machine (or finite-state automaton) exists in its simplest form from computational theory, defined as 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.

Less abstractly, 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 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.

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 popular, so popular that the Unified Modeling Language (UML) reserves one of its nine diagram types just for state machines.

Because game character behavior can be modeled (in most cases) as a sequence of different character "mental states" - where change in state is driven by the actions of the player or other characters, or possibly some feature of the game world - game programmers often find that finite state machines are a natural choice for defining character AI. 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 impressively 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 committee seeks to define a standard that captures the simple yet powerful way in which FSMs can be put to use.

FSM Committee Progress

So far, the committee has worked on the first two phases, exploring how game developers use FSMs, and reaching a consensus on a common language to describe an FSM.

FSMs in Practice

Early on, we examined the ways in which FSMs were implemented in practice. We determined that two common methods were "flat" and "hierarchical". By "flat" we mean the standard way in which FSMs are thought of - as atomic states and transitions between them. A "hierarchical" (or "nested") state refers to states that encapsulate other FSMs. Thus, being in a "hierarchical state" really amounts to being in a set of atomic states.

"Inherited" states are object-oriented implementations of states. This type of state inherits all the functionality (and possibly transitions) of a pre-existing state but can change its behavior.

Another implementation distinction we uncovered was "polling" versus "event-driven." Polling implementations have FSMs actively query states of the world when executing transition logic. Event-driven approaches, by contrast, wait for the game engine to signal some event. This event will drive state execution and transition logic. Event-driven approaches are most efficient, and have been the current focus.

Representing FSMs

As it turns out, there are already a number of existing pieces of work that implement or depict finite state machines. For example, SourceForge hosts a number of FSM projects, such as the generically-named Finite State Machine, a State Machine Compiler, a Qt-based FSM called Qfsm, a Finite State Machine Language, and our dear leader's project Fizzim.

In terms of authoring and depicting FSMs, we examined a number of graphical methods, such as GraphViz and an emerging graph standard called GXL.

State of Work

Currently the FSM group is in a stage of discussing requirements on a common language to describe an FSM. From there, we will prescribe an XML-based ontology and game engine interface.

Group Members

Current members of the working group on finite state machines:

This section was written with the help of Ryan Houlette of Stottler Henke Associates.

Navigation: Overview >> Working Group on Finite State Machines