Behavior tree implementation

I was planning to post an overview of my behavior tree implementation on thursday but ended up fixing some stuff instead, including some minor changes to the data structures for the behavior tree.

Without further dely, this is my behavior tree implementation.

The implementation is a data oriented solution without heritage, virtual functions and recursion. Instead the whole tree is laid out in a flat array in a depth first order.

All nodes share the same data structure;

struct BehaviorTreeNode
{
node_types::Enum node_type;

union
{
u32                       end; //this is the index after the last child
BehaviorFunction   execute;
};
};

there end is the index after the last child for a selector node and execute is a function pointer to a behavior function which takes a blackboard and the delta time as arguments. For example the priority selector (index 0) has (index 9) as end. After the creation of a tree (or loaded it from disk) the array is run through a initiation function to set the correct function pointers.

in run time each AI entity have a behavior tree interpreter which contains a pointer to the appropriate behavior tree and a blackboard with the needed state knowledge for the entity. On each frame an interpreter  function loops through the behavior tree. The parent nodes are pushed or poped to/from a stack and used to decide how to handle a return state from a behavior function.

For now the only parent node types are priority selector and sequence selector since no more are needed for this application. Also the only return states from the behavior functions are FAILURE or SUCCESS. However it shouldn’t be to hard to expand with more node types and return states.

/Per Erskjäns

 

Be Sociable, Share!