Article
files/QUESTIONS

10 Reasons the Age of Finite State Machines is Over

Alex J. Champandard on December 28, 2007

Over the last few months, AiGameDev.com has grown into a wonderful little community thanks to you guys! On Fridays, I take the time to answer your questions, either from the blog or the increasingly busy forums.

Finite state machines have become extremely popular over the last decade, and helped game developers build some pretty fun games. But all good things must come to an end! Has time come for FSMs to let better techniques take care of AI logic?

This week’s question is a comment that was moderated out for being impolite… However, erm@duh.org raises an interesting question about Wednesday’s tutorial series. I’ll paraphrase the question in a more constructive way:

“It’s my belief that the rest of the galaxy (i.e. the games industry) uses finite state machines for its game AI. Why didn’t you use them to implement the behaviors of the dogs in this simulation game?”

If anything, the tutorials use a behavior tree to show how they differ from state machines, and how game AI developers can benefit from this form of hierarchical logic.

Sure you could build the very same behaviors with a finite state machine (FSM). But anyone who has worked with this kind of technology in industry knows how fragile such logic gets as it grows. A finely tuned hierarchical FSM before a game ships is often a temperamental work of art not to be messed with!

Photo 1: Where do problems with FSMs come from?

#1
They’re Unorthodox

Problem: Building a FSM is a very different process from any other form of software engineering. Sure, the concept is “designer friendly” but a surprisingly small amount of mainstream programming knowledge applies to FSMs.

Reason: FSMs require each state to be wired with an explicit transition to the next state. No programming language requires this; everything is done implicitly based on the semantics of the language itself (e.g. a C++ compiler builds sequences from statements).

#2
They’re Low-Level

Problem: The process of editing the logic of a FSM is very low-level and quite mechanical. You often find yourself rebuilding the similar behaviors over and over from scratch — which takes a lot of time.

Reason: All you can do is edit transitions from a state to another. There’s no way to capture higher-level patterns that reoccur frequently like sequences or conditionals. Meta-programming doesn’t exist in the world of finite state machines.

#3
Their Logic is Limited

Problem: Finite state machines, as they are defined formally, are computationally limited (a.k.a. Turing incomplete). This means you can’t do things like counting by default.

Reason: If you consider events as symbols, you can only recognize regular grammars with a finite state automaton — in the same way a regular expression can’t recognize certain categories of text patterns. Likewise, finite state machines can only act as transducers for regular languages.

#4
They Require Custom Extensions

Problem: Game developers often use extensions to make FSMs useful in practice. However, these hacks aren’t always easy to understand and aren’t so well documented either — unlike the academic foundations of FSMs.

Reason: Because FSMs are theoretically limited, developers must add functionality externally to implement certain features. This means leveraging the underlying programming language to implement things like counters, timers, or any form of memory.

#5
They Are Hard to Standardize

Problem: Unlike planners (HTN) or search algorithms (A*) which are implemented in relatively common ways, FSMs are very difficult to reuse across multiple games or in different parts of the engine.

Reason: Since FSMs aren’t turing complete, FSMs need customizing to be able to deal with the special cases of each problem. This makes them very narrowly applicable, unlike scripting languages which can easily be repackaged.

Finite State Machines Fragile Like Mikado Sticks

Photo 2: Making changes; watch out for that transition!

#6
They Are Not Deliberative

Problem: It takes a lot of work to use a FSMs to create goal-directed behaviors. This is an issue as most purposeful AI will require dealing with long-term goals.

Reason: FSMs operate in a reactive mode, only dealing with events and triggering transitions. They are not capable of searching ahead (a.k.a. deliberation), so you have to edit the transitions for dealing with all the different goals manually.

#7
They Have Concurrency Nightmares

Problem: FSMs just don’t like concurrency. When running multiple state machines in parallel, you either end up with deadlocks or you have edit them all in a way they are compatible.

Reason: FSMs have as much trouble dealing with external resource conflicts as they do storing information. Solutions to make state machines concurrent are typically external to the FSM itself, either as support logic or as a set of tools to make them concurrency safe.

#8
They Scale Poorly

Problem: Finite state machines, even hierarchical ones, don’t scale very well. They often end up being edited as a large block of logic, instead of behaviors edited modularly.

Reason: FSMs are not built with the many mechanisms of programming languages that help them scale up to solve large problems, in particular indirection. Also, FSMs provide no easy way to synchronize multiple modular behaviors together.

#9
They Are Labor Intensive

Problem: It takes a lot of work to wire up a FSM to implement any design. Certain problems occur only because of the state machine itself!

Reason: Dealing with all the challenges mentioned previously takes a lot of time by the designers, and this ultimately becomes a source of bugs in the behaviors.

#10
Industry is Moving On

Fact: Experienced game developers are using finite state machines less and less, switching to alternatives like behavior trees.

Fact: Middleware vendors for game AI are focusing their development efforts mainly on planners, and 2008 should see more of these becoming available off the shelf.

Conclusion

FSMs, like any other technology, have their place in the game development process. However, the age of finite state machines, where developers pick them by default to implement their AI, is coming to an end. Scripts with coroutines are the most popular these days, and hierarchical planners are increasingly making their way into games and middleware.

Discussion 4 Comments

alexjc on December 30th, 2007

[B]Pi[/B], With a little help from the underlying language (for things I mentioned like counting), you can "compile" most programs to FSMs. If you want to get technical, a continuation-based compiler does something very similar also. But that's a great example, I'll have to look into it. Unreal script I believe also has support to help build state machines... Planners are ultimately more scalable when you start implementing complex AI logic though! See my article on the [URL=http://aigamedev.com/reviews/fear-ai]AI in F.E.A.R.[/URL] for more details. Alex

alexjc on December 31st, 2007

First, there are a few more comments on [URL=http://programming.reddit.com/info/645q5/comments/]Reddit[/URL] for those of you that are interested. [B]Andrew[/B], Thanks for your insights. Sure, executing arbitrary code is a necessity, but that becomes a problem when you want to expose tools to the designers for them to build the FSM themselves without any coding. Then, figuring out the set of extensions you need is a tedious process! You're right, Harel's work is the most used in games (readers see [URL=http://aigamedev.com/hierarchical-logic/hfsm-gist]The Gist of Hierarchical FSM[/URL]) and is certainly practical. But for lack of meta-programming facilities, it struggles when you repeatedly create simple tasks like [I]sequences[/I] or [I]selectors[/I] (like behavior trees). It's true also that behavior tree's can't typically jump from one branch to another in the same way it's hard to just [TT]GOTO[/TT] any label in structured programming; you'd have to restore the stack somehow, which requires a form of continuations. That said, game AI developers often implement this as a hack somehow, and they did support the feature in Halo's AI. I covered some of the tools you mentioned previously on this blog (see [URL=http://aigamedev.com/questions/fsm-implementation]Common Ways to Implement Finite State Machines in Games[/URL]) but the most common ways game developers use FSMs these days is to build a data-driven interpreter then put a tree editor into the hands of the designers. That takes a lot more work to get right since you need to think about your custom code when writing the interpreter instead of when building your FSM. As for an example of a non-regular grammar, the the cry wolf scenario in a sneaker game is perfect. Your in-game actor should react differently to the same suspicious event, first going to investigate for a few times, then saying "Not again." a few more times, then eventually getting bored and letting the player sneak up on him. (Of course, you could do that with a traditional sequence of states, but if you want to count the number of suspicious events and preform a different reaction then you'll need custom logic.) [B]Tony,[/B] Thanks for that; I will take a look at it. But just to clarify, my main complaint is with logical concurrency not necessarily dealing with multiple threads (see [URL=http://aigamedev.com/concurrent-ai/fsm-struggle]Why State Machines Suck at Concurrency[/URL]). It's more about getting multiple FSMs to synchronise together to provide the correct behavior. The solution to the problem of allowing modularly edited behaviors as FSMs to work together is surprisingly hard. See Fabrice Lamarche's solution that he presented in a [URL=http://aigamedev.com/coverage/2007-lyon-gdc-research-part1]GDC Lyon[/URL] research session earlier this month... [B]Nikola,[/B] Many thanks for your comment too, you're absolutely right. I haven't looked at Ragel, but it would do the trick for helping programmers build FSMs. The problem is figuring out a way for designer to get what they want without any coding. I should have emphasized this a bit more in the post... True, in practice computers are just state-machines, but you'd never model programs that way or they'd blow up in your face! That indeed was my main complaint, since finding a language suitable for designers is what it's all about for game AI developers. Alex

premium on January 31st, 2009

Hi [B]Rune,[/B] Thanks for coming down from your ivory tower to take the time to comment about this article. But the crux of your argument seems: [I]"You didn't define this term very well according to my academic standards, I don't have time to mention the rest of the issues I have..."[/I] It seems you missed the practical perspective/context of the article, which talks about creating complex behavior with FSMs, like for NPCs (defined: non-player characters). Theoretically FSM are important for games and virtual worlds, but in practice they are mostly useless. There are many better techniques like behavior trees and planners which will relegate FSMs pretty much to trivial kinds of problems. That said, I'd be curious to hear about your research! Alex

developeraigames on October 16th, 2010

I'm not sure that the time is over. I have post a message about HSM (Hash State Machines) if you want can write to me at post : HSM chess finals solution. I try to understand your view but I remain in my opinion. HSM is simply to realize and provide sopport to the developing of intelligent application.

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!