Behaviour Trees: The Cornerstone of Modern Game AI | AI 101

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.

, , , , , , , , , , , , , , , , ,

Post navigation

39 thoughts on “Behaviour Trees: The Cornerstone of Modern Game AI | AI 101

  1. AI 101 is back for 2019 with a new episode dedicated to Behaviour Trees: one of the most commonly adopted AI technologies in modern video game development. Long-term viewers of the show will have noticed how frequently Behaviour Trees have appeared – with them cropping up in Spec Ops: The Line, Far Cry, Halo and The Division last year alone. So let's take a moment to explain how they work and why developers and designers like to use them.

  2. We use something similar in automation technologies to program the behaviour of machines. We have a special programming language for this, called "SFC" or "Sequential Function Chart".

  3. I'm currently developing an Tank AI using Behaviour Trees. I have found it to be very challenging to debug my AI as I work on it. My solution was to make a simple Debug leaf node, that would output custom text whenever the behaviour tree hit that point of the tree. What other techniques do you use to debug your behaviour trees?

  4. @ 1:19 the background marine says “They killed the Chief! You bastards!”

    That’s gotta be a south park reference.

  5. This is monumental work, thank you for crafting these videos with so much care. The only issue in my opinion was in the comparison between the methods, you gave behaviour trees and FSMs so much attention but almost forgot GOAP :c

  6. I may be focusing on the wrong issue here, but wouldn't it make more sense to say Behavior Trees are the 'powerhouse' of modern game AI. Clearly the 'cornerstone' of modern game AI is the state machine, which is used to build said powerhouse.

    I can already sense I'm giving this way more thought that I should. Great video as always.

  7. The root can also be a selector. It doesn't have to be Root->selector, it can be root(selector) where the root is an event in the world that has a selector inside it.

  8. AIs are quite fascinating. without them we wouldn't have video games. i'm grateful for all the talented people through the years which have been responsible for creating such wonderful things.

  9. Since using Behavior Trees depends on the type of game and its scale, what is recommended to use in a simple tactical rpg? I have made a finite state machine but I think it's lacking and the code will get really complicated if I get into this, so are behaviour trees more appropriate?

  10. Nothing stopping you from using the same event-driven optimizations in state-driven system. So the whole "performance" argument is kinda wrong. The same about reusability – nothing stops from writing states and transitions in an isolated, reusable fashion. You are comparing the bare bones state machines with real optimized implementations of BT's which is just incorrect.

  11. Do they learn on the fly? Like you would train a decision tree algorithm using some optimization technique? Also, is there a concept of a "forest" of behaviour trees, like a random forest in decision trees?

  12. One thing I didn't get the 4:11 caching thing . I am making a game where the enemy_director tells each instance of a particular enemy what to do each frame using a (small)behaviour tree. The thing is taht I am traversing the tree and making the pertinent checks every frame; how can I store data about the state in wich it was and still check wether it shoud choose an other path?

  13. As an aspiring game developer, there are moments when I feel particularly excited and motivated to make games. For example, every time I listen to the silent hill 2 soundtrack. In this instance, it's new insights and knowledge from you that is driving that inspiration. Thanks Tommy?

  14. behavior trees could be good for a story driven game. because assuming each character has their own tree they could be programmed to behave in a fashion that is far more consistent with their character for example in a shooter game if a character needs reviving an character who doesn't know them very well will only attempt to revive them if their near by but someone who they are close friends with would immediately drop what they are doing and go out of their way to revive them.

Leave a Reply

Your email address will not be published. Required fields are marked *