In-Depth: Behavior Tree Entrails

[In this reprinted #altdevblogaday in-depth piece, Bjoern Knafla looks at the shape of a behavior tree, and interpreting shapes and actor states for decision making and action execution scheduling.] Today I peek at the main data structures forming my behavior tree runtime implementation and their interplay during the update of a behavior tree controlled agent. Data-oriented Behavior Tree Series This article is part of a series of blog posts about my data-oriented behavior tree experiment:

Oh – It Is Full Of Data! In the last installment of this blog series, I depicted the central ideas behind my data-oriented behavior tree approach. My central experimentation idea is to minimize the memory necessary to store and process behavior trees and to make it easy (unproven yet) to stream data to the local cache or storage of the deployed compute units. My implementation is based on three main data structures:

Shape Of A Behavior Tree A shape describes the static structure of a behavior tree. The behavior tree is flattened into a one dimensional array or stream. Array elements are shape items which represent tree nodes. Shape items are differentiated by their type. Inner nodes a.k.a. branches are deciders which decide when to run which of their children. Therefore, deciders steer behavior tree traversal. Leaf nodes and their shape items are actions (persistent, immediate, or deferred). Currently all shape items are 64bit in size and contain a type field and a union for the data of different node types. I'm pondering if to cut that down to 32bit and then use multiple items if necessary to represent a node, or, alternatively, to adopt a binary blob design as described by Niklas Frykholm in his AltDevBlogADay (ADBAD) post Managing Decoupling Part 3 – C++ Duck Typing. A shape data structure references:

Actor – Execution State Multiple agents might share the same behavior tree shape but as each has an individual world view their behavior execution states differ from each other. An actor data structure consists out of:

Action states encode the behavior or execution state of an action (ready, running, success, fail). The action is identified by the index of the associated shape item in the shape item stream. To save memory, only non-default states are stored. When a game system completes execution of a deferred action for an agent, it changes the actor's running action state to the termination state so the interpretation process can react to the change (event) during the next update. Decider states contain the non-default traversal state of a decider from the previous update and connect it to the decider's shape item via an index. For example, sequence decider states carry the last running child shape item index to enable the sequence to pick up traversal from it. Persistent states belong to shape items representing persistent actions or decorators with timers or counters. All states are stored in increasing order of their shape item indices. This aligns the order in which shape items and their states are iterated during an update tick. Currently, each kind of state has its own fixed-bit-sized data structure but I might split this to store the shape item indices and the data separately to save memory and to unify the code for searching and sorting shape item states. An agent's blackboard aggregates all agent specific game world knowledge. It's the only data immediate action functions are allowed to access to keep cache misses at bay. A blackboard data structure might just be a C struct with fields like used by Halo 2 or a key-value dictionary. It's favorable if the blackboard can be stored as a data blob that's easily kept or streamed into local memory/cache. Interpreter Data The update process itself facilitates an interpreter data structure to collect the next action and decider states and requests to launch or cancel deferred actions. It also contains buffers for persistent state changes. Furthermore, the interpreter maintains indices for its reading position in the behavior shape item stream and in the decider, action, and persistent state buffers of the interpreted actor. An interpreter contains a cancellation token. It represents the range of shape items that need to be explicitly cancelled or deactivated if a higher-up decider abandons previously running sub-behaviors and their active actions. Last but not least, a stack for so called decider guards is used to capture the current traversal location in the behavior tree hierarchy. The stack's top decider guard represents the parent decider of the currently ticked shape item and handles the traversal semantics for the decider node it's associated with. Each decider guard stores: