Deterministic Lockstep

Source: https://gafferongames.com/post/deterministic_lockstep/ Author: Glenn Fiedler | Date: 2014-11-29 | Series: Networked Physics

Definition

Network by sending only inputs that control the system, not object state. Bandwidth ∝ input size, not object count. Requires bit-identical determinism: same initial state + same inputs + same dt → identical checksum of physics state each frame.

Determinism hazards

ODE (example) used RNG in constraint order → non-determinism until seed tied to frame. Cross-compiler/OS/arch/debug-vs-release FP differences remain hard; no silver bullet (see Floating Point Determinism article).

Networking inputs

Sample an Input struct each simulation frame (only keys that affect sim). Right side may simulate frame n only when input n is available. Key-press events over TCP are wrong; need frame-indexed identical inputs.

Playout delay buffer

Buffer inputs briefly so they appear at a steady rate despite jitter (similar to video streaming). Cost = added latency. Simple impl: first input sets t0; deliver at t0+100ms. Cap catch-up (e.g. max 4 sim frames per render) to avoid spiral of death. Patents exist around "playout delay" terminology.

TCP is not good enough

Even with playout buffer, TCP loss → wait ~RTT*2 for retransmit → hitch because frame n cannot advance without input n. Worse at higher latency/loss.

Beat TCP for small inputs: redundant send

Include all unacked inputs in every UDP packet until ack. Inputs tiny (e.g. 6 bits). Worst-case RTT budget (e.g. 2s timeout) → ~120 inputs still small. Delta-encode consecutive inputs (1 bit same / 7 bits if changed). Receiver sends ack of most recent input received; sender discards older.

Result: never wait for retransmission of a single lost input packet. Works even at extreme latency/loss where TCP would stall constantly.

Player count note

Waiting for all players' inputs makes lockstep best for ~2–4 players; large counts amplify worst-peer wait.