Collision and movements in RTS

A small journey with me on RTS dev land with my tailor made rts engine.

How to get from this?

To this

Why do we need good collision and movement handling?

RTS is all about readability and responsiveness. Both things are difficult things to do well. While the first one is impacted by art a lot it will all be worthless if all units stack on just one point. Subjective things asside responsiveness is related to two things: do units behave quickly to my commands AND do units behave accordingly to my command?

Starcraft 2 has been the ultimate reference for unit control and responsiveness in term of RTS. It handles everything swiftly and feels like units do exactly what you want. In this dev log I will explain how I manage to get close to that feeling and what it took to get there.

In this dev log I will focus on collision handling as it took me a lot more effort to get to somewthing I liked. I will not dive into path finding as it is a very well documented topic for game dev, on the other side I struggled to find good information on crowd management and collision handling.

How to handle collision

Crowd management is a complex subject. It is a pretty well documented subject in the literature, a lot of research papers can be found. But only a few actually work in a real time environment and with a lot of agents (think thousands).

Computation wise it is an expensive subject. You need to find close neighbours and react to them. Maybe do several iteration every game loop in order to have someting acceptable. For my Engine my goal was to be able to have a refresh rate of 100 game loop per seconds.

Why 100 game loops per seconds?

The number of game loops per second defines how fast your engine can handle an input. Since an input can only be processed by the NEXT iteration. If your iteration lasts 50ms it means your engine actually has a built in 50ms input lag IN LOCAL PLAY. No netcode will be able to remove that input lag. 100 loops per second allow a lowest input lag of 10ms (not accounting for network). For example Starcraft 2 was around 25 loops per second and stormgate aims for 64 loops per second. I set up 100 as my goal just to see if it was possible to top that.

That only leaves 10ms to compute every collision solving every step. Not a lot of time. Not even accounting for everything else that need to be done.

My approach(ES)

I started by building a hand crafted algorithm. Computing every collision and moving the unit out of collision manually. By iterating multiple times in case solving one collision caused another one. Of course, that was a very naive approach. I did not perform to well, especially in a very crowded situation when a LOT of units where stacked (again think thousands of units in one point trying to unstack)

On reading scientific papers I came across the Optimal Reciprocal Collision Avoidance algorithm, ORCA. It looks like it is now the state of the art method to handle crowd simulation. You can find the paper on the internet pretty easily. There are implementations around.

I went on to try an implementation of this algorithm, and it work pretty well pretty quickly. However, There were some situations where it did not.

What now?

As stated above there are some things to be worked on the basic algorithm.

Orca does not handle weighted units very well

One major issue when handling mutliple units responding to multiple different commands. ORCA is designed to avoid collision between agents. Therefore you would handle with situation like this one :

or this one :

We can easily see how that would not check the responsiveness criterion.

Stopping becomes non trivial

When an algorithm gets in charge of solving collision between units, it will become difficult for a large group to reach a destination. Units will then get stuck moving for a while (if not forever) all competing for the same goal point :

Orca tuning

Previous diffculties are of course critical when trying to build a quick and snappy rts. Those needed to be adressed and it was not that easy to find the correct approach.

Weight handling

Making sure that units get out of the way of moving unit can be the cause of a lot of headaches. I tried different things

half plane tuning

ORCA works by restraining speed using lines in the velocity spaces (just imagine the screen where each pixel is a velocity for the unit, ORCA removes all pixels that will cause a collision). It is possible to reduce the number of pixels that are removed for heavily weighted units and increase the ones of lightly weighted units.

This actually worked pretty poorly.

Ignoring collision restriction for heavy units

Another approach is to just ignore collision for heavy units when checking against lighter units. This worked better, but it created a lot of unwanted collisions when a lot of heavier units ended up pushing lighter units into each others.

Adding a non tolerance threshold

We were getting close enough. We just needed to remove the collision happening. To do so I added a threshold under which collision where never allowed even when one unit was supposed to push the other.

All is nice but HOW do we weight units?

This is what comes once you have heavy units pushing light units. But what units should be considered light or heavy?

The first thing could be that every unit with a move command would be heavy and the other would be light. This works nicely in this case :

But that does not solve the issue when a lot of units are moving or trying to attack and you want to micro a unit back.

What would a player expect?

In an RTS when a lot of units move around what would a player expect? Usually in RTS a lot of commands are issued (multiple in one second for the fastest players). In most cases, if you just moved a unit and it collided with another one executing an older order you would expect your latest order to have priority, since it is likely that the order is actually a reaction to something new happening in the battelfield :

Of course you would only want this kind of adjustement to happen between units of the same player.

Stopping condition

In order to have a nice stopping condition when moving a lot of units we need to add a stopping condition that change the more units reach the target. The first ones need to get very close to the point but the others wont be able to do so if a lot of units tru to compete collision less. We need to increase the stopping radius the more units arrive. This is not easy to fine tune and may in some cases but gives very nice results at a low computational cost :

Conclusion

We reached the end of my journey through collision handling for the octopus engine. Having something that feels right to control took a lot of effort and brain juice. It is not perfect but handles most situations very nicely. I hope you got some food for thoughts while reading all this.

Thank you for the attention! Here I go to the mountains, connectionless.