diff options
Diffstat (limited to 'research')
| -rw-r--r-- | research/deterministic-physics.org | 114 | ||||
| -rw-r--r-- | research/tech-stack.org | 10 |
2 files changed, 123 insertions, 1 deletions
diff --git a/research/deterministic-physics.org b/research/deterministic-physics.org new file mode 100644 index 0000000..66cb489 --- /dev/null +++ b/research/deterministic-physics.org @@ -0,0 +1,114 @@ +#+TITLE: Deterministic Physics Plan +#+DATE: 2026-07-17 +#+OPTIONS: toc:2 num:t + +* Why this document + +Lockstep multiplayer (the Forts model) requires that every peer's simulation +produces bit-identical results from the same inputs. Our simulation is the +custom stiff mass-spring solver in =src/game/build_graph.cpp=, not Box2D. Box2D +v3 is linked but idle, so its cross-platform determinism does not help us: the +code that decides who wins is the mass-spring solver, and it currently calls +=sin/cos/atan2= and mixes float widths, so it is not deterministic across builds +or platforms. + +This plan makes the mass-spring solver deterministic. It supersedes the +Box2D-based framing under "Deterministic Simulation Design" in +=research/tech-stack.org=. + +* Decision: strict IEEE-754 float, not fixed-point + +Keep the float solver and make it reproducible by controlling the compiler and +owning the transcendental functions. This is the approach Box2D v3 and Factorio +take. It needs no rewrite and does not disturb the tuned constants. + +** Rejected: fixed-point / integer math + +Bulletproof by construction, but a full rewrite of the solver and a poor fit for +a stiff damped spring system: 14 substeps of accumulation and a large dynamic +range between rest and impact forces make precision and overflow hard to manage. +Hold it in reserve; adopt only if strict-float fails cross-platform testing. + +** Rejected: rollback as a substitute + +GGPO-style rollback replays inputs through the simulation, so it *requires* +determinism rather than providing it. It is a netcode feature layered on top of +this plan, not an alternative to it. + +* Sources of float divergence, and how each is closed + +1. FMA contraction (=a*b+c= fused to a single rounding). Disable with + =-ffp-contract=off=. +2. =-ffast-math= / reassociation. Never enable on the simulation code. +3. Transcendentals (=sin=, =cos=, =atan2=, =exp=). Not required to be correctly + rounded by IEEE-754, so libm differs across OS and libc versions. Replace the + ones used in the sim with our own implementations, compiled identically + everywhere. Box2D v3's MIT =b2Atan2/b2Sin/b2Cos= are a ready source. + +=sqrt= is safe to keep: hardware =sqrtss/sqrtsd= is correctly rounded per +IEEE-754 and portable. + +* The plan + +** 1. Isolate the tick as a pure step + +The simulation step must read no wall clock, allocate nothing, touch no global +mutable state, and iterate in a fixed order. We are mostly there: fixed 60 Hz, +fixed =OVERSAMPLES=, node and edge arrays walked in index order. Audit for two +leaks: +- any =std::unordered_map= iterated inside the tick (iteration order is + unspecified), +- any RNG not driven by a seeded PCG shared across peers (fire spread?). + +=rand()= and hash-map iteration order are the classic desync sources. + +** 2. Pin the FP flags on the simulation translation units + +Scope =-ffp-contract=off=, no =-ffast-math=, and SSE2 (the x86-64 default) to +=build_graph.cpp= in =meson.build=, so the rest of the engine is unaffected. We +build in the container, so the flags are controlled for every shipped build. + +** 3. Own the transcendentals (cross-platform only) + +Replace =std::sin/cos/atan2= in the solver (strut angles, the 30 degree +angle-stress rule) with fixed implementations; keep =sqrt=. This is the step +that buys cross-platform determinism, and the only expensive one. + +** 4. One float width, no mixing + +Doubles are as deterministic as floats under strict FP and give headroom for the +stiff springs; floats match Box2D and Forts and halve the memory. Pick one and +never mix. Given the stiffness, prefer =double= for the solver unless a SIMD or +cache reason argues otherwise. Consistency, not width, is what determinism +needs. + +** 5. Determinism harness (do this first) + +A test target that runs a fixed scenario (a small fort, a scripted shot) for N +ticks and hashes the state: node positions and velocities, edge and fire flags. +Run it in CI in the container so a regression trips immediately. The real +payoff: run the same hash on a native host build and compare against the +container build. Matching hashes mean cross-platform determinism is real, not +assumed. + +* The scoping decision that sets the workload + +What is the multiplayer matrix? + +- *Same-binary only* (per-platform builds, never a Linux host against a Windows + host in one match): same-binary determinism suffices. Steps 1, 2, 4 and 5 + almost certainly clear it, and step 3 can be deferred entirely. +- *Cross-platform* (different platform builds in one lockstep match): step 3 + (own the transcendentals) becomes mandatory. + +* Sequencing + +- Now, while building M4/M5: adopt steps 1, 2, 4 and 5. They are cheap and stop + us digging the hole deeper. Build the harness (step 5) first, as the safety + net. +- Later, when committing to cross-platform matches: flip on step 3. +- Keep Box2D idle until projectiles need it; its determinism story then lines up + with this one. +- Threading: keep the solver single-threaded, or use a deterministic reduction + order if it is ever parallelised. Non-deterministic reduction order breaks + bit-identity. diff --git a/research/tech-stack.org b/research/tech-stack.org index ce0a9c1..3e43e44 100644 --- a/research/tech-stack.org +++ b/research/tech-stack.org @@ -436,6 +436,12 @@ my_mod/ * Deterministic Simulation Design +NOTE: the authoritative plan is =research/deterministic-physics.org=. The +section below predates the custom solver and assumes Box2D owns the simulation. +It does not: the game is decided by the mass-spring solver in +=src/game/build_graph.cpp=, and Box2D is idle. The determinism work targets that +solver (strict IEEE-754 float, owned transcendentals), not Box2D. + For lockstep multiplayer, the simulation must be exactly identical on all machines. @@ -474,7 +480,9 @@ Projects to study during development: * Open Questions -- [ ] Fixed-point math fallback vs trusting Box2D v3 determinism +- [X] Fixed-point math fallback vs trusting Box2D v3 determinism — resolved: + strict IEEE-754 float on the custom solver, fixed-point held in reserve. See + =research/deterministic-physics.org=. - [ ] Exact rope simulation approach within Box2D (distance joints? soft constraints? custom spring?) - [ ] Fire propagation model (graph traversal along connected flammable |