Explain Behavior Trees like I'm 5 (and I am not a game developer)

In a recent Gamasutra featured post I examined behavior trees from a game dev point of view, suggesting there's a lot more to it than visual scripting.

Here is a short article introducing BT as a refreshing - and perhaps surprisingly effective - strategy for scaling complexity throughout a range of interactive and/or time based applications - from business systems to application development.

Debunking misconceptions around BT

BT is a new (~15 years) control paradigm. It was introduced by game developers (think Halo) and (surprise!), has been gaining ground in robotics and simulation for the past several years.

Here's a few misconceptions in how developers engage (or stay away from) behavior trees.

Is BT only for (game) AI?

AI is a moving frontier. What programmers commonly do in C#, Java or C++ today is reminiscent of expert systems. So are today's programmers yesteryear's AI scientists? Perhaps not.

BT is AI, but there is no search involved (let alone big data); in all, it is relatively close to functional programming and, as we shall see, mainly useful when dealing with time and fragile processes (think "Murphy's law").

Let's frame this a little: BT addresses a category of problems (and removes classes of bugs) that you will not encounter if you are feeding punch cards into mainframes.

If, however, you are dealing with complex business systems, or perhaps designing multimedia applications for miniaturized computing devices, read on!

Is BT a visual method for building hierarchies of behaviors?

BT has been popularized through visual scripting systems. Even so, it is not inherently visual. I see programmers dismissing BT right off the bat because designers can use it (through visual tools) and, well.

I can use a pen. My daughter (2 years old, 12kg) can also use a pen. We use them in different ways.

What's in a name? "Behavior trees" does not hint anything new or overly exciting. Let's get a closer look.

NOTE: BT is often associated with update loops, which are somewhat endemic to games and simulations. We'll get to this.

So what is BT? Is it any good?

At heart, BT is a control method based on tasks. A task is either done, running or failing.

Nothing remarkable about this... ? Wrong. We just put functional programming on its head:

1. Conventional programs are based on bools. We hardly notice but, aside from switch, control structures only ever process yes/no answers. A control paradigm using a tri-state logic... We haven't seen this since practically 1958.

BT has a "yes", a "no" and an in-between value that says... "hold on".

2. In conventional programming, failure is *exceptional*. Returning a bool to indicate failure is an anti-pattern, because programmers do not expect failure.

BT provides a method to consistently, concisely and effectively handle the possibility of failing at every step!

So, BT is about timely tasks (anything that takes time) and addressing failure with a different mindset. These are two sides of the same coin:

• When the time spent into a given function is nearing zero, it is increasingly safe to assume that this function owns the resources it is manipulating.

• Conversely, wherever time is involved, either ownership is reduced, or (assuming we're working on a private copy) our data is getting stale. As such longer time scales require "taking failure seriously".

Approaches which only handle the "time" dimension (such as coroutines, or callbacks) are at best misleading or semi-useful.

One problem though: how do we concisely handle "failure at every step"? Sounds like a lot of petty case logic, right?

To address this, BT offers two complementary composition strategies:

• A sequence iterates through tasks, until a failing task is encountered (thereupon, the sequence fails).
• A selector prioritizes tasks. Try A first. If A fails, try B, otherwise try C, and so forth...

So, how does this match up to traditional techniques?

• Conventional control flow allows sequencing and prioritizing (say, using if-elses or conditionals), however the time dimension is excluded.
• Coroutines and event handlers allow waiting on tasks. However you lose oversight (more about this later).

Running tasks through a BT sequence is different from coroutines. With BT, execution re-iterates all tasks, up to the current task. This is happens at every iteration (likewise with selectors). The consequence is that, if the result of an earlier task gets undone, the task will be re-applied.

So this is a stateless model (there is no need to index the current task - which often does more harm than good) affording very concise descriptions (no more if-elses) and a great deal of flexibility (by combining sequencing and prioritizing).

Implementation woes, and a breakthrough

When I encountered BT two years ago, all libraries I found defined tasks as objects. The provided interfaces prescribed an init-step-end pattern; initially I didn't think much of this, because I extensively use the command pattern, still...

I could see that BT is essentially stateless, and there are significant benefits to this. To boot, parameterizing objects is more work than parameterizing functions. Also, emulating statelessness using (stateful) objects is, well, roundabout.

A high level understanding of this problem is, since conventional languages (Java, C#, Python, list goes on...) normalize control around bools, a tri-state approach is not easily shoe-horned into this.

Eventually, I noticed that BT could be implemented in C# very effectively, owing to a quirky feature designed to support SQL's three valued logic:

pending HandleOrder(Order x)
    => ProcessOrder(x) || Cancel(x) || Resolve(x);

status ProcessOrder(Order x)
    => AvailItems(x) && ProcessPayment(x) && Ship(x);

status CancelOrder(Order x)
    => Recall(x) && CancelPayment(x) && RestockItems(x);

pending Resolve(Order x)
    => /* Unpretty stuff */;

Wow. If this is a behavior tree, I'll drink water:

• status returns cont, fail or running as per specification.
• The conditional operators && and || are overloaded to implement sequences and selectors.

Remember: this is not boolean logic. In order to run the above, we setup an update loop (say, using a timer) and we iterate the main function (here HandleOrder) until it has succeeded or failed.

Countless events may affect a delivery, but we only care about fulfilling the key requirements. Re-iterating until the task is complete ensures we are focusing on these requirements.

At iteration N, if a requirement (such as availing items, or processing a payment) is already fulfilled, we just examine the next item.

"fully processed" payments can get reverted, and deliveries get lost. BT does not specify a strict ordering over tasks, and this is usually an advantage (most implementations let you tweak this too):

• Your model tracks the actual state of the target system
• Control revisits every step until a task is done.

In my own implementations, I use degenerate statuses (here pending) to indicate special cases (Resolve is not allowed to fail, it may only return success or running - as a result we also know (type safety), that HandleOrder will not fail).

If your designer cogs got spinning, you may question the above implementation. Do we need to fulfill cancellation tasks in order, or should they process in parallel? For this, BT has pseudo-concurrency constructs; here is an example:

status CancelOrder(Order x)
    => CancelPayment(x) * (Recall(x) && RestockItems(x));

Here * specifies that both tasks must complete for CancelOrder to return done (We still need to recall order items before reshelving).

If you're eager to experiment with BT, skip to the next section. Still on the fence? In the next section, I use a management metaphor to explain the shift from event-handling to behavior-trees.

Push or poll?

Let us picture a growing startup, initially they have say, three staff, zero clients and two founders. In this environment, a manager can (and probably should) respond to staff requests on the spot. They also have the bandwidth to listen to their staff and process detailed information.

As the company grows, the same manager will get interrupted more often. They have less time to process requests. Eventually they will be interrupted in the middle of interruptions (recursively). Sooner or later chaos ensues. That is, unless they take a different approach.

Conceptually, the solution is simple - hold meetings.

• Collect information from everyone.
• Make informed decisions about reassigning tasks, cancelling stuff, and so forth.
• Frequent meetings is better.
• Condense information - done, fail or cont is as terse as it gets; also, it is actionable.

This metaphor, simply, describes a shift from pushing (stay on call) to polling (hold meetings).

So, if your application is starting to look like a fire-fighting fiesta of handlers and redundant logic, this is a sign that event driven logic is not serving you well; then, BT is a worthy contender.

Living without update loops

For lack of concrete applications in my (mostly game dev) work, I haven't been knee deep into "how do I do BT without update loops. Conceptually, however the answer is very simple: use events to "tick" your behavior trees.

In general, store your event data inside an object, and replace it within an appropriate context before running your tree from the root:

// receive an event
void OnEvent(T x){
    // if there is enough context, handle the request:
    // (event driven approach)
    // ProcessEvent(x);
    // Otherwise, build a request object:
    model.requests += new Request(x);
    // Defer processing to the behavior tree
    // (In due time, your BT will 'revisit' pending
    // requests)
    btRoot.Step();
}

This lets you handle simple cases without overhead, while retaining oversight. If say you needed to postpone, optimise or concatenate requests (anything, really!) this can be done without duplicating logic, or compromising the integrity of your control layer.

Fun with BT and more

To get you started, I share a couple of libraries on Github.

• For quick experiments, there is a purely stateless implementation (MIT).
• Active Logic is my BT library for C# 7 and later (AGPL; licenses on request).

For advice (or serious inquiries), you may get in touch via linked-in.