@zakkster/lite-spatial

Zero-GC spatial hash grid with linked-list chaining, epoch deduplication, box + radius queries, and O(1) insert/remove. Zero dependencies.

Why lite-spatial?

| Feature | lite-spatial | rbush | spatial-hash | p2.js | |---|---|---|---|---| | Zero-GC | Yes (TypedArrays) | No (objects) | No | No | | Insert | O(1) prepend | O(log n) | O(1) | O(1) | | Remove | O(k) cell | O(log n) | O(k) | O(k) | | Deduplication | Epoch marker | N/A | Manual | N/A | | Query output | Pre-allocated buffer | New array | New array | New array | | SoA aligned | Yes (id-indexed) | No | No | No | | Dependencies | 0 | 0 | 0 | 0 |

Installation

npm install @zakkster/lite-spatial

Quick Start

import { SpatialGrid } from '@zakkster/lite-spatial';

const grid = new SpatialGrid(800, 600, 64, 10000);
const queryBuf = new Int32Array(256);

// Per frame:
grid.clear();
for (let i = 0; i < entityCount; i++) grid.insert(i, x[i], y[i]);

// Query neighbors
const count = grid.queryBox(player.x - 100, player.y - 100, player.x + 100, player.y + 100, queryBuf);
for (let i = 0; i < count; i++) {
    const id = queryBuf[i];
    // narrow-phase collision check with entity id
}

How It Works

Linked-List Chaining

Each grid cell stores the head ID of a linked list. insert() prepends in O(1):

head[cell] → id3 → id1 → id0 → -1

No arrays-of-arrays, no push/pop, no GC. Just Int32Array pointer chasing.

Epoch Deduplication

When entities span multiple cells, queryBox can return duplicates. The dedupe flag uses a Uint8Array marker with epoch incrementing — the seen buffer is only flushed every 255 queries, not every call.

const count = grid.queryBox(0, 0, 800, 600, buf, true); // dedupe=true

Pre-Allocated Output Buffer

Query results write into a caller-owned Int32Array. No array allocation per query. Buffer overflow is handled by early-exit — the grid stops writing when the buffer is full and returns the count.

Full API

new SpatialGrid(width, height, cellSize, capacity)

| Param | Description | |---|---| | width/height | World dimensions (px) | | cellSize | Bucket size. Tune to ~2× your largest entity. | | capacity | Max entity count. Aligns with SoA pool size. |

Methods

| Method | Complexity | Description | |---|---|---| | .clear() | O(cells) | Reset all heads to -1. Call once per frame. | | .insert(id, x, y) | O(1) | Linked-list prepend. Out-of-bounds ignored. | | .remove(id, x, y) | O(k) | Unlink from cell. k = items in that cell. | | .queryBox(minX, minY, maxX, maxY, out, dedupe?) | O(cells × k) | Fill out buffer with IDs. Returns count. | | .queryRadius(x, y, r, out, dedupe?) | O(cells × k) | Box approximation of circle query. | | .destroy() | O(1) | Null all typed arrays. |

Recipes

import { SpatialGrid } from '@zakkster/lite-spatial';
import { testPolygonPolygon, translatePoly } from '@zakkster/lite-sat';

const grid = new SpatialGrid(800, 600, 64, 1000);
const buf = new Int32Array(64);
const mtv = new Float32Array(2);

// Per frame:
grid.clear();
for (let i = 0; i < count; i++) grid.insert(i, x[i], y[i]);

for (let i = 0; i < count; i++) {
    const n = grid.queryRadius(x[i], y[i], 32, buf);
    for (let j = 0; j < n; j++) {
        const other = buf[j];
        if (other <= i) continue;
        if (testPolygonPolygon(polys[i], polys[other], mtv)) {
            translatePoly(polys[i], mtv[0] * 0.5, mtv[1] * 0.5);
            translatePoly(polys[other], -mtv[0] * 0.5, -mtv[1] * 0.5);
        }
    }
}

grid.clear();
for (const a of agents) grid.insert(a.id, a.x, a.y);

for (const a of agents) {
    const n = grid.queryRadius(a.x, a.y, 60, buf, true);
    // separation, alignment, cohesion with buf[0..n-1]
}

License

MIT — Part of the @zakkster ecosystem.