← How a game is made: Daily Challenge's Snake · Lesson 16/16

Lockstep: everyone sees the same game

1/9

The naive way: everyone applies what reaches them

Picture two phones. Each applies its own buttons instantly and the other's when they arrive. The trouble is they arrive late, and not equally late: phone A applies B's button two ticks after B pressed it, and B applies A's three ticks after. Each simulates a slightly different game and, since in Snake one tick is the difference between crashing or not, soon they're two different games.

Run the program: the same game, the same buttons, only when they're applied changes.

leccion.js

1class Juego {
2  constructor(n) { this.pos = Array(n).fill(0); this.puntos = Array(n).fill(0); this.tick = 0; }
3  update(masks) {
4    this.tick++;
5    masks.forEach((m, i) => {
6      if (m & 8) this.pos[i]++;                       // right
7      if (m & 4) this.pos[i]--;                       // left
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A on a coin
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// What each player presses on each tick (a fixed rule, so it can be repeated)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17// Each phone sees its own button instantly and the other's with a delay
18function phone(yo, retrasoDelOtro) {
19  const g = new Juego(2);
20  for (let t = 0; t < 30; t++) {
21    const masks = [0, 0];
22    masks[yo] = aprieta(yo, t);
23    const otro = 1 - yo;
24    if (t - retrasoDelOtro >= 0) masks[otro] = aprieta(otro, t - retrasoDelOtro);
25    g.update(masks);
26  }
27  return g.huella();
28}
29
30console.log("phone A:", phone(0, 2));
31console.log("phone B:", phone(1, 3));

class Juego {
  constructor(n) { this.pos = Array(n).fill(0); this.puntos = Array(n).fill(0); this.tick = 0; }
  update(masks) {
    this.tick++;
    masks.forEach((m, i) => {
      if (m & 8) this.pos[i]++;                       // right
      if (m & 4) this.pos[i]--;                       // left
      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A on a coin
    });
  }
  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
}

// What each player presses on each tick (a fixed rule, so it can be repeated)
const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];

// Each phone sees its own button instantly and the other's with a delay
function phone(yo, retrasoDelOtro) {
  const g = new Juego(2);
  for (let t = 0; t < 30; t++) {
    const masks = [0, 0];
    masks[yo] = aprieta(yo, t);
    const otro = 1 - yo;
    if (t - retrasoDelOtro >= 0) masks[otro] = aprieta(otro, t - retrasoDelOtro);
    g.update(masks);
  }
  return g.huella();
}

console.log("phone A:", phone(0, 2));
console.log("phone B:", phone(1, 3));

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The fingerprint is tick | positions | points. The two differ: each phone believes in a different game, and neither is wrong given what it saw.

The whole lesson on one page

The naive way: everyone applies what reaches them

Run the program: the same game, the same buttons, only when they're applied changes.

1class Juego {
2  constructor(n) { this.pos = Array(n).fill(0); this.puntos = Array(n).fill(0); this.tick = 0; }
3  update(masks) {
4    this.tick++;
5    masks.forEach((m, i) => {
6      if (m & 8) this.pos[i]++;                       // right
7      if (m & 4) this.pos[i]--;                       // left
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A on a coin
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// What each player presses on each tick (a fixed rule, so it can be repeated)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17// Each phone sees its own button instantly and the other's with a delay
18function phone(yo, retrasoDelOtro) {
19  const g = new Juego(2);
20  for (let t = 0; t < 30; t++) {
21    const masks = [0, 0];
22    masks[yo] = aprieta(yo, t);
23    const otro = 1 - yo;
24    if (t - retrasoDelOtro >= 0) masks[otro] = aprieta(otro, t - retrasoDelOtro);
25    g.update(masks);
26  }
27  return g.huella();
28}
29
30console.log("phone A:", phone(0, 2));
31console.log("phone B:", phone(1, 3));

The fingerprint is tick | positions | points. The two differ: each phone believes in a different game, and neither is wrong given what it saw.

Turns from the host

versus.js's solution is called lockstep. One phone is the host. The others send it their buttons; every 6-tick turn (200 ms) the host builds a { k, masks } packet with one input per player and sends it to everyone.

The golden rule: nobody simulates with anything else, not even the host with its own buttons. Everyone waits for turn k, applies it for 6 ticks and moves on to k + 1. If packets arrive at odd times, no matter: they're applied in order. Same packets, same order, same game.

The pipe is one Supabase Realtime channel per round (party:CODIGO:r0), with *broadcast* messages: they go from phone to phone without touching the database.

1class Juego {
2  constructor(n) { this.pos = Array(n).fill(0); this.puntos = Array(n).fill(0); this.tick = 0; }
3  update(masks) {
4    this.tick++;
5    masks.forEach((m, i) => {
6      if (m & 8) this.pos[i]++;                       // right
7      if (m & 4) this.pos[i]--;                       // left
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A on a coin
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// What each player presses on each tick (a fixed rule, so it can be repeated)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17const TURN = 6;
18// A fake channel with delay: each message reaches each phone at a different time
19function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) >>> 0; let t = a; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
20const azar = mulberry32(3);
21
22const telefonos = [0, 1, 2].map((i) => ({ i, juego: new Juego(3), turnos: [], siguiente: 0, buzon: [] }));
23
24for (let k = 0; k < 10; k++) {
25  // the host (phone 0) builds turn k with each player's latest input
26  const turno = { k, masks: telefonos.map((t) => aprieta(t.i, k)) };
27  // sends it to everyone, itself included; each copy arrives 0 to 3 turns late
28  for (const t of telefonos) t.buzon.push({ llega: k + Math.floor(azar() * 4), turno });
29
30  for (const t of telefonos) {
31    for (const m of t.buzon.filter((m) => m.llega <= k)) t.turnos[m.turno.k] = m.turno;
32    t.buzon = t.buzon.filter((m) => m.llega > k);
33    // only advance with the next turn, in order
34    while (t.turnos[t.siguiente]) {
35      const { masks } = t.turnos[t.siguiente++];
36      for (let i = 0; i < TURN; i++) t.juego.update(masks);
37    }
38  }
39}
40// at the end, everything still missing arrives
41for (const t of telefonos) {
42  for (const m of t.buzon) t.turnos[m.turno.k] = m.turno;
43  while (t.turnos[t.siguiente]) { const { masks } = t.turnos[t.siguiente++]; for (let i = 0; i < TURN; i++) t.juego.update(masks); }
44  console.log("phone", t.i, t.juego.huella());
45}

The three phones got the turns at different times and still end with the same fingerprint: 60 ticks, same positions, same points. None of them simulated a tick without the turn it needed.

Lost packets and people who leave

On a real network, sometimes a message doesn't arrive. If a phone gets turn 4 without having had turn 3, it knows it's missing one: it sends 'need' with from: 3 and the host resends every turn from there out of its history. Meanwhile that phone waits: better behind than wrong.

Other cases versus.js handles:

Anyone who hasn't sent buttons for more than 1.5 s (closed the app) stands still: the host puts 0 in their slot.
If the party's creator doesn't show up within 6 s, the host is the first present member on the list, and the choice is locked when the round starts (hostFijo).
If turns stop arriving for 6 s, the round is called with whatever there is.

1class Juego {
2  constructor(n) { this.pos = Array(n).fill(0); this.puntos = Array(n).fill(0); this.tick = 0; }
3  update(masks) {
4    this.tick++;
5    masks.forEach((m, i) => {
6      if (m & 8) this.pos[i]++;                       // right
7      if (m & 4) this.pos[i]--;                       // left
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A on a coin
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// What each player presses on each tick (a fixed rule, so it can be repeated)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17const TURN = 6;
18const historial = [];               // what the host keeps
19const turnos = [];                  // what the guest has
20let siguiente = 0;
21const juego = new Juego(2);
22
23function recibirTurno(t) {          // recibirTurno() from versus.js, summarized
24  turnos[t.k] = t;
25  if (t.k > siguiente && !turnos[siguiente]) {
26    console.log("  missing", siguiente, "-> need from", siguiente);
27    for (const v of historial.slice(siguiente)) turnos[v.k] = v;   // the host resends
28  }
29}
30
31for (let k = 0; k < 6; k++) {
32  const t = { k, masks: [aprieta(0, k), aprieta(1, k)] };
33  historial[k] = t;
34  if (k === 3) { console.log("turn 3: lost on the way"); continue; }
35  console.log("turn", k, "arrives");
36  recibirTurno(t);
37  while (turnos[siguiente]) { const { masks } = turnos[siguiente++]; for (let i = 0; i < TURN; i++) juego.update(masks); }
38}
39
40// The host simulated everything without losing anything
41const anfitrion = new Juego(2);
42for (const { masks } of historial) for (let i = 0; i < TURN; i++) anfitrion.update(masks);
43console.log("guest:    ", juego.huella());
44console.log("host:     ", anfitrion.huella());

When turn 4 arrives without turn 3, the guest asks for what's missing and catches up. Its fingerprint matches the host's: the lost turn left no trace in the game, just a bit of delay.

The price, and the log for the server

Lockstep has a price you can feel: between pressing a button and your snake turning there are 200 to 400 ms, the time for your button to reach the host, get into the next turn and come back. In exchange, nobody can see a different game, and Realtime only carries a few bytes per turn.

At the end, the host has every turn. log() unrolls them into one array of masks per tick (each turn counts for 6 ticks) and that's what goes to the server, which re-simulates it with verifyVersus to hand out points: the same idea as unit 7.

Kazan, the studio's strategy game, takes this same idea to 50 players on an island, with orders instead of buttons.

1const TURN = 6;
2const turnos = [
3  { k: 0, masks: [8, 0] },
4  { k: 1, masks: [8, 1] },
5  { k: 2, masks: [2, 1] },
6];
7
8// log() from versus.js: one input per player per tick
9function log(turnos, turnoFin) {
10  const out = [];
11  for (let k = 0; k < turnoFin && turnos[k]; k++)
12    for (let i = 0; i < TURN; i++) out.push(turnos[k].masks);
13  return out;
14}
15
16const registro = log(turnos, turnos.length);
17console.log("ticks:", registro.length);
18console.log("first 8:", JSON.stringify(registro.slice(0, 8)));
19console.log("one turn of delay:", (TURN * 1000 / 30).toFixed(0), "ms");

Three turns are 18 ticks: each packet repeats six times in a row. A turn lasts 200 ms; with the network's round trip on top, the delay you feel lands between 200 and 400 ms.