1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
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.
|
