main.js

// Blids — WebGPU boids tuned for Chrome/Blink (Dawn).
//
// Physics layer (tester-certified in the v14-v16 brute-force builds):
//   - Gaussian influence weights — no hard kernel edge (a cutoff at radius r
//     makes the flock condense into r-spaced clusters that read as a grid).
//     For grid acceleration the Gaussian is truncated at 2.5σ where it is
//     already ~4% of peak, with a smoothstep fade to exactly zero.
//   - Front-weighted vision (neighbors ahead count more), which damps the
//     band/stripe instabilities of symmetric-kernel flocks.
//   - Circular arena with a purely radial boundary force (default), or torus
//     wrap (toggle) — both verified artifact-free.
//   - Per-boid noise melts residual crystal ordering.
//
// Performance layer: counting-sort spatial grid (bit-exact in every audit),
// used ONLY to find neighbors — every force is an exact pairwise function of
// true Euclidean distance. The interaction radius auto-shrinks with
// population so the neighbor loop stays exact at any count; the grid runs up
// to 1024x1024 cells via a 3-level prefix scan.

const BUILD = 'v27 release: made-with-ai + labs hosting';
const WORLD_H = 1000;          // world height in sim units; width follows aspect
const SCAN_BLOCK = 256;        // cells per scan workgroup
const MAX_GRID = 1024;         // per-axis cell cap (1M cells, 4096 scan blocks)
const SUPPORT_NEIGHBORS = 72;  // auto-radius targets this many boids in the support disc
const MAX_READS_PER_CELL = 96; // safety valve for pathological transient clumps
document.getElementById('build').textContent = 'build: ' + BUILD;

// ---------------------------------------------------------------- WGSL ----

const COMMON = /* wgsl */`
struct Params {
  worldSize : vec2f,
  invCell   : vec2f,
  gridW     : u32,
  gridH     : u32,
  numBoids  : u32,
  dt        : f32,
  radius    : f32,   // effective (auto-scaled) interaction radius
  lerpT     : f32,   // render interpolation between prev (0) and curr (1) state
  wSep      : f32,
  wAlign    : f32,
  wCoh      : f32,
  maxSpeed  : f32,
  minSpeed  : f32,
  boidSize  : f32,
  mousePos  : vec2f,
  mouseForce: f32,
  frame     : u32,
  noiseAmp  : f32,
  wrapMode  : u32,   // 1 = torus wrap, 0 = circular arena
  gridOffset: vec2f, // slow-drifting sub-cell shift of the binning grid
}

struct Boid { pos : vec2f, vel : vec2f }

// position in the jittered grid frame, wrapped back into [0, world)
fn shiftedPos(p : vec2f, params : Params) -> vec2f {
  let q = p + params.gridOffset;
  return q - params.worldSize * floor(q / params.worldSize);
}

fn cellCoords(p : vec2f, params : Params) -> vec2u {
  let c = vec2u(shiftedPos(p, params) * params.invCell);
  return min(c, vec2u(params.gridW - 1u, params.gridH - 1u));
}

fn cellIndex(c : vec2u, params : Params) -> u32 {
  return c.y * params.gridW + c.x;
}

// shortest vector a->b on the torus
fn wrapDelta(d : vec2f, world : vec2f) -> vec2f {
  return d - world * round(d / world);
}
`;

const COUNT_WGSL = COMMON + /* wgsl */`
@group(0) @binding(0) var<uniform> params : Params;
@group(0) @binding(1) var<storage, read> boids : array<Boid>;
@group(0) @binding(2) var<storage, read_write> counts : array<atomic<u32>>;

@compute @workgroup_size(256)
fn main(@builtin(global_invocation_id) gid : vec3u) {
  let i = gid.x;
  if (i >= params.numBoids) { return; }
  let c = cellIndex(cellCoords(boids[i].pos, params), params);
  atomicAdd(&counts[c], 1u);
}
`;

// Exclusive prefix sum over cell counts — three scan levels + one add pass,
// good for up to 1024x1024 cells (4096 blocks, 16 superblocks).
const SCAN1_WGSL = COMMON + /* wgsl */`
@group(0) @binding(0) var<storage, read> counts : array<u32>;
@group(0) @binding(1) var<storage, read_write> cellStart : array<u32>;
@group(0) @binding(2) var<storage, read_write> blockSums : array<u32>;

var<workgroup> temp : array<u32, ${SCAN_BLOCK}>;

@compute @workgroup_size(${SCAN_BLOCK})
fn main(@builtin(global_invocation_id) gid : vec3u,
        @builtin(local_invocation_id) lid : vec3u,
        @builtin(workgroup_id) wid : vec3u) {
  let x = counts[gid.x];
  temp[lid.x] = x;
  for (var offset = 1u; offset < ${SCAN_BLOCK}u; offset = offset << 1u) {
    workgroupBarrier();
    var v = 0u;
    if (lid.x >= offset) { v = temp[lid.x - offset]; }
    workgroupBarrier();
    temp[lid.x] += v;
  }
  workgroupBarrier();
  cellStart[gid.x] = temp[lid.x] - x;           // inclusive -> exclusive
  if (lid.x == ${SCAN_BLOCK - 1}u) { blockSums[wid.x] = temp[lid.x]; }
}
`;

const SCAN2_WGSL = /* wgsl */`
@group(0) @binding(0) var<storage, read_write> blockSums : array<u32>;
@group(0) @binding(1) var<storage, read_write> superSums : array<u32>;

var<workgroup> temp : array<u32, ${SCAN_BLOCK}>;

@compute @workgroup_size(${SCAN_BLOCK})
fn main(@builtin(global_invocation_id) gid : vec3u,
        @builtin(local_invocation_id) lid : vec3u,
        @builtin(workgroup_id) wid : vec3u) {
  var x = 0u;
  if (gid.x < arrayLength(&blockSums)) { x = blockSums[gid.x]; }
  temp[lid.x] = x;
  for (var offset = 1u; offset < ${SCAN_BLOCK}u; offset = offset << 1u) {
    workgroupBarrier();
    var v = 0u;
    if (lid.x >= offset) { v = temp[lid.x - offset]; }
    workgroupBarrier();
    temp[lid.x] += v;
  }
  workgroupBarrier();
  if (gid.x < arrayLength(&blockSums)) { blockSums[gid.x] = temp[lid.x] - x; }
  if (lid.x == ${SCAN_BLOCK - 1}u) { superSums[wid.x] = temp[lid.x]; }
}
`;

const SCAN3_WGSL = /* wgsl */`
@group(0) @binding(0) var<storage, read_write> superSums : array<u32>;

var<workgroup> temp : array<u32, ${SCAN_BLOCK}>;

@compute @workgroup_size(${SCAN_BLOCK})
fn main(@builtin(local_invocation_id) lid : vec3u) {
  let n = arrayLength(&superSums);
  var x = 0u;
  if (lid.x < n) { x = superSums[lid.x]; }
  temp[lid.x] = x;
  for (var offset = 1u; offset < ${SCAN_BLOCK}u; offset = offset << 1u) {
    workgroupBarrier();
    var v = 0u;
    if (lid.x >= offset) { v = temp[lid.x - offset]; }
    workgroupBarrier();
    temp[lid.x] += v;
  }
  workgroupBarrier();
  if (lid.x < n) { superSums[lid.x] = temp[lid.x] - x; }
}
`;

const ADDOFF_WGSL = /* wgsl */`
@group(0) @binding(0) var<storage, read_write> cellStart : array<u32>;
@group(0) @binding(1) var<storage, read> blockSums : array<u32>;
@group(0) @binding(2) var<storage, read> superSums : array<u32>;

@compute @workgroup_size(${SCAN_BLOCK})
fn main(@builtin(global_invocation_id) gid : vec3u,
        @builtin(workgroup_id) wid : vec3u) {
  cellStart[gid.x] += blockSums[wid.x] + superSums[wid.x >> 8u];
}
`;

const SCATTER_WGSL = COMMON + /* wgsl */`
@group(0) @binding(0) var<uniform> params : Params;
@group(0) @binding(1) var<storage, read> boidsIn : array<Boid>;
@group(0) @binding(2) var<storage, read> cellStart : array<u32>;
@group(0) @binding(3) var<storage, read_write> cursor : array<atomic<u32>>;
@group(0) @binding(4) var<storage, read_write> boidsOut : array<Boid>;

@compute @workgroup_size(256)
fn main(@builtin(global_invocation_id) gid : vec3u) {
  let i = gid.x;
  if (i >= params.numBoids) { return; }
  let b = boidsIn[i];
  let c = cellIndex(cellCoords(b.pos, params), params);
  let dst = cellStart[c] + atomicAdd(&cursor[c], 1u);
  boidsOut[dst] = b;
}
`;

const UPDATE_WGSL = COMMON + /* wgsl */`
@group(0) @binding(0) var<uniform> params : Params;
@group(0) @binding(1) var<storage, read> boidsIn : array<Boid>;   // sorted
@group(0) @binding(2) var<storage, read> cellStart : array<u32>;
@group(0) @binding(3) var<storage, read> counts : array<u32>;
@group(0) @binding(4) var<storage, read_write> boidsOut : array<Boid>;

fn pcg(v0 : u32) -> u32 {
  var v = v0 * 747796405u + 2891336453u;
  let w = ((v >> ((v >> 28u) + 4u)) ^ v) * 277803737u;
  return (w >> 22u) ^ w;
}

@compute @workgroup_size(64)
fn main(@builtin(global_invocation_id) gid : vec3u) {
  let i = gid.x;
  if (i >= params.numBoids) { return; }

  let me = boidsIn[i];
  let myCell = vec2i(cellCoords(me.pos, params));
  let gw = i32(params.gridW);
  let gh = i32(params.gridH);

  // Classic Reynolds rules with one modern amendment: every hard radius cut
  // is replaced by a smooth skirt (uniform weight inside ~65% of the range,
  // gliding to exactly zero at the range). A step edge at distance r makes
  // the flock self-space into r-sized clusters — the skirt is the sole
  // artifact insurance; the rule structure is textbook boids.
  let R = params.radius;
  let R2 = R * R;
  let sepR = R * 0.35;         // classic separation range ratio
  let sepR2 = sepR * sepR;

  var alignVel = vec2f(0.0);
  var cohDelta = vec2f(0.0);
  var sep = vec2f(0.0);
  var wSum = 0.0;
  let myHeading = me.vel / max(length(me.vel), 1e-5);

  for (var dy = -1i; dy <= 1i; dy++) {
    for (var dx = -1i; dx <= 1i; dx++) {
      let cx = u32((myCell.x + dx + gw) % gw);
      let cy = u32((myCell.y + dy + gh) % gh);
      let c = cy * params.gridW + cx;
      let cnt = counts[c];
      if (cnt == 0u) { continue; }
      let start = cellStart[c];
      // Normally stride == 1 (exact). The stride only engages in pathological
      // transient clumps, jitter-phased and weighted so it stays unbiased.
      let stride = max(1u, (cnt + ${MAX_READS_PER_CELL}u - 1u) / ${MAX_READS_PER_CELL}u);
      var phase = 0u;
      if (stride > 1u) {
        phase = pcg((i * 0x9E3779B9u) ^ (c * 0x85EBCA77u) ^ params.frame) % stride;
      }
      let w = f32(stride);
      for (var j = start + phase; j < start + cnt; j += stride) {
        if (j == i) { continue; }
        let other = boidsIn[j];
        var d = other.pos - me.pos;
        if (params.wrapMode == 1u) {
          d -= params.worldSize * round(d / params.worldSize);
        }
        let dist2 = dot(d, d);
        if (dist2 >= R2) { continue; }
        let dist = sqrt(dist2);
        // classic: neighbors in range count equally — uniform inside 0.65R,
        // smooth skirt to zero at R
        var kw = (1.0 - smoothstep(R * 0.65, R, dist)) * w;
        // field of view (also classic Reynolds): neighbors ahead matter more
        if (dist2 > 1e-6) {
          let front = 0.5 + 0.5 * dot(myHeading, d / dist);
          kw *= 0.2 + 0.8 * front;
        }
        alignVel += other.vel * kw;
        cohDelta += d * kw;
        wSum += kw;
        if (dist2 < sepR2) {
          // classic separation: flee = (my_pos - their_pos) / d², with a
          // smooth skirt at the separation range instead of a step
          let fs = 1.0 - smoothstep(sepR * 0.6, sepR, dist);
          sep -= d * (fs * w / max(dist2, 1e-4));
        }
      }
    }
  }

  var vel = me.vel;
  if (wSum > 1e-5) {
    let inv = 1.0 / wSum;
    vel += (alignVel * inv - vel) * params.wAlign * params.dt; // match neighbors
    vel += cohDelta * inv * params.wCoh * params.dt;           // drift to center
  }
  vel += sep * params.wSep * params.dt;                        // don't crowd

  // pointer scatter
  if (params.mouseForce != 0.0) {
    var dm = me.pos - params.mousePos;
    if (params.wrapMode == 1u) {
      dm = wrapDelta(dm, params.worldSize);
    }
    let md2 = dot(dm, dm);
    let mr = 200.0;
    if (md2 < mr * mr) {
      vel += dm * (params.mouseForce / max(md2, 25.0)) * params.dt;
    }
  }

  // per-boid random kick: identical deterministic boids otherwise condense
  // into a crystal lattice once aligned
  let rnd = pcg((i * 0x9E3779B9u) ^ (params.frame * 0x27d4eb2du));
  let ang = f32(rnd) * 1.4629181e-9;   // maps u32 range onto [0, 2π)
  vel += vec2f(cos(ang), sin(ang)) * params.noiseAmp * params.dt;

  // boundary: radial circular arena (default) or torus wrap (toggle)
  if (params.wrapMode == 0u) {
    let center = params.worldSize * 0.5;
    let arenaR = min(center.x, center.y) - 20.0;
    let rel = me.pos - center;
    let rr = length(rel);
    if (rr > arenaR) {
      let overshoot = min((rr - arenaR) / 40.0, 3.0);
      vel -= (rel / max(rr, 1e-3)) * (params.maxSpeed * 2.5 * overshoot * params.dt);
    }
  }

  // clamp speed into [min, max]
  let speed = length(vel);
  let clamped = clamp(speed, params.minSpeed, params.maxSpeed);
  vel *= clamped / max(speed, 1e-5);

  var pos = me.pos + vel * params.dt;
  if (params.wrapMode == 1u) {
    pos -= params.worldSize * floor(pos / params.worldSize);   // torus wrap
    pos = clamp(pos, vec2f(0.0), params.worldSize - 1e-3);
  } else {
    let center = params.worldSize * 0.5;
    let arenaR = min(center.x, center.y) - 20.0;
    let rel2 = pos - center;
    let rr2 = length(rel2);
    let maxR = arenaR + 60.0;
    if (rr2 > maxR) { pos = center + rel2 * (maxR / rr2); }   // radial backstop
  }

  boidsOut[i] = Boid(pos, vel);
}
`;

const RENDER_WGSL = COMMON + /* wgsl */`
@group(0) @binding(0) var<uniform> params : Params;
@group(0) @binding(1) var<storage, read> boidsCurr : array<Boid>;  // post-update
@group(0) @binding(2) var<storage, read> boidsPrev : array<Boid>;  // pre-update, same index

struct VSOut {
  @builtin(position) clip : vec4f,
  @location(0) color : vec3f,
}

@vertex
fn vs(@builtin(vertex_index) vi : u32, @builtin(instance_index) ii : u32) -> VSOut {
  // Half-rate sim, full-rate motion: interpolate between the previous and
  // current sim state (the scatter buffer holds prev positions at the same
  // indices as the update output — the pipeline produces the pair for free).
  let cur = boidsCurr[ii];
  let prv = boidsPrev[ii];
  var delta = cur.pos - prv.pos;
  if (params.wrapMode == 1u) {
    delta = wrapDelta(delta, params.worldSize);   // don't streak across the seam
  }
  var bpos = prv.pos + delta * params.lerpT;
  if (params.wrapMode == 1u) {
    bpos -= params.worldSize * floor(bpos / params.worldSize);
  }
  let bvel = mix(prv.vel, cur.vel, params.lerpT);
  let b = Boid(bpos, bvel);
  let speed = length(b.vel);
  let heading = b.vel / max(speed, 1e-5);

  // dart shape in model space, +x = forward
  var corner : vec2f;
  switch (vi) {
    case 0u: { corner = vec2f( 1.7,  0.0); }
    case 1u: { corner = vec2f(-1.0,  0.75); }
    default: { corner = vec2f(-1.0, -0.75); }
  }
  corner *= params.boidSize;

  let worldPos = b.pos + vec2f(
    corner.x * heading.x - corner.y * heading.y,
    corner.x * heading.y + corner.y * heading.x,
  );

  var o : VSOut;
  let ndc = worldPos / params.worldSize * 2.0 - 1.0;
  o.clip = vec4f(ndc.x, -ndc.y, 0.0, 1.0);

  // hue from heading, brightness from speed
  let angle = atan2(heading.y, heading.x);
  let pal = 0.55 + 0.45 * cos(vec3f(angle) + vec3f(0.0, 2.094, 4.188));
  let energy = 0.55 + 0.45 * clamp(speed / params.maxSpeed, 0.0, 1.0);
  o.color = pal * energy;
  return o;
}

@fragment
fn fs(v : VSOut) -> @location(0) vec4f {
  // additive blending: overlap count reads as brightness
  return vec4f(v.color * 0.35, 1.0);
}
`;

// ------------------------------------------------------------- startup ----

function fatal(msg) {
  const el = document.getElementById('fatal');
  el.textContent = msg;
  el.style.display = 'grid';
  document.getElementById('hud').style.display = 'none';
}

if (!navigator.gpu) {
  fatal('WebGPU is not available. Run this in Chrome (Blink) with WebGPU enabled.');
  throw new Error('no webgpu');
}

const adapter = await navigator.gpu.requestAdapter({ powerPreference: 'high-performance' });
if (!adapter) { fatal('No GPU adapter found.'); throw new Error('no adapter'); }

const canTime = adapter.features.has('timestamp-query');
const device = await adapter.requestDevice({
  requiredFeatures: canTime ? ['timestamp-query'] : [],
  requiredLimits: {
    maxStorageBufferBindingSize: Math.min(adapter.limits.maxStorageBufferBindingSize, 1 << 30),
    maxBufferSize: Math.min(adapter.limits.maxBufferSize, 1 << 30),
  },
});
device.lost.then((info) => { if (info.reason !== 'destroyed') fatal(`GPU device lost: ${info.message}`); });

const DEBUG = location.hash.includes('debug');
const beacon = (tag, msg) => { if (DEBUG) fetch(`/${tag}?` + encodeURIComponent(msg)).catch(() => {}); };
addEventListener('error', (e) => beacon('JSERR', `${e.message} @ ${e.filename}:${e.lineno}`));
addEventListener('unhandledrejection', (e) => beacon('JSREJ', String(e.reason?.stack || e.reason)));
device.addEventListener('uncapturederror', (e) => beacon('GPUERR', e.error.message.slice(0, 800)));

const canvas = document.getElementById('gpu');
const ctx = canvas.getContext('webgpu');
const format = navigator.gpu.getPreferredCanvasFormat();
ctx.configure({ device, format, alphaMode: 'opaque' });

// ------------------------------------------------------------ pipelines ----

function computePipeline(code, label) {
  return device.createComputePipeline({
    label,
    layout: 'auto',
    compute: { module: device.createShaderModule({ code, label }), entryPoint: 'main' },
  });
}

const countPipe   = computePipeline(COUNT_WGSL, 'count');
const scan1Pipe   = computePipeline(SCAN1_WGSL, 'scan1');
const scan2Pipe   = computePipeline(SCAN2_WGSL, 'scan2');
const scan3Pipe   = computePipeline(SCAN3_WGSL, 'scan3');
const addOffPipe  = computePipeline(ADDOFF_WGSL, 'addOff');
const scatterPipe = computePipeline(SCATTER_WGSL, 'scatter');
const updatePipe  = computePipeline(UPDATE_WGSL, 'update');

const renderModule = device.createShaderModule({ code: RENDER_WGSL, label: 'render' });
const renderPipe = device.createRenderPipeline({
  label: 'render',
  layout: 'auto',
  vertex: { module: renderModule, entryPoint: 'vs' },
  multisample: { count: 4 },
  fragment: {
    module: renderModule, entryPoint: 'fs',
    targets: [{
      format,
      blend: {
        color: { srcFactor: 'one', dstFactor: 'one', operation: 'add' },
        alpha: { srcFactor: 'one', dstFactor: 'one', operation: 'add' },
      },
    }],
  },
  primitive: { topology: 'triangle-list' },
});

// -------------------------------------------------------------- state ----

const PARAMS_SIZE = 96;
const paramsBuf = device.createBuffer({
  size: PARAMS_SIZE, usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST,
});
const paramsArr = new ArrayBuffer(PARAMS_SIZE);
const pf = new Float32Array(paramsArr);
const pu = new Uint32Array(paramsArr);

const ui = {
  count:  document.getElementById('count'),
  radius: document.getElementById('radius'),
  wSep:   document.getElementById('wSep'),
  wAlign: document.getElementById('wAlign'),
  wCoh:   document.getElementById('wCoh'),
  speed:  document.getElementById('speed'),
  size:   document.getElementById('size'),
  noise:  document.getElementById('noise'),
  circle: document.getElementById('circle'),
  smooth: document.getElementById('smooth'),
  fps:    document.getElementById('fps'),
  gputime:document.getElementById('gputime'),
};

let numBoids = 0;
let world = { w: 0, h: 0 };
let grid = { w: 1, h: 1, cellsPadded: SCAN_BLOCK, blocks: 1 };
let boidsA, boidsB, countsBuf, cellStartBuf, cursorBuf, blockSumsBuf, superSumsBuf;
let bindings = null;
const mouse = { x: 0, y: 0, down: false };
const gridOff = { x: 0, y: 0 };

function makeStorage(size, label) {
  return device.createBuffer({
    label, size,
    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST | GPUBufferUsage.COPY_SRC,
  });
}

// The slider is an upper bound on the interaction scale; at high population
// it shrinks so the SUPPORT disc holds ~SUPPORT_NEIGHBORS boids and the
// neighbor loop stays exact.
function effectiveRadius() {
  const slider = parseFloat(ui.radius.value);
  const rTarget = Math.sqrt(SUPPORT_NEIGHBORS * world.w * world.h /
    (Math.PI * Math.max(numBoids, 1)));
  return Math.max(1.2, Math.min(slider, rTarget));
}

function rebuildGridBuffers() {
  const support = effectiveRadius();
  grid.w = Math.min(MAX_GRID, Math.max(1, Math.floor(world.w / support)));
  grid.h = Math.min(MAX_GRID, Math.max(1, Math.floor(world.h / support)));
  grid.blocks = Math.ceil((grid.w * grid.h) / SCAN_BLOCK);
  grid.cellsPadded = grid.blocks * SCAN_BLOCK;

  countsBuf?.destroy(); cellStartBuf?.destroy(); cursorBuf?.destroy();
  blockSumsBuf?.destroy(); superSumsBuf?.destroy();
  countsBuf    = makeStorage(grid.cellsPadded * 4, 'counts');
  cellStartBuf = makeStorage(grid.cellsPadded * 4, 'cellStart');
  cursorBuf    = makeStorage(grid.cellsPadded * 4, 'cursor');
  blockSumsBuf = makeStorage(Math.ceil(grid.blocks / SCAN_BLOCK) * SCAN_BLOCK * 4, 'blockSums');
  superSumsBuf = makeStorage(SCAN_BLOCK * 4, 'superSums');
  bindings = null;
}

function rebuildBoids() {
  numBoids = parseInt(ui.count.value, 10);
  const speed = parseFloat(ui.speed.value);
  boidsA?.destroy(); boidsB?.destroy();
  boidsA = makeStorage(numBoids * 16, 'boidsA');
  boidsB = makeStorage(numBoids * 16, 'boidsB');

  const init = new Float32Array(numBoids * 4);
  const arenaR = Math.min(world.w, world.h) / 2 - 20;
  const inCircle = ui.circle.checked;
  for (let i = 0; i < numBoids; i++) {
    const a = Math.random() * Math.PI * 2;
    const s = speed * (0.4 + 0.6 * Math.random());
    if (inCircle) {
      const pa = Math.random() * Math.PI * 2;
      const pr = arenaR * Math.sqrt(Math.random());   // uniform over the disc
      init[i * 4 + 0] = world.w / 2 + Math.cos(pa) * pr;
      init[i * 4 + 1] = world.h / 2 + Math.sin(pa) * pr;
    } else {
      init[i * 4 + 0] = Math.random() * world.w;      // uniform over the torus
      init[i * 4 + 1] = Math.random() * world.h;
    }
    init[i * 4 + 2] = Math.cos(a) * s;
    init[i * 4 + 3] = Math.sin(a) * s;
  }
  device.queue.writeBuffer(boidsA, 0, init);
  rebuildGridBuffers();   // effective radius depends on the count
}

function rebuildBindings() {
  const bg = (pipe, entries) => device.createBindGroup({
    layout: pipe.getBindGroupLayout(0),
    entries: entries.map((buffer, binding) => ({ binding, resource: { buffer } })),
  });
  bindings = {
    count:   bg(countPipe,   [paramsBuf, boidsA, countsBuf]),
    scan1:   bg(scan1Pipe,   [countsBuf, cellStartBuf, blockSumsBuf]),
    scan2:   bg(scan2Pipe,   [blockSumsBuf, superSumsBuf]),
    scan3:   bg(scan3Pipe,   [superSumsBuf]),
    addOff:  bg(addOffPipe,  [cellStartBuf, blockSumsBuf, superSumsBuf]),
    scatter: bg(scatterPipe, [paramsBuf, boidsA, cellStartBuf, cursorBuf, boidsB]),
    update:  bg(updatePipe,  [paramsBuf, boidsB, cellStartBuf, countsBuf, boidsA]),
    render:  bg(renderPipe,  [paramsBuf, boidsA, boidsB]),
  };
}

function writeParams(dt, lerpT = 1.0) {
  const effR = effectiveRadius();
  const speed = parseFloat(ui.speed.value);
  pf[0] = world.w;            pf[1] = world.h;
  pf[2] = grid.w / world.w;   pf[3] = grid.h / world.h;   // invCell
  pu[4] = grid.w;             pu[5] = grid.h;
  pu[6] = numBoids;
  pf[7] = dt;
  pf[8] = effR;
  pf[9] = lerpT;              // render interpolation factor
  pf[10] = parseFloat(ui.wSep.value);
  pf[11] = parseFloat(ui.wAlign.value);
  pf[12] = parseFloat(ui.wCoh.value);
  pf[13] = speed;             // maxSpeed
  pf[14] = speed * 0.35;      // minSpeed
  pf[15] = parseFloat(ui.size.value);
  pf[16] = mouse.x;           pf[17] = mouse.y;
  pf[18] = mouse.down ? 9000.0 : 0.0;
  pu[19] = frameIdx;
  pf[20] = parseFloat(ui.noise.value);
  pu[21] = ui.circle.checked ? 0 : 1;   // unchecked -> torus wrap
  // Drift the grid origin smoothly so no stationary cell boundary exists;
  // frame-to-frame change is tiny, keeping the counting sort cache-coherent.
  const cellW = world.w / grid.w, cellH = world.h / grid.h;
  gridOff.x = (gridOff.x + cellW * 0.29 * dt) % cellW;
  gridOff.y = (gridOff.y + cellH * 0.17 * dt) % cellH;
  pf[22] = gridOff.x;
  pf[23] = gridOff.y;
  device.queue.writeBuffer(paramsBuf, 0, paramsArr);
}

// -------------------------------------------------------------- resize ----

function resize() {
  const dpr = Math.min(devicePixelRatio || 1, 2);
  canvas.width = Math.max(1, Math.floor(canvas.clientWidth * dpr));
  canvas.height = Math.max(1, Math.floor(canvas.clientHeight * dpr));
  world.w = WORLD_H * (canvas.width / canvas.height);
  world.h = WORLD_H;
  rebuildGridBuffers();
}
resize();
addEventListener('resize', resize);

// allow #1000000 etc. to preset the boid count
{
  const m = (location.hash + location.search).match(/(\d+)/);
  if (m && [...ui.count.options].some(o => o.value === m[1])) ui.count.value = m[1];
}

// while a slider is being dragged, its label shows the live value
for (const input of document.querySelectorAll('#hud input[type="range"]')) {
  const em = input.closest('label')?.querySelector('em');
  if (!em) continue;
  const name = em.textContent;
  let dragging = false;
  const show = () => { em.textContent = `${name}: ${input.value}`; };
  input.addEventListener('pointerdown', () => { dragging = true; show(); });
  input.addEventListener('input', () => { if (dragging) show(); });
  const restore = () => { dragging = false; em.textContent = name; };
  input.addEventListener('pointerup', restore);
  input.addEventListener('pointercancel', restore);
}

ui.radius.addEventListener('input', rebuildGridBuffers);
ui.count.addEventListener('change', rebuildBoids);
document.getElementById('restart').addEventListener('click', (e) => {
  rebuildBoids();
  e.target.blur();   // don't let spacebar re-trigger it later
});
// Boid init happens on the first frame so the world is measured after layout.

canvas.addEventListener('pointermove', (e) => {
  mouse.x = (e.clientX / canvas.clientWidth) * world.w;
  mouse.y = (e.clientY / canvas.clientHeight) * world.h;
});
canvas.addEventListener('pointerdown', (e) => { mouse.down = true; canvas.setPointerCapture(e.pointerId); });
canvas.addEventListener('pointerup', () => { mouse.down = false; });

// -------------------------------------------------------- gpu timing ----

let msaaTex = null;
let querySet = null, queryResolve = null, queryRead = null, queryBusy = false;
if (canTime) {
  querySet = device.createQuerySet({ type: 'timestamp', count: 2 });
  queryResolve = device.createBuffer({ size: 16, usage: GPUBufferUsage.QUERY_RESOLVE | GPUBufferUsage.COPY_SRC });
  queryRead = device.createBuffer({ size: 16, usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ });
}
let gpuMsEma = 0;

// -------------------------------------------------------------- debug ----

let dbgFrames = 0;

async function debugDump() {
  const n = numBoids;
  const bbuf = device.createBuffer({ size: n * 16, usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ });
  const cbuf = device.createBuffer({ size: grid.cellsPadded * 4, usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ });
  const enc = device.createCommandEncoder();
  enc.copyBufferToBuffer(boidsA, 0, bbuf, 0, n * 16);
  enc.copyBufferToBuffer(countsBuf, 0, cbuf, 0, grid.cellsPadded * 4);
  device.queue.submit([enc.finish()]);
  await Promise.all([bbuf.mapAsync(GPUMapMode.READ), cbuf.mapAsync(GPUMapMode.READ)]);
  const f = new Float32Array(bbuf.getMappedRange());
  const c = new Uint32Array(cbuf.getMappedRange());

  let sx = 0, sy = 0, sm = 0, badBoids = 0, axAff = 0;
  for (let i = 0; i < n; i++) {
    const px = f[i * 4], py = f[i * 4 + 1], vx = f[i * 4 + 2], vy = f[i * 4 + 3];
    if (!Number.isFinite(px) || !Number.isFinite(py) || !Number.isFinite(vx) || !Number.isFinite(vy)
        || px < 0 || px > world.w || py < 0 || py > world.h) badBoids++;
    const sp = Math.hypot(vx, vy) || 1;
    const cx4 = (vx / sp) ** 2, cy4 = (vy / sp) ** 2;
    axAff += cx4 * cx4 + cy4 * cy4;   // 0.75 isotropic, 1.0 axis-locked
    sx += vx; sy += vy; sm += Math.hypot(vx, vy);
  }
  let total = 0, maxCell = 0;
  for (let i = 0; i < grid.cellsPadded; i++) { total += c[i]; if (c[i] > maxCell) maxCell = c[i]; }
  const payload = JSON.stringify({
    globalAlign: +(Math.hypot(sx, sy) / sm).toFixed(4),
    axisAffinity: +(axAff / n).toFixed(4),
    effR: +effectiveRadius().toFixed(2),
    countsSum: total, expected: n, maxCell, badBoids,
  });
  console.log('BLIDS_DEBUG ' + payload);
  fetch('/BLIDS_DEBUG?' + encodeURIComponent(payload)).catch(() => {});
  bbuf.destroy(); cbuf.destroy();
}

// --------------------------------------------------------------- frame ----

let lastT = performance.now();
let fpsEma = 0;
let frameIdx = 0;
let inited = false;
let simAccum = 0;
let needSim = true;   // force a sim step after (re)init so prev/curr are valid

function frame(now) {
  if (!inited) { inited = true; resize(); rebuildBoids(); }
  const rawDt = (now - lastT) / 1000;
  lastT = now;
  frameIdx++;
  const dt = Math.min(Math.max(rawDt, 1 / 240), 1 / 30);
  fpsEma = fpsEma ? fpsEma * 0.95 + (1 / rawDt) * 0.05 : 1 / rawDt;
  ui.fps.textContent = fpsEma.toFixed(0);

  if (!bindings) { rebuildBindings(); needSim = true; }

  let steps = 1;
  if (DEBUG && dbgFrames === 0) {
    steps = parseInt((location.hash.match(/s(\d+)/) || [])[1], 10) || 600;
  }

  // Half-rate sim: integrate every other frame with the accumulated dt; the
  // renderer interpolates prev->curr so motion stays full-rate smooth.
  simAccum += rawDt;
  const halfRate = ui.smooth.checked && steps === 1;
  const doSim = !halfRate || needSim || frameIdx % 2 === 1;
  const simDt = Math.min(Math.max(simAccum, 1 / 240), 1 / 24);
  const lerpT = halfRate && !needSim ? (doSim ? 0.5 : 1.0) : 1.0;
  writeParams(steps > 1 ? 1 / 60 : simDt, lerpT);

  const boidGroups256 = Math.ceil(numBoids / 256);
  const boidGroups64 = Math.ceil(numBoids / 64);

  const encodeStep = (e, withTimestamps) => {
    e.clearBuffer(countsBuf);
    e.clearBuffer(cursorBuf);
    const passDesc = withTimestamps
      ? { timestampWrites: { querySet, beginningOfPassWriteIndex: 0, endOfPassWriteIndex: 1 } }
      : {};
    const pass = e.beginComputePass(passDesc);
    pass.setPipeline(countPipe);   pass.setBindGroup(0, bindings.count);   pass.dispatchWorkgroups(boidGroups256);
    pass.setPipeline(scan1Pipe);   pass.setBindGroup(0, bindings.scan1);   pass.dispatchWorkgroups(grid.blocks);
    pass.setPipeline(scan2Pipe);   pass.setBindGroup(0, bindings.scan2);   pass.dispatchWorkgroups(Math.ceil(grid.blocks / SCAN_BLOCK));
    pass.setPipeline(scan3Pipe);   pass.setBindGroup(0, bindings.scan3);   pass.dispatchWorkgroups(1);
    pass.setPipeline(addOffPipe);  pass.setBindGroup(0, bindings.addOff);  pass.dispatchWorkgroups(grid.blocks);
    pass.setPipeline(scatterPipe); pass.setBindGroup(0, bindings.scatter); pass.dispatchWorkgroups(boidGroups256);
    pass.setPipeline(updatePipe);  pass.setBindGroup(0, bindings.update);  pass.dispatchWorkgroups(boidGroups64);
    pass.end();
  };

  for (let s = 0; s < steps - 1; ) {
    if (s > 0) { frameIdx++; writeParams(1 / 60); }
    const e = device.createCommandEncoder();
    for (let k = 0; k < 10 && s < steps - 1; k++, s++) encodeStep(e, false);
    device.queue.submit([e.finish()]);
  }
  if (steps > 1) { frameIdx++; writeParams(1 / 60); }

  const enc = device.createCommandEncoder();
  if (doSim) {
    encodeStep(enc, canTime && !queryBusy);
    simAccum = 0;
    needSim = false;
  }

  if (!msaaTex || msaaTex.width !== canvas.width || msaaTex.height !== canvas.height) {
    msaaTex?.destroy();
    msaaTex = device.createTexture({
      size: [canvas.width, canvas.height], sampleCount: 4, format,
      usage: GPUTextureUsage.RENDER_ATTACHMENT,
    });
  }
  const rp = enc.beginRenderPass({
    colorAttachments: [{
      view: msaaTex.createView(),
      resolveTarget: ctx.getCurrentTexture().createView(),
      loadOp: 'clear',
      clearValue: { r: 0.039, g: 0.055, b: 0.09, a: 1 },
      storeOp: 'discard',
    }],
  });
  rp.setPipeline(renderPipe);
  rp.setBindGroup(0, bindings.render);
  rp.draw(3, numBoids);
  rp.end();

  if (doSim && canTime && !queryBusy) {
    enc.resolveQuerySet(querySet, 0, 2, queryResolve, 0);
    enc.copyBufferToBuffer(queryResolve, 0, queryRead, 0, 16);
  }
  device.queue.submit([enc.finish()]);

  if (DEBUG) {
    dbgFrames++;
    if (dbgFrames === 1) {
      beacon('HEARTBEAT', `frame=1 steps=${steps} t=${now.toFixed(0)}`);
      debugDump().catch((e) => beacon('DUMPERR', String(e?.stack || e)));
    }
  }

  if (doSim && canTime && !queryBusy) {
    queryBusy = true;
    queryRead.mapAsync(GPUMapMode.READ).then(() => {
      const t = new BigInt64Array(queryRead.getMappedRange());
      const ms = Number(t[1] - t[0]) / 1e6;
      queryRead.unmap();
      if (ms >= 0 && ms < 1000) {
        gpuMsEma = gpuMsEma ? gpuMsEma * 0.9 + ms * 0.1 : ms;
        ui.gputime.textContent = gpuMsEma.toFixed(2) + ' ms';
      }
      queryBusy = false;
    }).catch(() => { queryBusy = false; });
  }

  requestAnimationFrame(frame);
}
requestAnimationFrame(frame);