Real-time strategy games often feature hundreds of units. A common number seems to be 100-200 per player (StarCraft, Age of Empires, Men of War, Company of Heroes) for up to 8 players – while some take it to the extremes. American Conquest allows up to 16.000 units, though that limit is fairly hard to reach.

American Conquest (2002) by GSC Game World.

This article is based on StarCraft II but the principles hold true for most modern RTS games. In StarCraft, up to 8 players can each control 200 units - for a total of 1600 units. These units need to stay synchronized across all connected clients.

message Unit {
  uint32 id = 1;
  Point2D pos = 2;
}

message Point2D {
  optional float x = 1;
  optional float y = 2;
}
Protobuf format for an extremely simplified unit description.

The naive approach would be to synchronize the game state across all the clients – but even an extremely simplified model of a unit like the one above would require 3.68Mbps to synchronize at 24Hz.

That is even ignoring buildings, critters, resources, the fact that Zerglings only take up ½ a supply, and the rest of the information that needs to be synchronized across clients. Not to mention that the real model for units in StarCraft II is much more complex.

The straightforward approach of continuous synchronization of the state is clearly not a feasible solution. The game state is simply too large. Instead, we must rely on deterministic game logic to reproduce exact copies of the state on each machine based on the actions performed by the players. This method is known as deterministic lockstep.

Player Actions

It would not be efficient to transmit mouse movement and keyboard input from each client. Selecting a group of units or panning across the map is generally only important to the local instance of the game. Only actions that affect the global game state needs to be transmitted – such as ordering a unit to move, attack or build. Whether the unit was ordered to attack using hotkeys or the graphical user interface is not of importance to the other clients.

message ActionRawUnitCommand {
  optional int32 ability_id = 1;
  oneof target {
    Point2D target_world_space_pos = 2;
    uint64 target_unit_tag = 3;
  }
  repeated uint64 unit_tags = 4;
  optional bool queue_command = 5;
}
Representation of an action used in the StarCraft II API.

Every action of every client is transmitted to every connected client. They can then locally calculate the result of applying all actions on the current game state and advance the simulation to the new shared state –  given that the simulation is fully deterministic.

Deterministic Game Logic

A program is said to be deterministic if it given a particular input sequence always outputs the same result, with the underlying machine passing through the same internal states – across different machines.

Consider the game of Chess. The exact same match can be played across multiple game boards as long as the same sequence of moves is executed.

This is not the case for Ludo. Throwing the dice introduces randomness that quickly makes the states drift.

Getting rid of randomness would generally be enough to make turn-based games deterministic. This is not the case with real-time games as they are also time-sensitive. Receiving an attack command with just a fraction of a second's delay could change the outcome – resulting in different states across the clients.

The solution? Make real-time strategy games turn-based.

Game/Simulation Ticks

Each client is running their own step-based simulation of the game. These run slow enough that the user's actions have time to be transmitted over the network – yet fast enough that the game feels responsive.

It is essentially running as a turn-based game where you automatically skip your turn if you do not act within the given time limit.

StarCraft II allows the user to select between 5 different game speeds. Choosing a faster game speed simply allows the simulation to advance more frequently.

Game Speed Speed Factor Simulations Step Delay
Slower 60% 9.6Hz 104.17ms
Slow 80% 12.8Hz 78.125ms
Normal 100% 16Hz 62.50ms
Fast 120% 19.2Hz 52.08ms
Faster 140% 22.4Hz 44.64ms

Fun fact: The frequency of the underlying simulation is now software-controlled – but was tied directly to the CPU clock speed in the early days of video games. This meant that getting a faster computer would increase the game speed, giving birth to the wonderful turbo button.

Fake it until you make it, real-time

Playing a game at 9.6 FPS is not particularly enjoyable. However, there is no reason for the game graphics to run at the same low frequency as the underlying simulation. We can show fancy animations in arbitrary high framerates between the simulation ticks to make the game feel seamless - even though the game state, such as unit health, is updated at a slow and fixed rate.

Eight steps of the game simulation.

StarCraft II seems to simulate everything deterministically – including graphics. This is not always the case. Company of Heroes use non-deterministic physics to create realistic-looking explosions, probably because it is easier and less compute-intensive. The game simulation is still kept in sync between clients – but the visual representation shown to the user is allowed 'creative freedom'.

Screenshot with in-game explosions from Company of Heroes by Relic Entertainment.

Pseudo-randomness

Two identical units that begin shooting at the same simulation tick could be expected to die simultaneously, but this is not the case in StarCraft II because every action is executed sequentially.

Fight between two identical Marines, StarCraft II

An element of pseudo-randomness is introduced to keep the simulation fair – by randomizing the order in which units get to execute their actions at every tick. The pseudo-random algorithm used is based on the current tick so the sequence can be re-created on every client without further communication.

Replays

Another benefit of the deterministic design is the ability to store replays efficiently – simply store the sequence of actions performed and play them in order to recreate the game states.

A consequence of this design is that the game states can also only be accessed sequentially. Jumping to the end of the match requires replaying every single action perform until that moment. This is the reason most games that rely on deterministic game logic do not allow you to jump back and forth in the replays.

The design also makes a big assumption: that the simulator remains unchanged. Even a small bug fix or a simple patch updating a single unit's attributes could affect the simulation outcome – thus alternating the replay.

That is why your old replays in Age of Empires IV are no longer valid.

Animation of the Mongol Town Center used in the announcement of Patch 7989.

You might have noticed StarCraft II is often able to still use play old replays even after patching. This is because the game was designed with a clear separation between the graphical interface shown to the user, the underlying game simulation and the unit attributes.

Every version of the game that you have downloaded is stored on your computer under ...\Blizzard\StarCraft II\Versions per default. This allows the game to run an older version of the simulator when showing replays - thus accurately recreating the battles.

A clever design choice since Blizzard is known for its frequent patches in the name of balancing. They can even submit patches to the game – e.g. new content, bug fixes or graphical updates, as long as the game simulator remains unchanged.

It is too early for me to tell if this is also the case for Age of Empires IV.  It seems likely that Patch 7989 was just an exception as it changed placement logic in the game simulation regarding the Mongols town center.

Hidden restrains of deterministic game logic

Ensuring your algorithm for pseudo-random numbers is deterministic, all clients are running the same version of the game and the simulation progresses at the same pace across clients is not enough to ensure your game logic is fully deterministic.

The use of concurrent programming can easily introduce unforeseen race conditions that result in indeterministic execution. For this reason, the game simulator itself is often limited to using a single thread for execution – while graphics, audio and IO can still make use of concurrent programming to increase performance.

As a consequence, the game simulation has to run extremely efficiently to ensure the deadline of each tick is met – as failing to do so would require all connected clients to halt execution until everyone has caught up again.

The time it takes to request the game state from the StarCraft II API when playing against AI.

This can also result in the in-game AI having fairly limited resources to play with – as the deadline must be met. The graph above shows periodic spikes in computing a single simulation step for every 10th tick, likely to be caused by the AI calculating its actions.

Avoiding concurrency altogether is not even a guarantee that your program will be deterministic. Computer architectures have slightly different implementations of primitive data types and arithmetic operations which can cause the simulations to differ slightly depending on the hardware. Special care has to be taken to avoid this, especially when working with floating-point values – making realistic-looking physics incredibly hard to keep deterministic across multiple machines.

Conclusion

I hope this post makes you appreciate (multiplayer) real-time strategy games as the fascinating piece of software engineering they are.

It is worth noting that these observations are qualified guesses at best. I have no association with the production of any of the mentioned games. A good place to start, if you want more insight into RTS games – is the official SC2 API

[adq_src] S2Client-Proto
Introduction to the official StarCraft II API - a request/response message system in protocol buffers.