Architecting Zero-Desync Deterministic Physics in Lockstep Multiplayer Engines

The problem of maintaining strict deterministic state across disparate hardware architectures remains one of the most notoriously difficult engineering challenges in multiplayer game development. Lockstep networking architectures—where only player inputs are transmitted and the simulation is deterministically advanced on all clients—offer massive bandwidth savings and inherent anti-cheat properties. However, a single floating-point divergence, a single uninitialized variable, or a single non-deterministic iteration order in a physics solver will butterfly-effect into a catastrophic state desynchronization (desync).

In this research note, I detail a comprehensive architecture for achieving 100% strict determinism in a rigid-body physics engine, moving beyond the trivial “just use fixed-point math” advice, and diving into SIMD-accelerated deterministic solvers, floating-point environment (fenv) control, and collision manifold consistency.

The Illusion of Floating-Point Determinism

The IEEE-754 standard for floating-point arithmetic dictates how arithmetic operations should be performed. In a naive view, A * B + C should yield the same result everywhere. In reality, the hardware implementation of these operations destroys determinism.

FMA (Fused Multiply-Add): Modern CPUs (x86_64 AVX, ARM NEON) fuse multiplication and addition into a single instruction (a * b + c). This operation executes with infinite intermediate precision before rounding. If one machine supports FMA and another does not, or if a compiler optimizes FMA differently based on target architecture, the final rounded result will differ by 1 ULP (Unit in the Last Place).
Transcendental Functions: Functions like sin(), cos(), and sqrt() are implemented via microcode or OS-level software libraries (libm). The polynomial approximations used vary wildly between glibc, MSVC, and Apple’s Accelerate framework.
x87 FPU vs SSE/AVX: Legacy x87 instructions compute with 80-bit internal precision, whereas SSE computes with 32-bit or 64-bit precision. A register spill to memory will truncate the 80-bit value to 64-bit, introducing compiler-driven non-determinism.

The Standard Solution: Soft-Float and Fixed-Point

The standard industry approach is to abandon hardware floating-point entirely in favor of software-emulated floats (soft-float) or fixed-point arithmetic (Q16.16 or Q32.32). Fixed-point math maps real numbers to integers, leveraging deterministic integer ALUs.

However, fixed-point math traditionally sacrifices performance. A vector dot product in fixed-point requires 64-bit intermediate multiplication and bit-shifting, which prevents auto-vectorization by modern compilers.

SIMD-Accelerated Fixed-Point Math

To achieve physics simulation at 120Hz with thousands of rigid bodies, we must vectorize fixed-point operations. Here is a custom implementation of a Q16.16 fixed-point vector utilizing AVX2 intrinsics to perform 8 simultaneous additions and multiplications.

#include <immintrin.h>
#include <cstdint>

// Q16.16 fixed-point SIMD wrapper
struct FixedVector8 {
    __m256i data;

    // Load 8 32-bit integers representing Q16.16 values
    inline void load(const int32_t* ptr) {
        data = _mm256_loadu_si256((const __m256i*)ptr);
    }

    // SIMD Addition: Integer addition is inherently deterministic
    inline FixedVector8 operator+(const FixedVector8& other) const {
        FixedVector8 res;
        res.data = _mm256_add_epi32(data, other.data);
        return res;
    }

    // SIMD Multiplication for Q16.16 requires widening to 64-bit, 
    // multiplying, shifting right by 16, and narrowing back to 32-bit.
    // AVX2 does not have a direct 32x32->64 multiplier that returns all 64 bits easily,
    // so we interleave and use _mm256_mul_epi32 (which multiplies even elements).
    inline FixedVector8 operator*(const FixedVector8& other) const {
        // Multiply even elements
        __m256i mul_even = _mm256_mul_epi32(data, other.data);
        // Shift right by fractional bits (16)
        mul_even = _mm256_srli_epi64(mul_even, 16);

        // Shift data to multiply odd elements
        __m256i odd1 = _mm256_srli_epi64(data, 32);
        __m256i odd2 = _mm256_srli_epi64(other.data, 32);
        __m256i mul_odd = _mm256_mul_epi32(odd1, odd2);
        
        // Shift right by 16, but shift left by 32 to place it back in the high 32 bits
        mul_odd = _mm256_srli_epi64(mul_odd, 16);
        mul_odd = _mm256_slli_epi64(mul_odd, 32);

        // Blend the results back into a 32-bit vector
        FixedVector8 res;
        res.data = _mm256_blend_epi32(mul_even, mul_odd, 0xAA); // 10101010
        return res;
    }
};

This SIMD structure guarantees bit-exact results across any CPU that supports AVX2 (Intel or AMD), bypassing the FPU entirely while maintaining massive data throughput for collision broad-phase culling.

Deterministic Broad-Phase and Narrow-Phase Collision

The Broad-Phase Problem

In physics engines, the broad-phase pairs objects that might be colliding. Bounding Volume Hierarchies (BVH) or Dynamic AABB Trees are common. However, inserting objects into a BVH tree often depends on the exact memory address (pointer) of the object, or the exact order of insertion.

Memory allocation in modern OSs (via ASLR) is randomized. If you sort collision pairs based on pointer addresses, Machine A and Machine B will resolve collisions in different orders.

Solution: Objects must be assigned a globally synchronized, monotonic EntityID. All collision pairs must be sorted strictly by EntityID before being passed to the solver.

struct CollisionPair {
    uint32_t entityA;
    uint32_t entityB;
    
    // Sort deterministically
    bool operator<(const CollisionPair& other) const {
        if (entityA != other.entityA) return entityA < other.entityA;
        return entityB < other.entityB;
    }
};

// ... inside the physics tick ...
std::vector<CollisionPair> activePairs = broadPhase.getPairs();
std::sort(activePairs.begin(), activePairs.end()); // Crucial for determinism!

The Narrow-Phase: SAT and GJK/EPA

The narrow-phase determines the exact contact points. The Gilbert-Johnson-Keerthi (GJK) algorithm and Expanding Polytope Algorithm (EPA) are notoriously difficult to implement in fixed-point due to their iterative nature and reliance on normalization and cross-products.

EPA, specifically, requires finding the closest triangle on a Minkowski Difference polytope. If the cross-product normal vectors are slightly inexact due to fixed-point rounding, EPA can get trapped in an infinite loop or select the wrong face.

Deterministic GJK/EPA Architecture:

Fallback to SAT: For simple primitives (Box-Box, Box-Sphere), abandon GJK and use the Separating Axis Theorem (SAT). SAT involves only dot products and projections, which are algebraically stable in fixed-point.
Bounded Iterations: If GJK must be used for complex convex hulls, the while loop MUST have a hard-coded maximum iteration count (e.g., 32 iterations). If it hits the limit, it deterministically exits and returns the best approximation so far.

Lockstep State Architecture

A deterministic physics engine is useless without a lockstep networking model. The architecture requires a clear separation between the “Simulation State” and the “Presentation State”.

sequenceDiagram
    participant Client A
    participant Server (Relay)
    participant Client B
    
    Client A->>Server: Frame 100 Input (Move Right)
    Client B->>Server: Frame 100 Input (Move Left)
    
    Server->>Client A: Broadcast Frame 100 Inputs
    Server->>Client B: Broadcast Frame 100 Inputs
    
    Note over Client A, Client B: Clients wait until ALL inputs for Frame 100 arrive
    
    Note over Client A: Physics Tick 100 executes<br/>StateHash: 0xA1B2
    Note over Client B: Physics Tick 100 executes<br/>StateHash: 0xA1B2
    
    Client A->>Server: Validate Hash(0xA1B2)
    Client B->>Server: Validate Hash(0xA1B2)

State Serialization and Hashing

To detect desyncs immediately, the entire physics state must be hashed at the end of every tick. This requires the physics engine memory layout to be tightly packed, preferably using Data-Oriented Design (DoD) via Arrays of Structs of Arrays (AoSoA).

struct PhysicsWorldState {
    FixedVector8 positions[MAX_ENTITIES / 8];
    FixedVector8 velocities[MAX_ENTITIES / 8];
    uint32_t entityFlags[MAX_ENTITIES];
    
    uint64_t computeHash() const {
        // Fast, deterministic hashing (e.g., MurmurHash3 or CityHash)
        return MurmurHash3_x64_128(this, sizeof(PhysicsWorldState), 0x9E3779B9);
    }
};

By ensuring that PhysicsWorldState contains no pointers, no padding (via #pragma pack(push, 1) if necessary), and no hidden vtables, the hash computation is simply a bulk memory read. If Client A and Client B hash their memory arrays and differ by even a single bit, the desync is instantly caught, and Client B can request a full memory state payload from the server to rollback and correct.

Conclusion

Architecting a deterministic physics engine for lockstep multiplayer requires paranoia at every level of the stack. By replacing floating-point operations with SIMD-accelerated fixed-point math, rigorously sorting all physics interactions by monotonic IDs to defeat ASLR variance, and enforcing strict memory layouts for bulk state hashing, true cross-platform determinism is achievable. This allows games with tens of thousands of dynamic physics objects to run over the network utilizing almost zero bandwidth.