Behaviour trees for missions and AI

This article is cross-posted from the Captain's Blog.

Hi, I’m Sam, one of the programmers on Defect! I thought I’d write a bit about the behaviour tree technology that we use to control missions and AI in Defect.

A Question of Control

Drew and Chris build most of the missions in Defect, and depending on a mission’s specifics, they need different things to happen. We need a way to control the AI for NPC ships, and a way to script missions and other events. We could do this completely in code based on specifications from Drew and Chris, but that puts a large burden on the programmers, and in a small team with only one full-time programmer and one part-time programmer, it’s simply not sustainable.

Ideally the game designers should be able create missions themselves with some kind of tool that lets them do things like spawn in ships and other objects, control the camera, and wait for specific in-game events to occur. They should also be able to define ship behaviours, like “fly to this point” or “shoot this ship”. It would be great if they could create bespoke behaviours for specific missions, but also create sets of behaviors for common scenarios that can be used between multiple missions.

There are a few ways to solve this problem. One method is to use finite state machines. FSMs are great for simple AI, but they can quickly explode in complexity with hundreds of states and conditions for transitioning between states. It can be very difficult to debug that kind of spaghetti nightmare! Unreal’s Blueprints system is an example of an FSM-based system. Here’s one I googled which looks pretty complex to me:

I have no idea what’s going on in there!

Behaviour trees are an alternative which are a little easier to read and debug. They can still become quite large and complex, but this can be mitigated in some ways, and because they are tree structures you can collapse entire sections easily.

We implemented our own behaviour tree system and editor. This is what our editor looks like:

On the left is the behaviour tree, and on the right are the properties for the selected node. This is what the currently selected node, the multi-alert, looks like:

Behaviour Tree Basics

Behaviour trees are a hierarchical node structure where each game tick the tree is evaluated from the top to the bottom. The nodes control decision making, and leaf nodes perform actions. In Defect we have many node types that can be combined to provide different behaviours. When a node is run it returns a condition to its parent, such as running (node is still doing something), success (node has finished successfully), or failed (node has finished and failed).

Although there are many specific nodes, all nodes fall into only a handful of basic categories: composite nodes; decorator nodes; and leaf nodes.

Composite nodes - a composite node can have any number of child nodes. The child nodes are processed in some way depending on the type of composite node. For example, the children could be processed in parallel, in sequence, or based on some priority.

Decorator nodes - a decorator node has only one child node. It transforms the result of the child node. For example, a “not” decorator node runs its child and inverts whatever result the child returns.

Leaf nodes - a leaf node can not have any children. It is the node that performs some specific action. For example, in the above screenshot the selected node is called “Display multi-alert”. This is a leaf node that displays a pop-up in the game with some text, a head sprite, and sounds.

These nodes are all combined to control AI or missions.

An Example

Let’s look at a simple example tree:

This behaviour tree implements a skippable intro sequence for the start of the game. How does this work?

Here’s a screenshot that shows just the direct children of the root node:

At the root we have a “Sequence” composite node. This node runs all child nodes until one node fails or all nodes are executed. Each node is executed fully, in order:

Remember, each node is executed fully, before the behaviour tree runtime moves onto the next node.

The priority sub-tree looks like this:

The “Priority” composite node runs each child node in order and stops on the first child that isn’t failing. If a higher priority child starts running, the currently running child is interrupted. “Priority” has two children: a “Skip” sequence and another sequence, “Intro Sequence”.

The “Skip” sequence has one child, “Skip cutscene” which is a leaf node that checks if the cutscene should be skipped. It returns a failure if none of the skip keys have been pressed. This failure bubbles up to the “Priority” composite, which then runs the next node, “Intro Sequence”.

The “Intro sequence” composite performs these actions:

Issues

There are two main downsides to our behaviour tree implementation:

Point (1) we mitigate with tools to allow the designers to more easily search for the nodes that they want to use. We could also do some refactoring to remove duplication, and audit the existing nodes and perhaps remove unused nodes and roll rarely used nodes’ functionality into other nodes.

The performance can be a problem when there are deep tree hierarchies, because the tree is processed from top to bottom every frame, and it is a deeply virtual class hierarchy. There are some optimisations that we could try. We could keep track of the currently running nodes and tick them directly, so we don’t have to iterate over the entire tree. The performance is adequate on PC/Mac at the moment, and it really only shows up as a problem on phone/tablet, so we probably won’t look into this just yet.

Summary

As you can see the behaviour trees can let you create quite complex sets of actions and conditions. They can be read and debugged in a natural way by scanning down the tree in the editor. We also have a feature where the tree can be displayed at runtime, and the currently running nodes will render in different colours, allowing us to debug the trees as they are running.

Because the trees can grow large, we also have a special node called an “embedded tree” that lets us reference an external behaviour tree. The external tree is inserted at the location of the embedded tree. This lets us keep the tree tidy and easier to read and maintain.

Overall the behaviour tree system has worked out well for us. It’s simple for the programmers to expose new actions to the tree, and the designers have a huge amount of flexibility.