Multiplayer game worlds

every tick (33.3 ms at 30 Hz)
  1. take inputs     queued per player since the last tick, already validated
  2. simulate        step(state, input) with a FIXED dt, never the frame time
  3. record          positions per tick (lag compensation history)
  4. every Nth tick  send each client a snapshot: what it may see + ack of its last input

export type Vec = { x: number; y: number };
export type Input = { seq: number; dx: number; dy: number };
 
export const TICK_HZ = 30;
export const DT = 1 / TICK_HZ; // seconds per tick
const SPEED = 6; // units per second
 
// shared by server and client: same input → same result
export function step(p: Vec, i: Input): Vec {
  const len = Math.hypot(i.dx, i.dy) || 1;
  return {
    x: p.x + (i.dx / len) * SPEED * DT,
    y: p.y + (i.dy / len) * SPEED * DT,
  };
}

import { step, type Input, type Vec } from "./sim";
 
type Player = {
  eid: number; // small numeric id for the wire
  pos: Vec;
  queue: Input[]; // received, not yet simulated
  ack: number; // last seq simulated
};
const MAX_QUEUE = 8; // ≈ 250 ms of inputs at 30 Hz
 
export function createWorld() {
  const players = new Map<string, Player>();
  let tick = 0;
  let nextEid = 1;
  return {
    join(id: string): number {
      const eid = nextEid++;
      const pos = { x: 0, y: 0 };
      players.set(id, { eid, pos, queue: [], ack: 0 });
      return eid; // tell the client which entity is theirs
    },
    leave: (id: string) => players.delete(id),
    // from the socket: validated, then queued (not applied)
    input(id: string, i: Input) {
      const p = players.get(id);
      if (!p) return;
      const last = p.queue.at(-1)?.seq ?? p.ack;
      if (i.seq <= last) return; // duplicate or stale
      if (p.queue.length >= MAX_QUEUE) return; // flooding
      players.set(id, { ...p, queue: [...p.queue, i] });
    },
    // one fixed tick: at most one input per player
    update() {
      tick += 1;
      for (const [id, p] of players) {
        const [next, ...rest] = p.queue;
        if (!next) continue; // no input: stand still
        const pos = step(p.pos, next);
        const ack = next.seq;
        players.set(id, { ...p, pos, queue: rest, ack });
      }
    },
    snapshotFor(id: string) {
      const ents = [...players.values()].map((p) => ({
        id: p.eid,
        ...p.pos,
      }));
      return { tick, ack: players.get(id)?.ack ?? 0, ents };
    },
  };
}

import { TICK_HZ } from "./sim";
 
const TICK_MS = 1000 / TICK_HZ;
const SEND_EVERY = 2; // 30 Hz sim, 15 Hz snapshots
 
// fixed-step accumulator: timers jitter, the sim must not
export function runLoop(
  update: () => void,
  broadcast: () => void,
) {
  let last = performance.now();
  let acc = 0;
  let tick = 0;
  const timer = setInterval(() => {
    const now = performance.now();
    acc += Math.min(now - last, 250); // cap catch-up
    last = now;
    while (acc >= TICK_MS) {
      update();
      acc -= TICK_MS;
      tick += 1;
      if (tick % SEND_EVERY === 0) broadcast();
    }
  }, TICK_MS / 2);
  return () => clearInterval(timer);
}

// client → server, one per client tick
export type InputMsg = {
  t: "input";
  seq: number; // +1 every client tick, never reused
  dx: -1 | 0 | 1; // intent, never a position
  dy: -1 | 0 | 1;
  fire: boolean;
};
 
// server → each client, every send tick
export type SnapshotMsg = {
  t: "snap";
  tick: number; // server tick of this state
  ack: number; // last seq applied for this client
  ents: { id: number; x: number; y: number }[];
};

type Ent = { id: number; x: number; y: number };
const SNAP = 1; // message type byte
const SCALE = 100; // 0.01-unit precision, ±327 units
 
// 1 type + 4 tick + 4 ack + 2 count, then 6 per entity
export function encodeSnap(
  tick: number,
  ack: number,
  ents: Ent[],
): ArrayBuffer {
  const buf = new ArrayBuffer(11 + ents.length * 6);
  const v = new DataView(buf);
  v.setUint8(0, SNAP);
  v.setUint32(1, tick);
  v.setUint32(5, ack);
  v.setUint16(9, ents.length);
  ents.forEach((e, n) => {
    const o = 11 + n * 6;
    v.setUint16(o, e.id);
    v.setInt16(o + 2, Math.round(e.x * SCALE));
    v.setInt16(o + 4, Math.round(e.y * SCALE));
  });
  return buf;
}
 
export function decodeSnap(buf: ArrayBuffer) {
  const v = new DataView(buf);
  if (v.getUint8(0) !== SNAP) throw new Error("not a snap");
  const count = v.getUint16(9);
  if (buf.byteLength !== 11 + count * 6) {
    throw new Error("bad length"); // never trust sizes
  }
  const ents = Array.from({ length: count }, (_, n) => {
    const o = 11 + n * 6;
    return {
      id: v.getUint16(o),
      x: v.getInt16(o + 2) / SCALE,
      y: v.getInt16(o + 4) / SCALE,
    };
  });
  return { tick: v.getUint32(1), ack: v.getUint32(5), ents };
}

import { step, type Input, type Vec } from "./sim";
 
export function createPredictor(start: Vec) {
  let seq = 0;
  let pending: Input[] = []; // sent, not yet acked
  let pos = start;
  return {
    get pos() {
      return pos;
    },
    get pending() {
      return pending.length;
    },
    // every client tick: apply now, then send
    input(dx: number, dy: number): Input {
      const i = { seq: ++seq, dx, dy };
      pending = [...pending, i];
      pos = step(pos, i);
      return i; // → socket
    },
    // every snapshot: rewind to the server, replay the rest
    reconcile(server: Vec, ack: number) {
      pending = pending.filter((i) => i.seq > ack);
      pos = pending.reduce(step, server);
    },
  };
}

type Sample = { t: number; x: number; y: number };
const DELAY_MS = 100; // ≥ 2 snapshot intervals at 20 Hz
 
// one buffer per remote entity; t = server time in ms
export function createInterp(max = 30) {
  let buf: Sample[] = [];
  return {
    push(s: Sample) {
      buf = [...buf, s].slice(-max);
    },
    at(serverNow: number): Sample | undefined {
      const t = serverNow - DELAY_MS; // render the past
      const i = buf.findIndex((s) => s.t > t);
      if (i === -1) return buf.at(-1); // starved: hold
      if (i === 0) return buf[0]; // too early
      const a = buf[i - 1]!;
      const b = buf[i]!;
      const k = (t - a.t) / (b.t - a.t);
      return {
        t,
        x: a.x + (b.x - a.x) * k,
        y: a.y + (b.y - a.y) * k,
      };
    },
  };
}

command execution time = server time − packet latency − client interpolation delay   (Valve)

type Pos = { x: number; y: number };
type Frame = { t: number; pos: Map<number, Pos> };
const MAX_REWIND_MS = 250; // cap: limits "shot behind cover"
 
// server: record every tick, rewind for hit tests
export function createHistory(keepMs = 1000) {
  let frames: Frame[] = [];
  return {
    record(t: number, pos: Map<number, Pos>) {
      frames = [...frames, { t, pos }].filter(
        (f) => f.t >= t - keepMs,
      );
    },
    // world as the shooter saw it at their render time
    seenAt(renderT: number, now: number) {
      const t = Math.max(renderT, now - MAX_REWIND_MS);
      return frames.findLast((f) => f.t <= t)?.pos;
    },
  };
}

type Sample = { rtt: number; offset: number };
 
// client sends { t: "ping", c: performance.now() }
// server answers { t: "pong", c, s: its own clock }
export function createClock(keep = 8) {
  let samples: Sample[] = [];
  const best = () =>
    samples.reduce<Sample | undefined>(
      (a, b) => (!a || b.rtt < a.rtt ? b : a),
      undefined,
    );
  return {
    pong(c: number, s: number, now = performance.now()) {
      const rtt = now - c;
      const offset = s + rtt / 2 - now; // server - local
      samples = [...samples, { rtt, offset }].slice(-keep);
    },
    // the lowest-RTT sample has the least queuing error
    get offset() {
      return best()?.offset ?? 0;
    },
    get rtt() {
      return best()?.rtt ?? 0;
    },
    serverNow(now = performance.now()) {
      return now + (best()?.offset ?? 0);
    },
  };
}

type Ent = { id: number; x: number; y: number };
const CELL = 50; // ≈ view radius
 
const cellOf = (x: number, y: number) =>
  `${Math.floor(x / CELL)},${Math.floor(y / CELL)}`;
 
// rebuild once per tick: O(n)
export function buildGrid(ents: Ent[]) {
  const grid = new Map<string, Ent[]>();
  for (const e of ents) {
    const k = cellOf(e.x, e.y);
    grid.set(k, [...(grid.get(k) ?? []), e]);
  }
  return grid;
}
 
// the 3×3 cells around a player: what they may see
export function nearby(
  grid: Map<string, Ent[]>,
  x: number,
  y: number,
): Ent[] {
  const cx = Math.floor(x / CELL);
  const cy = Math.floor(y / CELL);
  return [-1, 0, 1].flatMap((dx) =>
    [-1, 0, 1].flatMap(
      (dy) => grid.get(`${cx + dx},${cy + dy}`) ?? [],
    ),
  );
}

import { z } from "zod";
 
const Dir = z.union([
  z.literal(-1),
  z.literal(0),
  z.literal(1),
]);
export const InputMsg = z.object({
  t: z.literal("input"),
  seq: z.number().int().nonnegative(),
  dx: Dir,
  dy: Dir,
  fire: z.boolean(),
});
 
// a hit claim is checked, never believed
export function canHit(
  shooter: { x: number; y: number; lastShot: number },
  target: { x: number; y: number }, // rewound position
  now: number,
): boolean {
  const RANGE = 30;
  const COOLDOWN_MS = 250;
  const d = Math.hypot(
    target.x - shooter.x,
    target.y - shooter.y,
  );
  return d <= RANGE && now - shooter.lastShot >= COOLDOWN_MS;
}

// WebRTC: unordered, no retransmits ≈ UDP
export function stateChannel(pc: RTCPeerConnection) {
  const ch = pc.createDataChannel("state", {
    ordered: false,
    maxRetransmits: 0,
  });
  ch.binaryType = "arraybuffer";
  return ch;
}
 
// WebTransport: QUIC datagrams (HTTPS, HTTP/3 server)
export async function datagrams(url: string) {
  const wt = new WebTransport(url);
  await wt.ready;
  const dg = wt.datagrams;
  // Firefox/Safari: createWritable(); Chrome: .writable
  type Dg = { createWritable?: () => WritableStream };
  const make = (dg as Dg).createWritable;
  const w = make ? make.call(dg) : dg.writable;
  const out = w.getWriter();
  const reader = dg.readable.getReader();
  return {
    max: dg.maxDatagramSize, // bytes; larger ones drop
    send: (b: Uint8Array) => out.write(b),
    async *receive() {
      for (;;) {
        const { value, done } = await reader.read();
        if (done) return;
        yield value as Uint8Array;
      }
    },
  };
}

// shared by server and client
import { schema, t } from "@colyseus/schema";
import type { SchemaType } from "@colyseus/schema";
 
export const Player = schema(
  {
    x: t.float32().default(0),
    y: t.float32().default(0),
  },
  "Player",
);
export const State = schema(
  { players: t.map(Player) },
  "State",
);
export type State = SchemaType<typeof State>;

import {
  Room,
  defineRoom,
  defineServer,
  validate,
  type Client,
} from "colyseus";
import { z } from "zod";
import { Player, State } from "./schema";
 
const Move = z.object({
  dx: z.number().min(-1).max(1),
  dy: z.number().min(-1).max(1),
});
type Move = z.infer<typeof Move>;
 
export class Arena extends Room<{ state: State }> {
  override maxClients = 16;
  override maxMessagesPerSecond = 60; // then kicked
  override state = new State();
  moves = new Map<string, Move>();
 
  override messages = {
    // invalid payloads never reach the handler
    move: validate(Move, (client: Client, m: Move) => {
      this.moves.set(client.sessionId, m);
    }),
  };
 
  override onCreate() {
    this.patchRate = 50; // state patches at 20 Hz
    // variable step: ms = measured time since last tick
    this.setTimestep((ms) => this.tick(ms / 1000), 33);
  }
 
  tick(dt: number) {
    for (const [id, m] of this.moves) {
      const p = this.state.players.get(id);
      if (!p) continue;
      p.x += m.dx * 6 * dt; // schema records the delta
      p.y += m.dy * 6 * dt;
    }
  }
 
  override onJoin(client: Client) {
    this.state.players.set(client.sessionId, new Player());
  }
 
  override onLeave(client: Client) {
    this.state.players.delete(client.sessionId);
    this.moves.delete(client.sessionId);
  }
}
 
export const server = defineServer({
  rooms: { arena: defineRoom(Arena) },
});
// await server.listen(2567);

import { Client, Callbacks } from "@colyseus/sdk";
import type { State } from "./schema";
 
const client = new Client("http://localhost:2567");
const room = await client.joinOrCreate<State>("arena");
const $ = Callbacks.get(room);
 
$.onAdd("players", (player, sessionId) => {
  // draw a sprite; then follow every patch
  $.onChange(player, () => {
    // interpolate toward player.x / player.y
  });
});
$.onRemove("players", (_player, sessionId) => {
  // remove the sprite
});
 
room.send("move", { dx: 1, dy: 0 });

import { createWorld } from "./world";
import { runLoop } from "./loop";
import { encodeSnap } from "./codec";
import { InputMsg } from "./validate";
 
type Data = { id: string };
const parse = (s: string): unknown => {
  try {
    return JSON.parse(s);
  } catch {
    return undefined; // fails the schema below
  }
};
const world = createWorld();
const sockets = new Map<string, Bun.ServerWebSocket<Data>>();
 
export const server = Bun.serve({
  port: 3001,
  fetch(req, server) {
    const id = crypto.randomUUID(); // real app: session
    if (server.upgrade(req, { data: { id } })) return;
    return new Response("Upgrade required", { status: 426 });
  },
  websocket: {
    data: {} as Data,
    open(ws) {
      sockets.set(ws.data.id, ws);
      const eid = world.join(ws.data.id);
      ws.send(JSON.stringify({ t: "welcome", eid }));
    },
    message(ws, raw) {
      const msg = InputMsg.safeParse(parse(String(raw)));
      if (!msg.success) return ws.close(1008, "bad input");
      world.input(ws.data.id, msg.data);
    },
    close(ws) {
      sockets.delete(ws.data.id);
      world.leave(ws.data.id);
    },
  },
});
 
// per-client snapshot: each one carries its own ack
export const stop = runLoop(world.update, () => {
  for (const [id, ws] of sockets) {
    const s = world.snapshotFor(id);
    ws.send(encodeSnap(s.tick, s.ack, s.ents));
  }
});

import { createPredictor } from "./predict";
import { createInterp } from "./interp";
import { createClock } from "./clock";
import { decodeSnap } from "./codec";
import { DT } from "./sim";
 
declare const ws: WebSocket; // binaryType = "arraybuffer"
declare const myId: number;
declare function keys(): { dx: number; dy: number };
declare function draw(id: number, x: number, y: number):
  void;
 
const me = createPredictor({ x: 0, y: 0 });
const clock = createClock(); // fed by ping/pong
type Interp = ReturnType<typeof createInterp>;
const others = new Map<number, Interp>();
 
ws.addEventListener("message", (e) => {
  const snap = decodeSnap(e.data as ArrayBuffer);
  const t = snap.tick * DT * 1000; // server ms
  for (const ent of snap.ents) {
    if (ent.id === myId) me.reconcile(ent, snap.ack);
    else {
      const buf = others.get(ent.id) ?? createInterp();
      others.set(ent.id, buf);
      buf.push({ t, x: ent.x, y: ent.y });
    }
  }
});
 
// fixed-rate input, same rate as the server tick
setInterval(() => {
  const { dx, dy } = keys();
  const i = me.input(dx, dy);
  ws.send(JSON.stringify({ t: "input", ...i, fire: false }));
}, DT * 1000);
 
// render at display rate: own = predicted, others = past
function frame() {
  draw(myId, me.pos.x, me.pos.y);
  const now = clock.serverNow();
  for (const [id, buf] of others) {
    const p = buf.at(now);
    if (p) draw(id, p.x, p.y);
  }
  requestAnimationFrame(frame);
}
requestAnimationFrame(frame);

type Vec = { x: number; y: number };
 
// hide small reconciliation snaps: draw at sim + offset,
// and let the offset decay to zero over ~100 ms
export function createSmoother(halfLifeMs = 35) {
  let offset: Vec = { x: 0, y: 0 };
  return {
    // call with positions before and after reconcile()
    corrected(before: Vec, after: Vec) {
      offset = {
        x: offset.x + before.x - after.x,
        y: offset.y + before.y - after.y,
      };
      if (Math.hypot(offset.x, offset.y) > 3) {
        offset = { x: 0, y: 0 }; // too far: just snap
      }
    },
    // every frame: position to draw
    draw(sim: Vec, frameMs: number): Vec {
      const k = Math.pow(0.5, frameMs / halfLifeMs);
      offset = { x: offset.x * k, y: offset.y * k };
      return { x: sim.x + offset.x, y: sim.y + offset.y };
    },
  };
}

import type { Input } from "./sim";
 
// unreliable channel: resend the last 3 inputs in every
// packet so one lost packet loses nothing
export function inputPacker(copies = 3) {
  let recent: Input[] = [];
  return (next: Input): Input[] => {
    recent = [...recent, next].slice(-copies);
    return recent; // → datagram
  };
}
 
// server side: the seq check in world.input() already
// drops the copies it has seen

// wrap any send() to test with bad networks locally
export function laggy<T>(
  deliver: (msg: T) => void,
  { ms = 100, jitter = 30, loss = 0.02 } = {},
) {
  return (msg: T) => {
    if (Math.random() < loss) return; // dropped
    const delay = ms + (Math.random() * 2 - 1) * jitter;
    setTimeout(() => deliver(msg), Math.max(0, delay));
  };
}

const sendToServer = laggy((m: string) => ws.send(m), {
  ms: 75, // one way; RTT ≈ 150 ms
  jitter: 20,
  loss: 0.05,
});