< Home mto.io

Creating a Behaviour-Tree

Introduction

If you're struggling to understand how a behaviour-tree looks on the inside, reading this article and compiling the provided source file should serve as good starting point. To understand this tutorial you need to have a relatively good knowledge of C and an understanding of what a behaviour-tree is. If that is not the case, here is a link to the excellent "Lean C The Hard Way" by Zed Shaw and a good behaviour-tree overview by Chris Simpson "Behavior trees for AI: How they work"

After watching numerous videos and reading through several articles online, including the helpful "The Spore Behavior Tree AI System Documentation" by Chris Hecker, I've come to the conclusion that just hacking away would be best approach. As there is nothing (reasonably findable) reasonably low-level on the interwebs concerning the implementation of behaviour-trees I'd like to share mine with you.

The following was developed for creating complex and convincing behaviours of agents in a simulated world.

Leaves

Have a look at this:

#define LEAF 0

struct node
{   
    int type;
    int current_child_index;
    int child_count;
    struct node** children;
    int(*action)(void* agent);
};

struct node* CreateLeaf(int(*action)(void* agent));

This node structure is the only one we'll need as it can either act as a leaf or a branch.

To create and allocate a new leaf-node, the CreateLeaf function is called and passed a function-pointer to an action that will be called every time the leaf-node is ticked.

When being called, the leaf's action is passed a void-pointer which points to the agent the behaviour belongs to. The agent could be a human, a cat or something completely different. Let's think about what that means.

Imagine an agent who has a behaviour that, at one point, consists of stepping towards a location until he reached that location. The passed-in agent-data allows the action-function to check if the agent has reached that location, and return a status based on that condition. Have a look at the leaf-action below:

#define FAILURE 0
#define SUCCESS 1
#define RUNNING 2

int WalkToDestinationAction(void* a)
{
    struct agent* agent = a;

    if (agent->x < agent->destination.x)
    {
    agent->x++;
    return RUNNING;
    }
    else if (agent->x == agent->target.x) 
    {
    return SUCCESS; 
    }
    else
    {
    return FAILURE;
    }
}

Notice that the destination is stored inside the agent struct. This is the easiest solution for exchanging data between leaves. We need to exchange data because the destination might have been created by another behaviour that successfully searched for something.

The parent of the leaf will receive the returned status and decide which value to return to it's parent. A wild recursion appears. To keep this blog entry reasonably short and meaty, we will only look at cases where a leaf's parent is a branch and not another leaf as that is less common. The implementation does however support this kind of hierarchy should you need it.

Branches

#define AND 1
#define OR 2

struct node* CreateBranch(int branch_type, int child_count, struct node* child, ...);

We will cover the two most important types of branches for this tutorial. The AND-branch is sometimes called SEQUENCE, while OR is sometimes called PRIORITY. I like to call them AND and OR because they behave similarly to the boolean operators.

We create a branch by passing the type, the number of children and all it's sub-leaves and sub-branches into the CreateBranch function. Making the CreateBranch function take an arbitrary amount of children makes it a bit intimidating to look at, but basically all it does is putting the provided pointers into the children-array.

Each branch - no matter what kind - will Tick through it's children in order, one child at a time. Every time, based on the returned status of the child (which, again, could be a leaf or a branch), the branch will do one of the following things:

We'll look at what the two kinds of branches do differently in a bit. First, let's look at the most important piece of the behaviour-tree.

The Tick

int Tick(struct node* node, void* agent);

This function lies at the heart of the behaviour-tree. It is passed the root-branch of your behaviour-tree, and the agent. Often it is called every frame, but you can do as you like. I for example call it every 12 frames. Let's take a look inside:

if (node->type == LEAF)
    return node->action(agent);

If the passed node is a leaf, the Tick function will run it's action and return the state. Thats it. Next, the AND branch:

Ticking the AND Branch

The AND-branch needs all of it's children to succeed in order for itself to succeed. Since all branches step through their children in order, that means, if the last one succeeds, the branch succeeds.

if (node->type == AND)
{
    struct node* child = node->children[node->current_child_index];
    int state = Tick(child, agent);

    if (state == SUCCESS && node->current_child_index == (node->child_count - 1))
    {
    node->current_child_index = 0;
    return SUCCESS;
    }
    if (state == SUCCESS)
    {
    node->current_child_index++;
    return RUNNING;
    }
    if (state == RUNNING)
    {
    return RUNNING;
    }
    if (state == FAILURE)
    {
    node->current_child_index = 0;
    return FAILURE;
    }
}

That translates to the following return values:

Next the OR branch:

Ticking the OR Branch

The OR branch needs only one of it's children to succeed for itself to succeed. Since all branches step through their children in order: if the last one fails, the branch fails.

if (node->type == OR)
{
    struct node* child = node->children[node->current_child_index];
    int state = Tick(child, agent);

    if (state == SUCCESS)
    {
    node->current_child_index = 0;
    return SUCCESS;
    }
    if (state == FAILURE && node->current_child_index == (node->child_count - 1))
    {
    node->current_child_index = 0;
    return FAILURE;
    }
    if (state == FAILURE)
    {
    node->current_child_index++;
    return RUNNING;
    }
    if (state == RUNNING)
    {
    return RUNNING;
    }
}

The branch returns the following values:

Putting it to work

Thats all the functionality we need for a behaviour-tree to work. We can do some really complicated things with it already. So let's make up an example to see how it would work out in the wild.

When drafting a behaviour-tree it is really helpful to think of it's goal as something you want CHANGED, not something you want to do. Also, write it down first. Also, use a pencil.

Earlier we imagined an agent walking towards a destination. Let's make up something a bit more interesting. Imagine our agent is hungry. The only (reasonable) way he could change that is eating something. To eat something he needs food. To get food he needs to find food, move to it and (bare with me) pick it up. In that order. Only then can he eat it, stopping the hunger. Well, that already sounds like a decision tree.

Notice, when the agent can't find food nearby he would simply stand around until he starves to death. So let's put in a go-out leaf, which should actually be a huge branch. But for testing we can simply fake it.

Our first behaviour tree

Lets write that down in code.

struct agent agent;
agent.hunger = 1;

struct node* leaf_findfoodnearby = CreateLeaf(FindFoodNearby);
struct node* leaf_movetofood = CreateLeaf(MoveToFood);
struct node* leaf_pickupfood = CreateLeaf(PickUpFood);
struct node* leaf_goout = CreateLeaf(GoOut);
struct node* leaf_eatfood = CreateLeaf(EatFood);

struct node* branch_getnearbyfood = 
CreateBranch(AND, 3, leaf_findfoodnearby, leaf_movetofood, leaf_pickupfood);

struct node* branch_getfood =
CreateBranch(OR, 2, branch_getnearbyfood, leaf_goout);

struct node* root_stophunger = 
CreateBranch(AND, 2, branch_getfood, leaf_eatfood);

while(1)
{
    Tick(root_stophunger, &agent);
    usleep(1000 * 1000 * 2);
}

Thats about all there is to it. The actions for the leaves aren't listed because writing them out here would make things unnecessarily complicated. Seeing the behaviour-tree work really helps understanding it. So I encourage you to download the source code below and put it into your compiler.

clang behaviourtree.c -o bt && ./bt

Further thoughts

There is a caveat in using this raw version of the behaviour tree with multiple agents. Since all current-child-indeces are stored inside the branches, you cannot simply do this:

Tick(root, &agent0);
Tick(root, &agent1);

Because the agents will pass through the tree differently, but the tree's branches only support a single state. A quick solution would be to give each agent a copy of the tree just for himself.

struct tree
{
    struct node* branch_getnearbyfood;
    struct node* branch_getfood;
    struct node* root_stophunger;
}

struct agent
{
    int hunger;
    struct tree tree;
}

CreateBranches(&a1.tree);

The leaves can be reused as they have no behaviour-tree-specific states to save. After you've initialized all the branches with CreateBranches, which does nothing more than call CreateBranch on every branch inside the tree struct, you can Tick every agent with it's own tree.

Tick(a0.tree.root_stophunger, &a0);
Tick(a1.tree.root_stophunger, &a1);

This concludes our adventure into behaviour-trees.

If you have questions or want to share your thoughts, feel free to use the comment section below.

Download Source

Want to check out my macOS apps?

I think you'll like them. And they're both free to use :)

Cassette

Low profile, modern music player for macOS.

Youtube Backup

Online video downloader and converter.

From Germany with

Developed by Maximilian Schmidt