Spatial Hashing

in reviewThis lesson is complete and being validated before release - details may still change.

Spatial hashing

Loading interactive demo…

A scatter of points on a field, a grid of square cells over it, and one query: which points lie within a radius of the probe? Each point is filed under the cell its coordinates floor to, one division per axis. The query probes only the cells the radius can touch, measures the points in them, and keeps those within the radius. Everything in a cell that was never probed is never looked at.Take the tour, or press and explore. Legend:

The panel beside the stage is the real SpatialHash class from the published library executing in your browser, with the current line highlighted.

The probe, ringed, and the cell being probed; its dashed circle is the radius.
A cell the query has probed.
A candidate: a point in a probed cell, measured and found outside the radius.
A hit: a candidate within the radius.
A point filed in the hash but in no probed cell: never measured.
A point not yet filed; cells shade darker the more points they hold.

cells counts the cells probed, candidates the points measured against every point there is, hits the points within the radius, and largest bucket the most points any one cell holds. Drag the probe to query elsewhere.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A cell is a floor division. With cells $s$ wide, a point at $(x, y)$ lives in cell $\big(\lfloor x / s \rfloor,\ \lfloor y / s \rfloor\big)$ . Filing a point is two divisions and one append to that cell's bucket, $O(1)$ , and nothing is compared with anything. The buckets sit in a map keyed by the cell's column and row, so a cell nobody is in costs nothing and the field has no edges: a point at $(-3, 400)$ files as happily as one in the middle.

A query probes a block of cells. The points within $r$ of a probe $q$ can only lie in cells between $\lfloor (q_x - r)/s \rfloor$ and $\lfloor (q_x + r)/s \rfloor$ on each axis, a block of about $(2r/s + 1)^2$ cells. The query looks each one up, measures every point in them, and keeps those within $r$ . The cells cover a square and the answer is a circle, so a point in a probed cell's corner can be measured and dropped, but no point within $r$ is ever missed: the hash's answer equals the brute-force one, in fewer checks.

What it costs. A query is $O(c + k)$ for $c$ cells probed and $k$ candidates measured, against $O(n)$ for measuring every point. For $n$ points spread evenly over an area $A$ , the candidates number about $n \cdot (2r + 2s)^2 / A$ , which does not grow with $n$ at a fixed density: that is the near-constant query a simulation wants. The cell size trades the two terms. At $s \ll r$ the block is many cells, most of them empty lookups; at $s \gg r$ one cell holds far more points than the circle does and the query measures them all. $s \approx r$ probes a $3 \times 3$ block and measures about $9 s^2 / \pi r^2 \approx 3$ times the points the circle holds.

Where it degrades. The argument assumes an even spread. Gather the points into a crowd, and one cell holds most of them; a query in the crowd measures nearly everything and the hash is back to $O(n)$ , a long collision chain in a hash table's terms. The largest bucket readout is the warning sign. A quadtree, the next lesson, splits a crowded cell further and a sparse one not at all.

Many queries. A flock asks the question once per boid per tick. Rebuilding the hash is $O(n)$ and each of the $n$ queries is near constant, so a tick is near $O(n)$ instead of $O(n^2)$ ; the boids lesson's cost note is this lesson. A body with extent, a circle or a box, is filed under every cell its bounds overlap, and a pair found in any shared cell goes on to the narrow test.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The grid is a Map, not an array: a cell is a string key made of its column and row, so the plane is unbounded and an empty region holds no buckets at all. cellOf is the only place the cell size is used, and it is a floor, so negative coordinates file correctly (a truncation would put $-0.5$ in cell $0$ ).
query floors the corners of the search square, probe minus and plus the radius, and walks the cells between them row by row. It never asks whether a cell is empty first: the lookup returns an empty list and the loop over it does nothing, which is why an empty probe costs one lookup.
A candidate is measured once, with Math.hypot, and the comparison is <=, so a point exactly at the radius is a hit; the stage's circle is drawn to the same rule.
near is the brute-force check, a static the tests hold every query against and the stage uses for the candidates readout's denominator. A hash that disagreed with it would be wrong, not fast.
Every bucket, probe, candidate, and hit is traced, which is the whole cost of the query laid out in order; the trace is short because the query is.

Simulations of many bodies all ask the same question every tick: which of these things are near this one? Measuring every pair is quadratic, and molecular dynamics hit the wall first. In 1973 Quentrec and Brot cut the box into cells as wide as the interaction range and compared a particle only with those in its own and the neighbouring cells, the cell list every particle code since has used. Geometry calls the idea bucketing, graphics the uniform grid. Hashing the cell coordinates instead of allocating a cell array let the grid be sparse and unbounded, the form games and physics engines use.

1973Bernard Quentrec and Claude Brot - Publish the cell list for molecular dynamics: particles filed into cells the width of the cutoff radius, so each one is compared only with the particles in the twenty-seven cells around it.source
1980Jon Bentley, Bruce Weide, and Andrew Yao - Analyse bucketing for closest-point problems: for points spread roughly evenly, a grid of cells answers nearest-neighbour queries in constant expected time.source
2003Matthias Teschner and colleagues - Present 'Optimized Spatial Hashing for Collision Detection of Deformable Objects': cell coordinates hashed into a fixed table with three large primes, so a deforming mesh needs no bounded grid.source
2007Scott Lembcke - Ships the Chipmunk physics engine with a spatial hash as its broad phase, a choice many 2D games inherited through the engines built on it.source

Used today

Broad-phase collision - Bodies are filed by the cells their bounds cover; only bodies sharing a cell are tested for contact.
Flocking and crowds - A boid's neighbours within its radius come from its cell and the ring around it, which takes the flock from quadratic to near linear.
Particle fluids - Smoothed-particle hydrodynamics sums over neighbours inside a kernel radius; the hash makes that sum affordable for a million particles.
Molecular dynamics - Cell lists and Verlet neighbour lists are how a simulation of millions of atoms finds the pairs within the cutoff.

points24

cell size2.0

radius2.0

layout

cells: 9 of 160 probed
candidates: 1 of 24 points
hits: 1
largest bucket: 3

spatial-hash.ts

import type { Tracer } from "../trace";/** A point on the plane; a Vec2 will do. */export interface SpatialPoint {  readonly x: number;  readonly y: number;}/** One cell of the grid, by its integer column and row. */export interface SpatialCell {  readonly cx: number;  readonly column: number;  readonly cy: number;  readonly row: number;}/** A point the query reached and how far away it was. */export interface SpatialHit {  readonly index: number;  readonly distance: number;}/** * A spatial hash: the plane cut into square cells of one size, each * cell a bucket of the points inside it, keyed by its integer column * and row. Inserting a point is one floor division per axis; finding * the points within a radius of a place probes only the cells the * radius touches and measures the points in them, so a query costs * the candidates in those cells rather than every point there is. * The grid is a map, not an array, so an empty region costs nothing * and the plane has no edges. A cell as wide as the radius probes at * most nine cells; a far smaller cell probes many empty ones, a far * larger one measures far more candidates than hits. * * Time: O(1) to insert; a query is O(cells probed + candidates), near * O(1) for a sparse, even scatter and O(n) for n points in one cell. * Space: O(n + occupied cells). */export class SpatialHash {  private readonly buckets = new Map<string, number[]>();  private readonly points: SpatialPoint[] = [];  constructor(    readonly cellSize: number,    private readonly tracer?: Tracer,  ) {    if (!(cellSize > 0) || !Number.isFinite(cellSize)) {      throw new RangeError(`cellSize must be positive, got ${cellSize}`);    }  }  /** How many points are in the hash. */  get size(): number {    return this.points.length;  }  /** The cell a point falls in: the floor of each coordinate over the cell size. */  cellOf(point: SpatialPoint): SpatialCell {    return { cx: Math.floor(point.x / this.cellSize), cy: Math.floor(point.y / this.cellSize) };    return { column: Math.floor(point.x / this.cellSize), row: Math.floor(point.y / this.cellSize) };  }  /** Every occupied cell with how many points it holds, in insertion order of first occupancy. */  cells(): { cell: SpatialCell; count: number }[] {    return [...this.buckets.entries()].map(([key, ids]) => ({ cell: SpatialHash.parse(key), count: ids.length }));    return [...this.buckets.entries()].map(([key, bucket]) => ({ cell: SpatialHash.parse(key), count: bucket.length }));  }  /** The point at an index. */  at(index: number): SpatialPoint {    const point = this.points[index];    if (!point) throw new RangeError(`no point ${index}`);    return point;  }  /** Files a point under its cell; returns its index. */  insert(point: SpatialPoint): number {    const index = this.points.length;    this.points.push(point);    const { cx, cy } = this.cellOf(point);    const { column, row } = this.cellOf(point);    const key = SpatialHash.key(cx, cy);    const key = SpatialHash.key(column, row);    const ids = this.buckets.get(key) ?? [];    const bucket = this.buckets.get(key) ?? [];    ids.push(index);    bucket.push(index);    this.buckets.set(key, ids);    this.buckets.set(key, bucket);    // ▸ file the point under the cell its coordinates floor to    this.tracer?.emit("bucket", { index, x: point.x, y: point.y, cx, cy, size: ids.length });    this.tracer?.emit("bucket", { index, x: point.x, y: point.y, column, row, size: bucket.length });    return index;  }  /**   * The points within `radius` of `point`, by index with their   * distances, probing only the cells the radius reaches. Candidates   * come out in cell order, row by row.   */  query(point: SpatialPoint, radius: number): SpatialHit[] {    if (!(radius >= 0)) throw new RangeError(`radius must not be negative, got ${radius}`);    const low = this.cellOf({ x: point.x - radius, y: point.y - radius });    const high = this.cellOf({ x: point.x + radius, y: point.y + radius });    const hits: SpatialHit[] = [];    let probed = 0;    let candidates = 0;    for (let cy = low.cy; cy <= high.cy; cy++) {    for (let row = low.row; row <= high.row; row++) {      for (let cx = low.cx; cx <= high.cx; cx++) {      for (let column = low.column; column <= high.column; column++) {        const ids = this.buckets.get(SpatialHash.key(cx, cy)) ?? [];        const bucket = this.buckets.get(SpatialHash.key(column, row)) ?? [];        probed += 1;        // ▸ probe one cell the radius touches, row by row        this.tracer?.emit("probe", { cx, cy, size: ids.length, probed });        this.tracer?.emit("probe", { column, row, size: bucket.length, probed });        for (const index of ids) {        for (const index of bucket) {          const p = this.points[index]!;          const stored = this.points[index]!;          const d = Math.hypot(p.x - point.x, p.y - point.y);          const howFar = Math.hypot(stored.x - point.x, stored.y - point.y);          const within = d <= radius;          const within = howFar <= radius;          candidates += 1;          // ▸ measure a point in the cell against the probe          this.tracer?.emit("candidate", { index, x: p.x, y: p.y, distance: d, within, candidates });          this.tracer?.emit("candidate", { index, x: stored.x, y: stored.y, distance: howFar, within, candidates });          if (within) {            hits.push({ index, distance: d });            hits.push({ index, distance: howFar });            // ▸ within the radius: keep it            this.tracer?.emit("hit", { index, distance: d, hits: hits.length });            this.tracer?.emit("hit", { index, distance: howFar, hits: hits.length });          }        }      }    }    return hits;  }  /** The same answer by measuring every point: the check a hash is judged against. */  static near(points: readonly SpatialPoint[], point: SpatialPoint, radius: number): SpatialHit[] {    const hits: SpatialHit[] = [];    points.forEach((p, index) => {    points.forEach((stored, index) => {      const distance = Math.hypot(p.x - point.x, p.y - point.y);      const distance = Math.hypot(stored.x - point.x, stored.y - point.y);      if (distance <= radius) hits.push({ index, distance });    });    return hits;  }  private static key(cx: number, cy: number): string {  private static key(column: number, row: number): string {    return `${cx},${cy}`;  }  private static parse(key: string): SpatialCell {    const [cx, cy] = key.split(",").map(Number);    const [column, row] = key.split(",").map(Number);    return { cx: cx ?? 0, cy: cy ?? 0 };    return { column: column ?? 0, row: row ?? 0 };  }}

hits =: 1
candidates =: 1
probed =: 9
every point =: 24

1 hit from 1 candidate in 9 cells probed, where measuring every point would have taken 24 checks. 21 cells hold anything at all.

import type { Tracer } from "../trace";/** A point on the plane; a Vec2 will do. */export interface SpatialPoint { readonly x: number; readonly y: number;}/** One cell of the grid, by its integer column and row. */export interface SpatialCell { readonly cx: number; readonly column: number; readonly cy: number; readonly row: number;}/** A point the query reached and how far away it was. */export interface SpatialHit { readonly index: number; readonly distance: number;}/** * A spatial hash: the plane cut into square cells of one size, each * cell a bucket of the points inside it, keyed by its integer column * and row. Inserting a point is one floor division per axis; finding * the points within a radius of a place probes only the cells the * radius touches and measures the points in them, so a query costs * the candidates in those cells rather than every point there is. * The grid is a map, not an array, so an empty region costs nothing * and the plane has no edges. A cell as wide as the radius probes at * most nine cells; a far smaller cell probes many empty ones, a far * larger one measures far more candidates than hits. * * Time: O(1) to insert; a query is O(cells probed + candidates), near * O(1) for a sparse, even scatter and O(n) for n points in one cell. * Space: O(n + occupied cells). */export class SpatialHash { private readonly buckets = new Map<string, number[]>(); private readonly points: SpatialPoint[] = []; constructor( readonly cellSize: number, private readonly tracer?: Tracer, ) { if (!(cellSize > 0) || !Number.isFinite(cellSize)) { throw new RangeError(`cellSize must be positive, got ${cellSize}`); } } /** How many points are in the hash. */ get size(): number { return this.points.length; } /** The cell a point falls in: the floor of each coordinate over the cell size. */ cellOf(point: SpatialPoint): SpatialCell { return { cx: Math.floor(point.x / this.cellSize), cy: Math.floor(point.y / this.cellSize) }; return { column: Math.floor(point.x / this.cellSize), row: Math.floor(point.y / this.cellSize) }; } /** Every occupied cell with how many points it holds, in insertion order of first occupancy. */ cells(): { cell: SpatialCell; count: number }[] { return [...this.buckets.entries()].map(([key, ids]) => ({ cell: SpatialHash.parse(key), count: ids.length })); return [...this.buckets.entries()].map(([key, bucket]) => ({ cell: SpatialHash.parse(key), count: bucket.length })); } /** The point at an index. */ at(index: number): SpatialPoint { const point = this.points[index]; if (!point) throw new RangeError(`no point ${index}`); return point; } /** Files a point under its cell; returns its index. */ insert(point: SpatialPoint): number { const index = this.points.length; this.points.push(point); const { cx, cy } = this.cellOf(point); const { column, row } = this.cellOf(point); const key = SpatialHash.key(cx, cy); const key = SpatialHash.key(column, row); const ids = this.buckets.get(key) ?? []; const bucket = this.buckets.get(key) ?? []; ids.push(index); bucket.push(index); this.buckets.set(key, ids); this.buckets.set(key, bucket); // ▸ file the point under the cell its coordinates floor to this.tracer?.emit("bucket", { index, x: point.x, y: point.y, cx, cy, size: ids.length }); this.tracer?.emit("bucket", { index, x: point.x, y: point.y, column, row, size: bucket.length }); return index; } /** * The points within `radius` of `point`, by index with their * distances, probing only the cells the radius reaches. Candidates * come out in cell order, row by row. */ query(point: SpatialPoint, radius: number): SpatialHit[] { if (!(radius >= 0)) throw new RangeError(`radius must not be negative, got ${radius}`); const low = this.cellOf({ x: point.x - radius, y: point.y - radius }); const high = this.cellOf({ x: point.x + radius, y: point.y + radius }); const hits: SpatialHit[] = []; let probed = 0; let candidates = 0; for (let cy = low.cy; cy <= high.cy; cy++) { for (let row = low.row; row <= high.row; row++) { for (let cx = low.cx; cx <= high.cx; cx++) { for (let column = low.column; column <= high.column; column++) { const ids = this.buckets.get(SpatialHash.key(cx, cy)) ?? []; const bucket = this.buckets.get(SpatialHash.key(column, row)) ?? []; probed += 1; // ▸ probe one cell the radius touches, row by row this.tracer?.emit("probe", { cx, cy, size: ids.length, probed }); this.tracer?.emit("probe", { column, row, size: bucket.length, probed }); for (const index of ids) { for (const index of bucket) { const p = this.points[index]!; const stored = this.points[index]!; const d = Math.hypot(p.x - point.x, p.y - point.y); const howFar = Math.hypot(stored.x - point.x, stored.y - point.y); const within = d <= radius; const within = howFar <= radius; candidates += 1; // ▸ measure a point in the cell against the probe this.tracer?.emit("candidate", { index, x: p.x, y: p.y, distance: d, within, candidates }); this.tracer?.emit("candidate", { index, x: stored.x, y: stored.y, distance: howFar, within, candidates }); if (within) { hits.push({ index, distance: d }); hits.push({ index, distance: howFar }); // ▸ within the radius: keep it this.tracer?.emit("hit", { index, distance: d, hits: hits.length }); this.tracer?.emit("hit", { index, distance: howFar, hits: hits.length }); } } } } return hits; } /** The same answer by measuring every point: the check a hash is judged against. */ static near(points: readonly SpatialPoint[], point: SpatialPoint, radius: number): SpatialHit[] { const hits: SpatialHit[] = []; points.forEach((p, index) => { points.forEach((stored, index) => { const distance = Math.hypot(p.x - point.x, p.y - point.y); const distance = Math.hypot(stored.x - point.x, stored.y - point.y); if (distance <= radius) hits.push({ index, distance }); }); return hits; } private static key(cx: number, cy: number): string { private static key(column: number, row: number): string { return `${cx},${cy}`; } private static parse(key: string): SpatialCell { const [cx, cy] = key.split(",").map(Number); const [column, row] = key.split(",").map(Number); return { cx: cx ?? 0, cy: cy ?? 0 }; return { column: column ?? 0, row: row ?? 0 }; }}