"Joining the Living: State Machines < Behavior Trees"

Posted by Ryan C. Scott on Thu 30 September 2010
Approaching AI for what was essentially the first time, I picked up Ian Millington's "Artificial Intelligence for Games". This book covers a substantial amount of ground, but the 2nd edition was dated in areas when I read it (a third edition has recently been published or is about to be or was published a while ago... who cares).

When examining the various systems for AI reasoning the one that seemed the most straight forward and versatile was hierarchical finite state machines (HFSM). And certainly they are straight forward. It's worth noting here that when researching online I came across Behavior Trees and mistakenly, one could say even "Fatefully", I misread the term as "Decision Trees"; which isn't 100% wrong but certainly not right.

The problem with FSM/HFSM approaches:
Until you try to build an AI agent using one, you will not really, fully understand that getting them to behave properly is a hell of a scene. Broken transitions, problems in your logic, etc. all wreak terrible havok on your AI. What's more, because transitions are so important to this structure, a broken one can break nearly everything.

Behavior Trees at their core:
Ignoring for a moment all of the bells and whistles, at the very core behavior trees are dead simple and could be implemented as a series of clauses.
The Basics (somewhat specific to the approach I've used):
  • Branches are visited when their criteria is met (this is like have a selector on each node)
  • Branch nodes just handle branching
  • Leaf nodes indicate an action (or a condition check to execute)
  • Nodes are processed left to right (although this is a design decision and dependent on the logic of your composite/flow control nodes)
The simple and powerful thing here is that a failed branching results only in an incorrect branch being followed. But as your branches all represent sane agent behaviors, your agent might be doing the wrong thing, but they'll be doing it the right way. That might not seem like much of a benefit, but failing is a part of game AI that you will not escape. Your game state will fall on its face at some point. Failing elegantly is arguably just as important as anything else.

Simplicity of implementation:
Endeavor a very simple node based tree structure. Nodes can succeed, fail, or error and can communicate that to their parent node. Conditions, actions, decorators, and flow controls (such as sequences, selectors, etc.) can then fairly trivially be implemented as derived classes that succeed/fail/error and handle child node responses based on whatever criteria they need to take into account.

Grafting:
An advanced concept which I've not personally implemented, but find rather compelling, is grafting (i.e. inserting) trees onto other trees dynamically. If your implementation is a graph of node instances, you could, per agent, attach any tree or part of tree fairly easily to any part of any other. The implications include being able to have special behaviors/actions associated with specific entities (such as a phone that tells characters how to use it, a vehicle that has specialized needs, etc.). That's a topic for some day in the future after I've experimented with that.

I initially put together a tool which took diagrams and generated an FSM using these basic rules (my trees were always evaluated from the top and only when my blackboard structures was "Dirty") and it became limiting and very tricky to work with rather quickly. That structure proved to work well enough for simple responsive AI, but had massive issues when trying to scale up and do more complex and long term behaviors/sequences of actions. So as with anything I or anyone else could possibly tell you, your mileage may vary.

As a quick example, with a basic idea borrowed from Alex Champandard's TreeBuilder structure from AIGameDev.com's AI Sandbox, here's the code that's generated by my graphical tool:
return new RootNode()
.AddChild( new PrioritySelectorNode()
.AddChild( new ParallelNode()
.AddChild( new GenericFilterNode( delegate( KnowledgeRepresentation knowledge ){ return( !(knowledge as ThisAgentKnowledge).SomethingToCheck ); } )

.AddChild( new SequenceNode()
.AddChild( new Wander() )
.AddChild( new Idle() )
)
)
);
And an image of the graph used to generate that code:


You'll notice some things in that example, the least of which is that it's in C#. I have created a generic filter node type that takes a C# delegate, accepting an instance of a blackboard class I've created, which casts that blackboard into a derived class and checking a value. Any code could be inside of that delegate, but my tool which converts the diagram to code makes some assumptions. Also, just so you don't hurt yourself trying to figure out what that square box with an ellipses is, this diagram has been truncated bot to make the example more concise and to remove some project specific stuff that I'm most certainly not supposed to be exposing. .__.

A great resource for behavior trees and game AI in general is http://aigamedev.com/ . These concepts are explored in far greater depth there. Alex presented a presentation on BTs at GDC several years ago that serves as a nice intro to the basic concepts: http://aigamedev.com/insider/presentations/behavior-trees/


-r