Parties of more than two
Open the live demo · Read the source · View on GitHub
Rollback works the same way with four players as with two. Every machine
runs every step at once on every player's input. Its own input is known.
The others are guessed from the last input that came from each of them.
When a real input arrives and the guess was wrong, the machine goes back to
the step the guess was made on and runs forward again. With more than two
machines, a correction about one player has to leave the guesses about the
others as they were. RollbackSession in flutter3d_net does this for
two to thirty-two players. PeerWire.party carries each message to every
other machine with the sender's slot. PartyTape and PartyTapeWatcher let
someone watch without playing.
On this page five lanes stand side by side. The first four are four machines, each drawing the game as it currently believes it is, and the fifth is a spectator. Messages arrive four steps late and a tenth are lost. When a ball jumps, that machine has just corrected a wrong guess. Steps late changes how late the messages are, and its label counts the steps rerun so far.
Step 1: A game worth guessing wrong about #
The state is how far round the track each player is, in whole centimetres. Each step moves every player by its own input. The first player is also dragged by the last player's position, so a wrong guess about the last player moves the first one as well. The inputs change nearly every step, which means the guesses are often wrong.
/// The whole game: how far round the track each player is, in centimetres.
/// Each step moves every player by its own frame, and drags the first one
/// by the last one's position, so a wrong guess about anybody moves
/// somebody else too.
List<int> _step(List<int> at, Map<int, Map<String, Object?>> frames) {
final next = List<int>.of(at);
for (final MapEntry(:key, :value) in frames.entries) {
next[key] += (value['dx'] as int?) ?? 0;
}
next[0] += next.last % 3;
return next;
}
/// What machine [slot] presses at its [n]th step: changing often, so that
/// guessing it from the last one is often wrong.
int _press(int slot, int n) => 2 + (n * 7 + slot * 13) % 5;
Step 2: Four machines and a spectator on one wire #
LoopbackParty is the wire a test uses for a party: one process, messages
delivered a set number of ticks late, unreliable ones dropped at a set rate,
and the same messages lost for the same seed. Over a network the same
objects sit on PartyWire.over a relay's party room. Each machine gets a
PartyRollback with its slot, two steps of input delay, and a window of
twelve steps it can roll back through. The host, slot 0, hands each step
that leaves the window to a PartyTape. The fifth slot takes no part in
the rollback. It is a PartyTapeWatcher that only plays what the host
sends.
_Party({required int delay, required double loss, required int seed})
: wire = LoopbackParty(
_players + 1,
delaySteps: delay,
lossRate: loss,
seed: seed,
) {
tape = PartyTape<List<int>>(wire: wire.wire(0), encode: (s) => s);
for (var slot = 0; slot < _players; slot++) {
var captures = 0;
machines.add(
RollbackSession<List<int>>(
wire: wire.wire(slot),
players: _players,
inputDelay: 2,
maxRollbackFrames: 12,
captureLocalFrame: () => <String, Object?>{
'dx': pressing ? _press(slot, captures++) : 0,
},
applyAndStep: (step) =>
states[slot] = _step(states[slot], step.frames),
save: () => List<int>.of(states[slot]),
restore: (state) => states[slot] = List<int>.of(state),
// The host hands what settles to the tape, and hears who watches.
onSettled: (s) {
settled[slot][s.step + 1] = s.after;
if (slot == 0) tape.settled(s);
},
onMessage: slot == 0 ? tape.hear : null,
),
);
}
// The fifth slot plays no part in the rollback: it only watches.
watcher = PartyTapeWatcher<List<int>>(
wire: wire.wire(_players),
decode: (encoded) => List<int>.from(encoded! as List<Object?>),
restore: (state) => watched = state,
applyAndStep: (step) => watched = _step(watched, step.frames),
);
}
Step 3: One tick #
A tick advances every machine one step: it captures this machine's input, sends it with the last few inputs again in case some were lost, and runs the step. After a while the spectator arrives and asks to watch. The host sends it the last settled state, then every settled step after that. Then the wire delivers whatever is due.
/// One step on every machine, the spectator's turn after a while, and
/// then whatever the wire has due arrives.
void tick() {
for (final machine in machines) {
machine.stepOnce();
}
if (ticks >= 40) {
watcher
..ask()
..step();
}
wire.step();
ticks++;
}
Step 4: What has to hold #
The test plays the same party for four seconds, then everybody lets go of the controls and the wire gets forty more steps to catch up. Guesses have to have been wrong at least once, or the test would prove nothing. The four machines have to end on one state digest, and it has to be the digest of the same game played on a wire that is never late and never loses anything. Any step two machines both settled has to have been settled the same. The spectator, who came in late, has to be exactly where the players settled at the step it has reached.
// Four seconds of play four steps late, a tenth of the messages lost;
// then everybody lets go, and the wire is given time to catch up.
final party = _Party(delay: 4, loss: 0.1, seed: 5);
for (var i = 0; i < 240; i++) {
party.tick();
}
party.pressing = false;
for (var i = 0; i < 40; i++) {
party.tick();
}
final int reruns = party.machines.fold(0, (a, m) => a + m.stepsRerun);
if (reruns == 0) throw StateError('no guess was ever wrong');
final Set<int> digests = <int>{
for (final List<int> state in party.states) StateDigest.of(state),
};
if (digests.length != 1) {
throw StateError('the four machines ended on $digests');
}
// And that one is the game played on a wire that is never late and
// never loses anything.
final perfect = _Party(delay: 0, loss: 0.0, seed: 5);
for (var i = 0; i < 280; i++) {
if (i == 240) perfect.pressing = false;
perfect.tick();
}
if (StateDigest.of(perfect.states[0]) != digests.single) {
throw StateError('the four agree on something that never happened');
}
// Every step any two machines settled, they settled the same.
for (final MapEntry(key: step, value: state) in party.settled[0].entries) {
for (var slot = 1; slot < _players; slot++) {
final List<int>? other = party.settled[slot][step];
if (other != null && StateDigest.of(other) != StateDigest.of(state)) {
throw StateError('slot $slot settled step $step differently');
}
}
}
// The spectator, who came late, is where the players settled.
final int? next = party.watcher.next;
final List<int>? truth = next == null ? null : party.settled[0][next];
if (truth == null ||
StateDigest.of(party.watched) != StateDigest.of(truth)) {
throw StateError('the spectator is not on the settled tape');
}
Note. Rollback costs a full re-run of every step since the wrong guess, on every machine, and the cost grows with the number of players and how late their inputs are. At ten steps late this page reruns about twenty-four thousand steps in its first four seconds. Past what the window holds, a late input can no longer correct anything. For a party too large to roll back,
AuthorityServerandPredictingClientuse the other model, with one machine running the game for everybody. The relay hands out slots and matches strangers first come, first seated, with no skill rating and no region.