Spatial Hash Grid: Broad-Phase Collision Indexing (2D)

Collision Method

Particles

Particle count 500

Speed 1.0×

Grid cell size (× diameter) 2.0×

Live Readouts

Candidate pairs / frame

–

Brute-force would need

–

Occupied cells

–

Frame time

–

Speedup vs. brute force

–

Active collisions this frame

How it works

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

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

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 9 cells around it (its own cell plus its 8 neighbours) instead of all n−1 other particles — that's the broad phase. Only the pairs that survive the broad phase get a real narrow-phase circle-circle distance test:

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

When the grid cell size h is close to the circle 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/quadtree) 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 square so you can see the index's buckets directly.
Hover a particle — highlights the exact 9 cells the broad phase queries for it, and every candidate it was actually tested against this frame.

Idle particle Colliding this frame Occupied grid cell Queried by hovered particle