Hi I'm Tommy Thompson and welcome to AI 101: the series that explores the AI tools and
techniques used in video game development. In the first entry of this series I looked
at the navigation mesh: a data structure commonly used in 3D games to enable AI characters to
move around an environment, recognise obstacles and make decisions about how to get from A
to B as fast as possible. In this video, we're looking at one of the core AI technologies
that is now pervasive throughout much of AAA video games: the behaviour tree.
While the wider world is caught in the thrall of machine learning, the games industry is
heavily reliant on behaviour tree techniques. Now I first explored how behaviour trees are
used in my video on Halo 2 - the game largely responsible for their proliferation - but
since then regular views will have noticed how frequently their popping up. They've since
resurfaced in my videos on Alien Isolation, Far Cry 4, BioShock Infinite, Spec Ops: The
Line, Far Cry Primal, Halo 3, Tom Clancy's The Division and that's just the games I've
elected to talk about on the show. So, in this episode I'm going to address what these
systems are, how they work, how they're integrated into commercial game engines and - from my
perspective - discuss why they're becoming increasingly more popular in games and why
as a developer and designer you might be more inclined to use them.
So first up, let's cover the fundamentals, what is a behaviour tree and how does it work?
A behaviour tree is a data structure in which we set the rules of how certain behaviours
can occur and the order in which they would execute. The term 'tree' is denoted given
that it follows the traditional rules of the tree data structure in computer science: meaning
it has a series of nodes that start at the root - which is this one here at the top - which
is then linked to other nodes by connections.
Now in fancy computer science terms this is a directed acylic graph: meaning it's a collection
of nodes that are connected to each other, but in each case there is a fixed direction
and that it doesn't loop back or repeat itself. The logic of the works its way down from the
top, to a specific portion set of one or more nodes where a specific behaviour is going
to be executed. A node that has been linked to by another one above it calls that node
it's parent, and any nodes it links to below it are called it's children. That's some good
comp sci. knowledge you need to remember right there!
Now how a behaviour is selected is based on how it moves down into the tree and the nodes
it executes. Nodes are typically found to be one of four types:
- First up there is the root node: that's the one at the top, it has no parent, only
ever has children and is where the execution starts from.
- Next up is the basic node of a tree called a leaf: this is where we actually put AI behaviours,
such as running to a fixed position in the world, shooting an enemy or interacting with
an object. It's the opposite of the root, it can only have parents and no children.
- After this we have composite nodes: these are special nodes that control the flow of
how we move through the tree. There are two main types:
-- A selector, where it decides which child to execute based on some logic in the world.
So for example, if the player is too far away, it won't execute the child node that does
a melee attack, but it might decide to use a gun and attack from range.
-- Secondly up there is the sequence node: this allows us to execute several child nodes
in sequence one after the other. This is great if you have an that is under fire and you
want it to run towards cover, hide behind it, then take a shot at the player. Given
that's arguably three nodes you've executed in sequence.
- Lastly there are also decorator nodes: these take existing logic of a child and manipulate
it. This is great for making us repeat actions, or make a selector take the inverse of a decision
it would typically make and so on.
So already with this setup you can come up with trees that mash up mulitple behaviours.
Like say deciding whether to have an AI shoot from nearby cover, rush in to attack the player
up close or stand their ground. Like what you see here, it's easy to start visualising
this design and subsequently implementing it. Even using a navigation mesh to move the
player - which I covered in my last AI 101 episode - in the specific nodes that require
it.
Alright, so with the basics down, let's explore how they work and some of the cool features
they carry.
So traditionally, when behaviour trees were first devised, the idea was that every frame
of a given the system would run an update from the root called a tick. The system then
borrows down into the tree to find the node that is active, rechecking whether other nodes
should be active along the way down. However that's a bit expensive - especially when the
tree starts to get bigger, so nowadays the tree will retain a reference to the active
node and process the tick. If it eventually finishes the behaviour at that node, then
it'll re-evaluate what to do.
In addition, a concept advocated by the Halo franchise was to make them more event-driven:
meaning that the tree can quickly switch out of a given node to re-evaluate where it is
in the tree should an event occur in the game world.
Now on top of all of this, is an addition component known as the blackboard: blackboards
are used to store useful data that the tree uses as part of the behaviour of multiple
nodes: target locations, distances to nearest items of interest, even things like status
variables like if the character is under fire or they've already executed a specific behaviour.
The blackboard not only allows us to store this information to minimise the need for
repeated calculations, but also you can use the same blackboard across multiple behaviour
trees. This makes it easier for different AI characters that are all using behaviour
trees to share information - like where the player is for example!
For those keen to experiment with making their own AI that uses behaviour trees, the toolchain
found in Unreal Engine 4 is arguably the best freely available tool out there to use. Pretty
much everything I've explained thus far is implemented in the same fashion in the UE4
tree system and you can get up and running with it pretty quickly.
Now a common question that arises is why would you use Behaviour Trees versus the likes of
say a Finite State Machine - which we've seen in my videos on DOOM and Arkham Asylum - or
even something like planning used in F.E.A.R.? So let's discuss some common issues that can
arise and why many developers adopt behaviour trees as their method of choice.
First up, let's consider how streamlined the flow is: users can clearly watch the decision
making happen in a top-down fashion from root to leaf. This makes for a more scalable system
even as the tree gets bigger. We can still follow the train of logic that gets us from
the root down to a specific behaviour. This visual readability is so important as the
number of unique paths increases. Even in this shot taken from my case study on The
Division - which was simply a visualisation to imply the overall scale of the system - you
can still read the flow of it. Conversely a finite state machine becomes a nightmare
to follow the more complex it becomes and more connections are made between states and
this gets me to the second point.
By streamlining the logic, they're not only more designer friendly but perhaps more critically
- they're easier to debug! The combination of simplified flow, modular behaviours and
shared knowledge through the blackboard reduces the capacity for error and it also resolves
so many of the major issues a designer would have in building behaviours. By comparison,
finite state machines are typically very code intensive - given the conditions of their
execution are typically tied to the code of the behaviour - and even in more recent implementations
such as DOOM 2016, those states machines were built by programmers on request from designers.
Meanwhile many modern behaviour tree systems better support workflows where designers can
quickly build new behaviours using modules already built by the programmers and only
then pester them for specific bits of behaviour that might be missing.
The third valuable aspect is reusability: we typically build individual behaviours in
these trees such that they can be used in different contexts and the logic of the tree
will allow us to reuse the same node whenever we need it. Conversely with finite state machines,
many of the states are typically tied to that specific context. So it gets a little uglier
the more you try to maintain it.
Lastly there's the big issue that impacts every AI system in a game regardless of scale:
the CPU power and memory required to execute. The optimisations of tick processing and event-driven
overrides have enabled behaviour trees to become more optimised over time, whereas a
finite state machine still needs to update every typically every frame it's still in
the correct state and conduct state transitions accordingly. Lastly the use of blackboards
help keep memory to a minimum, given it allows for data to be shared across nodes as well
as different AI all executing the same behaviour tree. As mentioned in my case study on Spec
Ops: The Line, the use of the event-driven overrides was critical to resolve performance
issues the game had when porting it over to consoles.
Now while this episode is dedicated to explaining how effective behaviour trees are, this isn't
to say that they're the one and only option for crafting behaviours in your games. If
you're behaviour logic is relatively small scale and simple, finite state machines are
more than sufficient for your needs. If you need something dynamic and reactive, planning
is also well suited in a number of circumstances, but it often means the problem scale needs
to be compact. Otherwise the overheads of the planner could prove overwhelming, especially
as the number of characters using the planner for decision making increases.
Alrighty, I hope this helps you better understand the theory of how behaviour trees work. As
I say they're incredibly popular in the games industry and you can expect them to continue
to crop up in future case study videos when I'm exploring the AI of AAA games. Behaviour
trees were the most voted for topic by my supporters over on Patreon. If you have a
topic you'd like to see me explore next, let me know in the comments, but don't forget
it's patrons who will ultimately decide the next video. To make your voice heard, join
the AI and Games patreon using the links on screen and in the description. Thanks for
watching and I'll see y'all again soon.