On Finite State Machines and Reusability

Alex J. Champandard on September 4, 2007

Theoretically speaking, finite state machines (FSM) provide a specific type of logic, similar to regular grammars recognized by finite state automata. In practice also, FSMs are highly tuned to the problem they solve.

This is both a blessing and a curse for games — most of which use FSMs. They start off very simple, but can become very challenging to manage as they grow. It’s important to understand why this is the case if you want to build something better for the logic of your AI characters.

What is a State?

A finite state machine is based on the concept of a state, which typically consists of two things:

  1. A set of actions running at the same time (e.g. playing an animation, a sound, or waiting for a certain amount of time).

  2. A set of transitions with a conditional check to determine when to engage the next state.

States can be made quite generic and robust by adding many transitions to support all the desired cases. For simple problems, this is fine, but for large problems you need a more scalable approach.

Reusable Behaviors in Games

The challenge of game AI involves scheduling behaviors in a context sensitive way, and this requires increasingly large FSMs. The logic must work:

  • Depending on dynamic goals and tasks of the actor.

  • Adapting to the current status of the actor (e.g. health, emotions).

When using FSMs, the hard part is preventing the logic of each state from exploding in complexity with each new context you want to add, while at the same time keeping the number of states down to a minimum.

To do that effectively, you need to be able to divide up the responsibility among multiple states, and reuse the logic of states in different contexts.

States Break Modularity

The problem with states in a traditional FSM is that the logic is not reusable as-is. States perform a very specific role inside a state machine:

  • Transitions are hardwired and must assume a certain context; you can’t use parts of a FSM to solve a different problem unless you designed it that way.

  • Transitions rely on specific states and transitions, so the FSM fails if the required logic is not provided.

Because of this, you can’t treat a state as a modular block and reference it from a different context in the logic. You have no choice but to make a new state with different transitions specifically for that new context.

Reusable Logic

The question is, how easily can you reuse chunks of logic to make new states? Both hierarchical FSM and behaviors trees take a very different approach to this.

The next few articles in this series examines how this works in practice.

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!