Movement simulation

When we setup on the journey to build an RTS game, we knew that the movement simulation would be one of the central and most complex pieces of technology we had to build, and we had to get it right. The challenges were multiple:

• Had to be really performant so that we can have hundreds and thousands of units in the field, and still have enough frame time to compute the rest of the game logic.
• Should be possible to sync over the network at an acceptable bandwidth and latency.
• Should support both battalion movement and individual unit movement (heroes, monsters, builders).
• Has to feel responsive, and units should behave in the least stupid way when facing obstacles, unreachable paths etc.
• Movement should feel realistic and match the detailed animations that BFME and Reforged use to create an immersive game experience.

Using Unreal's Character Movement Component was not a possibility - It is extremely expensive in both performance and network usage, too detailed for our purposes, and hard to modify.

After some research, we decided to build a 2D movement simulation based on the Boids artificial life program by Craig Reynolds. In this system, each entity (or boid) behaves according to a set of rules that are computed each frame and will determine the forces and therefore, velocity and position changes performed. This proved to be a really flexible framework in which we can add different behaviours to our units, such as moving in formation, avoiding other boids, avoiding static geometry, or colliding against each other.

It has the additional benefit of being easy to multithread, since each boid's movement can be calculated independently from the others (more details on that later). It is also very organic in nature, since each boid moves independently.

Battalions also have their own (vastly simpler) boid simulation - each battalion is a circle or bubble that encompasses all the units in the formation, and can collide with other battalions, follow a path, etc.

How it works (brief overview)

1. Terrain and static geometry are computed into a NavMesh. We use Unreal's Recast implementation, which is configurable in the level via navigation volumes. Buildings modify the NavMesh when placed so that they are also taken into account when pathfinding.

2. The pathfinding algorithm finds the best path from the battalion's current location to the destination point. The path is comprised of path points, which mark the different "steps" of the path and can mark direction changes, for example, when circulating around a building.

3. Battalions will try to move along the path, potentially colliding or avoiding other battalions or buildings. Units will follow the battalion in formation, following a straight path from their location until the desired formation spot. If there are obstacles on the way (other units, buildings etc) they will interact with them and try to reach their formation spot again as quickly as possible.

4. A unit can be "lost", that is, separated from their battalion. In those cases, the lost unit speed is allowed to be slightly higher than the maximum speed of the battalion, to allow catching up, and the unit uses global pathfinding in order to arrive to the position of its companions.