Oh, Behave (I) – Introduction

Time to talk about Austin Powers.

No, wait…

Behavior Trees.

Time to talk about behavior trees.

behave

This will be the first in a series of articles describing what behavior trees are and how Crimild implements them.

Throughout the next articles I’ll be talking about what are the different components in a Behavior Tree, how to create simple behaviors and how to combine them into more complex ones.

Before we begin…

Keep in mind that Behavior Trees were recently introduced to Crimild and, as any new feature, they might change during the course of the writing of this series (actually, that applies to pretty much the entire engine). Whenever that happens, I’ll try and update the already existing articles as much as possible so they don’t get too far behind.

What are Behavior Trees?

A Behavior Tree is a tree-like structure where each node is a self-contained action that executes and terminates independently of the other nodes. In contrast, a Finite State Machine requires that each state also provides the necessary transitions to other states, avoiding reusability of states and therefore limiting its scalability.

Due to their self-contained nature, behaviors can be easily grouped together to represent advanced logics in a modular way.

Since each behavior does not explicitly define a transition to the next one, it’s the parent behavior’s responsibility to execute its children. If we make the analogy with functions (for example, in C++), each function contains one or more instructions executed sequentially. A parent behavior may execute each one of its children in the same way (and the parent itself may be a child of another behavior). But the parent behavior might need to execute its children in a different way, say, only until one of them fails or succeeds. And thats were the true power of Behavior Trees is shown.

The next image shows the simplest Behavior Tree: one that contains only an action that prints the value of a variable:

Behavior Tree - Simple

A single-node behavior tree that prints a value from the context

In order to work, each Behavior Tree has an associated context that stores values which are accessible from every node in the tree. The context is used a way to communicate behaviors with one another, like registers in a low-level programming language. In the example above, the PrintContextValue action will look for the value of “x” (the argument) stored in the context and displays it on the screen.

A little bit more complex tree would look like this:

Behavior Tree - Intro (1)

A behavior tree to add two values

Making an analogy with the x86 Assembly programming language, the above graphic shows a parent node that will execute each of its children in sequence. Then, we have three operations for setting and adding the values of X and Y together and storing the result in X (that’s how ADD operates). Finally, we output the result stored in X.

Due to its modular nature, Behavior Trees can be as powerful as any programming language.

Implementing Behavior Trees in Crimild

The Behavior class represents a single node in the Behavior Tree. It’s an abstract class defining the basic interface for all behaviors and implementing the common code for all of them. Probably its most important method is the step() one, that is executed every frame for the active behavior in the tree. When a behavior is executed, the step() method will return one of three possible results:

  • Behavior::State::SUCCESS: The behavior has completed its execution and has a valid result
  • Behavior::State::FAILURE: There was a problem when executing the behavior and there is no result
  • Behavior::State::RUNNING: The behavior has not completed its execution yet, so it should be executed at least one more time.

Simple behaviors, like the ones in the diagram above, perform basic operations but they can still fail if the arguments do not match with context values. More complex behaviors, like a character walking towards a destination will require several updates before completing (either by succeeding or failing) and therefore will make use of the RUNNING state while they’re being processed.

The BehaviorContext class contains the data that is shared among all nodes in a behavior tree. The context is usually passed as an argument to the step() function in behaviors. It includes methods for getting and setting values directly and converting them to the correct data types.

The BehaviorContext also stores a reference an agent, which is a Node object that is linked to the behavior tree. In addition to the agent, the context also stores one or more Node objects that serve as targets for some behaviors. For example, if you implement an attack behavior for you game, the agent would be the character attacking while the target would be the victim.

Finally, the BehaviorController component is used to store the behavior tree and execute it each frame. This controller may contain more than one tree, switching them by using messages or other mechanisms based on your app’s logic.

In practice, you’ll end up seeing something like this:

auto node = crimild::alloc< Node >();
auto sequence = crimild::alloc< Sequence >();
sequence->attachBehavior( crimild::alloc< MOVBehavior >( "x", 5 ) );
sequence->attachBehavior( crimild::alloc< MOVBehavior >( "y", 10 ) );
sequence->attachBehavior( crimild::alloc< ADDBehavior >( "x", "y" ) );
sequence->attachBehavior( crimild::alloc<PrintMessage >( "x" ) );
auto controller = crimild::alloc< BehaviorController >();
controller->getBehaviorContext()->setValue( "x", 0 );
controller->getBehaviorContext()->setValue( "y", 0 );
controller->attachBehavior( BehaviorController:SCENE_STARTED_BEHAVIOR_NAME, sequence );
node->attachComponent( controller );

When attaching behaviors to a controller, you need to take into account when that behavior should be triggered. In the example above, we use SCENE_STARTED_BEHAVIOR_NAME to indicate that we want to execute our behavior only once at the very beginning of our program. In contrast, by using DEFAULT_BEHAVIOR_NAME we would end up trigger the behavior every frame, leading to the value of X being constantly incremented by 10 until de program stops.

We’ll talk more about behaviors and events in later posts. For now, let’s just say that, during an update process, the controller will traverse down the current behavior tree (set by an event) following the path described by those nodes that are still running. This will make more sense once we’ve seen sequences in the next article.

At the time of this writing there are several generic behaviors already available in Crimild.

Data driven design

Hopefully, by now you should have enough knowledge about the very basics of behavior trees to see that they can be easily setup in a data driven fashion. Crimild already includes a set of builders for Lua to define behavior trees like this:

local bt = {
    type = 'crimild::behaviors::composites::Sequence',
    behaviors = {
        {
            type = 'crimild::behaviors::actions::PrintMessage',
            message = 'Hello World!',
        }
    }
}

This construct leads to a very expressive solution and now it’s possible to easily write logic for actors in a simulation using scripting without having to actually code it. In practice, I usually group behaviors together in small modules that are later reused by different actors.

It’s a really powerful tool.

In the next episode…

Now that we have a basic idea of Behavior Trees, in the next article we’ll continue talking about sequences and how they can be used to execute behaviors one after the other.

References

If you want to know more about behavior trees, I recommend the following websites:

 

 

Advertisements

2 thoughts on “Oh, Behave (I) – Introduction

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s