Battalion simulation

The battalion movement simulation was introduced as a higher level way to control organized unit movement. In this way, we can have battalions block or push each other. Furthermore, we have more control on scenarios where multiple battalions try to occupy the same spot, so that bigger armies move and arrive to destination in a more ordered manner. Individual units (heroes, monsters, builders...) also have their own battalion, although in this case it is comprised of a single entity.

The battalion movement simulation is comprised of the following phases:

1. Rule processing

Each battalion's position is inserted into a Quadtree. This allows us to do spatial queries to find other nearby battalions. We then can compute each rule to generate force vectors that will dictate the battalion's movement that frame. Each rule has a different weight between 0 and 1, so that we can calibrate the relative importance of each one.

1.1 Arrive Rule

This rule defines how the battalion follows their path (if any). It will generate a force vector clamped to the battalion's maximum movement speed, in the direction of the next pathpoint. Once the pathpoint is reached, we delete it from the path and continue moving towards the next one.

1.2 Avoid Rule

Battalions will sometimes collide. However, movement feels better if collisions are totally or partially avoided by changing direction when a clash is likely to happen. We achieve this by generating a force that is perpendicular to the line between both battalions. This will push the battalions sideways.

1.3 Collision Rule

Collision is computed as a strong force that will try to separate both battalions. We don't "teleport" battalions out of collision, rather, we push them softly. This is more friendly towards client/server setups and also resolves more organically when a collision does happen. In order to make unit movement friendly towards the player, collision is often NOT or partially calculated:

  • Battalions from different teams (enemies) always block each other. This ensures that blocking armies and sorrounds are meaningful.
  • Two battalions from the same team that move in different directions towards different destinations won't block each other, rather, we allow them to traverse normally to have smoother movement.
  • Two battalions from the same team that move in the general same direction will block each other, so that they don't get mixed up during movement.
  • If a battalion wants to occupy a destination that is already taken, it will push the idle battalion.
  • If two battalions want to end movement in the same destination, the last one to arrive will push the other.

2. Velocity calculations

Once the rules have been calculated, we will have a 2D force vector that defines the direction and intensity of movement on that frame. We will clamp that vector to the battalion's max speed, to ensure that the combined result of the forces doesn't move the battalion too much, and apply this result to the velocity.

3. Location change

Once the velocity is calculated, we modify the location of the battalion for that frame, completing the movement.

Multithreading

By avoiding to modify the same attribute (location, velocity or forces) on the same phase, we can safely spread computations between threads:

  • Rule processing: Reads location (for current and neighbouring battalions), and outputs forces.
  • Velocity calculation: Reads forces and outputs velocity.
  • Location change: Reads velocity and outputs new location.

Replication

Having a battalion-based movement system has the benefit of reducing the size of network sync payloads significantly (between 5 and 20 times smaller depending on the battalion size) - instead of updating each unit's individual position, in most situations we can just update the battalion's location, since it's the main indicator that units will follow when moving. Also, since units calculate movement smoothly, we can skip interpolation of battalion location updates - the battalion position will be corrected inmediately while units smoothly adapt their position to the new reference.