Boids for RTS

Agents in an RTS often need to pathfind across a map containing various obstacles. Finding the most efficient route at this high-level can be solved with methods such as navigation meshes/grids or flowfields. However, in a fast moving environment with lots of dynamic obstacles moving around & quickly going in & out of existence, it is not always practical to keep making new pathing requests. This is where local navigation techniques, such as boids, can start to be useful.

Iteration with boids demonstrating the behaviours discussed in more detail below

It’s easy to search for a basic introduction to boids, and so, I won’t be discussing that here. Having implemented some basic boids to allow for reasonable group movement there were a few areas I wanted to adjust. This post is a list of notes on the way to improving local avoidance (including agents navigating concave depressions) & implementing a surround mechanic, where a small swarm of melee attackers surround a group of targets.

Spatial Partitioning

Tiles coloured according to agent count

Boids involves lots of comparisons to neighbour agents so having a grid-based spatial partitioning system for dynamic agents helped keep things performant. Systems such as target scanning & boids would access this map to know which agents are nearby, avoiding the otherwise costly O(n2) agent comparisons.

Avoidance

I had originally implemented a separation behaviour but soon realised that a more traditional avoidance force would work better for my goals. There is a behaviour state where the agent is expected to hold it’s position, which is used if the agent is explicitly commanded to do so or if it’s performing some task where it shouldn’t move for other agents, such as attacking. Currently agents could be pushed around by other agents at anytime so a robust avoidance force seemed the best way to fix this.

Initially I used a typical boid separation force which caused the agent to move away from neighbours. This raised the first problem: units getting trapped when surrounded by multiple neighbours. Sometimes they would slow down and eventually push through, other times they would just get stuck as the separation force more or less cancelled out the seek force.

Problem 1: Avoidance force is approximately opposite to seek

I replaced the separation force with a typical boids avoidance force which adjusted the steering to aim either side of a neighbour. The next problem was that the agent avoidance direction was not consistent. It would flicker between two neighbours either side of the agents forward vector.

Problem 2: Non-consistent avoidance direction

To fix the rapid switching of avoidance direction for different neighbours I locked the avoidance force to the same side of the agents forward vector if there was an existing avoidance force (diagrams 1 & 2). This stopped the flickering.

The agent would now navigate around a concave depression of neighbours, however, it had a tendency to continue along the perimeter on the other side of the neighbours rather than head straight for the goal once the path was clear. The solution was to alter the avoidance force to be perpendicular to the goal vector in certain situations (diagrams 3 & 4).

This iteration of the avoidance forces is demonstrated in the video link at the top of this post. It’s worth bearing in mind that in addition to these new ways of calculating the avoidance force, there was a decent amount of iteration tweaking the strength and radius of various boid forces to help get the right effect.

Surrounding

In many RTS games a group of agents can surround an enemy and trap them. This was a very satisfying move to pull off in Warcraft3 in particular where you could trap a high priority hero unit. I wanted something similar to be possible in this prototype. And, in addition to targeting a single agent, I wanted a swarm of melee attackers to spread and surround a defensive block of units. The avoidance work I’d done so far, mentioned above, went a long way to helping achieve the surrounding part, but there were problems. The first problem was targets simply pushing enemy units out of the way to escape. To fix this I had to come up with new rules on who could push who. The seek force of an agent is reduced depending on how much it points towards a close neighbour & what the properties of that neighbour are. ie an enemy would have a strong seek reduction on the moving unit, a friendly holding ground less so. The progression with this behaviour is demonstrated in the linked video too.

Visualisation & Debugging

As can be seen in the video and screenshots, verbose debug visualisation & rapid & easy live tweaking of boid variables is almost essential to getting these behaviours working. Boid activation radii, force arrows sized to magnitude and clear colour coding all went a long way to getting it working as desired. In addition, a replay system or simply recording interactions using a screen recorder program can help considerably. There were lots of times I would rewatch a recording, single stepping through the frames until I understood exactly what was happening and how I might adjust settings or add new behaviours to improve things.

Syncronised Arrival

Sometimes when a group of boids move in a closely packed group I observed that units arriving later would push other arrived units forwards out of position. This wasn’t really desired, so when a unit arrives at a destination it checks if it’s neighbours are in contact with it and zeros their velocity and sets them as arrived too. This appears to make all units in a packed group come to a complete stop over a far smaller number of frames. Previously there was a visible wave-like pattern visible of the units stopping that spread over multiple frames.

Syncronised stop is disabled if a unit isn’t within a threshold distance to the movement goal, this means that units too far away will push others forwards until they enter within this larger stopping distance. I added this so that units stop in a smaller circular radius around the movement goal, rather than a long thin line of units forming (like a line of ants coming to a stop).

10 Comments

  1. Would love more of these! I am the guy from SO, the targeting system would be an interesting read as well, tuning it to get the right behaviour is so tricky. You have the best/ closest feel for the combat/ movement system of any project I’ve seen that tries to go for SC2 behaviour.

    1. Hi Nikola,
      The targetting is actually quite straight forward. Attackers scan for the nearest target at staggered intervals every 10 or so updates. Once an attacker is engaged (no longer moving to target but actively performing the attack) it will stay with that target until the target is destroyed.
      While an attacker is moving towards a target it may scan and update to pick a new target that is closer (unless it’s been given an explicit order to attack a specific target).
      This is all reasonably efficient thanks to the spatial partitioning so that attackers only scan for the targets assigned to tiles within their attack radius. I think I also put a hard limit on the max target count to scan, eg. if there’s a thousand potential targets within range, only scan the first 50, starting in the nearest tiles to the attacker.

  2. Really a nice post!
    In your video there’s a situation where two groups of units move onto each other and resolve this situation very well. What techniques do you use to make it work? It seem like your didn’t mention that in your post. I think it should be similar to what you’ve used for avoiding static units.

    1. Hi, thanks!
      I’m assuming you mean when the two groups of friendly units move through each other here https://youtu.be/ngh9GSZj0HY?t=36

      I zero avoidance & cohesion leaving only seek and alignment forces. The units smaller ‘hard’ physics radius and the physics solver do the rest and it just kind of works. This was an area where I didn’t really iterate much because it just fell into place quite easily.

      I could guess this worked out because the groups formation spreads units out so they are generally not tightly packed. There is usually about 1.5-2.5* a units hard physical radius (the actual collider) between units when they group up in formation. Because of this there is space to be pushed around a bit without blocking others constantly.

      The avoidance force is quite powerful and not used here. A unit ‘A’ only avoids another unit ‘B’ if (going on my memory):
      1) A avoids if it is moving, and B is in a ‘hold-ground’ state
      2) B is a different faction/team to A – an enemy
      3) A is not targetting B for a melee attack

      I experimented with a lighter-weight ‘separation’ force before but it didn’t solve any problems for this use-case and interfered with cohesion, alignment and the others etc.

      1. Hi, thanks for the response!

        Yeah, that’s what I was talking about.

        I’m also not using cohesion at all, but using separation. I’ve tried to disable separation for the units that move towards each other, so they would only separate from units that move in the same general direction.

        Unfortunately, leaving just physical collisions did not produce a good result, since separation radius is not that large, so units were pushing through each other and it did not look very well. Decreasing physical radius solved that problem partially but made a feeling that units aren’t solid physical objects.

        So eventually i decided to use avoidance behaviour. I made units avoid units that are moving towards them and the result was surprisingly good.

        Here’re some gifs: ,

        Actually there’s still a problem that sometimes two groups are trying to avoid each other in the same general direction which makes them stuck (halway “dance”) for some time (gif #2). Starcraft 2 GDC talk mentioned some tecnique that units are “reading minds” of other unit’s to prevent such halfway “dances”, but I did not manage to figure out how it actually works.

        1. That looks pretty good!

          I think the ‘reading minds’ comment is probably referring to finding 2 (or more) units that are on a collision course, and applying a slight avoidance style force to each that is opposite (so they avoid in different directions).

          Howtorts has implemented something similar I think: https://howtorts.github.io/2014/01/14/avoidance-behaviours.html

          https://howtorts.github.io/examples/8-2-crossing-groups-avoidance-behaviour/index.html#smallgroups

          In this case you could say that the 2 agents are reading each others mind because they effectively both know which way the other agent wants to move and how best to avoid.

          1. Hi, sorry for the late response
            Things described on howtorts might be exactly what I need, might try it later. Currently gonna focus on navmesh and pathfinding

  3. Hi, really a nice post!

    When you detect concaves and escape them with your implementation, do you also account potential walls on either side? e.g. avoidance locks to the left side but there is no available path because there is static terrain besides the outmost enemy.

    Also do you mind sharing some code snippets of the implementation?

    1. Hi, thanks for the comment.
      I haven’t tested that particular situation much. I think the unit might get blocked at the wall and the player would have to manually adjust the blocking units in this case. In general in an RTS, it might be better for friendly units to default to pushing each other rather than avoiding most of the time. But sometimes you really do want them to block, like if they’re explicitely told to hold ground or are busy doing something that requires a certain position. So I guess my point is that maybe the blocking behaviour should be used sparingly. I’m not even sure what the desired outcome would be if they get blocked at a wall now that I think about it. I suppose a real person would simply stay stuck & maybe wait, or try to pathfind another way around.
      I’m not really ready to share code right now but it’s something I’d consider in the future. The code and my engine are still changing quite rapidly. I’m not sure it would be that helpful to share right now.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>