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.
9 Comments ↓
Actually, there is a programming language that is based on state machines - Second Life’s LSL. (So I’m sort of cheating.)
Pi,
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 AI in F.E.A.R. for more details.
Alex
While it’s true that NFAs and DFAs are non-turing complete, most real-life state languages allow for arbitrary statements to be executed on entry and exit, the guard to be arbitrary code etc. These are clearly turing complete. You surely aren’t arguing for using labelled transition systems (http://en.wikipedia.org/wiki/State_transition_system) directly without any of the niceities that make FSM development so powerful?
I’ve found hierarchical state machines (harel) to be extremely useful, primarily because they capture the links between the states, and can hide complexity through nesting. i’ll have to look into decision trees, but i didn’t think they did the linking bit.
Many of the complaints seem to come down also to the way the state machines are translated into underlying code skeletons. I presume you’ve looked into smc (http://smc.sourceforge.net/) and the like? what about quantum framework (http://www.quantum-leaps.com/products/qf.htm)? However, in general i also find this a pain. It would be nice to see a mainstream language with actual state machine primitives.
As for concurrency, i’ve always used a translation into simple LTS which can be easily analysed for concurrency issues: http://www.doc.ic.ac.uk/ltsa/ . This also deals very well with composition (aka hierarchical state charts).
Andrew
oh, one other thing. it’s certainly true that pure NFA/DFAs only recognise regular languages. however, with arbitrary statements allowable as the guards, you can easily recognise languages to the equivalent power of context free grammars also. just keep a stack, and the whole thing becomes a pushdown automata.
Andrew
p.s. can you give an example of the type of non-regular language you’ve needed to “generate”/recognise in your problem domain?
FSMs can work wonderfully in concurrent environments. Just look at Erlang’s gen_fsm
It generally sounds like whatever tool you’re using to write FSMs (and compile them to something else) sucks. I highly recommend looking at Ragel; it has a very powerful language, embeds nicely as “just part of a function,” and compiles to C, C++, and Java. OTOH, it’s designed for handling strings.
I have to point out that, as far as most applications are concerned, computers are finite state machines (granted, with a very large number of states). Your problem doesn’t seem to be with the underlying computational model, but with the tools used to express computations (i.e. languages).
There is one point in the original post that I agree with: an emphasis on reactive (instead of proactive) things (which you call non-deliberation) that’s prevalent in FSM languages. Planners obviously provide (hopefully) simple ways to specify the attainment of a goal, and the decomposition of attainment based on available (and future) tasks.
Your underlying assumption is that closed-form, prescriptive computing will fade away. With the advent of incredibly powerful, often redundant, computing infrastructure this is almost certainly true.
I remember seeing a survey (may even have been here!) that named evolutionary computing as the most likely area for AI progression. It certainly seems that way to me - especially with the large numbers of increasingly elegant evolutionary schema emerging.
I’ve been solving extremely hard problems with these techniques for the best part of 20 years and there hasn’t been a single challenge that they haven’t risen to
First, there are a few more comments on Reddit for those of you that are interested.
Andrew,
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 The Gist of Hierarchical FSM) and is certainly practical. But for lack of meta-programming facilities, it struggles when you repeatedly create simple tasks like sequences or selectors (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 GOTO 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 Common Ways to Implement Finite State Machines in Games) 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.)
Tony,
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 Why State Machines Suck at Concurrency). 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 GDC Lyon research session earlier this month…
Nikola,
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
@Alex
I think you have a good point about the division between what a programmer and a designer do. i can well imagine that placing FSM customisation tools in front of a games designer would be very problematic.
Just a small point — i’m not sure the cry wolf scenario you mentioned is actually iregular. as long as there is a finite set of states to go through before finishing, it’s regular. it may be vary *large* but technically as long as it has a maximum upper bound… ;-)
it would make it irregular if there was an undetermined number of times before terminating *and* you had to do something like ensure that the gamer visited each room the same number of times… something that would require the keeping of unbounded state. e.g. ensuring any binary string has the same number of 1’s and 0’s cannot be handled by a pure FSM.
But if you are prepared to allow counting, then context free (non-regular) grammars can be handled also. in this case the scenario is handled with counters. the same power of a CFG can be achieved by an FSM with push-down state.
Andrew
Leave a Comment