Rollback Netcode

in reviewThis lesson is complete and being validated before release - details may still change.

Rollback netcode

Loading interactive demo…

The grid is time: one row per frame, the start on top, the newest frame at the bottom, and the track across. P1 is you, on the left; P2 is the remote player, on the right; neither may pass the other. The strips beneath are your presses by frame, P2's presses as the session knows them, the saved states, and the tapped row. Tap a row to read its frame.Take the tour, or press and explore. Legend:

The panel beside the stage is the real RollbackSession class from the published library executing in your browser, with the current line highlighted.

P1, your player, and the frame under way.
P2 in a confirmed frame, and a press that has landed.
P2 in a frame resting on a guess, and the guessed press.
A wrong guess, the frames a rollback redoes, and a stalled frame.
A result a rollback replaced, kept faded, and presses still in flight.

confirmed through is the last frame with every frame before it confirmed; rollbacks counts wrong guesses found; resimulated counts the frames run a second time, and largest the deepest single rollback; stalls counts the wall frames the session waited instead of running a frame; saved counts the states held right now.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Lockstep. A server-authoritative game sends state: the server simulates, the clients draw what they are told. A lockstep game sends nothing but inputs. Both machines run the same simulation from the same start, and frame $f$ on each is a function of the two presses for frame $f$ . That only works if the simulation is deterministic, meaning the same inputs produce the same state on both machines, bit for bit: integer positions, a seeded random generator, no reliance on frame timing or on the order a hash map happens to iterate. The stage runs on integers for the same reason its trace must agree between a build server and your browser.

Waiting is the lag. The first lockstep games waited: a frame could not run until both presses were in hand, so every press, including your own, took a round trip to show. The remedy of the lockstep era was input delay, which Age of Empires wore openly, scheduling each command two turns ahead. With a delay $d$ and a one-way lag $L$ (both in frames), the remote press for frame $f$ is made at frame $f - d$ and lands at frame $f - d + L$ . It is in hand in time exactly when

d \ge L .

Set the delay slider to the lag and the trace has no predict at all. Every press, your own too, shows $d$ frames after you make it.

Guess instead. Rollback keeps the shared simulation and drops the wait. When frame $f$ is due and P2's press has not landed, the session guesses it, saves the state before the frame, and runs the frame. Human inputs are sticky, so the guess is the last press that landed, repeated, and most guesses are right: the stage's steady walk is wrong once. When the real press lands and matches, the frame is confirmed and its saved state freed; nothing on the screen moves. When it does not match, the session restores the saved state and runs every frame since with the truth. The number of frames a wrong guess reaches back is

\text{depth} = L - d ,

the frames that ran between the press being made and its landing. The delay slider shrinks it; at $d = L$ it is zero and rollback has become input delay.

What a rollback costs. A frame of the stage's game is two additions; a frame of a real game is collision, animation, and physics for every object. A rollback of depth $k$ runs $k$ frames in one, so the engine must simulate $k + 1$ frames in the time it has for one. That is why the window exists: a session will not let more than $w$ frames rest on guesses. Past the window it stalls, which is the freeze delay-based netcode shows all the time, now reserved for a bad connection. Shipping games set $w$ around seven or eight frames, and save state every frame because a save is a copy of a few kilobytes while a resimulation is real work.

Both players move. Look at the second rollback on the default script. The guess had P2 still walking toward you, so the two of you stood blocked nose to nose for three frames; the truth had P2 turn and run, so you both walk on. P1 jumps three cells in a single frame though your presses never changed. In a lockstep game there is no separate truth for the local player: every state is a function of both inputs, and a wrong guess about the other player rewrites your own past. This is the difference from the prediction lesson, where the server owned the truth and only your own entity was ever corrected.

The arc, closed. Snapshot interpolation drew remote players a little in the past and blended between real states. Client-side prediction applied your own presses at once and reconciled with the server's answer. Lag compensation let the server judge a shot in the past the shooter was looking at. Rollback is the case where no server holds the truth and both machines must agree frame by frame, so prediction and correction are applied to everyone. Across all four, the same two ideas recur: render or simulate from the best knowledge you have, and keep enough history to correct it when better knowledge lands. The distributed systems arc speaks the same language with different nouns: its logical clocks order events that no shared clock can, and its replicas, like these two machines, apply the same log of operations and diverge only when a message is late. Desync detection is where to read on: shipping rollback games exchange a checksum of the confirmed state every few frames, and a mismatch means the two simulations were never the same game, the bug Age of Empires spent its development hunting.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

run is a wall clock, not a game clock. It loops over wall frames and keeps a separate g, the next game frame to run, so a stall can let the wall advance while the game waits, and the run goes on past the last frame until every press has landed and every frame is confirmed.
arrive comes before advance in each wall frame, so a press landing now confirms or rolls back before the frame is run. That is why the depth of a rollback is lag - delay and not one more.
remoteInput is the one place a frame's state is saved. A known press frees any save the frame had; a guess saves the state before the frame and records the guess, whether the caller is advance running a new frame or rollback running one again. Confirming later means comparing the landed press with that record.
rollback runs the frames it redoes through the same simulate as a first run, with the real press where it is known and a fresh guess beyond, and reports how far the drawn positions moved. A real engine would also fast-forward animation and sound from the restored state, which is the hard part it leaves out.
simulate is the whole game, and it is deterministic: two clamps and one rule, that the players may not meet or cross, which holds both still. That rule is what makes a wrong guess about P2 change P1's outcome.
The guess repeats the last press that landed. Shipping libraries do the same, because a human holds a direction for many frames; a smarter guess buys little and costs a rollback whenever it is wrong.
Not here, by design: checksums of the confirmed state for desync detection, a frame-rate handshake so neither machine runs ahead, more than two players, and the visual smoothing that hides a rollback's jump.

Running one simulation on every machine and exchanging only the players' commands predates the internet shooter: Age of Empires did it in 1997, scheduling each command two turns ahead and halting when a checksum showed a machine had drifted. Waiting for the other side's input was what fighting-game players felt as lag. Tony Cannon's GGPO, released in late 2006, kept the shared simulation but stopped waiting: it guessed the remote input, ran the frame, and rolled back when the guess proved wrong. Licensed into games from 2010 and open-sourced in 2019, it is what the genre means by good netcode.

2001Paul Bettner - The Age of Empires networking article describes a synchronous simulation on every machine fed identical commands, each scheduled two 200 ms turns ahead, with checksums to catch a machine that falls out of sync.source
2006Tony Cannon - Releases GGPO, written after the online play of that year's Street Fighter II: Hyper Fighting re-release disappointed him; instead of waiting for the other player's input it predicts it and rolls back when wrong.source
2011Capcom - Street Fighter III: 3rd Strike Online Edition ships with GGPO's netcode, after Cannon demonstrated the middleware to the company.source
2012Reverge Labs - Skullgirls runs its ranked and unranked matches on a licensed GGPO, one of the first new fighting games built around rollback.source
2013Double Helix Games - Killer Instinct launches with GGPO-style rollback netcode developed with help from GGPO's creator.source
2019Tony Cannon - GGPO is released as open source under the MIT License on October 9, so any game can adopt rollback without a licence.source

Used today

Fighting games - Rollback is the expected netcode of the genre: one wrong frame costs a match, so inputs must apply the instant they are pressed.
Platform fighters and sports games - Any peer-to-peer game whose state is small enough to save every frame can predict the other side and roll back.
Deterministic strategy games - Real-time strategy games still run the shared simulation of the lockstep era, usually with input delay rather than rollback, since thousands of units are costly to resimulate.
Client-side prediction, generalized - A server-authoritative shooter predicts its own player; rollback predicts the other player too, which is why the two lessons share their vocabulary.

Did you know

GGPO stands for Good Game Peace Out. Its creator Tony Cannon also co-founded the Shoryuken community site and the Evolution Championship Series, the biggest fighting-game tournament.source
Before Age of Empires shipped, a Microsoft product manager predicted that out-of-sync would be its worst problem. He was right: very subtle differences between two machines' simulations multiplied over time, and the team checksummed the world, every object, and the pathfinding to find them.source
Fans have added rollback to games whose developers never did, among them Super Smash Bros. Melee and Touhou Hisoutensoku, by patching the game to save and restore its state every frame.source
A fan-created update to Skullgirls' netcode keeps two machines in step by omitting one frame in every seven, a resync trick rather than a longer wait.source

scenario

lag3 frames

delay0 frames

window6 frames

confirmed through: frame 13
rollbacks: 2
resimulated: 6 frames
largest: 3 frames
stalls: 0
saved: 0 states

rollback.ts

import type { Tracer } from "../trace";/** Cells on the one-dimensional track the two players share. */export const ROLLBACK_TRACK_LENGTH = 16;/** Where the local player starts; the remote player starts to its right and the two never pass. */export const ROLLBACK_P1_START = 3;export const ROLLBACK_P2_START = 12;/** Frames a remote input takes to arrive. */export const MAX_ROLLBACK_LAG = 6;/** Frames a press waits before it applies, on both machines. */export const MAX_INPUT_DELAY = 3;/** Frames the session will let rest on guesses before it stalls. */export const MAX_ROLLBACK_WINDOW = 8;export const MAX_ROLLBACK_FRAMES = 20;/** One frame's press: left, stay, or right. */export type RollbackInput = -1 | 0 | 1;export interface RollbackOptions {  /** Frames a remote input takes to reach this machine, 1 to MAX_ROLLBACK_LAG (default 3). */  lag?: number;  /** Frames a press waits before the frame it applies to, 0 to MAX_INPUT_DELAY (default 0). */  delay?: number;  /** Frames that may rest on guesses at once, 1 to MAX_ROLLBACK_WINDOW (default 6); past it the session stalls. */  window?: number;  /** Game frames to play, 1 to MAX_ROLLBACK_FRAMES (default 14). */  frames?: number;}/** The whole game state: two positions on the track. */export interface RollbackState {  p1: number;  p2: number;}export interface RollbackReport {  frames: number;  /** Wall-clock frames the run took, stalls included. */  wallFrames: number;  rollbacks: number;  /** Frames run a second time, over every rollback. */  resimulated: number;  largestRollback: number;  stalls: number;  /** The last frame with every frame before it confirmed, or -1. */  confirmedThrough: number;}/** * Rollback netcode, the way fighting games play over the internet: both * machines run the same deterministic game, and a frame needs both * players' inputs. The local press is at hand; the remote one is still * in flight, so the session guesses it (the last input it knows, * repeated), saves the state, and runs the frame anyway. When the real * input lands, a right guess confirms the frame and frees the saved * state; a wrong one rolls the game back to the state saved before that * frame and runs every frame since again with the truth, which can move * the local player too, because the two block each other. An input * delay on both sides shrinks how far a wrong guess reaches, and a * window caps how many frames may rest on guesses before the session * stalls and waits instead. * * Time: O(window) per wall frame, the frames a rollback can redo. * Space: O(window) saved states. */export class RollbackSession {  readonly lag: number;  readonly delay: number;  readonly window: number;  readonly frames: number;  private local: readonly RollbackInput[] = [];  private remote: readonly RollbackInput[] = [];  private state: RollbackState = { p1: ROLLBACK_P1_START, p2: ROLLBACK_P2_START };  /** Each simulated frame's result, by frame. */  private readonly results: RollbackState[] = [];  /** The state before each frame that rests on a guess, by frame. */  private readonly saved = new Map<number, RollbackState>();  /** The guess each unconfirmed frame ran on, by frame. */  private readonly guesses = new Map<number, RollbackInput>();  /** Remote inputs that have arrived, frame 0 first; they land in order. */  private readonly known: RollbackInput[] = [];  /** The next game frame to run. */  private g = 0;  private nextFrame = 0;  /** The wall-clock frame under way. */  private w = 0;  private clockFrame = 0;  private rollbacks = 0;  private resimulated = 0;  private largest = 0;  private stalls = 0;  constructor(options: RollbackOptions = {}, private readonly tracer?: Tracer) {    this.lag = RollbackSession.checkRange("lag", options.lag ?? 3, 1, MAX_ROLLBACK_LAG);    this.delay = RollbackSession.checkRange("delay", options.delay ?? 0, 0, MAX_INPUT_DELAY);    this.window = RollbackSession.checkRange("window", options.window ?? 6, 1, MAX_ROLLBACK_WINDOW);    this.frames = RollbackSession.checkRange("frames", options.frames ?? 14, 1, MAX_ROLLBACK_FRAMES);  }  /** The game: each player moves one cell, clamped to the track, and neither may meet or pass the other. */  static simulate(state: RollbackState, in1: RollbackInput, in2: RollbackInput): RollbackState {  static simulate(state: RollbackState, localPress: RollbackInput, remotePress: RollbackInput): RollbackState {    let p1 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p1 + in1));    let p1 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p1 + localPress));    let p2 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p2 + in2));    let p2 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p2 + remotePress));    if (p1 >= p2) {      p1 = state.p1;      p2 = state.p2;    }    return { p1, p2 };  }  /** The local press that applies to a frame: made `delay` frames earlier, so nothing before frame `delay`. */  localInput(frame: number): RollbackInput {    return frame < this.delay ? 0 : (this.local[frame - this.delay] ?? 0);  }  /** The wall frame at which the remote input for a frame lands here: pressed `delay` frames early, in flight for `lag`. */  arrivalOf(frame: number): number {    return frame - this.delay + this.lag;  }  /** Both players' presses by wall frame; a missing entry is stay. Runs to the end and until every frame is confirmed. */  run(local: readonly RollbackInput[], remote: readonly RollbackInput[]): RollbackReport {    this.local = RollbackSession.checkScript("local", local);    this.remote = RollbackSession.checkScript("remote", remote);    // Frames before the delay apply no press at all, so their inputs are known from the start.    for (let frame = 0; frame < Math.min(this.delay, this.frames); frame++) this.known.push(0);    const cap = this.frames + this.lag + this.window + 2;    for (this.w = 0; this.w < cap && (this.g < this.frames || this.guesses.size > 0); this.w++) {    for (this.clockFrame = 0; this.clockFrame < cap && (this.nextFrame < this.frames || this.guesses.size > 0); this.clockFrame++) {      this.arrive();      if (this.g < this.frames) this.advance();      if (this.nextFrame < this.frames) this.advance();    }    return this.report();  }  report(): RollbackReport {    const pending = [...this.guesses.keys()];    const confirmedThrough = pending.length === 0 ? this.g - 1 : Math.min(...pending) - 1;    const confirmedThrough = pending.length === 0 ? this.nextFrame - 1 : Math.min(...pending) - 1;    return {      frames: this.frames,      wallFrames: this.w,      wallFrames: this.clockFrame,      rollbacks: this.rollbacks,      resimulated: this.resimulated,      largestRollback: this.largest,      stalls: this.stalls,      confirmedThrough,    };  }  /** The remote input landing this wall frame, if one does: confirm the frame it was guessed for, or roll back. */  private arrive(): void {    const frame = this.known.length;    if (frame >= this.frames || frame < this.delay || this.arrivalOf(frame) !== this.w) return;    if (frame >= this.frames || frame < this.delay || this.arrivalOf(frame) !== this.clockFrame) return;    const input = this.remote[frame - this.delay] ?? 0;    this.known.push(input);    const guess = this.guesses.get(frame);    const guessed = guess !== undefined;    // ▸ a remote input lands, lag frames after it was pressed    this.tracer?.emit("receive", { wall: this.w, forFrame: frame, input, guessed, lateBy: guessed ? this.w - frame : 0 });    this.tracer?.emit("receive", { wall: this.clockFrame, forFrame: frame, input, guessed, lateBy: guessed ? this.clockFrame - frame : 0 });    if (!guessed) return;    if (guess === input) {      this.saved.delete(frame);      this.guesses.delete(frame);      // ▸ it matches the guess that frame ran on: the frame is confirmed and its saved state freed      this.tracer?.emit("confirm", { wall: this.w, forFrame: frame, input, pending: this.guesses.size });      this.tracer?.emit("confirm", { wall: this.clockFrame, forFrame: frame, input, pending: this.guesses.size });      return;    }    this.rollback(frame, guess, input);  }  /** Restore the state saved before the frame and run every frame since again, now with the real input. */  private rollback(frame: number, wrong: RollbackInput, actual: RollbackInput): void {    const depth = this.g - frame;    const depth = this.nextFrame - frame;    this.rollbacks++;    this.resimulated += depth;    this.largest = Math.max(this.largest, depth);    // ▸ it does not match: go back to the state saved before that frame    this.tracer?.emit("rollback", { wall: this.w, toFrame: frame, depth, wrong, actual });    this.tracer?.emit("rollback", { wall: this.clockFrame, toFrame: frame, depth, wrong, actual });    this.state = this.saved.get(frame)!;    for (let k = frame; k < this.g; k++) {    for (let redoFrame = frame; redoFrame < this.nextFrame; redoFrame++) {      const old = this.results[k]!;      const old = this.results[redoFrame]!;      const in1 = this.localInput(k);      const localPress = this.localInput(redoFrame);      const in2 = this.remoteInput(k);      const remotePress = this.remoteInput(redoFrame);      this.state = RollbackSession.simulate(this.state, in1, in2);      this.state = RollbackSession.simulate(this.state, localPress, remotePress);      this.results[k] = this.state;      this.results[redoFrame] = this.state;      const moved = Math.abs(this.state.p1 - old.p1) + Math.abs(this.state.p2 - old.p2);      // ▸ run every frame since then again, with the real input where it is known and new guesses beyond      this.tracer?.emit("resimulate", { wall: this.w, redo: k, in1, in2, guessed: this.guesses.has(k), p1: this.state.p1, p2: this.state.p2, oldP1: old.p1, oldP2: old.p2, moved });      this.tracer?.emit("resimulate", { wall: this.clockFrame, redo: redoFrame, localPress, remotePress, guessed: this.guesses.has(redoFrame), p1: this.state.p1, p2: this.state.p2, oldP1: old.p1, oldP2: old.p2, moved });    }  }  /** Run the next frame, on a guess if the remote input is still in flight, unless too many frames already rest on guesses. */  private advance(): void {    const frame = this.g;    const frame = this.nextFrame;    if (frame >= this.known.length && this.guesses.size >= this.window) {      this.stalls++;      // ▸ too many frames already rest on guesses: do not run this one, wait for the oldest input      this.tracer?.emit("stall", { wall: this.w, frame, waitingFor: Math.min(...this.guesses.keys()), pending: this.guesses.size });      this.tracer?.emit("stall", { wall: this.clockFrame, frame, waitingFor: Math.min(...this.guesses.keys()), pending: this.guesses.size });      return;    }    if (frame >= this.known.length) {      const basedOn = this.known.length - 1;      // ▸ the remote input for this frame has not landed, so guess it: the last one known, repeated      this.tracer?.emit("predict", { wall: this.w, frame, guess: this.lastKnown(), basedOn });      this.tracer?.emit("predict", { wall: this.clockFrame, frame, guess: this.lastKnown(), basedOn });    }    const in1 = this.localInput(frame);    const localPress = this.localInput(frame);    const in2 = this.remoteInput(frame);    const remotePress = this.remoteInput(frame);    this.state = RollbackSession.simulate(this.state, in1, in2);    this.state = RollbackSession.simulate(this.state, localPress, remotePress);    this.results[frame] = this.state;    this.g = frame + 1;    this.nextFrame = frame + 1;    // ▸ run the frame on whatever inputs we have; a guessed frame had its state saved first    this.tracer?.emit("frame", { wall: this.w, frame, in1, in2, guessed: this.guesses.has(frame), p1: this.state.p1, p2: this.state.p2 });    this.tracer?.emit("frame", { wall: this.clockFrame, frame, localPress, remotePress, guessed: this.guesses.has(frame), p1: this.state.p1, p2: this.state.p2 });  }  /** The remote input a frame runs on: the real one once it has landed, else a guess, with the state saved first. */  private remoteInput(frame: number): RollbackInput {    const known = this.known[frame];    if (known !== undefined) {      this.saved.delete(frame);      this.guesses.delete(frame);      return known;    }    const guess = this.lastKnown();    this.saved.set(frame, this.state);    this.guesses.set(frame, guess);    return guess;  }  /** The guess: the newest remote input that has landed, repeated; stay before any has. */  private lastKnown(): RollbackInput {    return this.known[this.known.length - 1] ?? 0;  }  private static checkRange(name: string, value: number, min: number, max: number): number {    if (!Number.isInteger(value) || value < min || value > max) throw new RangeError(`${name} must be an integer in [${min}, ${max}], got ${value}`);    return value;  }  private static checkScript(name: string, script: readonly RollbackInput[]): readonly RollbackInput[] {    if (script.length > MAX_ROLLBACK_FRAMES) throw new RangeError(`${name} script has ${script.length} presses, more than ${MAX_ROLLBACK_FRAMES}`);    for (const press of script) if (press !== -1 && press !== 0 && press !== 1) throw new RangeError(`${name} script holds ${press}; a press is -1, 0, or 1`);    return [...script];  }}

rollbacks =: 2
resimulated =: 6
stalls =: 0

14 frames in 17 wall frames: 2 rollbacks ran 6 frames again, the deepest 3 frames, and the session stalled 0 times. Confirmed through frame 13.

import type { Tracer } from "../trace";/** Cells on the one-dimensional track the two players share. */export const ROLLBACK_TRACK_LENGTH = 16;/** Where the local player starts; the remote player starts to its right and the two never pass. */export const ROLLBACK_P1_START = 3;export const ROLLBACK_P2_START = 12;/** Frames a remote input takes to arrive. */export const MAX_ROLLBACK_LAG = 6;/** Frames a press waits before it applies, on both machines. */export const MAX_INPUT_DELAY = 3;/** Frames the session will let rest on guesses before it stalls. */export const MAX_ROLLBACK_WINDOW = 8;export const MAX_ROLLBACK_FRAMES = 20;/** One frame's press: left, stay, or right. */export type RollbackInput = -1 | 0 | 1;export interface RollbackOptions { /** Frames a remote input takes to reach this machine, 1 to MAX_ROLLBACK_LAG (default 3). */ lag?: number; /** Frames a press waits before the frame it applies to, 0 to MAX_INPUT_DELAY (default 0). */ delay?: number; /** Frames that may rest on guesses at once, 1 to MAX_ROLLBACK_WINDOW (default 6); past it the session stalls. */ window?: number; /** Game frames to play, 1 to MAX_ROLLBACK_FRAMES (default 14). */ frames?: number;}/** The whole game state: two positions on the track. */export interface RollbackState { p1: number; p2: number;}export interface RollbackReport { frames: number; /** Wall-clock frames the run took, stalls included. */ wallFrames: number; rollbacks: number; /** Frames run a second time, over every rollback. */ resimulated: number; largestRollback: number; stalls: number; /** The last frame with every frame before it confirmed, or -1. */ confirmedThrough: number;}/** * Rollback netcode, the way fighting games play over the internet: both * machines run the same deterministic game, and a frame needs both * players' inputs. The local press is at hand; the remote one is still * in flight, so the session guesses it (the last input it knows, * repeated), saves the state, and runs the frame anyway. When the real * input lands, a right guess confirms the frame and frees the saved * state; a wrong one rolls the game back to the state saved before that * frame and runs every frame since again with the truth, which can move * the local player too, because the two block each other. An input * delay on both sides shrinks how far a wrong guess reaches, and a * window caps how many frames may rest on guesses before the session * stalls and waits instead. * * Time: O(window) per wall frame, the frames a rollback can redo. * Space: O(window) saved states. */export class RollbackSession { readonly lag: number; readonly delay: number; readonly window: number; readonly frames: number; private local: readonly RollbackInput[] = []; private remote: readonly RollbackInput[] = []; private state: RollbackState = { p1: ROLLBACK_P1_START, p2: ROLLBACK_P2_START }; /** Each simulated frame's result, by frame. */ private readonly results: RollbackState[] = []; /** The state before each frame that rests on a guess, by frame. */ private readonly saved = new Map<number, RollbackState>(); /** The guess each unconfirmed frame ran on, by frame. */ private readonly guesses = new Map<number, RollbackInput>(); /** Remote inputs that have arrived, frame 0 first; they land in order. */ private readonly known: RollbackInput[] = []; /** The next game frame to run. */ private g = 0; private nextFrame = 0; /** The wall-clock frame under way. */ private w = 0; private clockFrame = 0; private rollbacks = 0; private resimulated = 0; private largest = 0; private stalls = 0; constructor(options: RollbackOptions = {}, private readonly tracer?: Tracer) { this.lag = RollbackSession.checkRange("lag", options.lag ?? 3, 1, MAX_ROLLBACK_LAG); this.delay = RollbackSession.checkRange("delay", options.delay ?? 0, 0, MAX_INPUT_DELAY); this.window = RollbackSession.checkRange("window", options.window ?? 6, 1, MAX_ROLLBACK_WINDOW); this.frames = RollbackSession.checkRange("frames", options.frames ?? 14, 1, MAX_ROLLBACK_FRAMES); } /** The game: each player moves one cell, clamped to the track, and neither may meet or pass the other. */ static simulate(state: RollbackState, in1: RollbackInput, in2: RollbackInput): RollbackState { static simulate(state: RollbackState, localPress: RollbackInput, remotePress: RollbackInput): RollbackState { let p1 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p1 + in1)); let p1 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p1 + localPress)); let p2 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p2 + in2)); let p2 = Math.min(ROLLBACK_TRACK_LENGTH - 1, Math.max(0, state.p2 + remotePress)); if (p1 >= p2) { p1 = state.p1; p2 = state.p2; } return { p1, p2 }; } /** The local press that applies to a frame: made `delay` frames earlier, so nothing before frame `delay`. */ localInput(frame: number): RollbackInput { return frame < this.delay ? 0 : (this.local[frame - this.delay] ?? 0); } /** The wall frame at which the remote input for a frame lands here: pressed `delay` frames early, in flight for `lag`. */ arrivalOf(frame: number): number { return frame - this.delay + this.lag; } /** Both players' presses by wall frame; a missing entry is stay. Runs to the end and until every frame is confirmed. */ run(local: readonly RollbackInput[], remote: readonly RollbackInput[]): RollbackReport { this.local = RollbackSession.checkScript("local", local); this.remote = RollbackSession.checkScript("remote", remote); // Frames before the delay apply no press at all, so their inputs are known from the start. for (let frame = 0; frame < Math.min(this.delay, this.frames); frame++) this.known.push(0); const cap = this.frames + this.lag + this.window + 2; for (this.w = 0; this.w < cap && (this.g < this.frames || this.guesses.size > 0); this.w++) { for (this.clockFrame = 0; this.clockFrame < cap && (this.nextFrame < this.frames || this.guesses.size > 0); this.clockFrame++) { this.arrive(); if (this.g < this.frames) this.advance(); if (this.nextFrame < this.frames) this.advance(); } return this.report(); } report(): RollbackReport { const pending = [...this.guesses.keys()]; const confirmedThrough = pending.length === 0 ? this.g - 1 : Math.min(...pending) - 1; const confirmedThrough = pending.length === 0 ? this.nextFrame - 1 : Math.min(...pending) - 1; return { frames: this.frames, wallFrames: this.w, wallFrames: this.clockFrame, rollbacks: this.rollbacks, resimulated: this.resimulated, largestRollback: this.largest, stalls: this.stalls, confirmedThrough, }; } /** The remote input landing this wall frame, if one does: confirm the frame it was guessed for, or roll back. */ private arrive(): void { const frame = this.known.length; if (frame >= this.frames || frame < this.delay || this.arrivalOf(frame) !== this.w) return; if (frame >= this.frames || frame < this.delay || this.arrivalOf(frame) !== this.clockFrame) return; const input = this.remote[frame - this.delay] ?? 0; this.known.push(input); const guess = this.guesses.get(frame); const guessed = guess !== undefined; // ▸ a remote input lands, lag frames after it was pressed this.tracer?.emit("receive", { wall: this.w, forFrame: frame, input, guessed, lateBy: guessed ? this.w - frame : 0 }); this.tracer?.emit("receive", { wall: this.clockFrame, forFrame: frame, input, guessed, lateBy: guessed ? this.clockFrame - frame : 0 }); if (!guessed) return; if (guess === input) { this.saved.delete(frame); this.guesses.delete(frame); // ▸ it matches the guess that frame ran on: the frame is confirmed and its saved state freed this.tracer?.emit("confirm", { wall: this.w, forFrame: frame, input, pending: this.guesses.size }); this.tracer?.emit("confirm", { wall: this.clockFrame, forFrame: frame, input, pending: this.guesses.size }); return; } this.rollback(frame, guess, input); } /** Restore the state saved before the frame and run every frame since again, now with the real input. */ private rollback(frame: number, wrong: RollbackInput, actual: RollbackInput): void { const depth = this.g - frame; const depth = this.nextFrame - frame; this.rollbacks++; this.resimulated += depth; this.largest = Math.max(this.largest, depth); // ▸ it does not match: go back to the state saved before that frame this.tracer?.emit("rollback", { wall: this.w, toFrame: frame, depth, wrong, actual }); this.tracer?.emit("rollback", { wall: this.clockFrame, toFrame: frame, depth, wrong, actual }); this.state = this.saved.get(frame)!; for (let k = frame; k < this.g; k++) { for (let redoFrame = frame; redoFrame < this.nextFrame; redoFrame++) { const old = this.results[k]!; const old = this.results[redoFrame]!; const in1 = this.localInput(k); const localPress = this.localInput(redoFrame); const in2 = this.remoteInput(k); const remotePress = this.remoteInput(redoFrame); this.state = RollbackSession.simulate(this.state, in1, in2); this.state = RollbackSession.simulate(this.state, localPress, remotePress); this.results[k] = this.state; this.results[redoFrame] = this.state; const moved = Math.abs(this.state.p1 - old.p1) + Math.abs(this.state.p2 - old.p2); // ▸ run every frame since then again, with the real input where it is known and new guesses beyond this.tracer?.emit("resimulate", { wall: this.w, redo: k, in1, in2, guessed: this.guesses.has(k), p1: this.state.p1, p2: this.state.p2, oldP1: old.p1, oldP2: old.p2, moved }); this.tracer?.emit("resimulate", { wall: this.clockFrame, redo: redoFrame, localPress, remotePress, guessed: this.guesses.has(redoFrame), p1: this.state.p1, p2: this.state.p2, oldP1: old.p1, oldP2: old.p2, moved }); } } /** Run the next frame, on a guess if the remote input is still in flight, unless too many frames already rest on guesses. */ private advance(): void { const frame = this.g; const frame = this.nextFrame; if (frame >= this.known.length && this.guesses.size >= this.window) { this.stalls++; // ▸ too many frames already rest on guesses: do not run this one, wait for the oldest input this.tracer?.emit("stall", { wall: this.w, frame, waitingFor: Math.min(...this.guesses.keys()), pending: this.guesses.size }); this.tracer?.emit("stall", { wall: this.clockFrame, frame, waitingFor: Math.min(...this.guesses.keys()), pending: this.guesses.size }); return; } if (frame >= this.known.length) { const basedOn = this.known.length - 1; // ▸ the remote input for this frame has not landed, so guess it: the last one known, repeated this.tracer?.emit("predict", { wall: this.w, frame, guess: this.lastKnown(), basedOn }); this.tracer?.emit("predict", { wall: this.clockFrame, frame, guess: this.lastKnown(), basedOn }); } const in1 = this.localInput(frame); const localPress = this.localInput(frame); const in2 = this.remoteInput(frame); const remotePress = this.remoteInput(frame); this.state = RollbackSession.simulate(this.state, in1, in2); this.state = RollbackSession.simulate(this.state, localPress, remotePress); this.results[frame] = this.state; this.g = frame + 1; this.nextFrame = frame + 1; // ▸ run the frame on whatever inputs we have; a guessed frame had its state saved first this.tracer?.emit("frame", { wall: this.w, frame, in1, in2, guessed: this.guesses.has(frame), p1: this.state.p1, p2: this.state.p2 }); this.tracer?.emit("frame", { wall: this.clockFrame, frame, localPress, remotePress, guessed: this.guesses.has(frame), p1: this.state.p1, p2: this.state.p2 }); } /** The remote input a frame runs on: the real one once it has landed, else a guess, with the state saved first. */ private remoteInput(frame: number): RollbackInput { const known = this.known[frame]; if (known !== undefined) { this.saved.delete(frame); this.guesses.delete(frame); return known; } const guess = this.lastKnown(); this.saved.set(frame, this.state); this.guesses.set(frame, guess); return guess; } /** The guess: the newest remote input that has landed, repeated; stay before any has. */ private lastKnown(): RollbackInput { return this.known[this.known.length - 1] ?? 0; } private static checkRange(name: string, value: number, min: number, max: number): number { if (!Number.isInteger(value) || value < min || value > max) throw new RangeError(`${name} must be an integer in [${min}, ${max}], got ${value}`); return value; } private static checkScript(name: string, script: readonly RollbackInput[]): readonly RollbackInput[] { if (script.length > MAX_ROLLBACK_FRAMES) throw new RangeError(`${name} script has ${script.length} presses, more than ${MAX_ROLLBACK_FRAMES}`); for (const press of script) if (press !== -1 && press !== 0 && press !== 1) throw new RangeError(`${name} script holds ${press}; a press is -1, 0, or 1`); return [...script]; }}