Article
files/faceoff

Game AI Technology Faceoff: Attack Behaviors

Alex J. Champandard on October 14, 2007

In last week’s sketches, you saw two different ways to implement simple suspicious behaviors for an action game. This Sunday you’ll see how well these two systems handle an additional attack behavior.

What’s the Challenge?

“Implement the attack behavior of an immobile soldier. When an enemy contact is in sight, the soldier should load his weapon, and fire at will until the target is lost.”

The biggest difficulty in this example is to make sure that the attack behaviors override all the other behaviors. The soldier shouldn’t act suspicious if there’s a target visible!

The Finite State Machine

The cycle of attack behaviors is very similar to the suspicious cycle. However, one has priority over the other, so there needs to be transitions from all of the suspicious states into the new attack cycle.

To do this, it makes sense to use a hierarchical FSM. The HFSM allows generalized transitions to apply to composite states, so by regrouping all the suspicious states together, only one transition is required rather than many specialized ones.

Hierarchical FSM

The generalized transition into the SHOUT & AIM state is only engaged when an enemy is visible. Once the soldier has aimed, the FIRE AT WILL state takes over and continues until the target is no longer valid. Then a default transition takes the FSM into the LOWER WEAPON state, which leads back into the composite state. The default IDLE state in the composite is enabled again.

The Behavior Tree

Using the behavior tree (BT) approach, another sequence is created for the ATTACK behavior (similarly to the INVESTIGATE). This sequence can only execute when a target is visible.

Attack Behavior Tree

To enable this new sequence, it needs to be plugged into the root of the behavior tree.

Behavior Tree Root

The root behavior is the same selector as used in last week’s example. It dynamically selects the highest priority child behavior that is able to execute. So the top priority is ATTACK, with INVESTIGATE and IDLE as fallback options.

Verdict: You Decide!

With the HFSM, priorities in the behaviors are implemented using more transitions that must be connected up manually. Using composite states with generalized transitions reduces the amount of work necessary to wire up individual states, while still allowing complete control over the logic. The disadvantage of this approach is that the “hierarchy” and structure of the graph do not reflect priorities very explicitly.

Using the BT, there are no new concepts required to implement the attack behaviors compared to the suspicious behaviors. It’s just another sequence that gets plugged into the priority selector. The tree reveals the overall priorities rather intuitively, and the hierarchy of behaviors is more obvious: the sequences are mid-level and the selector is at the top level.

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

Discussion 8 Comments

Sergio on October 15th, 2007

Well, this is clearly not fair. It's just not fair presenting the HFSM as one big, disorganized blob of states, while the BT is so neat and structured. Actually, [URL=http://www.flickr.com/photos/39606784@N00/1573136184/]both techniques have the exact same structure[/URL]. The difference, as Alex pointed out in the previous face-off, is in how the transitions are defined. The BT relies on generic transitions: notice how the top-level Behave node relies on the behaviours themselves to find out which one it should schedule. The HFSM on the other hand has explicit conditions for each transition. With FSMs the transition logic doesn't live in the node, but on the containing structure. BTs push that logic into the node to make building the structure easier. FSMs are better at handling exceptions, but reusing is harder, as the transitions have to be ported as well as the nodes. Maybe a better representation would have the transition conditions exposed. They would be touching the nodes in the case of the BT, but they would stay in the middle of the arrow in the FSM. This might make the drawing too complicated, though.

alexjc on October 15th, 2007

You're absolutely right Sergio; the trees can be made to look the same. A few additional points though: [LIST] [*]The composite state around the attack states in the HFSM is purely cosmetic. It serves no purpose... [*]The composite states in a HFSM do not necessarily reflect a task decomposition, they simply help with generalized transitions (both in-to and out-of states). [*]You can edit a HFSM in the task decomposition fashion, but then you no longer have the ability to fine-tune the transitions at a low-level. [*]In my experience, HFSM tend to be edited as a whole and not modularly for this reason. It's not a bad thing, that's just what they do best at. [*]Because behavior trees are based on task decomposition, they are intended to be edited as modularly as I drew them. That can be both a blessing and a curse... [/LIST] I'm trying to think of an example for next week that will emphasize these differences even more. If you have any suggestions, please let me know! Alex

alexjc on October 15th, 2007

P.S. Two more points I forgot... [LIST] [*]Nice diagrams ;-) I wanted to go for a sketchy look in this "column" by design but now I'm having my doubts! [*]In your HFSM, you have a duplicate transition from [TT]IDLE[/TT] and all the [TT]SUSPICIOUS[/TT] states. Ideally, you should regroup them into another composite state to prevent duplication of the logic. [/LIST] Thanks again for your comments Sergio, they're always very pertinent! :) Alex

mihaic on October 18th, 2007

Good informative article as usual, however I have a question, make it more a curiosity if you like: In your experience, how do the FSMs and HFSMs get implemented? Do programmers implement them as static FSMs, namely you define and hardcode a bunch of states and transitions, or are they implemented as a graph that gets initialized from a file in which each state is declared together with their transitions? In the latter case, the advantage would be that new states would be much easier to add.

alexjc on October 18th, 2007

[B]Mihai,[/B] Good question. I'll go into more detail in a future Reader Questions post on Fridays... In my experience, the most common and useful for AI is to implement a HFSM in a very data-driven way. So you'd have some large tree editor that saves XML, the data gets loaded at runtime, and an interpreter is responsible for executing actions within states and checking transitions. Both actions and conditions for transitions are implemented natively of course... I've heard of FSM to C/C++ compilers but never used one before... Alex

mihaic on October 19th, 2007

Hi Alex, Thanks for the information. Can you please explain a bit what do you mean by "actions and conditions for transitons are implemented natively"? Are the FSM to C/C++ compilers generating C/C++ code from the xml tree representing the FSM? Thanks, Mihai

alexjc on October 28th, 2007

[B]Mihai[/B], I mean that actions and conditions are usually coded up in C++ as discussed in this article: [URL=http://aigamedev.com/modular-behaviors/actions-conditions]The Importance of Actions and Conditions[/URL] I presume that's what a simple compiler would do, yes. I've done Lua code generation for behavior trees before, but not for FSM yet... Alex

mihaic on October 28th, 2007

Alex, thanks again for taking the time to answer.

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!