Article
files/QUESTIONS

Common Ways to Implement Finite State Machines in Games

Alex J. Champandard on November 16, 2007

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.

Finite State Machine

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!

Discussion 4 Comments

mihaic on November 18th, 2007

Hi Alex, Thanks for taking the time to explain the methods for FSM implementation in more detail, I feel I have a better understanding of the subject now. While reading the article, I was thinking that by using the compiling method, you get the flexibility and performance from both the hard coding and the data driven implementation. However, you will always need to compile the FSM into code after each change you may apply to them, so I was wondering if there are some plugin engines such as those implementing the OSGi specifications, that would allow the game developers to use the compiled FSMs directly at runtime. Have fun, Mihai

kingius on November 19th, 2007

One way around the disadvantage of having to compile code with the third method is to compile it into a DLL and just have the rest of your engine link to it, meaning that you do not have to compile the whole of the engine when the HFSM changes.

mihaic on November 20th, 2007

Good point if you develop for Windows, but there are no DLL's on other platforms, as far as I know.

alexjc on February 16th, 2008

[B]Kriss,[/B] Thanks for your comment. I don't recommend building a finite state machine like that either, unless it's something very small. (But those techniques are still the most common in games.) For bigger problems like NPC AI, state machines also have their problems: [URL=http://aigamedev.com/questions/fsm-age-is-over]10 Reasons the Age of Finite State Machines is Over[/URL] I'm not sure whether you can consider a script a finite state machine, but it certainly serves a similar purpose. Anyway, for the same reasons you mention, I like to use behavior trees as they provide a nice language for expressing automata (and more). To each his own I guess! Alex

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!