Spatial partitioning
Only test things that are near each other.
Checking every object against every other object costs n squared: 500 bullets means about 125,000 checks a frame. Dropping everything into grid cells (or a quadtree, or a BVH) and only checking neighbours cuts that to a few thousand, which is how games manage crowds, bullets and particles.
Try this: Raise the object count with the grid off and watch the checks explode. Turn the grid on with G.
Same collisions found either way; only the work changes.
Prompt bit
Works for 2D or 3D in any engine (Unity, Unreal, Godot, web). Paste the short one for a quick fix, or the detailed one when you want it done properly.
Add a uniform grid broadphase: put each object in cells sized about twice its radius, test only pairs in the same or neighbouring cells, rebuild the grid every 0.016 s physics step, and insert objects bigger than a cell into every cell they overlap.
Add spatial partitioning to collision and proximity queries (2D or 3D; engines already have a broadphase for physics bodies, so use this for your own systems such as bullets, boids, or "enemies near the player"). Start with a uniform grid: cell size about 2x the typical object radius. Each frame, clear the grid and insert each object into the cell that contains its centre (or every cell its bounds overlap if it is larger than a cell). For each object, test only objects in its own and the 8 (2D) or 26 (3D) neighbouring cells, and test each pair once (only when idA < idB). Store cells in a hash map keyed by integer cell coordinates so the world can be unbounded. For very uneven density use a quadtree, octree, or BVH instead. Show a debug counter of pair checks per frame and compare against n*(n-1)/2.
Where it's used
- Bullet hells and shooters: thousands of bullets vs enemies
- RTS and crowds: unit separation and nearby queries
- Boids and particles: neighbour searches
- Open worlds: what is near the player
- Physics engines: the broadphase before exact tests
Common mistakes
Cells far too small or far too big (both lose the benefit), forgetting big objects that span several cells, testing each pair twice, and rebuilding complex trees every frame when a grid would do.
Writing this with an AI assistant? See our best AI coding assistants for game developers.
Missing a concept? Request one.
