Spatial hash grid for uniform distributions and fast neighbor lookups
npm install @gridworkjs/hashgrid
A particle simulation where thousands of uniform-sized particles need fast collision checks every frame:
import { createHashGrid } from '@gridworkjs/hashgrid'
import { point, bounds } from '@gridworkjs/core'
// particles are ~10 units across, so a 20-unit cell size works well
const particles = createHashGrid(p => bounds(p.position), { cellSize: 20 })
particles.insert({ id: 'a', position: point(10, 20), vx: 1, vy: 0 })
particles.insert({ id: 'b', position: point(15, 22), vx: -1, vy: 1 })
const c = { id: 'c', position: point(300, 400), vx: 0, vy: -1 }
particles.insert(c)
// each frame, check for collisions near each particle
const nearby = particles.search({ minX: 5, minY: 15, maxX: 25, maxY: 30 })
// => [particle a, particle b] - fast O(1) cell lookup
// find the closest neighbor for attraction/repulsion forces
particles.nearest({ x: 10, y: 20 }, 1)
// => [particle b]
// particle leaves the simulation (by reference)
particles.remove(c)Hash grids are ideal when your data is uniformly distributed and items are roughly the same size. They offer O(1) cell lookups, making them excellent for collision detection, particle systems, and game engines.
If your data is clustered or varies widely in size, consider @gridworkjs/quadtree or @gridworkjs/rtree instead.
The cellSize parameter controls the width and height of each grid cell. For best performance:
- Set
cellSizeto roughly the size of your items or the typical query range - Too small: items span many cells, increasing memory and insert cost
- Too large: cells contain many items, reducing search selectivity
Creates a new hash grid. The accessor function maps each item to its bounding box ({ minX, minY, maxX, maxY }). Use bounds() from @gridworkjs/core to convert geometries.
The cellSize option is required.
Returns a spatial index implementing the gridwork protocol.
Adds an item to the grid. The item is placed into every cell its bounding box overlaps.
Removes an item by identity (===). Returns true if found and removed.
Returns all items whose bounds intersect the query. Accepts bounds objects or geometry objects (point, rect, circle).
Returns the k nearest items to the given point, sorted by distance. Defaults to k=1. Accepts { x, y } or a point geometry.
Removes all items from the grid.
Number of items in the grid.
Bounding box of all items, or null if empty.
MIT