Boid simulation

The boid simulation is the lower level logic that rules each individual's movement. It is similar to the battalion simulation, but more complex and detailed. It comprises the sames general phases as the battalion simulation:

1. Rule processing

Each boid's and building position is inserted into a Quadtree. This allows us to do spatial queries to find other nearby entities. We then can compute each rule to generate force vectors that will dictate the boid'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

Boids will move in a formation, the formation itself being (in a simplified way) a 2D array of spots. Each boid will be assigned to a spot so that they can calculate an offset from the battalion's center position. Since the battalion's center is moving along the path, units within a battalion will follow the same path (this avoids situations where units sorround a building from different sides while moving, for example).

1.2 Avoid Rule

Boids 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 boids. Some exceptions apply:

• Avoidance won't be calculated if both units go towards the same direction, and with similar speed (since they won't collide in those circumstances).
• Avoidance won't be calculated if the other boid is behind.
• Avoidance won't be calculated if we're going to attach the other boid.

1.3 Collision Rule

Collision is computed as a strong force that will try to separate both boids. In the same fashion as battalions, we don't "teleport" boids out of collision, rather, we push them softly across frames. This is more friendly towards client/server setups and also resolves more organically when a collision does happen. It also allows for two boids to occupy the same space temporarily in corner case scenarios (for example, we prefer to have two boids in the same space rather than push one of them inside a building). Collision against static geometry works similarly, but has a higher strength so that it can override the rest of the forces. In this way we avoid the situation where all the other forces combined push a boid inside a building.

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 boids max speed, to ensure that the combined result of the forces doesn't move the boid past that limit, and apply this result to the velocity.

3. Location change

Once the velocity is calculated, we modify the location of the boid 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 entities), and outputs forces.
• Velocity calculation: Reads forces and outputs velocity.
• Location change: Reads velocity and outputs new location.