Behavior Tree Builder
I recently integrated a behavior tree implementation into my current game project, Plume. I’m fairly new to behavior trees, since I’ve primarily worked with state machines on my previous projects. But so far they’re a ton of fun to work with – although they can be a little counter-intuitive until your brain gets used to designing with them. There are a lot of resources on behavior trees, so I won’t talk about specific details of their implementation. However, if they’re new to you or you want more resources on them, there’s a great article in Steve Rabin’s new book, Game AI Pro. There are also a lot of really good articles on aigamedev.com (even open source projects like btsk).
When I first started playing around with behavior trees, I would create trees by simply allocating behaviors and adding children manually:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// create a root selector behavior_tree* bt = new selector(); // create sub-sequence sequence* seq = new sequence(); seq->add_child(new behavior_reposition()); seq->add_child(new behavior_sweep()); // add children bt->add_child(seq); bt->add_child(new behavior_armbar()); |
But as you can see, it’s unclear what this actually represents without stopping to think about it. And that’s only a few lines of code. It’s obvious that this will become harder and harder to read the more we add to our tree.
The Behavior Tree Builder
What would be really nice is some kind of GUI tool – something that a designer could use easily and effectively without further developer intervention. However, if you’re working on a smaller project written almost entirely in C++, like I am, then this kind of tool might be overkill, especially given time constraints or a lack of resources. When I was first reading about behavior trees, I found a cool construction syntax (Chapter 6 in Game AI Pro). It was something like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// generates same tree structure as before behavior_tree* bt = behavior_tree_builder() .composite .composite .node .end() .node .end() .end() .node .end() .end(); |
I thought it was pretty cool. It gives us a much better understanding of the tree structure just by using a bit of indentation. It’s also very easy to add more nodes to the tree, and since the templating enforces use of the proper types, any mistakes made in the process will be caught either by the compiler. For someone writing trees directly in C++, this can be a robust, expandable way to do it. I had a lot of fun creating this kind of interface in my project, so I thought I’d share my implementation.
Implementation
This kind of interface almost looks like its own little language, but really it’s just a bunch of member function calls. But these methods construct nodes for us based on templated types. This is done using a set of four “builder” classes:
» behavior_tree_builder
» composite_builder
» decorator_builder
» leaf_builder
These individual classes separate construction of each individual type of behavior we can create, and provides a base behavior_tree_builder interface to centralize it all. Keep in mind that when we call a function to add a node, like the composite function, we’re going to return an instance of the corresponding builder class. Also, when we call the end function, we’ll return the parent builder class. This allows us to link everything together into the same tree.
Leaf Builder
Let’s start off at the simplest level – the leaf. At this level we know that we’re not going to be adding more children, so all we really need to be able to do is call methods of the underlying node and return our parent. It’s probably easiest to understand by just looking at the code itself.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// leaf_builder.h template class leaf_builder { public: // constructor leaf_builder(parent_type* parent, behavior_type* leaf_behavior); // calls a member function of the underlying behavior template leaf_builder& invoke(ret (obj::*func)(param_types...), param_types... params) { (m_leaf_behavior->*func)(params...); return (*this); } // ends operations on the current node, returning its parent parent_type& end(void) { return (*m_parent); } private: parent_type* m_parent; // this node's parent builder behavior_type* m_leaf_behavior; // the raw behavior we're constructing }; // class leaf_builder |
It seems like we have a lot to look at here, but it’s actually quite simple. First off, the class is templated. This allows us to keep a pointer to the exact type of the behavior and of its parent. Both of which are passed into the constructor as pointers. At first, it may seem better to simply construct the behavior within the constructor instead of passing it in like this. However, as we’ll see later on, constructing it before-hand allows us to pass parameters to the behavior’s constructor from the parent’s function call. It’s the difference between this:
|
1 2 3 4 5 6 7 |
// arguments passed into behavior_tree_builder's node method behavior_tree_builder() .node .end() .end(); |
and this:
|
1 2 3 4 5 6 7 8 |
// arguments passed in from within the leaf_builder behavior_tree_builder() .node .construct("from guard", 3.0f) .end() .end() |
The syntax from the first example looks better, it’s more clear, and it’s less prone to user error. It’s a win-win-win.
Looking back at our leaf_builder implementation, you’ll also notice an ugly templated method called invoke:
|
1 2 3 4 5 6 7 8 9 |
// calls a member function of the underlying behavior template leaf_builder& invoke(ret (obj::*func)(param_types...), param_types... params) { (m_leaf_behavior->*func)(params...); return (*this); } |
This method allows us to call a member function of the underlying behavior, allowing any number of arguments. This is just in case a behavior requires more setting up to do than just a constructor can provide. If you’re new to C++ delegates and/or C++11’s variadic templates, it might look a little weird. The first argument is just a member function pointer belonging to the class obj. It takes as arguments param_types, which can be any number of arguments, and returns something of type ret. The next parameter, params, is all of the actual parameters to pass to the function. Thankfully, the template types can all be deduced at compile-time. Here’s how you’d use the function while building:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
/* simple example behavior class */ class bjj : public behavior { public: void submit(float time); }; // class bjj // invokes the submit member function behavior_tree* bt = behavior_tree_builder() .node .invoke(&bjj::submit, 3.0f); .end() .end(); |
Now let’s look inside the invoke call:
|
1 2 3 |
(m_leaf_behavior->*func)(params...); |
Pretty short and simple – we’re dereferencing our function pointer, invoking it on our leaf behavior, and passing in our arguments.
Finally, we return a reference of our leaf_builder, allowing us to continue operations on this node.
|
1 2 3 |
return (*this); |
Composite Builder
The composite_builder gets slightly more complex. Composite behaviors have the ability to maintain numerous child nodes. That means it needs the ability to construct multiple different nodes, including another composite. To do this, we’ll just create a set of template methods that return a builder object of the desired type.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// composite_builder.h template class composite_builder { public: // constructor composite_builder(parent_type* parent, crusher::composite* comp); // adds a node to the composite's list of children template leaf_builder // adds a composite node to list of children template composite_builder // ends current node and returns parent parent_type& end(void); private: // private members parent_type* m_parent; crusher::composite* m_composite; }; // class composite_builder |
Unlike the leaf_builder, the composite_builder class has only one template parameter. Here we don’t need to know the exact type of the underlying behavior, since all of the underlying child management is handled by the composite class.
Don’t be tricked by the crusher::composite * in the constructor. This is a pointer to an actual composite behavior. But, since I like having the function have the same name as the object it creates, it’s necessary to be explicit about what composite I really mean. crusher is the namespace that contains the behaviors, so we can simply write crusher::composite to mean a composite behavior and not the composite function belonging to this class.
The node function allows us to use the previously defined leaf_builder.
|
1 2 3 4 5 6 7 8 9 10 11 |
template leaf_builder { // allocate node and add it to children node_type* node = new node_type(params...); m_composite->add_child(node); return (leaf_builder } |
There’s really nothing fancy going on here. But, as you’ll notice, we’re returning a leaf_builder object that has a parent type of composite_builder . That’s exactly the type of the composite_builder, and we simply pass in the this pointer as the parent.
The composite version is very similar.
|
1 2 3 4 5 6 7 8 9 10 11 |
template composite_builder { // allocate composite and add it to children composite_type* node = new composite_type(params...); m_composite->add_child(node); return (composite_builder } |
We just construct a behavior of the given type and return a composite_builder with composite_builder as its parent.
Decorator Builder
The decorator_builder is also similar to the composite_builder.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
template class decorator_builder { public: // constructor decorator_builder(parent_type* parent, crusher::decorator* decor); // public methods // leaf node construction template leaf_builder // composite node construction template composite_builder // decorator node construction template decorator_builder // ends current node and returns its parent parent_type& end(void); private: // private members parent_type* m_parent; crusher::decorator* m_decorator; }; // class decorator_builder |
As you can see all of the methods are the same as before, except this time we’ve added the decorator function. This just allows us to create another decorator.
|
1 2 3 4 5 6 7 8 9 10 11 |
template decorator_builder { // create child node_type* node = new node_type(params...); m_decorator->set_child(node); return (decorator_builder } |
The only thing different here is the call to set_child. My initial implementation of decorator behaviors didn’t include this functionality. It just took its child behavior as a parameter to its constructor. Having a child setter function like this could be dangerous if it gets called multiple times (i.e. leaked memory). A check could be made to see if a child behavior is already present and delete it first. But, really the only time we’d want to set a child is when building. So what I opted to do was keep it as a private function and made decorator_builder a friend.
Behavior Tree Builder
The behavior_tree_builder class brings all of the other builder classes together and allows us to access the actual behavior tree we’re building. Most of the class, however, is the same as before, although this class has no need to be templated.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// behavior_tree_builder.h class behavior_tree_builder { public: // leaf node construction template leaf_builder // composite node construction template composite_builder // decorator node construction template decorator_builder // ends construction and returns the behavior tree behavior_tree* end(void); private: // private members behavior* m_root; }; // class behavior_tree_builder |
There’s actually almost nothing new here. We can construct our three types of behaviors and we can call end – except this time when we create a node, we set it as the root in our tree. And finally when we call end we get the actual tree structure.
That’s all there is to the behavior_tree_builder. It’s a little ugly, but it’s just a bunch of template programming with a bit of C++11. So far this implementation has served me pretty well. It’s clear and easy to use, and that’s really all I was going for. When I originally implemented this for Plume, I didn’t have support for variadic templates, so I recreated the project separately to try it out.