informa
12 min read
article

Extending Behavior Trees

A summary of my GDC 2017 talk on design patterns for authoring and 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:

  • Mika: using node decorators for more compact tree representations 
  • Bobby: best practices and combining BTs with finite-state machines 
  • Ben: extending behavior trees and integrating with other systems

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:

  • Additional node types to consider
  • Design patterns for authoring with behavior trees
  • Integrating behavior trees with other AI architectures 

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:

  • Spawn Goal: create a new goal to pursue attached to the current node. In ABL, subgoal and spawngoal are similar to the select node type in a BT. The key distinction with spawngoal is that the goal is pursued concurrently, it’s like spawning a new thread of execution. If the parent node is removed from the tree, then the spawned goal is aborted. 
  • Working Memory Modifiers: one feature I used heavily in my StarCraft bot was reading and writing to the agent’s working memory, or blackboard. ABL can do this using mental acts, but it’s something to consider making a primitive in BT libraries. 
  • Success Test: this is a step modifier that is used to pursue a subgoal until a set of conditions becomes true. It is most commonly used with the wait step to suspend the execution of a behavior until a set of conditions becomes true. 

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:

  • Daemon behaviors: spawn a new thread of activity and continue to pursue a specific goal
  • Managers: decompose gameplay into different subsystems 
  • Message Passing: enables coordination across the different managers 
  • Behavior Locking: prevents specific behaviors from executing 
  • Unit Subtasks: assigns a unit temporarily to a different task  

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: 

  • Income Manager: responsible for working units and resource gathering 
  • Construction Manager: constructs new structures 
  • Tactics Manager: forms squads and manages attack units  
  • Scouting Manager: responsible for reconnaissance 
  • Strategy Manager: selects a build order and determines when to attack. Does not directly execute actions, uses message passing instead. 

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:

  1. A suitable unit is found to perform a task
  2. A flag is set on the unit, assigning it to a new task 
  3. The unit performs the temporary task 
  4. The flag is cleared and the unit is reassigned to it’s original owner 

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:

  1. Augmenting working memory: an external component writes to the agent’s working memory 
  2. External plan generation: an external component generates behaviors used to accomplish goals  
  3. External goal formulation: an external component selects goals for the agent to pursue 

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.

  • Joint goals: a primitive for supporting coordinated goal pursuit across two or more ABL agents 
  • Meta-behaviors: modifying the structure of the tree at runtime. ABL agents can introspect and modify the tree, such as changing priorities 
  • Partial programming: underspecifying conditions for a behavior to execute and having a policy learned a runtime using a reward function. 

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. 

Latest Jobs

Treyarch

Playa Vista, California
6.20.22
Audio Engineer

Digital Extremes

London, Ontario, Canada
6.20.22
Communications Director

High Moon Studios

Carlsbad, California
6.20.22
Senior Producer

Build a Rocket Boy Games

Edinburgh, Scotland
6.20.22
Lead UI Programmer
More Jobs   

CONNECT WITH US

Register for a
Subscribe to
Follow us

Game Developer Account

Game Developer Newsletter

@gamedevdotcom

Register for a

Game Developer Account

Gain full access to resources (events, white paper, webinars, reports, etc)
Single sign-on to all Informa products

Register
Subscribe to

Game Developer Newsletter

Get daily Game Developer top stories every morning straight into your inbox

Subscribe
Follow us

@gamedevdotcom

Follow us @gamedevdotcom to stay up-to-date with the latest news & insider information about events & more