categories

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.

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.