Making a RTS game #34: Improving unit navigation & adding unit formations 1/2 (Unity/C#)

Let’s keep working on our RTS and talk about unit navigation and formations!

This article is also available on Medium.

Disclaimer: once again, thanks to Nexus for giving me this idea of tutorial! 🙂

In one of the earlier episodes of this series, we implemented a basic character unit movement system using Unity’s AI navigation. Then, we later incorporated this system inside a behaviour tree.

This is how we are able to make our characters move across the map by right-clicking either on the terrain (to set a specific destination point) or on another unit (to set it as target and make our unit follow it):

There is, however, a problem with this setup. Right now, if you select multiple character units and right-click on the ground, you’ll see that they all try to go to the exact same point… which results in ugly collisions!

Similarly, they will compete to find a spot if you ask them to follow a target.

So, in this duo of episodes, let’s improve our navigation system and talk a bit about unit formations.

Today, we’ll start by introducing the unit formation system, see why it somewhat conflicts with our current codebase and start a bit of implementation. Next time, we’ll finish this formation system and get our fully-functional improved unit movement!

Just as a quick mouth-watering teaser, here’s a demo of the formation system we’ll have by the end of these two episodes, with multiple possible formation types 🙂

An overview of our formation system

Formations are a common feature in strategy games: they allow you to (more or less) control the final placement of your units when you ask multiple units to move. So, rather than having just a pack of units fighting each other for “the” target position, you give them nicely computed unique positions and avoid the mess.

These formations can be of various type: you can have very rigid and strict alignments (like a line, a grid or a cross) or you can go for something a bit more “untidy” but that still assigns a unique position to each unit.

Today, we’re first going to handle the “untidy” case, and next time we’ll take a look at some stricter formations.

But no matter what formation type we choose to implement, we’re going to face a sweet problem: how can we get multiple units to all work together when they each handle their behaviour on their own in isolation, thanks to our behaviour trees?

The difficulty: working with our multi-agent system!

If you think about it, for now, we’ve specifically made sure that every unit in our game is able to take care of its lifecycle on its own. When we transformed our unit logic into behaviour trees a few weeks ago, we saw that this is nice because it decouples all unit from the other…

… but, wait: we would like these units to work as a group, now, right?

Well, that’s the difficulty we need to overcome here: so far, we’ve created a multi-agent system (with our behaviour trees) and now, we need it to allow for group manoeuvres and shared agent logic.

It’s a bit like a flock of birds: of course, each bird is an individual that can live a life of its own but, when they fly together, they’d better not bump into the others!

The secret is to implement some sort of communication scheme and to designate a leader for this flock: this leader will decide where the units need to go (based on the destination point or target unit we give it) and tell the others how to “spread” around it to get a nice “flock” of units.

Defining a leader

Ok so – at the heart of our formation system is going to be this question of “leadership”.

The leader is going to be a unit amongst the ones that are selected that has a special (although temporary) state. It will be the only one that actually performs the computation; the others will just receive the info.

Why? Because we can’t have each unit compute a set of points and then tell the others to move over there: it would mean having a whole bunch of conflicting orders!

Note however that the leader will send the positions to everyone, itself included — and it will act as a “normal agent” for the receiving process.

The important thing is that because every unit runs the same script (they each share the same structure of behaviour tree), only the “input state” can differentiate their end actions.

Note: that’s a problem that is very common when you do parallel computation, for example with CUDA. Because you share the same script on each execution unit, you have to differentiate in the code the behaviours thanks to the entry state.

To a certain extent, this idea of having a leader handle the computation for the rest of the group relates to the master/slave paradigm (also known as controller/agent, or source/replica, or primary/secondary…), where one agent acts as a central hub, a controller of sorts, and the others serve it to achieve the proper result. Here, we simply say that our source is also a replica, so that it too moves to a position that it’s computed, but we keep the uniqueness of the source.

There are many ways to define who is the leader in the “flock”. In this tutorial, I’m going to go for something really simple and say that the first unit that was selected is the leader. Note that this is arbitrary and that you could as easily take the last one, or a random one, but it doesn’t really matter in our case: since the leader will also move like the other agents, we will have the same behaviour in the end regardless of who does the computation.

Note: you also see that when you create a new selection of units, the leader is assigned temporarily – a unit that was the first selected at one point (and is therefore designated as the leader for this selection) could be a simple agent later on, when you reselect units but don’t start with this one!

However, this means that we need to know the index of the unit in the current selection. We can store this info in our UnitManager, along with the _selected flag we added a few tutorials ago when we implemented our behaviour trees:

Following a target or reaching a destination

The final thing I want to discuss before diving into the actual implementation of the formation system is how we will manage our “follow”/”go to destination” behaviours.

For now, the character behaviour tree has two possible pieces of data it can use for movement, either a destinationPoint or the currentTarget, and those are examined in our check nodes to know whether the unit is going for a specific point on the map, following a target unit or simply in idle mode (remember the bottom of the unit behaviour tree):

These variables are set in the “TrySetDestinationOrTarget” task node whenever we have a unit selected and we right-click on the ground or another unit.

Overall, this logic will stay the same. The difference is that:

  • for a “to-destination movement”: instead of directly assigning the destination point, the unit will compute positions and send them if it’s the leader, or receive it from the leader otherwise. Only when the position is received will it be assigned to the destinationPoint data slot.
  • for a “follow movement”: in addition to storing the transform to follow, the unit will also have an offset to this target – this way, our various units will spread around the target while following it. These offsets will be computed by the leader and received by the others: only when the offset is received will it be assigned to the (newly added) currentTargetOffset data slot.

Of course, we will also need to update our “HasTarget” check node so that it waits for this offset before actually returning a success.

Alright – with all that said, time to actually get into the code and see how to make all of this happen! 🙂

Checking for leadership and computing the offsets/positions

Important note: because the tutorial is a bit long, the implementation of the new formation system is split in two parts. We won’t have something functional by the end of today’s tutorial – we will have prepared a lot of things but our character units movement will temporarily be disabled. Don’t worry – it will be fixed next time! 😉

Calling the computation functions if we are the leader

Ok – let’s update our character behaviour tree nodes to start implementing this new formation system. To begin with, we’ll go to the TrySetDestinationOrTarget and change the raycast code a bit.

If we are the leader, i.e. if our current selection index is zero, then we’ll need to compute the offsets (for a target) or positions (for a point destination) and send them to the entire “flock”:

You see that, depending on the “follow a target”/”reach a destination” mode, we either send a “TargetFormationOffsets” or “TargetFormationPositions” event but that, in each case, we pass in the result of our computation.

Offsets are Vector2s because we won’t be computing the upwards offset: we just move “horizontally” on the terrain and then re-project our positions on the mesh if need be.

But note that, at this point, we have completely removed the logic that actually updates the behaviour tree branch data (at the destinationPoint or currentTarget/currentTargetOffset keys).

As I said before, we’ll of course put it back in the second part of this unit formation tutorial, but at the moment we are not able to go to the move behaviour anymore!

However, for now, let’s focus on the leader and see how to compute our target offsets and positions.

Computing the target offsets/positions

Truth be told, computing offsets around a target unit or exact positions around a destination point is pretty similar: in both cases, we want to take a reference position and “jitter” a bit around it to add some variation and avoid collapsing all target positions in the same place. The only difference is that when we follow a target, the reference position might update (if the target moves).

That’s why we’ll differentiate between the “target offsets” and “target positions”, but that they’ll share some logic:

As you can see here, the “target positions” are simply computed based on the “target offsets” applied to the (fixed) destination point we gave. Since that point won’t move in the future, we can bake our results once and store them as exact positions.

So the real question is actually: how do we compute those offsets, in the _ComputeFormationTargetOffsets() method?

The easy case: the position of the leader

First of all, we’d like the leader to aim for the designated reference point exactly: therefore, if we have only one unit selected, it will go for the target or destination point you gave without further computation.

But what about the other agents that are selected?

Getting our offsets with Poisson disc sampling

Remember that, for now, we want to get a random set of points around the reference position. Ideally, we’d like these points to be spread somewhat uniformly so that we don’t get a cluster of points on one side.

A nice solution for this is to use a technique called Poisson disc sampling. This algorithm gives us an ensemble of tightly-packed points within an area that are however each separated by a minimum distance, which usually results in pretty organic patterns.

Basic Poisson sampling in a box – Image adapted from: “Point samples generated using Poisson Disk sampling, and graphical representation of the minimum inter-point distance.” by Grap-wh (https://commons.wikimedia.org/wiki/File:Poisson_disk_sampling.svg#filelinks)

There are various articles and videos on the net that explain this concept nicely, so I won’t go into the details here. I’ve actually gone ahead and copied an implementation of Poisson disc sampling in C# by Sebastian Lague, a great guy who does lots of amazing coding videos on a wide variety of topics – if you don’t know his Youtube channel, be sure to check it out! 😉

You can simply create a new PoissonDiscSampling.cs file in your project and copy the code from the Github repo inside it 🙂

By using this PoissonDiscSampling class, we can now easily generate a list of 2D positions that are all within a given area and with a minimal radius. We will sample points from a square area with sides of length samplingRange. The only thing is that, by default, the algorithm computes as many points as possible in a square of a particular size, which bottom left corner is anchored at the origin. So we need to adapt the results:

  • we’ll recenter these offsets around 0 to also get negative values – this way, we’ll get target positions all around the initial reference point
  • we’ll also limit the number of results to the number of selected units, minus 1 (because we already took care of the leader)

For a more visual intuition of the transform we’re going to apply, here’s a little diagram of the offsets before/after the process:

This gives us the following code:

Here, I’ve chosen some arbitrary radius and sampling area size that seem to work fine with my own prefabs, but of course you might need to adapt this a bit: don’t forget that if you have too small a radius, your units might collide… but if you increase the radius, you’ll have to increase the sampling area size too to get enough samples! 🙂

However, this particular piece of code (that gets us “nice” random positions around a reference, optionally projected onto the navigation mesh as fixed positions) is something that could be extracted to our utils, so it’s accessible from other places in our codebase:

Why? Well… to let us spawn units easily, for example!

Preparing a little spawning tool

Yes – let’s end today’s tutorial with a little tooling: an easy way to spawn multiple units! And, of course, we’ll place them randomly using our Poisson disc sampling routine to avoid collisions… This way, next time, when we come back to our unit formation system, we’ll be able to quickly make a “flock” of agents 🙂

Because we’ve extracted our SampleOffsets() and SamplePositions() methods, we can access them from anywhere in our project – for example from the DebugConsole class we made a couple of tutorials ago.

What we want is to add a new command, “instantiate_characters”, that allows us to create a given number of instances of a specific character unit type. The command will have the following format:

instantiate_characters <unit_type> <amount>

And it will create the characters roughly in the middle of the screen, using the Poisson disc sampling to spread them a bit better. For example, in the end, we’ll be able to invoke something like:

instantiate_characters soldier 5

This will spawn 5 soldiers in the middle of the screen.

To get this working, we need to do a few things:

  • make an easy-to-access mapping of our character data Scriptable objects with their codes (because our command uses the character reference code as input parameter) – we’ll add a new dictionary in our Globals class and fill it in the DataHandler:

Note: for this code to work, you need to put all of your CharacterData Scriptable Objects inside the assets sub-folder: Resources/ScriptableObjects/Units/Characters 😉

  • add a new type of DebugCommand that accepts two parameters:
  • and, in the DebugConsole script, make sure we handle this case in the _HandleConsoleInput() function:

Now, we’re ready to add our new command! This “instantiate_characters” will use the given code to retrieve the corresponding CharacterData variable, and it will take the current player index as the owner for these new units.

Then, it will use the SamplePositions() function (passing in the world-point equivalent of the middle of the screen as reference position) to get the units positions.

Finally, it will instantiate the characters and place them at their computed position.

Again, note that the values I use here for the radius and spawning area size are arbitrary and might need to be tweaked a bit – from my tests, they seem to work fine with my Soldier prefab and for something like 3 to 8 instances, though 🙂

Important note: this is a debug command, so I don’t want to spend too much time on this. But with this code, you’ll see that if you try to spawn units while other units are already in the middle of the screen, the new ones might get blocked. So, to use this, make sure to take an open area!

You can try this out to quickly spawn a group of units in the middle of the screen… and here’s even another sneak-peek at the formation feature that we’ll finish up in the next episode!

Conclusion

At that point, we’ve successfully defined a leader in the “flock” of selected units and we had it compute some target offsets and/or positions for our agents. We’ve also sent an event that both the leader itself and the other units will catch to actually use this data in their behaviour tree, and we’ve prepared a little in-game tool to quickly spawn units.

Next week, we’ll wrap up this formation system by taking care of receiving this event and using it to set the behaviour tree data, and by talking about “strict formations”! 🙂

Leave a Reply

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