My liner notes for spore/Spore Behavior Tree Docs
Jump to navigation Jump to search
This is from the example code for Spore's Behavior Tree AI System.
SPBehaviorTreeDocs - The Spore Behavior Tree AI System Documentation Chris Hecker - Maxis / Electronic Arts
"The present letter is a very long one, simply because I had no leisure to make it shorter." - Blaise Pascal
This documentation is written as a sort of "literate program", which means the documentation and the demo code are interspersed, and the code can actually be compiled to make a running sample of the AI (if you've also got the Animpreview prototyping environment to link in, but even if you don't, you at least know the code is real since it's used as the test rig). This means the demo code is slightly exaggerated to be a good example of the system's features; you wouldn't necessarily use as many different features in such close proximity during normal use.
S01: Overview S02: Design Principles S03: Differences From Halo's Behavior Tree AI S04: How Deciders Decide S05: Subset Rule S06: Preconditions & Stimuli S07: Memory & Blocks S08: Behaviors S09: Initializing and Ticking the Behavior Tree S10: Performance S11: Debugging S12: Macros S13: Behavior Declaraction S14: Behavior Definitions S15: Behavior Flags S16: Decider Declarations S17: Decider Definitions S18: Decider and Behavior Function Definitions S19: The Agent Pointer S20: Basic Behavior Memory Blocks S21: Advanced Behavior Memory Blocks S22: Decider Blocks (DBlocks) S23: Group Decider Behaviors
You can search for sections using the "Sn:" section number. There are lots of comments that aren't big enough for sections, so also search for "//". S01: Overview -------------
The Behavior Tree (BT) system is a library for declaring and ticking Hierarchical Finite State Machines operating on "agents". The system is blind to the type of the agent, so the agent could be a character, or it could be some kind of strategic entity, or it could just be null.
At the highest level, a behavior tree is made up of arrays of "deciders". Eventually the deciders bottom out and reference specific "behaviors".
Deciders can contain references to arrays of other deciders (called "group deciders", and the referenced deciders are called "children"), or they can reference behaviors (called "behavior deciders").
As their name implies, deciders do the decision-making in the tree. A decider has a function called Decide which looks at the state of the world and calculates whether the decider should activate. If the decider was a group decider, then the decision process repeats for the children. There are a number of policies for determining which child in a group will run, including prioritized list, random, sequential, Sims-like scored competition, etc. These are covered below in detail. Behavior deciders activate their referenced behavior when they activate. The behavior is where the actual AI action code lives. Behaviors have Activate, Deactivate, and Tick functions for accomplishing their goals. Assuming no higher priority deciders interrupt it, the currently active behavior will get ticked every frame and the AI will do its stuff.
A decider that references a behavior is a leaf of the tree. A given behavior can be referenced from multiple behavior deciders, and deciders can be referenced by multiple group deciders. This means the BT is actually potentially a DAG and is not limited to a tree structure.
A simple example of a behavior tree might be:
+--------+ *ROOT+-->| FLEE | +----------------+ | GUARD+-|------------------------------>| YELL_FOR_HELP | | FIGHT | | FIGHT | |*EAT+---|--------+ +------------+ | PATROL | | IDLE+--|--+ +---->| FIND_FOOD | | REST | +--------+ | |*EAT_FOOD | +----------------+ | +------------+ | +-------+ +->| PLAY+-|--+ +--------+ | REST | +-->| FLIP | +-------+ | ROLL | | DANCE | +--------+ Figure 1.
Figure 1 only shows deciders in the tree, in ALL CAPS. The deciders with arrows coming out of them are group deciders, and they point to their children arrays (the boxes), which contain other deciders. The deciders with no arrows coming from them--the leaves of the tree--are behavior deciders. These behavior deciders reference a set of behaviors (not shown in the figure) that may or may not be named similarly to the deciders and may or may not be shared between the deciders.
Each call to TickBehaviorTree with the ROOT decider works its way down the deciders, finding either a new path through the tree to activate, or continuing with the currently active path.
Walking through a simple example, assume the starred deciders in Figure 1 are active (ROOT->EAT->EAT_FOOD). Also assume the group decision policy on the various groups is kGroupPrioritizedList, which means each decider's Decide will be called in order until either one accepts, or the execution reaches the currently active decider, and then it recurses.
During a tick of this tree, we start at the ROOT and see it is active, so we enter the group and call the Decide function on FLEE, GUARD, and FIGHT in order, because they're higher priority than EAT. If none accept, we recurse into EAT without calling its Decide since it's already active. This is how the system exhibits hysteresis: the test to activate a decider is different from the test to continue executing.
In this case, we recurse into EAT, and call FIND_FOOD's Decide. If it also does not want to run, we go into the active EAT_FOOD, and call Tick on the referenced behavior.
On the other hand, if GUARD's Decide accepts, then we deactivate the EAT->EAT_FOOD path through the tree (so the behaviors and deciders can clean up if they want), and then we activate GUARD and recurse. The GUARD decider's children are then decided, one is activated, and that path becomes the new active path through the tree. Next tick, only FLEE's Decide will be called in the ROOT group, because only FLEE is higher priority than GUARD.
To extend the walkthrough one step farther, if, within its Tick, the EAT_FOOD behavior decides it no longer wants to run, it returns false and the group does a "masked redecide", meaning that the other children in the group are given a chance to Decide, but the child who failed is masked out of this decision step. If one accepts, then the old path is deactivated and the new child is activated. If none accept, the group decider pops back up a level and another masked redecide occurs, but now at the ROOT group level, with EAT masked out for this tick. This gives IDLE a chance to activate.
S02: Design Principles ---------------------- There are a few design principles that permeate the whole system:
1. Clear, monolithic, and static declaration of the tree of states. As you'll see below, the declaration syntax of the state machine is highly C macro-driven and can be statically defined at file scope in a way that tries to make the overall structure of the tree visible at a glance, so it is fairly self-documenting. The actual behavior function code itself can be in multiple files or anywhere you want it, but the tree structure should be declared in a single block of definition statements like below. This architecture has the side benefit of compiling extremely quickly.
2. Avoid O(n^2) coupling of behaviors by brute force, and make the brute force execution efficient. The entire active part of the tree is ticked every frame, which--in the case of the common prioritized list group decision policy--means all designated higher priority behaviors get a chance to interrupt the current active behavior before it is ticked. This frees a behavior from having to know about other behaviors or unrelated external stimuli; if a more important behavior is supposed to activate, it will activate naturally due to the flow of decision making. Various flags and masks allow this ticking to proceed without even calling functions a lot of the time. 3. Easy visualization and debuggability. Because a tree is a static plain C struct data structure with no need for a dynamic initialization/construction phase or allocations, it is clearly visible in the debugger watch window at any point during execution, with full named symbols even in optimized builds. Also, multiple runtime visualization tools are provided to display the entire tree, the active path through the tree, and hookable debug output with 5 debug levels of output detail, covering everything from outputing only changes in the active state, to full output of every decision result.
4. No boilerplate code. Just about everything in the BT system has defaults and custom creation macros, so you should only ever need to write code that actually does something for your AI. If you have a behavior that only needs to Tick, you don't have to write default Activate/Deactivate functions that simply return, or vice-versa if you only want Activate/Deactivate but don't need to Tick, etc.
5. Diagonal design. As Larry Wall says, orthogonal design is totally overrated. You don't want to travel in right angles, you cut across and go direct. There is more than one way to do just about everything in the BT system. This is flexible, but can be confusing.
S03: Differences From Halo's Behavior Tree AI --------------------------------------------- This BT system is basically trying to be "version 1.5" of Halo's AI system. The Halo system is documented in the Gamasutra article "Handling Complexity in the Halo 2 AI" by Damian Isla, mirrored in this directory as halo_ai_isla.htm. I talked with the Halo guys a bunch about their current system, and then brainstormed with them about how to improve it since we were starting from scratch. This system is the result. The Halo guys were incredibly helpful and open with sharing detailed information about their system, and its pros and cons, and this system owes much to them.
The Halo paper is slightly misleading in one key area: their tree is actually completely static. Impusles and stimulus behaviors are not inserted into the tree at runtime, they are simply checked every tick like everything else, it's just that they won't fire until the conditions for them to fire are present. This is conceptually like they are inserted dynamically, but in fact the tree structure is compile-time static. Our system is the same.
The biggest difference between the two systems is that we separated out the concept of a "decider" from a "behavior". The Halo tree is all behaviors (group/mutex or regular) and impulses, and impulses can jump to behaviors to activate them at different priorities. We unified the impulses and group behaviors into deciders, and the behaviors are completely separate. This lets us reuse behaviors in multiple places in the tree like impulses do, without having a separate type.
There are a bunch of minor differences as well (we don't check preconditions on already active deciders, Halo does, etc.), but the concepts and design principles are basically the same.
S04: How Deciders Decide ------------------------
Conceptually, a decider has a Decide function that gets called, and depending on the group policy, the floating point return value of the Decide function indicates whether the decider will activate.
In practice, there are a number of options available for deciders. The specific code expression of these options will be shown below, so this section will only give an overview. 1. There does not need to be a Decide function. If it is 0, then it is semantically the same as if it had returned 1.0. This can be used by itself to make a decider that always accepts, say as the last entry in a priority list, like IDLE in Figure 1, or it can be combined with the other decider options listed here to avoid writing a dummy Decide.
2. There are optional preconditions that are checked before the Decide is called. These preconditions can do things like only allow the Decide to be called after a given timeout, or they can do logical operations on two kinds of flags, DecisionFlags and StimuliFlags, covered below.
3. A Decide can delegate its decision to its children. There are currently a number of caveats to this mentioned in the header at the function declaration, but it is possible.
4. The deciders have a flag that controls whether the Decide of the group is called when it redecides because a child failed. This allows you to avoid writing the redundant checks inside the children if you want to check whether a group is still valid to run.
In general, Decide functions should not set state on the agent unless you know what you're doing. If you know the structure of your tree, and know that if you return 1.0 from a Decide that you will activate it, then it's fine to set state since you know your return will cause a change in the AI state. But, if you're in a Decide that you don't know will guarantee activation, setting state on the agent could cause bugs (you set state, then don't get activated, so your state isn't cleaned up or you hose existing state). Decide functions can use DBlocks (see below) to handle transient data communication between Decides and behaviors.
S05: Subset Rule ---------------- The most important thing to remember when writing a Decide function for a group decider is that the Decide has to obey the "Subset Rule". The Subset Rule says that a Decide on a group must be a subset of the Decides on the children. This could mean they are equal (ie. it does not have to be a proper subset), but the parent Decide can not be a superset of the child Decides. If the parent was a superset, then the parent would accept in some circumstances, but the children would all reject, and then the parent's group would redecide, the parent would potentially accept again (ignoring the masking on redecides for the moment), and you'd get an infinite loop. There is a redecide loop count to guard against this, but if it fires, the TickBehaviorTree exits with an error (which makes it easy to call EA_VERIFY()), and potentially no behavior ticked that frame so the AI is frozen.
The Subset Rule is pretty easy to obey, it just takes a small amount of thought when designing your tree. There is nothing stopping children from calling the parent's Decide directly (or using the kFlagsCallDecideOnRedecide) if that's the easiest way to enforce it. It's not really a constraint, because all it is actually saying is that if you're going to enter a sub-state, the states within it had better be ready to run.
The Subset Rule makes it slightly inconvenient if all you're trying to do is pull some deciders out of a group into a child group to clean up a large list or something. In that case, you need to use the DelegateDecideToChildren function in the subgroup Decide, which has some performance and behavior caveats as documented at its declaration. If this turns out to be a big problem, it would be a bit of work to fix, but we can make a flag for delegation and handle this within the TickBehaviorTree. Usually, groups are used as semantic units, like GUARD_NEST, where the decision to guard the nest is very different from the children decisions about how to guard the nest, so I don't forsee this being much of an issue.
S06: Preconditions & Stimuli ----------------------------
As mentioned above, a decider can have preconditions that are evaluated before the Decide is called. There are two basic kinds: time checks, and flag checks.
Time check preconditions allow you to mask off deciders based on a countdown, so a time check precondition of 30.0 would mean only evaluate this decider every 30 seconds. The delay is from the last call to Decide, not from the Deactivate, which might change in the future.
There are two kinds of flags checks, DecisionFlags and StimuliFlags, but they both have the same behavior. You can specify "any" and "all" type checks (AND and OR), with 0 or 1 bits required in the check.
DecisionFlags are simple ad hoc flags passed into TickBehaviorTree to control the enabling and disabling of deciders. DecisionFlags might be used for the agent's level, whether it's an herbivore or a carnivore, whether it's part of a squad, whether it's dead, whether it's nighttime in the level, etc.
The StimuliFlags support the same precondition logical checks as DecisionFlags, but they have more explicit semantic structure. The StimuliFlags are passed in as a pointer to the StimuliAllFlags member of a behavior_stimuli structure, which stores "stimuli" for an agent. A stimulus is a token with some optional data associated with it and a timeout. It is used for things like inviting an agent to play, or notifying an agent that it took a hit, or setting some temporary state on yourself to avoid repeating something, etc. There are lots of stimuli examples spread throughout the example code below (search for kStimuli_), and the behavior_stimuli struct is declared in SPBehaviorTreeHelpers.h.
Both of these flag checks allow the BT system to not even call a Decide if the preconditions are passes, and often you don't even need to write a Decide because you can express the conditions for activation with just the precondition checks.
The preconditions support arbitrary combinations of all of these checks simultaneously.
S07: Memory & Blocks --------------------
The BT system manages transient per-behavior data for you, and passes behaviors a pointer to a fixed size block of memory for the behavior's use. This memory is reused as behaviors are activated and deactivated, and it stores both the current path through the tree, and also any custom information a behavior needs for its execution. With casting, it can store arbitrary C++ data with constructors and destructors, as long as placement new and explicit deletes are used correctly. There are macros provided to make this easy and safe.
The Decide function also gets passed a block (called a DBlock) that it can use to pass information to its behavior if necessary.
Any persistent data is assumed to be stored on the agent (for example, the stimuli are a form of blackboard storage on the agent). Behaviors cannot pass information to other behaviors in the tree without using the agent or some other extra-tree means.
More details on these blocks are below near the usage examples.
S08: Behaviors --------------
Briefly, behaviors are the chunks of code that operate on the agent to perform actions. They are usually relatively chunky, like PATROL, and often have simple switch-statement finite state machines in them, using the blocks to keep their state. Any state machine could have been coded into the tree, but at some point it becomes easier to have a simple 3-state FSM in the behavior rather than keep breaking things up, especially if the behavior needs temporary data (which would have to be lifted up to the agent if the states were broken up).
It is expected there are layers of code somewhere that deal with things like animation blending between states, timesliced routing, and whatnot. The behaviors call these layers, and they handle any blending necessary between their own states. So, for example, the animation layer will handle blending between animations played by two different behaviors; the behaviors themselves should not have to know about behavior transitions (to avoid O(n^2) complexity scaling).
Group deciders can also have behaviors that Activate/Tick/Deactivate with the decider. This can be useful for doing setup and shutdown for the group state. For example, notifying the nest that you're guarding it or no longer guarding it. A false return value from Activate or Tick will fail the group and force a redecide, just like it does for behavior deciders.
S09: Initializing and Ticking the Behavior Tree -----------------------------------------------
Most of this documentation deals with creating the behavior tree itself, and writing the AI code in it, but there are a few things to know about setting it up and ticking it on agents.
Each behavior tree needs to have InitializeTreeData() called on it once before it will be ready to use (not per-agent). This will verify that the tree obeys some of the constraints (like kMaxNumShuffleDeciderGroupChildren, etc.), and it will initialize any timer preconditions that may be in the tree and set the total number of timers in the root decider. It returns true if the tree has been initialized correctly.
TickBehaviorTree will automatically call the InitializeTreeData function if it hasn't been called on the tree yet, but by that time it will be too late to allocate the timers if there are any in the tree (because you'll already be inside TickBehaviorTree).
Each agent should have behavior_tree_memory object, a behavior_stimuli object, and an array of decider_timers if the tree has any timer-based preconditions. The number of decider_timers is set by InitializeTreeData into Root.Preconditions.NumTimers, where Root is the name of the root level decider. This is the only decider that needs to be visible to the calling code, as you can see in SPBehaviorTreeDocs.h.
Every tick, the calling code should update the DecisionFlags for the agent state, call behavior_stimuli::Update(dt) on the agent's stimuli, and use the return value from this call to pass in as the StimuliAllFlags pointer to TickBehaviorTree. After ticking, you can optionally call DebugPrintState as documented below.
S10: Performance ----------------
The most important performance factor to keep in mind is that the Decide functions should be very fast, since it is potentially called a lot. It should use external timesliced systems for doing hard work, or at the very least use DBlocks so that it can communicate information to its behavior and the behavior won't have to redundantly compute stuff.
The behavior Tick functions should loop internally if the behavior is supposed to repeat, rather than failing and letting the BT choose them again. This avoids needless work.
S11: Debugging --------------
There are two main types of debugging helpers in the BT system.
1. DebugPrintState is a function that takes a tree and the memory state and will fill a text buffer with an indented view of either the active deciders or the entire tree, depending on a flag. This is useful for tooltip style floating text in-game, and you can see what state an agent is in.
Here is an example output from DebugPrintState on an agent:
*0:ROOT/0x2d5e207 (kGroup, kGroupPrioritizedList 0x0) time: 34.32 [(no group behavior)] idx: 1 *1:GUARD_NEST_GROUP/0x2d5e200 (kGroup, kGroupPrioritizedList 0x1) time: 34.32 [GUARD_NEST_GROUP/0x2c20c25] (0x00000000 0) idx: 3 *3:GUARD_NEST_PATROL/0x2d5e203 (kBehavior 0x0) time: 4.51 [PATROL/0x2c20c23] (0x00000000 0) 2. The BT system has debug output hooks for displaying what's going on during the decision making process inside TickBehaviorTree. The variables to hook into are at the top of SPBehaviorTree.h, and including DebugOutputLevel and its kin. DebugOutputLevel 0 is no output, 1 and 2 cause output only on behavior state transitions, and 3 through 5 cause output every tick. DebugOutputAgent set to 0 outputs for all agents, or if set masks all other agents. There are DebugOutputCurrent* variables for doing more custom masking inside the DebugOutputFunc.
Here is some example DebugOutputLevel == 1 output (notice the timestamps; it is not output every frame, but only on transitions):
BTDBO(1) 0x026DBE38 @ 106.017: activating behavior GROWL/0x2c20c22 with flags 0x0, in decider GUARD_NEST_GROWL/0x2d5e202 BTDBO(1) 0x026DBE38 @ 106.728: activating behavior FIGHT/0x2c20c21 with flags 0x3, in decider GUARD_NEST_FIGHT/0x2d5e201 BTDBO(1) 0x026DBE38 @ 110.266: activating behavior PATROL/0x2c20c23 with flags 0x0, in decider GUARD_NEST_PATROL/0x2d5e203
The BTDBO(n) indicates the output level for the line, the next pointer is the agent, then the time passed to TickBehaviorTree during this tick. Next is the number of spaces indicating the depth into the tree at which the output occured, and then is the custom message. Often the messages will have a SYMBOL/id pair, like GROWL/0x2c20c22 (from the example behavior tree below). And here is DebugOutputLevel == 5 output, dumped every frame:
BTDBO(3) 0x026DBE38 @ 149.267: **************** starting tree @ 0x00918CD0 for 0x026DBE38 **************** BTDBO(3) 0x026DBE38 @ 149.267: dt: 0.065555, DecisionFlags: 0x00000000, StimuliAllFlags: 0x00000000 BTDBO(5) 0x026DBE38 @ 149.267: processing decider ROOT/0x2d5e207, flags: 0x0, new: 0, mask: 0x00000000, redecide: 0, block id: 0x02d5e207 BTDBO(4) 0x026DBE38 @ 149.267: visiting current kGroup decider ROOT/0x2d5e207, kGroupPrioritizedList, 7 children, active child 1, duration 145.434 BTDBO(5) 0x026DBE38 @ 149.267: child 0 (DIE/0x2d5e211)...failed DecisionFlags check BTDBO(5) 0x026DBE38 @ 149.267: ChildrenDecide returned with RunIdx -1, ShuffleIdx -1 BTDBO(4) 0x026DBE38 @ 149.267: continuing child 1 GUARD_NEST_GROUP/0x2d5e200, duration: 145.433682 BTDBO(5) 0x026DBE38 @ 149.267: next_decider_push GUARD_NEST_GROUP/0x2d5e200 BTDBO(5) 0x026DBE38 @ 149.267: processing decider GUARD_NEST_GROUP/0x2d5e200, flags: 0x1, new: 0, mask: 0x00000000, redecide: 0, block id: 0x02d5e200 BTDBO(4) 0x026DBE38 @ 149.267: visiting current kGroup decider GUARD_NEST_GROUP/0x2d5e200, kGroupPrioritizedList, 5 children, active child 4, duration 145.434 BTDBO(5) 0x026DBE38 @ 149.267: child 0 (GUARD_NEST_HELP/0x2d5e212)...passed StimuliFlags check...Decide returned 0.000000 BTDBO(5) 0x026DBE38 @ 149.267: child 1 (GUARD_NEST_FIGHT/0x2d5e201)...has no preconditions...Decide returned 0.000000 BTDBO(5) 0x026DBE38 @ 149.267: child 2 (GUARD_NEST_GROWL/0x2d5e202)...has no preconditions...Decide returned 0.000000 BTDBO(5) 0x026DBE38 @ 149.267: child 3 (GUARD_NEST_PATROL/0x2d5e203)...has no preconditions...Decide returned 0.000000 BTDBO(5) 0x026DBE38 @ 149.267: ChildrenDecide returned with RunIdx -1, ShuffleIdx -1 BTDBO(4) 0x026DBE38 @ 149.267: continuing child 4 GUARD_NEST_IDLE/0x2d5e204, duration: 145.433682 BTDBO(5) 0x026DBE38 @ 149.267: next_decider_push GUARD_NEST_IDLE/0x2d5e204 BTDBO(5) 0x026DBE38 @ 149.267: processing decider GUARD_NEST_IDLE/0x2d5e204, flags: 0x0, new: 0, mask: 0x00000000, redecide: 0, block id: 0x02d5e204 BTDBO(4) 0x026DBE38 @ 149.267: visiting current kBehavior decider GUARD_NEST_IDLE/0x2d5e204, duration 7.904 BTDBO(3) 0x026DBE38 @ 149.267: ticking behavior IDLE_WALK/0x2c20c24 @ 149.266829 (dt: 0.065555) with flags 0x2, duration 7.904 BTDBO(3) 0x026DBE38 @ 149.267: current behavior IDLE_WALK/0x2c20c24 with flags 0x2, in decider GUARD_NEST_IDLE/0x2d5e204 BTDBO(3) 0x026DBE38 @ 149.267: **************** finished tree for 0x026DBE38, depth 3 ****************
You can also access the various Debug*Name char fields in the deciders and behaviors yourself, and there are some string arrays defined for introspection of types at the top of SPBehaviorTree.h.
S12: Macros -----------
As mentioned above, and as you'll see below, the BT system uses a lot of macros to reduce the need for the user to type boilerplate code. The general rule is that all BT macros begin with BT_, and are then usually followed by either DEFINE or DECLARE, depending on which the macros do. Most declarations can appear in header files, while most definitions have to appear in source files. Next is the type of object that's defined or declared, and then options. Often the options will come after a __, and the full version with all the options available is often postfixed with __FULL.
Sometimes a compile error on a line with a macro will be hard to figure out, because something about the generated code is wrong. Often you can spot the problem by inspection, but remember you can right-click on a file in the Solution Explorer in MSVC, select Properties|C/C++|Preprocessor, and turn on Generate Preprocessed File if you have a really hard problem to track down. Compiling the file will produce a filename.i file in the directory containing the sln file. You can usually search for your symbol name, so something similar and find the generated code. Don't forget to turn off the preprocessing so the compiler will generate object code again.
If you want, you can go all the way down to the aggregate initializer if you want, but you shouldn't have to. There is usually a __FULL macro that will give you all the access you need. You can avoid the auto-generated names, share functions between deciders, or whatever you want.
That's it for the high level overview. The rest of the documentation is interspersed through the code below. Major bits of documentation have section numbers like the above sections, but minor notes are just in regular C and C++ comments.
 No claim is made that HFSMs are the ultimate way to do game AI. However, they have certain nice clarity and development process advantages over other more complex simulated forms of decision making, like planning. The idea behind this BT system is to make writing big HFSMs easy enough that you can increase the complexity of the AI code without needing to turn to a more advanced form of decision making. Eventually I think we'll all have to switch over to more simuluation-y forms of decision making, but pushing that off as long as possible seems wise from a process standpoint.  There is a third kind of decider, a "reference decider", that can cause a jump from one part of the tree to another, but it is not implemented yet because we haven't found a use case for it in Spore's AI.