Making a RTS game #23: Implementing behaviour trees for our units 1/3 (Unity/C#)

Let’s see how to model complex AI behaviour for the units of our RTS!

This article is also available on Medium.

So far, we’ve gradually added more and more features to our units, but we’ve mostly focused on buildings. And actually, all that buildings can do is produce resources and some units. On the other hand, the only “skill” characters have at the moment is that they can move around the map using Unity’s built-in navigation system.

But what if we wanted to make a more interesting AI-behaviour for those entities? What if we wanted those character units to obey the player but also have some default reactions, for example if they spot an enemy? What if we wanted the buildings to have some range attacks to defend your camp?

Today and in the two next tutorials, we’re going to see how we can model those advanced AI systems and extend the skillset of our units. Since it’s a pretty complex feature, we’ll split it in 3 parts:

  • Part I (this article): I’ll introduce two common AI modelling tools, the behaviour trees (BTs) and the finite state machines (FSMs), and do a quick comparison between the two. I will also talk about how I initially thought I’d implement our units behaviour using FSMs… before realising that they fell short and that I had to revert to BTs! This will be a nice case study for identifying you’re on a wrong path and recovering from it 🙂
  • Part II: we’ll prepare our BT toolbox so that we’re ready to create our own custom trees, and we’ll start rewriting the current behaviour of our units in the BT format
  • Part III: we’ll extend the skillset of our units and have them react to the presence of enemies

This first part is going to be quite focused on theory, so strap on and get ready for a bunch of definitions and diagrams! 😉

What should our units be able to do?

Before we start coding anything, or even discuss the tools we’ll use, we need to write down what we want the overall behaviour of our units to be. Properly designing this is crucial to having a consistent and logical AI for both our buildings and characters.

Note: of course – this is where your own creativity will kick in! I’m going to detail what behaviour I’ll implement for this RTS tutorial but you should definitely adapt it to your own game to get an original AI 😉

In this game, I want the following:

Buildings
  • they should continuously produce in-game resources (gold, wood, stone) for the player that owns them thanks to the resource production system we defined in the last tutorial; for now, we’ll completely ignore units that we don’t own and only produce resources for us (we’ll see later how to handle resources for all of the players)
  • if an enemy unit enters their attack range, they should “attack” them

(We’ll see in just a sec how the attack system works)

Characters
  • if the player right-clicks on the ground and the character unit is selected, it should move to this new target destination
  • if the player right-clicks on a unit (owned by us or an enemy) and the character unit is selected, it should mark the designated unit as the character unit’s currentTarget
  • if an enemy unit enters the character’s FOV, it will also be marked as the currentTarget
  • if the character has a currentTarget and that this target is within the character’s attack range, then the character unit should “attack”
  • else, the character unit should follow the target, i.e. it should move towards it and optionally update its course if the target moves around on the map

So – both our subtypes of units can “attack”; but what do I mean by “attack”? Well, I’ll implement an attack system that works like that:

  • we’ll add some variables to our CharacterData script: the attackRange (how close the unit must be to the target to allow for attacks), the attackDamage (how much each strike hurts the enemy unit) and the attackRate (how often the unit can strike again); we’ll also say that if the attackDamage is zero, it means that the unit cannot attack
  • for now, we’ll say that each hit removes attackDamage health points (HP) to the enemy (we might upgrade how these attack points are computed in the future, though)
  • if a unit reaches 0 HP, it “dies”: its deselected and its game object is destroyed

Buildings can’t move: they can only have range attacks. Characters can be either ranged or melee units and they might first “follow” the target to get closer before actually joining the fight.

Alright! With all that said, it’s time to talk about the various tools we have at our disposal to implement such an advanced system…

A foreword on behaviour trees and finite state machines

So – I need to let you in on a little secret: this tutorial was not supposed to go like this. At first, I’d coded up most of it and even written the tutorial using finite state machines (FSMs)… but then, as I was preparing Part II and thought “I’ll just add an attack feature to my buildings as well”, I discovered that FSMs were falling short.

I think it’s an interesting case study of how you can convince yourself that a solution must be the right one and ultimately realise you were wrong. This is something that is rarely shown in tutorials, and for very good reasons: it’s never pleasant to feel like you’ve been tricked, or to feel like the person “teaching” you about a topic via their tutorial is completely lost. But, this time, I believe it can be beneficial because it will demonstrate how building intricate systems for large projects like our video game is hard and can lead to big mistakes.

So, let me explain my train of thoughts and how I eventually managed to revert to the right path…

What are FSMs?

Finite state machines, or FSMs, are a common way of implementing basic entity behaviour. They rely on states and transitions: you initially define a set of states your entity can be in, and then you decide what inputs will trigger a change from one state to another. Then, you simply define what’s your initial state and, from there, the entity will essentially “live its life on its own” by regularly updating it current state.

FSMs are really good for organising your project because they allow you to quickly decouple behaviours – each state of your entity corresponds to a particular context that is self-contained and completely defined in its own file. You can even “merge” the logic that is shared by multiple states in general states and transform your basic FSM into a hierarchical state machine.

However, remember that this decoupling is not perfect and that, in particular, you’ll still have ties to the state machine itself and the other states in it via all your variables. That’s why state machines are usually better for simple behaviours. And that’s why I eventually couldn’t model my advanced AI behaviour using those: when you need something with a lot of flexibility and maintainability, and especially complex systems that run multiple behaviours at the same time, you should probably go for behaviour trees instead.

Disclaimer: for a more in-depth description of finite state machines and how we can implement them in Unity/C#, you can check out my game dev tutorials on this topic! They’re available either in text format (part I and part II) or as Youtube videos! 🙂

A quick overview of my (failed) FSM implementation

To implement a state machine in our RTS, I thought I’d do the same as in the tutorials I linked above and have:

  • some parent virtual classes that are blueprints for either a state machine or a state inside this machine
  • the actual implementations that are derived from these virtual classes and define our specific character unit behaviour

My states would also expose 4 entry points with their Enter(), UpdateLogic(), UpdatePhysics() and Exit() methods. Those correspond to the 3 big moments in a state lifecycle: the initialisation, the continuous updates and the optional clean ups:

For finite state machines, we can separate the UpdateLogic() from the UpdatePhysics() entry points to better control the chaining of the actions and to make sure everything happens in the proper order (once again, for more info, check out this post).

And then I went ahead and prepared my hierarchy of states. I first focused on the character units because I already had in mind the different “skills” I wanted them to have:

  • a “moving” state: for when the player right-clicks on the ground with this unit selected and the unit then walks to the designated spot
  • a “following” state: for when the unit has no player-defined target destination but sees an enemy unit in its FOV range, and so it goes towards it!
  • an “attacking” state: for when the enemy is within our unit’s attack range and the unit should attack
  • an “idle” state (that’s the starter for the FSM): for just staying still somewhere if there is nothing else to do

I also knew I wanted to share some logic between several states, so I wanted to make a hierarchical state machine to avoid repeating code. In particular, all character units would need to handle the “destination point definition logic”, meaning that when you right-click on the ground with one or more character units selected, they have to move to this location. And that’s always true, no matter the state they’re in. So I thought I’d implement a general (virtual) state called CharacterFSMBaseState that would be a more refined blueprint for my character units FSM states and automatically share this logic between all actual states.

Similarly, I also designed a MonitoringBaseState for when there is no player-defined target destination and the unit has to monitor for close enemy units.

In the end, I had a schema like this one with all of my states hierarchy (the white blocks are actual instantiable state classes that are derived from the virtual ones they’re enclosed in):

It sounds sweet, right? Well. That’s when it went bad.

Because I continued writing the tutorial and naively wrote down that: “buildings and characters can both attack; buildings will be limited to range attacks, because they can’t move”.

Ok, that’s nice. Except it’s pretty hard to fit in there, actually.

Think about it: you could define two state machines, one for the buildings and one for the characters, but you’d quickly get into quite an intricate network of polymorphism, interfaces and virtual/override methods! (Trust me, I’ve tried 😉 )

Here, the “Idle” and “Attacking” state rely on different managers, they’ll probably have to deal with lots of null references or cross-variables and other tricky problems. Also, for the building units, it’s a bit weird to think of the “Attacking” state as one state that also produces resources on the side…

Not to say it’s impossible: you could spent days and days tweaking the thing so you don’t duplicate too much code, you reduce redundancy and you separate the building-specific and character-specific behaviour.

But let’s be honest: it’s just like using a hammer to screw a shelf. You might eventually succeed but it will be dirty and unnecessarily complicated.

That’s when I decided I had to approach this differently and that it was a good opportunity to finally try out behaviour trees.

Switching to behaviour trees

Once again, I think it’s interesting to see that I didn’t just pick this behaviour tree tool instinctively and got through all of this logic in a breeze. Coding AI is hard and there are lots of ways to do it. Some are valid in almost all cases; others are adapted to just a handful of situations; most are somewhere in-between. And that’s the danger: at times, it’s hard to see that your tool doesn’t fit entirely and that another one would suit better! 🙂

But anyway: what are behaviour trees? Why are they better than finite state machines for us? How did they solve these entanglement issues?

Behaviour trees (BTs) are quite different from finite state machines even though they’re also used to model entity behaviour. Both tools are task switching structures but, rather than having decoupled states and transitions between them, BTs rely on a graph of nodes that provide an easily maintainable, scalable and reusable AI-logic.

To be fair – there are plenty of tutorials and articles about behaviour trees: how they work, how to implement them… and there are also Github repositories with readily available examples, or Unity store assets. If you need something that works great and that you can use instantly, then perhaps you should take a look at those assets, especially the well-known Behavior Designer by Opsive.

But, in this series, I want to start from scratch and show you how to build your own BT system brick by brick. So, here, I’ll try and introduce them briefly but also relate to our past work on the RTS and how they can specifically be applied to the case at hand.

One of the best introductions to behaviour trees I’ve read is this one by Chris Simpson. In this post, Chris brilliantly explains the base concepts of BTs while regularly taking examples from the game he worked on, Project Zomboid. I’ll do my best to sum up his explanations but if you want to learn more, make sure to check out his article! 😉

Ok, so behaviour trees are trees. So far, so good. Trees are graphs that have only one node at the very top, the root, and then a hierarchy of nodes; in other words, each node can have zero or more children, and those children can themselves have children, and so on…

The nodes at the very bottom that have no children are called leaves. Those leaves are going to contain the actual checks and tasks performed by our AI while the rest of the tree is the logic structure that’s going to essentially “switch” from one behaviour branch to another. The inner nodes control the flow and the leaves ultimately implement the actions.

Each node will have its own Execute() method that determines its logic and sometimes calls the Execute() logic of its children (depending on the type of node). And so, nodes can be in either one of 3 states:

  • running: the node is still executing its logic
  • success: the node has successfully finished running the logic
  • failure: there was an error somewhere and the node couldn’t complete its execution properly

To execute the tree itself and essentially have the entity run its behaviour and “live its life”, we will execute its root in an infinite loop (using Unity’s built-in Update() entry point). This is often called a “tick” of the tree.

The Execute() logic is what differentiates nodes. It completely decouples nodes (for real, not like with FSMs where states are still sort of linked) and allows us to independently develop and update one without having to change the rest of the tree: BTs are very modular systems.

By the way, you can actually see that by looking at the Unity asset store: in addition to selling their full Behavior Designer, Opsive also has it cut down in little pieces that you can then re-assemble yourself 😉

But there are, however, grand “families” of execution logics – we can basically make the distinction between “flow-control” and “action” nodes.

Action nodes

The “action” nodes can do very diverse things – in this tutorial, we’ll distinguish between the checks and the tasks: a check will simply perform a boolean check on something and return “success” or “failure”; a task will make the entity perform some actual action (like moving or attacking). For example, we will check if an enemy is within the FOV range and optionally react to this flag to perform a “follow” task.

In the rest of the tutorial, I will represent checks and tasks with the following shapes:

Flow-control nodes

“Flow-control” nodes are the backbone of your BT: they specify how you’ll go from one branch to another, and how you should execute the nodes inside of a branch. We usually distinguish between composites and decorators:

  • Composites have one or more children and process them in a pre-determined or random order depending on the particular node. Their current state depends on the states of their children (and they are “running” while they are still processing the children).
  • Decorators have exactly one child node. They are an “intermediary layer” that may transform the result from the child, repeat or delay the processing of the child, terminate the child… depending on the particular node.

There are plenty of possible composites and decorators; and you could invent pretty crazy ones yourself! But it’s quite common to have at least a few in your BT toolbox:

  • the sequence is a composite that returns “success” only if all its children succeed – it is comparable to a logical AND
  • the selector is a composite that returns “success” as soon as at least one of its children has succeeded – it is comparable to a logical OR
  • the inverter is a decorator that “flips” around the result of its child, so a success will become a failure and vice-versa – it is comparable to a logical NOT. This node is pretty useful to re-use checks: rather than defining “my enemy is closer than” and “my enemy is further than”, you only define the first node and then apply an inverter to directly get the second behaviour
  • the parallel is a composite that runs all of its children at the same time and doesn’t interrupt its execution depending on their return; note that you can choose various success policies (either one of the children succeeded, or you need all of them to succeeded, or you automatically succeeded once they’ve all finished running…)
  • we’ll also have a timer decorator that repeats the processing of its child every X seconds

In the rest of the tutorials, I will represent those nodes with the following shapes:

Why use behaviour trees?

Alright so – behaviour trees can do lots of things. But why are they better than FSMs in our case? What are the real advantages of BTs?

Well, the real power of BTs comes from the fact that:

  • a node (and its children) has access to a data context that allows you to easily share info between each node in a branch

In the rest of the tutorial, I will indicate the nodes that set or get data with the following shapes:

  • you can iterate and gradually extend the behaviour during development: you can start with a simple tree and then add your branches one by one to handle additional checks or actions
  • defining the behaviours’ relative priorities is straight-forward: (except for randomly-ordered composites,) you read the children from left to right and whatever is on the far left will get executed first
  • you can re-use nodes in other parts of the tree very easily to re-integrate a particular piece of logic somewhere in the flow, thanks to a high modularity
  • nodes can even be entire subtrees that completely define a self-contained autonomous behaviour logic (you can have a little “library” of behaviours to pick from, a bunch of building blocks for your AIs)
  • (and they can be represented by nice graphs… which we might discuss in a later tutorial when we talk about tooling and visual editing for our behaviour trees!)

Something really nice with behaviour trees is that they inherently handle sequences, fallbacks and interruptions. With BTs, you can very easily define a series of actions to take one after the other if one or all succeeded so far; you can designate a specific action or check as the fallback if no other matches the current state of the entity; and you can have any task or check be interrupted by a more important (more high-priority) action.

Conclusion

Pfiou, that was a long one! And pretty much all theory, too… 🙂

Today, we’ve seen how behaviour trees work and why they can be useful in video games. We’ve seen their benefits compared to finite state machines and we’ve discussed what we want our units to be able to do.

We’re now ready to dive into behaviour trees and finally write some code!

So, next time, we’ll continue working on the AI of our units and actually start programming our BT base objects, plus we’ll rewrite our current unit behaviour in the BT format: time to get ours hands dirty! 😉

Leave a Reply

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