The Determinism Engine — Inside Brood War

Why floats are forbidden

1. Fixed-point math: no rounding arguments.

Floats can give slightly different results across CPUs, compilers, and optimization flags — a last-bit disagreement in 0.1 + 0.2. Invisible in a normal game; fatal in lockstep, where it means two machines compute different positions and desync. So the simulation uses no floats: every position, velocity, angle, and hit-point is an integer read as a fraction.

OpenBW's workhorse is fp8 — a 24.8 fixed-point number: 24 integer bits and 8 fractional bits, stored in a plain int32. The "real" value is just raw / 256. Adding, multiplying, and comparing these is pure integer math — perfectly reproducible everywhere.

// util.h:703 — the fixed-point family
using fp8  = fixed_point<24, 8, true>;   // 24 int bits . 8 fraction bits, signed
using fp16 = fixed_point<16, 16, true>;
using direction_t = fixed_point<0, 8, true, true>; // 256 directions = 360°

fp8 — 24.8 fixed-point inspector

drag a value · see the integer it's actually stored as · precision is exactly 1/256

value 3.70

Notice the value snaps to multiples of 1/256 ≈ 0.0039. There's no "almost 3.7" — there's raw 947, which is 947/256, identically on every CPU.

Angles as a full byte: the 256-direction circle deeper

Brood War divides the compass into 256 directions — one per value of a byte — rather than 360 degrees. Turning is integer addition that wraps cleanly at 256. To move a unit, the engine doesn't call sin/cos (floats!); it looks up a precomputed table of 256 unit-vectors:

// bwgame.h:34 — a 256-entry table of fp8 unit direction vectors
static const std::array<xy_fp8, 256> direction_table = { ... };

So "face the target and step forward" becomes: compute a direction byte, index the table, add the fp8 vector to position. All integer, all deterministic.

Multiply & divide without overflow deeper

Multiplying two 24.8 numbers naively overflows (the product has 16 fraction bits and a doubled integer range). The fixed-point type provides scaled operators plus helpers like multiply_divide(a, b, c) = a*b/c computed in a wider intermediate to avoid overflow (util.h:685). The key property isn't speed — it's that the result is defined and identical for all inputs on all platforms.

Synchronized chance

2. The RNG: random, but the same random everywhere.

Combat has randomness — a shot, a critical, spawn jitter. But "random" in lockstep must mean everyone rolls the same number. The tool: a linear congruential generator — one 32-bit state advanced by a fixed multiply-and-add. Same seed + same number of calls = identical sequence.

// bwgame.h:13192 — the entire random number generator
int lcg_rand(int source) {
  ++st.random_counts[source];          // track calls per source (256 sources)
  ++st.total_random_counts;
  st.lcg_rand_state = st.lcg_rand_state * 22695477 + 1;  // advance
  return (st.lcg_rand_state >> 16) & 0x7fff;  // take 15 high bits → [0, 32767]
}

The multiplier 22695477 is the same constant used by the MSVC runtime — unsurprising for a game built with Microsoft's compiler in the 90s.

lcg_rand — two machines, one seed

set a seed, roll on both "machines" — they never diverge, because the math is identical

seed

PLAYER 1 — Machine A

PLAYER 2 — Machine B

What is the source argument for? deeper

Every RNG call passes a source id, and the engine counts calls per source in random_counts[256]. This is a debugging and desync-forensics aid: if two machines diverge, comparing per-source call counts pinpoints which subsystem rolled a different number of times — the usual root cause of a desync (e.g. one machine iterated a list one extra time). It does not affect the values produced.

Where does the seed come from? deeper

At game start the server derives a single seed and ships it to everyone, so all machines initialize lcg_rand_state identically:

// sync.h:509 — fold the client UIDs into one shared seed
uint32_t seed = 0;
for (uint32_t v : sync_state::uid_t::generate().vals) seed ^= v;

In a replay, the seed is stored in the file header and restored on load — which is why a replay reproduces the match exactly. More in chapter 06.

The smoke alarm

3. Desync detection: hashing the whole game, constantly.

Determinism is the goal; the checksum is the proof. Every machine periodically folds its entire critical game state into one 32-bit FNV-1a hash and broadcasts it. Hashes differ → divergence → drop the offender, rather than let two games masquerade as one.

⬡ BW vs OpenBW. The concept — periodic sync checksums that catch divergence — is genuine original Brood War, fundamental to its lockstep design (it's why the infamous "desync" exists). But the specifics below — FNV-1a, the 32-frame cadence, kill_client() — are OpenBW's own implementation in sync.h; Blizzard's Storm layer used a different checksum scheme. And in original BW, detection wasn't always this clean — machines often silently diverged and players kept playing different games ("I killed you" / "no you didn't") until the game noticed or simply died. The tidy "drop the offender" framing is the idealized version.

// sync.h:625 — fold the game state into one FNV-1a hash
uint32_t hash = 2166136261u;             // FNV offset basis
auto add = [&](auto v){ hash ^= (uint32_t)v; hash *= 16777619u; };  // FNV prime

add(st.lcg_rand_state);                  // the RNG state itself
for (auto v : st.current_minerals) add(v); // economy
for (unit_t* u : ptr(st.visible_units)) {  // every visible unit...
  add((u->shield_points + u->hp).raw_value);
  add(u->exact_position.x.raw_value);     // ...its fixed-point position
  add(u->exact_position.y.raw_value);
}

Hashing the raw_value of fp8 positions is only meaningful because the math is fixed-point — two machines must agree on the exact integer, not "approximately."

insync_hash — flip one bit, get caught

two machines hash their unit state · nudge one unit's position by 1/256 of a pixel and watch the hashes split

How often, and what happens on mismatch? deeper

The hash is computed and broadcast every 32 frames (~1.3 seconds), with a 4-slot rolling history so a check can refer to a recent frame even with network jitter:

// sync.h:943
if (sync_st.game_started && sync_st.sync_frame % 32 == 0) {
  update_insync_hash();
  send_insync_check();
}
// sync.h:795 — on receipt
if (hash != sync_st.insync_hash.at(index)) kill_client(client);

There's no attempt to repair a desync — in a peer model there's no authority to repair toward. The only safe move is to remove the diverged player. This is why so much engineering goes into preventing divergence (fixed-point, seeded RNG, deterministic iteration order) rather than recovering from it.

The payload

The action stream: what actually crosses the wire.

A "command" is encoded as a 1-byte action id followed by parameters. The simulation reads these from a per-frame buffer and applies them in order. Because the encoding is fixed and the application is deterministic, the same bytes mean the same thing on every machine — and in every replay.

id	action	encoding	bytes
`9`	select units	count + n×unit_id(16-bit)	1 + 2n
`12`	build	order, tile_x, tile_y, unit_type	7
`20`	move / attack (default order)	x, y, target, type, queue	9
`21`	explicit order	order id + target	var
`87`	player leave	reason	2

// actions.h:1348 — the dispatcher: one byte selects the handler
bool read_action(int owner, reader_T&& r) {
  int action_id = r.get<uint8_t>();
  switch (action_id) {
    case 9:  return read_action_select(owner, r);
    case 12: return read_action_build(owner, r);
    case 20: return read_action_default_order(owner, r);
    // ... ~40 more
  }
}

Actions are grouped per game frame in the stream: a uint32 frame number, a length byte, then the concatenated actions for that frame (actions.h:1456). The simulation executes a frame's actions only when its current_frame matches — keeping command application locked to the frame clock.