Neighbour grid

stop after

6

Turn again

Tap an item or choose Turn again to change its walk through a box one cell deep. The grid visits sorted ranges from the starting cell, keeps neighbours within sight up tostop after, and numbers them in visit order across the three nonempty ranges of its 3×3 cells.

Boids, crowds and collisions need each item’s neighbours. Testing every pair costs the square of the item count. The fish tank’s 3 340 fish would need 11 million distance checks per step. A neighbour grid sorts the items by cell once a step, and a kernel reads only the cells around each item.

import * as grid from '@typegpu/kit/grid';
import { randf } from '@typegpu/noise';

const SIGHT = 1.5;
/** What a neighbour sees of a boid. */
const Seen = d.struct({ position: d.vec3f, velocity: d.vec3f });

const rows = boids.inject(); // what position and itemOf read
const cells = grid.create(root, {
  ...boids.live(), // the table's capacity, alive and span
  low: d.vec3f(-20, 0, -20),
  size: d.vec3f(40, 10, 40),
  sight: SIGHT,
  item: Seen,
  position: Boid.position.pipe(rows),
  itemOf: tgpu
    .fn((i: number) => {
      'use gpu';
      return Seen({ position: Boid.position(i), velocity: Boid.velocity(i) });
    })
    .pipe(rows),
});

const steer = tgpu.computeFn({
  workgroupSize: [64],
  in: { gid: d.builtin.globalInvocationId },
})(({ gid }) => {
  'use gpu';
  const i = gid.x;
  if (!Boid.alive(i)) return;

  const position = Boid.position(i);
  randf.seed4(d.vec4f(position, d.f32(i))); // the walk turns at random
  let heading = d.vec3f();
  let seen = d.f32(0);

  const walk = cells.walk(position);
  for (let r = d.u32(0); r < grid.RANGES; r++) {
    const range = cells.range(walk, r);
    for (let j = d.u32(0); j < range.count; j++) {
      const other = cells.neighbour(range, j);
      if (std.distance(other.position, position) < SIGHT) {
        heading += other.velocity;
        seen += 1;
      }
    }
  }

  const boid = Boid.device.$[i]!;
  // The walk meets the boid itself, so `seen` is at least 1
  boid.velocity = std.mix(boid.velocity, heading / seen, 0.02);
});
const steering = root.pipe(boids.inject()).pipe(cells.inject()).createComputePipeline({
  compute: steer,
});

frames.create(root, (frame) => {
  boids.flush();

  const compute = frame.encoder.beginComputePass();
  cells.sort(compute); // before the kernels that walk
  compute.setPipeline(steering);
  compute.dispatchWorkgroups(Math.ceil(boids.span / 64));
  compute.end();
});

• A cell is sight wide, so the nine ranges of three cells along x that a walk visits hold every item within sight. Cells along x sort together in order, so each range is one run of sorted items.
• A walk visits its own range first, then adjacent ranges. It uses randf to choose a direction along each axis, so seed it per item first. This avoids a directional bias when a walk stops early, such as after 16 neighbours.
• sort copies each itemOf result into sorted order using the item schema. A kernel can then move items while reading their neighbours’ pre-step values. Copy only the fields neighbours need. The fish tank copies position, velocity and species.
• cells.slot(range, j) returns the original slot i for a neighbour’s itemOf(i) value. Use it to act on that item or skip the walker itself. A walk can start anywhere, such as at a frog’s mouth, and identify nearby items by slot.
• slot binds a third storage buffer. A kernel short of bindings can copy the index in itemOf instead, at four bytes or more a neighbour.
• cells.around(point) starts a fixed-order walk without random draws, reading each range in sorted order. Use it when a shader reads every item in the ranges, such as for a fluid’s density or point lights. cells.slotAt(index) returns the original slot at a sorted index. A range spans first through first + count - 1. cells.candidates() returns both functions with fills, for lighting’s points.candidates.
• sort covers slots below span(), or below capacity without one, alive or not. Without alive, every slot holds an item, and the types refuse a span.
• An item outside the box belongs to the nearest cell. sight and box dimensions determine buffer sizes and shader constants. Changing either requires another grid.
• Each grid has its own accessors, so one kernel can walk two, say the fish and the pellets, each piped in with its own inject().

Order matters when a walk stops early, such as after 16 neighbours. A walk that starts at the corner visits the −z, −y and −x cells before its own, so its first neighbours lie mostly on those sides, and a school steered by them drifts towards the corner. The grid’s walk starts at its own range, then the ranges beside it along y, then along z, each from its middle cell and in a random direction, so no side comes first on average:

items per cell

16

stop after

8

Reduce the population or raise the stopping count to shrink the bias from starting in a corner. Arrows magnify mean neighbour offsets sixfold in this one-cell-deep box; the grid stays near zero, while the corner-first walk points toward the corner.

Working in sorted order

After sort, the live items sit at sorted indices 0 to cells.count() - 1, neighbours near each other. A kernel over sorted indices reads its own item with cells.neighbourAt(k), and keeps values it computes, such as a fluid’s pressure, at the same index. cells.index(range, j) gives a neighbour’s sorted index, where a later kernel finds that value. cells.dispatch runs a kernel over the sorted items, in workgroups of grid.WORKGROUP threads, enough for the count:

const crowding = root.createBuffer(d.arrayOf(d.f32, 4096)).$usage('storage');
const crowds = crowding.as('mutable');

const crowd = tgpu.computeFn({
  workgroupSize: [grid.WORKGROUP],
  in: { gid: d.builtin.globalInvocationId },
})(({ gid }) => {
  'use gpu';
  const k = gid.x;
  if (k >= cells.count()) return;

  const me = cells.neighbourAt(k);
  let near = d.f32(0);
  const walk = cells.around(me.position);
  for (let r = d.u32(0); r < grid.RANGES; r++) {
    const range = cells.range(walk, r);
    for (let j = d.u32(0); j < range.count; j++) {
      near += std.max(1 - std.distance(cells.neighbour(range, j).position, me.position) / SIGHT, 0);
    }
  }
  crowds.$[k] = near; // read back as crowds.$[cells.index(range, j)]
});
const crowded = root.pipe(cells.inject()).createComputePipeline({ compute: crowd });

cells.sort(compute);
compute.setPipeline(crowded);
cells.dispatch(compute);

A sort places items in a new order, so values kept in sorted order last until the next sort.

Blocks holding items

A sort also lists the blocks of 4 × 4 × 4 cells that hold items. cells.dispatchBlocks(pass) runs one workgroup of the pass’s pipeline per listed block, in any order, and workgroup w finds its block with cells.block(w), counted in blocks. cells.holds(block) tests whether a block holds items; blocks outside the grid hold none. With margin: n, the sort also lists every block within n blocks of one holding items, once each, so a fluid’s surface is rebuilt only in and around the water, as in SPH Sculpt.

Choosing a binning

binning sets how sort orders the items. Both give the same ranges and blocks.

• grid.counting, the default, counts the items of each cell with atomics and reserves one range per line of cells along x holding items. Its cost follows the item count and the lines holding items. Lines, and the items of one cell, land in any order, so a step need not repeat exactly.
• grid.radix sorts every slot by key with a sorter, eight bits a pass. Its cost follows the capacity and the number of cells, and a sort repeats exactly. Use it when items fill most lines of the box, or when a step must repeat exactly.

A grid holds eight bytes per cell and counting adds eight more.

Following the camera

The box’s low corner is a uniform. move(low) writes it, so a grid that covers the ground around the player follows them across a larger world:

const low = d.vec3f();

frames.create(root, (frame) => {
  low.x = player.x - 20; // a 40 × 40 box centred on the player
  low.z = player.z - 20;
  cells.move(low);

  const compute = frame.encoder.beginComputePass();
  cells.sort(compute); // into the moved box
  compute.end();
});

move uses a queue write. The sort and all walks in the next submit read the updated box. Sort again after a move before the next walk.

Setting up

@typegpu/kit/grid uses the kit’s required @typegpu/noise peer. Getting started shows the setup.

Limits

• A walk costs three randf draws per item and step.
• position and itemOf both read an item’s position.