Spatial Hash Grid: Broad-Phase Collision Indexing

Collision Method

Particles

Particle count 300

Speed 1.0×

Grid cell size (× diameter) 2.0×

Live Readouts

Distance checks / frame

–

Brute-force would need

–

Occupied cells

–

Frame time

–

Active collisions this frame

How it works

Every particle is indexed into a uniform 3D grid by truncating its position to a cell coordinate:

cell(p) = ( floor(px/h), floor(py/h), floor(pz/h) )
key = cellX + "," + cellY + "," + cellZ

A hash map from key → [particle indices] is rebuilt every frame in O(n) time. To find who a particle might collide with, the sim only ever inspects the 27 cells around it (its own cell plus its face/edge/corner neighbours) instead of all n−1 other particles:

Brute force:   n(n−1)/2 distance checks  →  O(n²)
Spatial hash:  ≈ n · k / 2 checks        →  O(n)  (k = avg. particles per 27-cell block)

When the grid cell size h is close to the sphere diameter, k stays roughly constant as n grows, so the spatial hash's work grows linearly with particle count while brute force grows quadratically — the same principle a physics engine's broad phase, a database index, or a spatial database (R-tree/octree) all exploit: don't compare everything to everything, only compare things that share a bucket.

Method — switch between the indexed grid and true brute-force O(n²) to see the counter diverge.
Cell size — too small and neighbouring cells miss pairs at the boundary (still corrected for, but with more empty lookups); too large and each cell holds many particles, degrading toward brute force.
Show grid cells — renders every non-empty bucket as a translucent box so you can see the index's buckets directly.

Idle particle Colliding this frame Occupied grid cell

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.