Game AI Technology Faceoff: Suspicious Behaviors

Alex J. Champandard on October 7, 2007

In last week’s sketches about game AI, you learned how to create behaviors by dealing with parts of the problem space at a time. This Sunday’s sketches shows how two different AI techniques solve the same in-game scenario.

What’s the Challenge?

“Implement the suspicious behavior of an immobile soldier. The soldier should respond to unexpected events, look around suspiciously, then go back to standing around idly.”

This challenge is certainly a simple example from a typical action game, but you’ll be surprised how differently the two contestants handle it.

The Finite State Machine

The top left circle is the default IDLE state which plays a looping animation. The transition to the REACT state is engaged when there’s a suspicious event. When the reaction animation is done, the LOOK AROUND state takes over until it times out and the FSM transitions into the GIVE UP state.

The Behavior Tree

With behavior trees, you don’t edit low-level transitions manually; you have to use high-level logic. The first step is to create an investigate behavior as a composite behavior made up of lower-level behaviors:

The behavior tree encodes the transitions between the behaviors implicitly by putting them inside a sequence. Once this is done, the new INVESTIGATE sequence can be used like any other behavior to build up the final behavior:

This is the top-level of the behavior tree, implemented as a selector that picks a child behavior according to a prioritized order. If the first behavior is not applicable (i.e. there’s no suspicious event) then the second IDLE behavior is engaged as a fallback. The selection of behaviors is done dynamically, so a suspicious event at any time would engage the INVESTIGATE behavior. Once the soldier has given up looking around, the selector falls back to standing idle.

Verdict: You Decide!

With the FSM, you have to encode all transitions manually: to engage behaviors when events occur (REACT), to specify default transitions (LOOK AROUND) a.k.a. sequences, or to specify the fallback of any behavior (back to IDLE). This example is simple enough so the structure of the graph is more than manageable, it’s even visually pleasing!

In the BT, you don’t encode transitions manually. Instead you build up the logic you need by selecting composite behaviors and building them into a tree. In this case, it was only necessary to use a sequence and a selector. In this case, it’s a bit more work, but the behaviors are more modular. For example the GIVE UP behavior is not wired follow-up with anything specific, it depends on the context.

So which technique do you think won this faceoff? Discuss.

Discussion 7 Comments

Dil on October 8th, 2007

For a BT, say you want to implement a Cover behavior. This could be implemented as a Sequence of five behaviours: LOOK AROUND, SEARCH FOR COVER, RUN TO COVER, CALL FOR ASSISTANCE, RESPOND TO FIRE. Between SEARCH FOR COVER and RUN TO COVER, you need to pass information (Selected cover node and the path to use), how would you implement this ?

alexjc on October 8th, 2007

Florian, Manakel, Yes, you're both absolutely correct. You need a way to store and retrieved information shared between behaviors. However, it doesn't only apply to BT, you probably need it for FSM also! Having a [URL=]static blackboard[/URL] or a dynamic one is a possible solution. A stack is also an alternative, so FIND COVER would push the cover point onto the stack, which would then get retrieved by the MOVE TO behavior. Both approaches are equally justifiable in different contexts... Alex

mihaic on October 8th, 2007

For the simple reason that I like modularity, I would choose to implement this behavior using a Behavior Tree. Even if it is probably more work than the FSM, eventually it would prove more useful because it can be used in other situations also since it doesn't depend on previous or next states. FSM would require a different implementation for a different situation.

Ian Morrison on October 8th, 2007

I'm really liking where your sketches are going. Like everyone else who's posted (and, most likely, as you expected us to) the behaviour tree seems to be the better option based on modularity. If it didn't need to be extended further than that, though, I'd stick with the FSM for clarity. Question: in your technical description of your AI engine that you posted a while ago, you mentioned implementing behaviours as custom searches. Will you be doing anything in later sketches to explain that? It sounds neat, but I'm still a little uncertain of the applications.

alexjc on October 8th, 2007

Ian, Yes, I can go into more details about the topic of search. I can't say I've had time to plan too far ahead, but I'll keep it in mind :-) The selector in the behavior tree is a depth first search to find the right behavior. The sequence for investigate could be a search too if there were multiple ways to do REACT or LOOK AROUND... By custom search, I mean that you can implement the logic for any composite behaviors. For example, this dynamic BEHAVE selector here has very specific logic — not just a simple static selector that makes the decision once and never rechecks higher priority behaviors. Mihai, Thanks for your verdict. :-) I'm inclined to think along the same lines too!

Sergio on October 11th, 2007

Devil's advocate here. Everyone likes modularity, but what happens if we transform the FSM into an HFSM (hierarchical finite state machine)? You get your modularity back. And the drawing also has two pictures. In the first one you have two states, IDLE and INVESTIGATE. While IDLE is a leaf state, INVESTIGATE has three states inside, which are unsurprisingly REACT, LOOK AROUND and GIVE UP. Transitions into INVESTIGATE automatically go to the REACT substate, while the transition out of GIVE UP forces also a transition out of INVESTIGATE. It seems that in this simple example, the HFSM and the BT look pretty much identical.

alexjc on October 12th, 2007

Sergio: You're absolutely right. The only difference is that the HFSM requires you to wire up everything manually. For example, you must pick a default state in the composite state for INVESTIGATE, and connect up the sequence state by state. The BT does this a bit more efficiently, but they're close. This Sunday I'll add an attack behavior, so we'll see how it looks then!

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!