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.
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.
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.
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.
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.
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.
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.
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).