← Así se hace un juego: Snake de Daily Challenge · Lección 16/16

Lockstep: todos ven la misma partida

1/9

Lo ingenuo: cada quien aplica lo que le llega

Imagina dos teléfonos. Cada uno aplica sus botones al instante y los del otro cuando llegan. El problema es que llegan tarde, y no igual de tarde: el teléfono A aplica un botón de B dos ticks después de que B lo apretó, y B aplica el de A tres ticks después. Cada uno simula una partida ligeramente distinta y, como en Snake un tick de diferencia es chocar o no chocar, al rato son dos partidas distintas.

Corre el programa: el mismo juego, los mismos botones, sólo cambia cuándo se aplican.

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]++;                       // derecha
7      if (m & 4) this.pos[i]--;                       // izquierda
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A sobre una moneda
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// Lo que aprieta cada jugador en cada tick (una regla fija, para poder repetirlo)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17// Cada teléfono ve su botón al momento y el del otro con retraso
18function teléfono(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("teléfono A:", teléfono(0, 2));
31console.log("teléfono B:", teléfono(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]++;                       // derecha
      if (m & 4) this.pos[i]--;                       // izquierda
      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A sobre una moneda
    });
  }
  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
}

// Lo que aprieta cada jugador en cada tick (una regla fija, para poder repetirlo)
const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];

// Cada teléfono ve su botón al momento y el del otro con retraso
function teléfono(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("teléfono A:", teléfono(0, 2));
console.log("teléfono B:", teléfono(1, 3));

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

La huella es tick | posiciones | puntos. Las dos salen distintas: cada teléfono cree en una partida diferente, y ninguno está mal según lo que vio.

Toda la lección en una página

Lo ingenuo: cada quien aplica lo que le llega

Corre el programa: el mismo juego, los mismos botones, sólo cambia cuándo se aplican.

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]++;                       // derecha
7      if (m & 4) this.pos[i]--;                       // izquierda
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A sobre una moneda
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// Lo que aprieta cada jugador en cada tick (una regla fija, para poder repetirlo)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17// Cada teléfono ve su botón al momento y el del otro con retraso
18function teléfono(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("teléfono A:", teléfono(0, 2));
31console.log("teléfono B:", teléfono(1, 3));

La huella es tick | posiciones | puntos. Las dos salen distintas: cada teléfono cree en una partida diferente, y ninguno está mal según lo que vio.

Turnos del anfitrión

La solución de versus.js se llama lockstep (paso al unísono). Uno de los teléfonos es el anfitrión. Los demás le mandan sus botones; el anfitrión, cada turno de 6 ticks (200 ms), arma un paquete { k, masks } con un input por jugador y lo manda a todos.

La regla de oro: nadie simula con otra cosa, ni siquiera el anfitrión con sus propios botones. Todos esperan el turno k, lo aplican durante 6 ticks y pasan al k + 1. Si los paquetes llegan a destiempo, da igual: se aplican en orden. Mismos paquetes, mismo orden, mismo juego.

El tubo es un canal de Supabase Realtime por ronda (party:CODIGO:r0), con mensajes *broadcast*: pasan de teléfono a teléfono sin tocar la base de datos.

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]++;                       // derecha
7      if (m & 4) this.pos[i]--;                       // izquierda
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A sobre una moneda
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// Lo que aprieta cada jugador en cada tick (una regla fija, para poder repetirlo)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17const TURN = 6;
18// Un canal de mentira con retraso: cada mensaje llega a cada teléfono en otro momento
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  // el anfitrión (teléfono 0) compone el turno k con lo último de cada jugador
26  const turno = { k, masks: telefonos.map((t) => aprieta(t.i, k)) };
27  // lo manda a todos, él incluido; cada copia llega con 0 a 3 turnos de retraso
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    // sólo se avanza con el turno que sigue, en orden
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// al final llega todo lo que faltaba
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("teléfono", t.i, t.juego.huella());
45}

Los tres teléfonos recibieron los turnos en momentos distintos y aun así terminan con la misma huella: 60 ticks, mismas posiciones, mismos puntos. Ninguno simuló un tick sin tener el turno que le tocaba.

Paquetes perdidos y gente que se va

En una red de verdad, a veces un mensaje no llega. Si a un teléfono le llega el turno 4 sin haber tenido el 3, sabe que le falta uno: manda 'need' con from: 3 y el anfitrión reenvía desde su historial todos los turnos desde ahí. Mientras tanto ese teléfono espera: prefiere ir atrasado a ir equivocado.

Otros casos que versus.js cubre:

Quien lleva más de 1.5 s sin mandar botones (cerró la app) se queda quieto: el anfitrión pone 0 en su lugar.
Si el creador de la party no aparece en 6 s, el anfitrión es el primer presente de la lista, y el elegido queda fijo al arrancar (hostFijo).
Si los turnos dejan de llegar por 6 s, la ronda se da por terminada con lo que haya.

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]++;                       // derecha
7      if (m & 4) this.pos[i]--;                       // izquierda
8      if (m & 16 && this.pos[i] % 3 === 0) this.puntos[i] += 10;   // A sobre una moneda
9    });
10  }
11  huella() { return this.tick + "|" + this.pos.join(",") + "|" + this.puntos.join(","); }
12}
13
14// Lo que aprieta cada jugador en cada tick (una regla fija, para poder repetirlo)
15const aprieta = (jugador, tick) => [8, 8, 16, 4, 0, 24][(tick * (jugador + 2) + jugador) % 6];
16
17const TURN = 6;
18const historial = [];               // lo que guarda el anfitrión
19const turnos = [];                  // lo que tiene el invitado
20let siguiente = 0;
21const juego = new Juego(2);
22
23function recibirTurno(t) {          // recibirTurno() de versus.js, resumido
24  turnos[t.k] = t;
25  if (t.k > siguiente && !turnos[siguiente]) {
26    console.log("  falta el", siguiente, "-> need from", siguiente);
27    for (const v of historial.slice(siguiente)) turnos[v.k] = v;   // el anfitrión reenvía
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("turno 3: se perdió en el camino"); continue; }
35  console.log("turno", k, "llega");
36  recibirTurno(t);
37  while (turnos[siguiente]) { const { masks } = turnos[siguiente++]; for (let i = 0; i < TURN; i++) juego.update(masks); }
38}
39
40// El anfitrión simuló todo sin perder nada
41const anfitrion = new Juego(2);
42for (const { masks } of historial) for (let i = 0; i < TURN; i++) anfitrion.update(masks);
43console.log("invitado: ", juego.huella());
44console.log("anfitrión:", anfitrion.huella());

Al llegar el 4 sin el 3, el invitado pide lo que le falta y se pone al día. Sus huellas y las del anfitrión coinciden: el turno perdido no dejó rastro en la partida, sólo un poco de retraso.

El precio, y el registro para el servidor

Lockstep tiene un costo que se siente: entre que aprietas y que tu serpiente gira pasan 200 a 400 ms, lo que tarda tu botón en llegar al anfitrión, en entrar al siguiente turno y en volver. A cambio, nadie puede ver una partida distinta, y Realtime sólo transporta unos cuantos bytes por turno.

Al terminar, el anfitrión tiene todos los turnos. log() los despliega en un arreglo de máscaras por tick (cada turno vale 6 ticks) y eso es lo que se manda al servidor, que lo re-simula con verifyVersus para repartir los puntos: la misma idea de la unidad 7.

Kazan, el juego de estrategia de la casa, lleva esto mismo a 50 jugadores en una isla, con órdenes en vez de botones.

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() de versus.js: un input por jugador por 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("primeros 8:", JSON.stringify(registro.slice(0, 8)));
19console.log("retraso de un turno:", (TURN * 1000 / 30).toFixed(0), "ms");

Tres turnos son 18 ticks: cada paquete se repite seis veces seguidas. El turno dura 200 ms; con lo que tarda la red en ir y volver, el retraso que se siente queda entre 200 y 400 ms.