A flexible, modern C++ implementation of behavior trees as described by Chris Simpson.
Behavior trees are often applied to writing AI systems in video games. See the article on Wikipedia for another overview.
- Header-only, C++14 template library with no other dependencies.
- Primitive composites and decorators are provided: sequence, selector, inverter, and so on. But you can always add your own!
- Custom behaviors do not have to subclass from anything -- they are just functions.
- Leaf nodes are just process functions with the signature
beehive::Status operator()(Context &context). In other words, nodes can be a functor, static function, lambda, or even a member function of theContextobject that you define. - Trees are composable.
- You can reuse the same tree instance for all entities, so complex trees do not need to be copied around. You can resume a RUNNING node by reusing the same
TreeStateobject. - Dynamic allocation is kept to a minimum. Nodes are kept in a contiguous array. See Future vision below.
Beehive is provided under the zlib license. This means you can do whatever you want with it, including commercial applications. See LICENSE.
Add this repo as a submodule, then add <path/to/beehive>/include/ to your build.
This project uses CMake. If you are also using CMake, you can add_subdirectory(path/to/beehive) and then use target_link_libraries(YourTarget, beehive)
In your project, #include <beehive/beehive.hpp>.
To generate a project with unit tests enabled, pass -DBEEHIVE_BuildTests=ON to CMake:
mkdir build && cd build
cmake .. -G Xcode -DBEEHIVE_BuildTests=ON
This README should contain everything you need to get started. For generated documentation, use the Doxyfile in docs/:
cd doc && doxygen
open html/index.html
If you have not read Chris Simpson's blog post on the subject, you should do so now. The terminology used in Beehive closely matches that defined or used by Chris Simpson.
To build a tree, use the Builder class to define the tree structure:
#include <beehive/beehive.hpp>
// Some context object relevant to your use case that you define
struct Context {};
int main() {
using namespace beehive;
auto tree = Builder<Context>{}
.leaf([](Context &context) {
auto success = DoSomething();
return success ? Status::SUCCESS : Status::FAILURE;
})
.build();
}
This builds a behavior tree that looks like this:
Root
|
v
Do Something
Not bad, but too simplistic to be useful. Take the example from Chris's blog post:
That tree could be defined as follows:
auto tree = Builder<ZombieState>{}
.sequence()
.leaf([](ZombieState &zombie) -> Status {
return zombie.is_hungry ? Status::SUCCESS : Status::FAILURE;
})
.leaf(&ZombieState::has_food)
.inverter()
.leaf(EnemiesAroundChecker{})
.end()
.void_leaf(&ZombieState::eat_food)
.end()
.build();This builder pattern is inspired by arvidsson's BrainTree.
As you can see, the pattern is to use beehive::Builder<YourContext>{} to start a build, then the chained list of primitive calls, then .build() to finalize the tree.
See a complete list of primitives at the bottom of this README.
Composites and decorators require a corresponding call to .end() on the builder, kind of like closing a tag in XML. Leaf nodes do not need an .end() because they can't have any children.
(Technically decorators wouldn't need an .end() either, because they can only have exactly one child, but when laying it out with the appropriate indentation, it looks weird without the end().) It helps to format the calls so that the builder code's indentation matches the nesting level of the calls. But don't worry! However you want to format it, if you make a mistake in the builder, Beehive will assert when you try to run your code. Ouch! (Thinking about making this compile-time assertion -- see Future Vision below).
The tree's root node is essentially a decorator that just returns the result of its child process() function. Therefore the root can not have more than one child. Use .build() to finalize the tree.
The above example uses many of the primitives available of Beehive. Note that the convenience functions .sequence() and .inverter() were used: these are shorthands for .composite(&beehive::sequence<ZombieState>) and .decorator(&beehive::inverter<ZombieState>), respectively. You can pass any callable -- including lambdas, free functions, functors, static member functions and context object member functions -- to .composite() that matches this callable signature:
beehive::Status operator()(Context &context, beehive::Generator<Context> next_child, beehive::TreeState &tree_state);This function is the process function called when the Tree is on this node. In this function, iterate through the child nodes by calling the next_child() generator. The generator returns beehive::Node<Context> const * or nullptr at the end of the child list.
For example, here's an implementation of the sequence composite:
Status sequence(
MyContext &context,
Generator<MyContext> const &next_child,
TreeState &state
) {
while (auto const *child = next_child()) // use the generator to iterate
{
auto status = child->process(context, state); // always pass the provided tree state
if (status != Status::SUCCESS)
{
return status; // if status did not succeed, return the status
}
}
return Status::SUCCESS; // if all children succeeded, this succeeded
}Similarly, you can pass any callable of the following signature to .decorator():
beehive::Status operator()(Context &context, beehive::Node const &child, beehive::TreeState &state);For example, here's an implementation of the inverter decorator:
Status inverter(MyContext &context, Node<MyContext> const &child, TreeState &state)
{
const auto status = child.process(context, state); // process the child
if (status == Status::RUNNING)
{
return status; // return RUNNING if that was the status
}
return status == Status::FAILURE ? Status::SUCCESS : Status::FAILURE; // otherwise, return the opposite
}You may not need to implement your own composites and decorators. If you come up with some generally useful ones, please feel free to open a pull request or issue to let me know about them!
Defining a leaf node is a matter of providing the process function. This is the function that the tree will run when it reaches that node. The functions can take many forms, but they boil down to this signature:
beehive::Status operator()(Context &);where Context is the template parameter passed in to the Builder in the first place.
Use the .leaf() function on the builder to add a leaf. No corresponding .end() call is required, as leaves may not have children.
Actually, it's possible to return bool from your leaf node process function, in case it never returns beehive::Status::RUNNING. Return true for SUCCESS, false for FAILURE.
If you want to use a function with any return type and do not care about the actual result, you can use the builder's .void_leaf() function. The resulting leaf will call whatever function you passed and always return SUCCESS.
In the above example, various approaches to adding the function are demonstrated:
- with a lambda:
.leaf(&ZombieState::has_food) { return beehive::Status::SUCCESS; } - with a member function pointer:
.leaf(&ZombieState::has_food)(givenbool ZombieState::has_food() const). This works because theZombieState &passed in as the first parameter becomes thethisof the member function call. - with a functor:
.leaf(EnemiesAroundChecker{})-- given
struct EnemiesAroundChecker {
beehive::Status operator()(ZombieState const &) const;
// maybe additional state/context members
};- with a void member function:
.void_leaf(&ZombieState::eat_food). The result ofZombieState::eat_food()is ignored.
Additionally, you could use a static member function pointer, a free function pointer or a lambda with captures.
Suppose you already have a tree built for the given Context type. You can reuse the builder code by using the builder's .tree() function to attach the entire tree as a child.
// given `tree` above
auto tree2 = Builder<ZombieState>{}
.sequence()
.tree(tree)
// ... etc.
.end()
.build();Your tree is associated with some context object defined by you. That context type will be specified in the template parameter for pretty much every template in Beehive: Tree, Builder, etc.
Whenever you call process() on a tree, you pass in the Context object by reference. That instance will be passed around to all the nodes that the process call reaches.
The above example used a ZombieState context similar to this:
struct ZombieState // An app-specific context object
{
bool is_hungry{true};
void eat_food();
beehive::Status has_food() const
{
return _has_food? beehive::Status::SUCCESS : beehive::Status::FAILURE;
}
bool _has_food{true};
};In order to resume RUNNING nodes on subsequent process() calls, you need to pass the same TreeState object to tree.process().
Obtain a TreeState instance for the tree with tree.make_state():
auto state = tree.make_state();Do not modify the state object directly.
If you want to "reset" the state, you can always just make a new state.
Rather than copying entire trees around to all entities who might want to use them, the externalized TreeState object allows many entities to share the same potentially huge tree while only needing to hang on to a tiny state object.
The TreeState passed to tree.process() must have originated from a call to the same tree's tree.make_state(). You cannot mix and match state objects.
Once the tree is built, you can run process() on it with a Context instance. When and how you decide to recreate the instance is up to you.
// once per entity using the tree
auto tree_state = tree.make_state(); // get tree state
ZombieState zombie_state = make_state(); // initialized state
// later, every frame ...
tree.process(tree_state, zombie_state);One common question is how to deal with interruptions without overcomplicating the tree. Suppose your character has to check that nobody is around before deciding it's safe to eat. Once the character starts the process of eating, that eat node returns RUNNING. As long as you pass the same TreeState instance to subsequent tree.process() calls, that character will continue eating until done. What happens if the situation changes, and it's no longer safe to eat? Without interruptions, the character will be stuck eating in an unsafe situation!
One solution as suggested again from Chris Simpson in the comments section of the original article is to have two (or more) trees: one for "high priority" checks and the other for the regular thing like eating. The high priority tree would probably have faster checks and fewer or shorter RUNNING states.
If the high priority tree succeeds, the normal tree runs. Otherwise, an issue has come up and the high priority tree needs to deal with it. Once the situation is resolved, the high priority tree will succeed again and allow the character to resume whatever they were doing.
Currently, beehive is implemented with std::vector and std::function. The latter on most implementations will have a small function optimization allowing storage of lambdas with small captures and other functors without dynamically allocating space for them. If there's interest, I could wrap the nodes in a custom type-erasing function wrapper that has more inline space for functors, which would further reduce allocation frequency.
The tree uses std::vector to allocate space for all nodes up-front. Nodes are stored contiguously depth-first. You can pass your own allocator to the Builder.
Something I'd like to look into is validating the builder at compile-time.
The following section outlines the out-of-the-box Composites, Decorators and Leafs available in Beehive, found in namespace beehive. This list may not be entirely complete. See the docs (Doxygen) for details. The <C> means template parameter Context. Lower-case names means it's a function, capitals means it is a class/functor.
Composites have at least 1 child and are used to filter their child's process result.
Processes child nodes in order. Logical AND of the child nodes.
- Returns SUCCESS if all children returned success.
- Stops processing and returns RUNNING if a child returned RUNNING. If you pass in the same
TreeStateinstance to the nexttree.process()call, the tree will resume at this node. - Stops processing and returns FAILURE if a child returned FAILURE.
Processes child nodes in order. Logical OR of the child nodes.
- Stops processing and returns SUCCESS if any child returned SUCCESS.
- Stops processing and returns RUNNING if any child returned RUNNING. If you pass in the same
TreeStateinstance to the nexttree.process()call, the tree will resume at this node. - Returns FAILURE if no child returned SUCCESS or RUNNING.
Decorators are composites with exactly 1 child.
- Returns SUCCESS if the child returned FAILED.
- Returns RUNNING if the child returned RUNNING.
- Returns FAILED if the child returned SUCCESS.
- Returns SUCCESS regardless of the child's status.
Nothing here.