Behavior Trees
I'm using Behavior Trees in the BattleTech AI for "flowcharty" logic. The sort of "if-then" stuff, like "IF my unit has been knocked down, THEN it should get up on its next turn.
Related Approaches
First, there were Finite State Machines. They were adequate to capture describing computation processes, but they quickly became unwieldy for actual work.
Then came the Hierarchical Finite State Machines. A little bit better, but also unwieldy.
Consider a somewhat separate thread of technologies: Rodney Brooks' "Subsumption Architecture", where behaviors were layered one upon another, higher level behaviors potentially suppressing or modifying lower level behaviors that didn't support the higher level behaviors.
And, riffing off the "inhibiting" notion, there's the "Activation Net" system from Pattie Maes. Independant competency blocks with various links to other blocks: precursor/successor links and inhibitor links. If a module needed another module to do something, there'd be a precursor link (or a successor link, looked at from the other end). If two competency modules interfered with each other, there'd be an inhibitor link. The current state would feed activation energy into modules that can activate in that state, goals would "pull" activation energy through the network.
In talking with Bruce Blumberg about Activation Nets, his observation was that the system doesn't really give the designer good control over time management - how long to try to do a thing before giving up and working on a different strategy.
Hierarchical Transition Networks are another approach to the idea of providing multiple competencies, and generating plans, some of which might be more successful than others.
For "BattleTech", I chose to go with Behavior Trees, which are a fairly general approach to describing AI agent logic. There have been many implementations of the idea, from Halo 2 to Spore and many others. I read some discussion by Damian Isla about the Halo 2 AI (See "Managing Complexity in the Halo 2 AI"), which seemed to make it feel like a good fit for what I was trying to accomplish.
One insight that really made it feel like this was an interesting tool to apply was that behavior trees embrace success and failure of lower-level behaviors, and really force you to always think of ways that the lower level behaviors might not succeed.
Requirements
Some of my goals for the BattleTech AI:
execute quickly
be visually understandable by designers
be easy to modify during development
didn't need complex flow (recursion, looping)
needed to select orders for a squad-based, turn-based game.
needed to deal with dynamic units (units can lose weapons and limbs
during gameplay, and can be customized between missions) on varied
terrain.
What are behavior trees?
Behavior trees are a pretty general set of tools, but at their simplest, they provide a fairly simple way to hierarchically structure decision logic (see, perhaps, "decision trees").
The basic idea of a behavior tree is that there is a tree of nodes - each node represents the competency to execute a particular behavior. This can be abstract and general (do an aggressive move, follow a patrol route) or very specific (issue a "brace" order, shoot at the highest priority hostile). If a node has children, the children serve to provide the component parts that are more concrete, specific implementation details.
There are many different kinds of nodes that people have used, but for the purposes of building a tree, I got most of my mileage out of two basic node types: sequence and selector.
The sequence node type represents a group of behaviors that need to be done in order. If one of the children fails, the entire behavior fails. This is similar to an AND statement in a lot of programming languages: "do task A AND then do task B AND then do task C" with the understanding that if task B fails, task C won't be attempted (this is important in languages like C, where this "early exit" is used to write succinct code like
If a sequence is AND, the selector is OR. The idea is that any of the behaviors that succeed will cause the parent behavior to succeed. An example of this from BattleTech is a selector node that has one child tree for movement behaviors and one child tree for attack behaviors. When the actor gets to move, if it can move, it tries to do that first. If it can't move (maybe because it's already moved this turn), it proceeds on to trying to attack.
TODO more here.
Behavior Nodes That We Used on BattleTech
Sequence
Selector
Inverter
Success Wrapper
Random Die Roll
Debugging Log
Leaf Nodes
Workflow
For BattleTech, most of our code is written in C#, which gets compiled to Mono bytecode to be run at the time of gameplay by the Unity runtime. I was concerned that if I wrote my behavior tree logic in C#, things would get messy, and the management of creating nodes and hooking them up quickly became spirit-crushing for the very first few experiments I did.
So, I wrote a Domain Specific Language (DSL) for my behavior trees. Or, rather, I pressed XML into service to be my behavior tree definition structure, and I began creating a library of XML nodes. XML felt like a reasonably good choice, as it handles nested structures pretty well.
I wrote a small script in Python that would parse one of our behavior tree XML files and translate the behavior tree description into a C# file that would get checked in to our project, and compiled and run for good efficiency.
Simple Example of XML
TODO a simple example goes here.
Once you get a few nodes, it became apparent that it would be difficult to understand how things fit together, so I applied GraphViz to generate a PDF of the behavior tree. This gets generated at the same time as the C#, so there's a visual tree diagram that can always be consulted. I had hoped that this would be a useful document for the team to refer to, but as the project went on, I seemed to be the only person who ever looked at the PDFs. They were still very useful to me.
TODO an example of a PDF goes here.
Last updated
Was this helpful?