Hilbert Curve

// Hilbert curve — space-filling curve that maps [0, 1] -> [0,1]^2
// while preserving locality: indices nearby on the 1D curve land in
// nearby 2D cells. At order n the curve visits N = 4^n cells on an
// NxN grid (N = 2^n). We generate orders 1..MAX_ORDER, animating the
// draw segment-by-segment, then pause and advance to the next order.
//
// d2xy uses the standard bit-interleaving construction with the four
// quadrant rotations (rx, ry) from Hacker's Delight / Wikipedia.

let W, H, order, n, total, drawn, perFrame, phase, phaseT;
let pts, padX, padY, cell;
const MAX_ORDER = 7;
const MIN_ORDER = 1;
const DRAW_TIME = 2.6;   // seconds spent drawing one order
const HOLD_TIME = 1.1;   // pause at full curve before next order

function d2xy(nSide, d) {
  let rx, ry, t = d;
  let x = 0, y = 0;
  for (let s = 1; s < nSide; s <<= 1) {
    rx = 1 & (t >> 1);
    ry = 1 & (t ^ rx);
    if (ry === 0) {
      if (rx === 1) {
        x = s - 1 - x;
        y = s - 1 - y;
      }
      const tmp = x; x = y; y = tmp;
    }
    x += s * rx;
    y += s * ry;
    t >>= 2;
  }
  return [x, y];
}

function buildOrder(o) {
  order = o;
  n = 1 << o;          // grid side
  total = n * n;        // number of cells
  const side = Math.min(W, H) - 24;
  cell = side / n;
  padX = (W - n * cell) * 0.5;
  padY = (H - n * cell) * 0.5;
  pts = new Float32Array(total * 2);
  for (let d = 0; d < total; d++) {
    const xy = d2xy(n, d);
    pts[d * 2] = padX + (xy[0] + 0.5) * cell;
    pts[d * 2 + 1] = padY + (xy[1] + 0.5) * cell;
  }
  drawn = 0;
  // draw the full curve over DRAW_TIME regardless of segment count
  perFrame = Math.max(1, Math.ceil(total / (DRAW_TIME * 60)));
  phase = "draw";
  phaseT = 0;
}

function background(ctx) {
  ctx.fillStyle = "#06080f";
  ctx.fillRect(0, 0, W, H);
  // soft grid backdrop showing the NxN partition
  ctx.strokeStyle = "rgba(120, 140, 200, 0.10)";
  ctx.lineWidth = 1;
  ctx.beginPath();
  for (let i = 0; i <= n; i++) {
    const x = padX + i * cell;
    ctx.moveTo(x, padY);
    ctx.lineTo(x, padY + n * cell);
    const y = padY + i * cell;
    ctx.moveTo(padX, y);
    ctx.lineTo(padX + n * cell, y);
  }
  ctx.stroke();
}

function drawSegments(ctx, upTo) {
  // color each segment by its traversal position (rainbow)
  // line width shrinks with order so order 7 stays legible
  const lw = Math.max(0.7, 4.6 - order * 0.55);
  ctx.lineWidth = lw;
  ctx.lineCap = "round";
  ctx.lineJoin = "round";
  // chunk the polyline so we can color each segment by index
  // but limit the per-segment stroke calls for high orders
  const stride = Math.max(1, Math.floor(total / 4096));
  for (let i = 0; i < upTo - stride; i += stride) {
    const t = i / total;
    const h = (t * 320 + 5) % 360;
    ctx.strokeStyle = "hsl(" + h.toFixed(1) + " 90% 58%)";
    ctx.beginPath();
    ctx.moveTo(pts[i * 2], pts[i * 2 + 1]);
    const end = Math.min(i + stride, upTo - 1);
    for (let j = i + 1; j <= end; j++) {
      ctx.lineTo(pts[j * 2], pts[j * 2 + 1]);
    }
    ctx.stroke();
  }
  // bright head marker at the leading edge while drawing
  if (phase === "draw" && upTo > 0 && upTo < total) {
    const hx = pts[(upTo - 1) * 2];
    const hy = pts[(upTo - 1) * 2 + 1];
    ctx.fillStyle = "#fff";
    ctx.beginPath();
    ctx.arc(hx, hy, Math.max(1.6, lw * 0.9), 0, Math.PI * 2);
    ctx.fill();
  }
}

function drawHUD(ctx) {
  ctx.fillStyle = "rgba(0,0,0,0.55)";
  ctx.fillRect(10, 10, 232, 64);
  ctx.fillStyle = "#fff";
  ctx.font = "13px ui-monospace, monospace";
  ctx.fillText("order n = " + order + "   side = " + n, 18, 30);
  ctx.fillText("cells 4^n = " + total, 18, 48);
  const pct = phase === "draw"
    ? Math.min(100, Math.floor((drawn / total) * 100))
    : 100;
  ctx.fillText("traversed: " + pct + "%", 18, 66);
}

function init({ width, height }) {
  W = width; H = height;
  buildOrder(MIN_ORDER);
}

function tick({ ctx, dt, width, height }) {
  if (width !== W || height !== H) {
    W = width; H = height;
    buildOrder(order || MIN_ORDER);
  }
  const step = dt || 0.016;
  phaseT += step;

  if (phase === "draw") {
    drawn = Math.min(total, drawn + perFrame);
    if (drawn >= total) {
      phase = "hold";
      phaseT = 0;
    }
  } else if (phase === "hold") {
    if (phaseT >= HOLD_TIME) {
      const next = order >= MAX_ORDER ? MIN_ORDER : order + 1;
      buildOrder(next);
    }
  }

  background(ctx);
  drawSegments(ctx, drawn);
  drawHUD(ctx);
}