Determinism is not free

Two machines run the same physics simulation from the same starting state and the same inputs. After thirty seconds they disagree. After two minutes they are describing different worlds.

Nothing is broken. Determinism is not a property you get by default, and the reasons are worth knowing whether or not you ever need it.

Why anyone cares

If a simulation is deterministic, identical inputs produce identical outputs. Which means you can send only the inputs across a network and let every machine compute the same world independently.

That is deterministic lockstep, and it is how real-time strategy games move thousands of units without moving thousands of positions. The canonical write-up is Bettner and Terrano’s account of Age of Empires, where the bandwidth budget was a 28.8k modem and the unit count was 1,500. Sending positions was impossible. Sending a few commands per turn was not.

Determinism also buys reproducible bug reports and replays that are a list of inputs rather than a recording.

What breaks it

Floating-point differences across platforms. IEEE 754 pins basic arithmetic, but not everything. Transcendental functions — sine, cosine, exponential — are not specified to the last bit, and different libraries produce different final digits. Compilers reassociate expressions under optimisation, and floating-point addition is not associative, so (a + b) + c and a + (b + c) can differ. x87 80-bit intermediates versus SSE 64-bit produce different rounding for the same source.

One differing bit is enough. Simulations are iterative, and iteration is the mechanism by which a last-digit difference becomes a visible divergence.

Variable timesteps. Integrating with whatever delta the last frame took makes the result depend on frame rate. Two machines rendering at different speeds compute different trajectories from identical inputs. This is also why a fixed timestep matters for buoyancy, springs and anything else with a stiff restoring force — the behaviour changes with the step size, not just the precision.

Iteration order. Anything that walks a hash map, or resolves collisions in an order determined by memory layout, can produce different results from the same set of objects. Sort by a stable key before iterating.

Unseeded randomness. Obvious in principle, easy to miss in practice — a particle effect that consumes from the same generator as gameplay logic will desynchronise it.

// Hash order is an implementation detail. It is stable within a run
// and gives no guarantee across builds, platforms or insertion history.
foreach (var e in world.Entities)
    e.Step(dt);

// Deterministic: impose an order the simulation controls.
foreach (var e in world.Entities.OrderBy(e => e.Id))
    e.Step(dt);

This one is easy to miss because it usually looks fine. Iteration order only changes the result when entities interact within a step — and then it changes it permanently.

The two strategies

Make it deterministic. Fixed timestep, fixed-point or carefully constrained floating-point arithmetic, your own transcendental implementations, sorted iteration, a dedicated seeded generator for anything gameplay-affecting. Fixed point is the reliable option because integer arithmetic is exact and platform-independent; the cost is that you give up the dynamic range floats provide, and range errors become your new failure mode.

const double Step = 1.0 / 60.0;
double accumulator = 0;

void Frame(double realDelta)
{
    accumulator += realDelta;

    // Same dt every time, regardless of frame rate.
    while (accumulator >= Step)
    {
        Simulate(Step);
        accumulator -= Step;
    }

    // Interpolation is display only. It must not feed back into state.
    Render(accumulator / Step);
}

The accumulator is the standard construction and the last line is the part people get wrong. The interpolated pose is for the renderer. The moment it writes back into simulation state, the frame rate is an input again and determinism is gone.

Do not rely on it. Replicate state instead of inputs, accept the bandwidth, and let an authority correct drift. This is what most action games do, and it is why they send positions rather than keystrokes.

The choice is largely determined by unit count. Thousands of entities make state replication expensive and determinism attractive. Dozens make replication cheap and determinism not worth its constraints.

Testing it

Determinism fails silently and slowly, so the test has to be mechanical: hash the full simulation state every fixed step and compare the hashes across machines. The first step where they diverge tells you which system to look at.

Without that, you find out from a bug report describing two players who saw different outcomes, minutes after the actual divergence, with no way to locate it.

The same instinct applies to testing time-dependent code generally. Controlling the clock — a virtual-time scheduler rather than real sleeps — is the same move: remove the source of nondeterminism so failures become reproducible.

References

1. P. Bettner, M. Terrano. “1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond.” Game Developers Conference, 2001. The canonical deterministic lockstep write-up.
2. D. Goldberg. “What Every Computer Scientist Should Know About Floating-Point Arithmetic.” ACM Computing Surveys, 23(1), 1991.
3. G. Fiedler. “Deterministic Lockstep” and “Fix Your Timestep!”, gafferongames.com. The practical treatment of fixed timesteps and integration.
4. E. Catto. “Soft Constraints: Reinventing the Spring.” Game Developers Conference, 2011. Why stiff systems and step size interact.
5. J.-M. Muller et al. Handbook of Floating-Point Arithmetic, 2nd ed. Birkhäuser, 2018. On which operations are specified exactly and which are not.