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
