Common Ways to Implement
Finite State Machines in Games

There’s one piece of technology you’re certain to find in most software: a finite state machine. However, they’re almost always implemented differently! In games, there are three major ways to implement FSM in the context of AI, logic, or animation. Naturally, each approach has its own benefits.

This week’s question comes from Mihai Campean who asks about the implementation of FSM “Can you please explain a bit what do you mean by ‘actions and conditions for transitions are implemented natively’? Are the FSM to C/C++ compilers generating C/C++ code from the XML tree representing the FSM?”

I’ll get into the details of actions/conditions in the context of FSM over the next few paragraphs, but read this article for more background. When it comes to implementing FSM, developers use a more or less extensible solution depending on the size of the problem.

Figure 1: A typical hierarchical finite state machine.

Hard-Coded

The most common way of building a small FSM is to write it entirely using the programming language of your game. When the language is C/C++ or any other compiled language, this process is known as hard-coding the state machine — since it results in static machine code.

There are two ways of hard-coding a FSM, either with centralized logic or distributed in a modular way. Specifically, this is done with:

• Switch Statement — All the transitions between states are encoded in one place, written as a large conditional check with multiple branches (a.k.a. case statements in C++). For example the event handler that deals with messages from the windowing system for desktop games.

• State Pattern — Each state is responsible for determining its successor state, so the transition logic is separated into many little chunks. This is often the case for simple AI behaviors. (See more about the state pattern in C++.)

Of course, the state pattern also requires its own conditional check internally to determine which state to transition to transition to next. Switch statements are only one way of implementing the transitions; you can use a lookup table also — which opens the door for more data driven solutions.

Interpreted

Another common way to implement a FSM is to use an interpreter which loads a file specifying the state graph and its transitions. In this case, the state machine is no longer fixed at runtime: it’s often called data-driven.

In game AI, it’s most common for states to be specified as:

1. A set of actions (e.g. Animate, ShakeCamera, PlaySound, etc.) that are updated while the state is active, and

2. a set of conditions (e.g. IsInCover, IsHealthLow, etc.) to determine which transitions should be activated.

These actions and conditions are always hard-coded in C/C++, so they are called native for that reason.

Under the hood, a FSM interpreter is typically written using a very similar approach to the state pattern, where each state is an object responsible for handling its transitions. The transitions are stored in a table that can be modified at runtime.

Compiled

Both hard-coded logic and the interpreter have their advantages; one is fast and down to the metal, while the other is flexible and easy to prototype with. Using a FSM compiler can bridge the gap between these two approaches.

The idea of a FSM compiler is to take the graph data from your data-driven system, then automatically generate the code for the FSM so it can be executed as a program. There are two ways of doing this in practice:

• Writing low-level machine code on the target hardware, or alternatively byte code directly.

• Generating source code in the a language like C/C++, and reusing the compiler for the whole game.

This is the least common approach used in games, but it certainly has its benefits for game AI. Large HFSM could certainly benefit from being compiled to reduce memory usage and increase performance.

Developing a compiler would take a little more work and a different skillset, but there are existing solutions available.

cfsm

“cfsm is a small program that accepts a specification for a finite state machine in a high-level text format, and compiles it into a C source and header file. It can also output the FSM in Graphviz dot format so you can make pretty pictures.”

smc

“The State Machine Compiler allows you to put your state diagram in one, and generates the state pattern classes for you. No need for hand-maintained transition matrices or widely scattered switch statements. Instead, the state diagram is in one place, coded directly from the picture to the SMC language and is easily maintained.”

Summary

The process of implementing a FSM is very similar to programming language technology. You can write it yourself at a low-level, you can write an interpreter and feed it data, or you can compile the whole using tools.

For small FSMs, it’s best to write it in the same language as your game, using a design pattern if necessary. Otherwise, write a simple interpreter and make it data-driven; that’s the best approach for most animation systems or AI logic. You can consider a compiler at a later stage in the unlikely event of there being bottlenecks in the FSM-logic!