Broad Phase

Naive: check every pair of bodies for collision. O(N²) — for 1000 bodies, 1M checks per frame.

Broad phase: cheaply prune non-colliding pairs.

Spatial hash grid:

Divide world into cells (e.g., 64x64).
Each body inserted into cells it overlaps.
Check pairs only within same cell.

Each pair from same cell: still need narrow-phase check.

Cell size tuning:

• Too small: each body in many cells, lots of duplicate checks.
• Too large: many bodies per cell, defeating purpose.
• Rule: cell_size ≈ avg body size.

Sort and sweep (sweep and prune):

• Sort bodies by min_x.
• Walk: for each pair where a.max_x ≥ b.min_x, do narrow check.

O(N log N + K) where K is pair count. Effective for moderate scenes.

Quad tree (2D BSP):

• Recursive 4-way subdivision.
• Insert body in node where it fits.
• Test only nearby quadrants.

BVH (Bounding Volume Hierarchy):

• Tree of AABBs.
• Each leaf = one body.
• Traversal: descend if AABB overlaps query.
• Used by Bullet, PhysX.

Engines combine: broad-phase (cheap reject) + narrow-phase (precise check).

Modern games: 10000+ bodies at 60 Hz. Broad-phase is critical.