Nagel-Schreckenberg Highway

drag Y to set density, click to toggle dawdle

The 1992 Nagel-Schreckenberg cellular automaton: a ring road of $L = 200$ cells, each either empty or hosting a car with integer velocity $v \in {0, 1, \dots, v_{m a x}}$ , $v_{m a x} = 5$ . Every timestep applies four rules in lockstep to all cars: (1) **accelerate** $v \leftarrow min (v + 1, v_{m a x})$ , (2) **brake to gap** $v \leftarrow min (v, d)$ where $d$ is the empty distance to the next car, (3) **dawdle** $v \leftarrow max (v - 1, 0)$ with probability $p$ , (4) **move** $x \leftarrow x + v (mod L)$ . The dawdle is the whole story: with $p = 0$ traffic asymptotes to a deterministic free-flow fixed point at any density, but with $p > 0$ a single random slowdown at moderate density propagates backwards as a phantom jam, surviving long after its cause is gone. The middle panel is the canonical space-time diagram — each row is one timestep, time flows downward, and stopped cars (blue) trace the backward-moving jam fronts at the famous $\approx - 1$ cell-per-timestep group velocity (about $- 5 km/h$ when cells are calibrated to $7.5 m$ at 1 Hz). The bottom panel plots the fundamental diagram $J (ρ) = ρ \overset{v}{ˉ}$ : a sharp linear free-flow branch up to $ρ \approx (1 - p) / (v_{m a x} + 1 - p)$ , a maximum around $ρ \sim 0.1 - 0.15$ , then a congested branch where added density removes flow. Drag the mouse vertically to scrub density between $0.05$ and $0.5$ ; click to toggle the dawdle on and off.

idle

300 lines · vanilla

view source

// Nagel-Schreckenberg cellular highway on a 1D ring of L cells.
// v in {0,..,VMAX}. Per timestep: accelerate -> brake-to-gap -> dawdle -> move.
// Render: road strip + scrolling space-time diagram + fundamental diagram.

const L = 200;
const VMAX = 5;
const HISTORY_ROWS = 200;
const FD_BINS = 60;

let W, H;
let road;        // Int8Array of length L; -1 = empty, else velocity 0..VMAX
let history;     // Uint8Array of HISTORY_ROWS*L; per cell stores velocity+1 (0 = empty)
let histHead;    // ring buffer write index (row)
let histCount;

let density;     // target density rho in [0.05, 0.5]
let actualRho;
let dawdle;      // 0 or 0.3
let stepAccum;   // sub-step accumulator for fixed-rate CA stepping
let stepsPerSec; // CA steps per real second

// Live measurements
let meanV;       // EMA of mean velocity over moving cars
let flow;        // EMA of throughput (cars passing a fixed observer) per step

// Fundamental diagram samples: array of {rho, J}, with rolling cap
let fdSamples;
let fdNext;
let fdCount;

// Layout (recomputed on resize)
let roadY, roadH, stY, stH, fdY, fdH, txtY;
let cellW;

function nCars() {
  let n = 0;
  for (let i = 0; i < L; i++) if (road[i] >= 0) n++;
  return n;
}

function seedRoad(targetDensity) {
  road.fill(-1);
  const target = Math.max(1, Math.round(targetDensity * L));
  // Pick distinct positions
  let placed = 0;
  while (placed < target) {
    const i = (Math.random() * L) | 0;
    if (road[i] < 0) {
      road[i] = (Math.random() * (VMAX + 1)) | 0;
      placed++;
    }
  }
}

function adjustDensity(targetDensity) {
  const target = Math.max(1, Math.round(targetDensity * L));
  let cur = nCars();
  // Add cars at random empty cells
  let safety = 0;
  while (cur < target && safety++ < L * 4) {
    const i = (Math.random() * L) | 0;
    if (road[i] < 0) { road[i] = 0; cur++; }
  }
  // Remove cars from random occupied cells
  safety = 0;
  while (cur > target && safety++ < L * 4) {
    const i = (Math.random() * L) | 0;
    if (road[i] >= 0) { road[i] = -1; cur--; }
  }
}

function step() {
  // Compute new velocities first, then move (synchronous update).
  const newV = new Int8Array(L);
  for (let i = 0; i < L; i++) newV[i] = -1;

  // For each car, compute v'
  // Pass 1: gather positions in order
  const cars = [];
  for (let i = 0; i < L; i++) if (road[i] >= 0) cars.push(i);
  if (cars.length === 0) return;

  // Compute gaps. Since cars[] is sorted, the next car after cars[k] is cars[(k+1) % n].
  const n = cars.length;
  let movingCount = 0;
  let velSum = 0;

  // Throughput: count how many cars cross cell index 0 (ring boundary) this step
  let crossings = 0;

  // First: compute new velocities (rules 1-3)
  const updatedV = new Int8Array(n);
  for (let k = 0; k < n; k++) {
    const pos = cars[k];
    let v = road[pos];
    // 1. Accelerate
    if (v < VMAX) v++;
    // 2. Brake to gap
    const nextPos = cars[(k + 1) % n];
    let gap = nextPos - pos - 1;
    if (gap < 0) gap += L;
    if (v > gap) v = gap;
    // 3. Dawdle
    if (dawdle > 0 && v > 0 && Math.random() < dawdle) v--;
    updatedV[k] = v;
  }

  // Then move
  for (let k = 0; k < n; k++) {
    const pos = cars[k];
    const v = updatedV[k];
    let np = pos + v;
    if (np >= L) { np -= L; crossings++; }
    newV[np] = v;
    velSum += v;
    if (v > 0) movingCount++;
  }

  // Commit
  for (let i = 0; i < L; i++) road[i] = newV[i];

  const meanThisStep = n > 0 ? velSum / n : 0;
  const flowThisStep = crossings; // cars passing observer per step

  // EMAs
  meanV = meanV * 0.9 + meanThisStep * 0.1;
  flow = flow * 0.9 + flowThisStep * 0.1;
  actualRho = n / L;

  // Sample fundamental diagram
  fdSamples[fdNext * 2] = actualRho;
  fdSamples[fdNext * 2 + 1] = actualRho * meanThisStep; // J = rho * v_bar
  fdNext = (fdNext + 1) % FD_BINS;
  if (fdCount < FD_BINS) fdCount++;

  // Push row to space-time history
  const rowOff = histHead * L;
  for (let i = 0; i < L; i++) {
    if (road[i] < 0) history[rowOff + i] = 0;
    else history[rowOff + i] = road[i] + 1; // 1..VMAX+1
  }
  histHead = (histHead + 1) % HISTORY_ROWS;
  if (histCount < HISTORY_ROWS) histCount++;
}

function velocityColor(v) {
  // 0 (stopped) = blue, VMAX = green
  const t = v / VMAX;
  const hue = 210 - t * 100; // 210 (blue) -> 110 (green)
  const light = 45 + t * 15;
  return `hsl(${hue}, 80%, ${light}%)`;
}

function computeLayout() {
  // Road strip slim, space-time biggest, FD bottom.
  const pad = 8;
  const titleH = 18;
  roadY = pad + titleH;
  roadH = Math.max(18, Math.min(28, Math.floor(H * 0.05)));

  stY = roadY + roadH + 14;
  fdH = Math.max(80, Math.min(140, Math.floor(H * 0.22)));
  txtY = H - 8;
  fdY = H - fdH - 22;
  stH = Math.max(60, fdY - stY - 8);

  cellW = W / L;
}

function init({ canvas, ctx, width, height }) {
  W = width;
  H = height;

  road = new Int8Array(L);
  history = new Uint8Array(HISTORY_ROWS * L);
  histHead = 0;
  histCount = 0;

  density = 0.2;
  actualRho = density;
  dawdle = 0.3;

  stepAccum = 0;
  stepsPerSec = 30;

  meanV = 0;
  flow = 0;

  fdSamples = new Float32Array(FD_BINS * 2);
  fdNext = 0;
  fdCount = 0;

  seedRoad(density);
  computeLayout();

  // Warm-up
  for (let i = 0; i < 60; i++) step();

  ctx.fillStyle = '#0a0d12';
  ctx.fillRect(0, 0, W, H);
}

function drawRoad(ctx) {
  // Background asphalt
  ctx.fillStyle = '#15191f';
  ctx.fillRect(0, roadY, W, roadH);
  // Dashed centerline
  ctx.strokeStyle = 'rgba(255, 220, 80, 0.35)';
  ctx.setLineDash([10, 8]);
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(0, roadY + roadH * 0.5);
  ctx.lineTo(W, roadY + roadH * 0.5);
  ctx.stroke();
  ctx.setLineDash([]);

  // Cars
  const cw = Math.max(1.5, cellW - 0.5);
  const ch = roadH - 6;
  for (let i = 0; i < L; i++) {
    const v = road[i];
    if (v < 0) continue;
    ctx.fillStyle = velocityColor(v);
    ctx.fillRect(i * cellW, roadY + 3, cw, ch);
  }
}

function drawSpaceTime(ctx) {
  // Frame
  ctx.fillStyle = '#0a0d12';
  ctx.fillRect(0, stY, W, stH);
  ctx.strokeStyle = 'rgba(255,255,255,0.08)';
  ctx.lineWidth = 1;
  ctx.strokeRect(0.5, stY + 0.5, W - 1, stH - 1);

  if (histCount === 0) return;

  const rowH = stH / HISTORY_ROWS;
  // Oldest row is at the top, newest at bottom.
  const startRow = (histHead - histCount + HISTORY_ROWS) % HISTORY_ROWS;
  const cw = cellW;

  for (let r = 0; r < histCount; r++) {
    const ringRow = (startRow + r) % HISTORY_ROWS;
    const off = ringRow * L;
    const y = stY + (HISTORY_ROWS - histCount + r) * rowH;
    for (let i = 0; i < L; i++) {
      const code = history[off + i];
      if (code === 0) continue;
      const v = code - 1;
      ctx.fillStyle = velocityColor(v);
      // Slight overdraw to avoid sub-pixel gaps
      ctx.fillRect(i * cw, y, cw + 0.6, rowH + 0.6);
    }
  }

  // Labels
  ctx.fillStyle = 'rgba(220,230,245,0.75)';
  ctx.font = '11px system-ui, sans-serif';
  ctx.textBaseline = 'top';
  ctx.fillText('space →', 6, stY + 4);
  ctx.save();
  ctx.translate(W - 8, stY + 6);
  ctx.fillText('time ↓', -38, 0);
  ctx.restore();
}

function drawFundamental(ctx) {
  const x0 = 10;
  const y0 = fdY;
  const fw = W - 20;
  const fh = fdH;

  // Axes background
  ctx.fillStyle = 'rgba(255,255,255,0.03)';
  ctx.fillRect(x0, y0, fw, fh);
  ctx.strokeStyle = 'rgba(255,255,255,0.18)';
  ctx.lineWidth = 1;
  ctx.strokeRect(x0 + 0.5, y0 + 0.5, fw - 1, fh - 1);

  // Axis labels
  ctx.fillStyle = 'rgba(200,210,225,0.7)';
  ctx.font = '10px system-ui, sans-serif';
  ctx.textBaseline = 'top';
  ctx.fillText('flow J', x0 + 4, y0 + 4);
  ctx.textBaseline = 'bottom';
  ctx.fillText('density ρ', x0 + fw - 56, y0 + fh - 4);

  // J_max for VMAX=5, p=0.3 is roughly 0.6 cells/step at rho ~ 0.15; pad axis.
  const rhoMax = 0.55;
  const Jmax = VMAX * 0.5; // generous ceiling
  const toX = (rho) => x0 + (rho / rhoMax) * fw;
  const toY = (J) => y0 + fh - (J / Jmax) * fh;

  // Gridlines
  ctx.strokeStyle = 'rgba(255,255,255,0.07)';
  ctx.beginPath();
  for (let g = 0.1; g < rhoMax; g += 0.1) {
    const gx = toX(g);
    ctx.moveTo(gx, y0); ctx.lineTo(gx, y0 + fh);
  }
  for (let g = 0.5; g < Jmax; g += 0.5) {
    const gy = toY(g);
    ctx.moveTo(x0, gy); ctx.lineTo(x0 + fw, gy);
  }
  ctx.stroke();

  // Historical samples as dots
  if (fdCount > 0) {
    const start = (fdNext - fdCount + FD_BINS) % FD_BINS;
    for (let k = 0; k < fdCount; k++) {
      const idx = (start + k) % FD_BINS;
      const rho = fdSamples[idx * 2];
      const J = fdSamples[idx * 2 + 1];
      const age = k / fdCount;
      ctx.fillStyle = `hsla(40, 90%, 70%, ${(0.15 + age * 0.55).toFixed(3)})`;
      ctx.beginPath();
      ctx.arc(toX(rho), toY(J), 2.2, 0, Math.PI * 2);
      ctx.fill();
    }
  }

  // Current operating point
  const Jnow = actualRho * meanV;
  ctx.strokeStyle = 'rgba(120,220,160,0.9)';
  ctx.fillStyle = 'rgba(120,220,160,0.95)';
  ctx.lineWidth = 1;
  const px = toX(actualRho);
  const py = toY(Jnow);
  ctx.beginPath();
  ctx.arc(px, py, 4.5, 0, Math.PI * 2);
  ctx.fill();
  // Crosshair
  ctx.beginPath();
  ctx.moveTo(x0, py); ctx.lineTo(x0 + fw, py);
  ctx.moveTo(px, y0); ctx.lineTo(px, y0 + fh);
  ctx.setLineDash([2, 4]);
  ctx.strokeStyle = 'rgba(120,220,160,0.35)';
  ctx.stroke();
  ctx.setLineDash([]);
}

function drawHud(ctx) {
  ctx.fillStyle = 'rgba(225,232,245,0.92)';
  ctx.font = '13px system-ui, sans-serif';
  ctx.textBaseline = 'top';
  ctx.fillText('Nagel-Schreckenberg Highway', 8, 6);

  ctx.font = '12px ui-monospace, monospace';
  ctx.textBaseline = 'alphabetic';
  const J = actualRho * meanV;
  const dawLabel = dawdle > 0 ? `p=${dawdle.toFixed(2)} (jams)` : 'p=0 (free flow)';
  const line = `ρ=${actualRho.toFixed(3)}   v̄=${meanV.toFixed(2)}   J=${J.toFixed(3)}   ${dawLabel}`;
  ctx.fillStyle = 'rgba(220,230,250,0.85)';
  ctx.fillText(line, 8, txtY);
}

function tick({ ctx, dt, width, height, input }) {
  if (width !== W || height !== H) {
    W = width;
    H = height;
    computeLayout();
  }

  // Click toggles dawdle
  const clicks = input.consumeClicks ? input.consumeClicks() : 0;
  if (clicks > 0) {
    dawdle = dawdle > 0 ? 0 : 0.3;
  }

  // mouseY scrubs density 0.05..0.5
  if (typeof input.mouseY === 'number' && input.mouseY >= 0 && input.mouseY <= H) {
    const t = Math.max(0, Math.min(1, input.mouseY / H));
    const target = 0.05 + t * 0.45;
    if (Math.abs(target - density) > 0.002) {
      density = target;
      adjustDensity(density);
    }
  }

  // Fixed-rate stepping
  stepAccum += dt * stepsPerSec;
  let steps = 0;
  while (stepAccum >= 1 && steps < 8) {
    step();
    stepAccum -= 1;
    steps++;
  }
  if (stepAccum > 4) stepAccum = 0; // clamp catch-up after tab-switch

  // Clear
  ctx.fillStyle = '#0a0d12';
  ctx.fillRect(0, 0, W, H);

  drawSpaceTime(ctx);
  drawRoad(ctx);
  drawFundamental(ctx);
  drawHud(ctx);
}

Nagel-Schreckenberg Highway

Comments (0)