Extending Behavior Trees

This past week I had the opportunity to speak about Behavior Trees (BT) along with my co-presenters Bobby Anguelov and Mika Vehkala at the GDC 2017 AI Summit. It’s been over 10 years since Damian Isla first presented Behavior Trees as a method for authoring game AI in Halo 2, and since then there’s been several presentations on the topic at GDC, the Paris Game AI Conference, and academic conferences. The goal of this session was to explore some of the best practices for using behavior trees learned over the past decade. Here’s what we covered in our session:

In this post, I’ll cover my portion of the presentation. The complete slides and video of the presentation should be on the GDC Vault in a few weeks. I covered the following topics during my section of the talk:

I was excited for the opportunity to be able to talk about BTs, since I got to talk about some of my graduate work at UC Santa Cruz. My dissertation project, EISBot, used a reactive planning language quite similar to BTs. 

My experience with behaviors trees was primarily focused on authoring a StarCraft bot with the ABL reactive planning language. I previously compared differences between these approaches in a blog post, but BTs have continued to evolve and the approaches have more and more similarities. Based on my experience with authoring game AI, I encourage people using or extending behavior tree libraries to consider the following node types:

Adding more features to a behavior tree library can cause performance issues, since it adds more state and concurrency to the tree, but doing so opens up more options for authoring complex behaviors. The language I used had performance challenges with dynamic lookup of behaviors and scheduling of actions. However, we are no longer constrained to the memory limits of the original Xbox and these performance concerns are now less of an issue. 

My goal was to author a bot that could play StarCraft at a high skill level, like the professional player Flash. This requires performing hundreds of actions per minute across different gameplay competencies. I also wanted the system to be able to learn from professional replays, which I discuss later in this post.

Here are some of the design patterns I used to author the bot:

The deamon behavior pattern is used to create a new thread of execution for the agent, where the thread continues to pursue a specific goal. This pattern is useful when the agent needs to perform several concurrent tasks. Here’s an overview of what a deamon behavior looks like in the tree representation. The spawngoal node type is used to create a new goal to pursue, represented as the selector node. The selector node binds to a behavior that loops and continues to pursue a specific task. 

Here’s an example daemon behavior in EISBot. If you’ve ever built reavers or carriers in StarCraft, you know that in order to use these units, you first need to build scarabs or interceptors, which is the ammo for these units. The ABL code snippet shows how this pattern can be used to achieve the goal of making sure that these units always have ammo available.

There are two behaviors in the example: initial_tree is the root behavior, and restockUnits is the daemon behavior. During execution, the spawngoal node type is used to create a new thread of execution. The tree will then pursue the goal of restockUnits, which continues to pursue two goals in parallel. The result of executing this tree is that a new thread of execution is used to continuously stock up units, while the main thread of execution pursue the goal of createManagers.

Another design pattern used in EISBot is the concept of managers, which decomposes RTS gameplay into separate competencies, or subsystems. This is a pattern that was quite common for bots in the StarCraft AI competition. Here are some of the managers in EISBot: 

Here’s an example of one of the managers in EISBot. The behavior is a parallel node type that concurrently pursues several different goals related to managing the income of the agent. The managers in EISBot are actually implemented as daemon behaviors, using the spawngoal and looping pattern previously described. 

For some behaviors, such as pumProbes, the manager is responsible for making the decision to produce additional worker units and taking the action to execute this decision. For behaviors such as processExpansionRequest, the decision making is performed by a separate manager, but the income manager is responsible for acting out this decision. When the strategy manager decides to expand, the income manager is responsible for creating a construction request and transfering worker units to the new location. 

Using managers is a nice way of decomposing gameplay into smaller problems. It also provides a nice architecture for interfacing with external systems, because a subsystem can be replaced with an external component. 

EISBot is composed of managers that need to work together. Message passing is one of the ways this is accomplished in EISBot. It uses behaviors that read and write to the agent’s blackboard in order to coordinate between different subsystems. In ABL this is implemented through mental acts, which are actually inline Java code segments to execute. If you want to use this type of functionality in your behavior trees, I’d recommend making this a primitive in your BT library.

This code segment shows examples for a message producer and a message consumer. The first behavior has a single step, which is a mental act that writes a message to the agent’s working memory. The second behavior is a message consuming that reads the message from memory, binds it to the message variable, passes it to a subgoal for acting upon, and then deletes the message from working memory. 

A pattern related to message passing is behavior locking. In this pattern, a message is written to working memory in order to prevent a different manager from executing a behavior, rather than delegating an action to another manager. This pattern is useful, because multiple managers in EISBot may use the same resources, such as minerals, and one manager needs to override another. 

An example of behavior locking is shown in the example above. The behavior uses the with success test pattern, which waits until a set of conditions are true in order to proceed. The negation in the example above is used to check for the absence of a message that tells the agent to perform a gas hold. If this message is in working memory, than the behavior will suspend, locking the execution of the behavior until it is removed from working memory. 

The pattern is used by the strategy manager in EISBot. Before expanding, the agent will put a gas hold message into working memory, which will force the agent to focus on collecting minerals rather than gas. Once the expansion has initiated, the strategy manager removes it from working memory, enabling worker units to be reassigned to collecting gas. 

In StarCraft, you often need to use a unit for a new task for a short amount of time before returning the unit to it’s prior task, such as when constructing a building. To handle this situation, where units are shared across managers, I use a unit subtask design pattern. Here’s the steps used in this pattern:

This pattern is also used in EISBot when performing micromanagement tasks and handling rushes with worker units. 

Here’s an example implementation of a unit subtask in EISBot. This behavior is used to implement micromanagement of dragoon units in combat, which makes them more effective. The behavior waits until a set of criteria is met: the agent has a dragoon which has taken damage and is not in a flee state. When this situation occurs, the behavior executes the mental act which flags the unit as performing a subtask, and then spawns a new goal to handle this micromanagement task. When this goal is completed, the behavior will also need to clear the flag from the unit so that it can be reassigned to a squad. 

Here’s a video of EISBot in action. The agent is one big behavior tree, which is shown on the left side of the screen. It starts relatively small, creating managers and assigning tasks to the initial worker units. It then grows as additional tasks are executed and goals are pursued. This video shows how the income manager uses worker units to collect resources, the construction manager is used to produce structures, the scouting manager finds the opponent, and the tactics manager forms squads and attacks the enemy. It also shows off the unit subtask pattern, where dragoons take damage and flee before reengaging enemy units. 

What I’ve discussed so far focused on a scripted version of the agent, where a fixed build order is used. One of my goals with EISBot was to create an agent that learns from professional players in order to select build orders, perform tech switches, and identify where to scout for enemy units.

This figure shows the general interface between EISBot and external systems. I used three approaches for interfacing external components:

One of the most direct approaches for interfacing external systems with a BT is simply writing to the blackboard. Rather than using mental acts to write to working memory from the BT itself, you can have external components write to the agent’s working memory. This approach works well with the message passing pattern, because requests to perform tasks can come from other managers or external components. This approach was used to implement particle filters in EISBot, which track estimated locations of enemy units. 

Another way to integrate external systems with a BT is to have the external component create behaviors at runtime that can be used by the agent. This is a form of external plan generation, where the external component decides which actions to take to accomplish a goal. For my dissertation project, I used case-based reasoning, which finds a situation that looks similar and sees what the player did in the situation. This slide shows one of the ways that this can be realized with BTs and is the approach used by Georgia Tech’s Darmok system. 

And a third example of how to interface BTs with external systems is external goal formation. In this setup, an external component decides with goals the agent should be pursuing. This can be accomplished by having an external component modify the structure of the tree. I used this in EISBot to determine when to perform tech switches. 

There’s many other extensions to consider for BTs when looking at other systems for inspiration. Here’s some of the features in ABL to consider.

I hope this session has given you some new ideas for how to use and extend behavior trees. BTs are a great approach for authoring agents that can be integrated with other systems and applied to a variety of different tasks.