Checking every pair of objects is O(n²) and too slow. Bounding volumes (AABB, circles) give cheap approximate tests, and the broad phase quickly rules out pairs that cannot possibly collide.
Exact shape-vs-shape tests are expensive, so you wrap each object in a simple bounding volume — a circle/sphere or an axis-aligned bounding box (AABB) — and test those first. If the cheap bounds do not overlap, the real shapes cannot collide, so you skip the expensive test. Bounding volumes are the first line of every collision system.
# circle vs circle: overlap if distance < sum of radii (compare SQUARED)
def circles_overlap(c1, r1, c2, r2):
dx, dy = c1[0]-c2[0], c1[1]-c2[1]
return dx*dx + dy*dy <= (r1 + r2) ** 2 # no sqrt needed
# AABB vs AABB: overlap if they overlap on BOTH axes
def aabb_overlap(a, b): # box = (min_x, min_y, max_x, max_y)
return (a[0] <= b[2] and a[2] >= b[0] and
a[1] <= b[3] and a[3] >= b[1])
print(circles_overlap((0,0), 1, (1.5,0), 1)) # True
print(aabb_overlap((0,0,2,2), (1,1,3,3))) # True
# cheap approximate bounds first; only do the exact shape test if these overlap.Testing every object against every other is O(n²) — a thousand objects means half a million pair checks per frame, which does not scale. The broad phase is a fast pre-pass that produces only the pairs that might collide, so the expensive narrow phase runs on a handful of candidates instead of all pairs. Splitting collision into broad and narrow phases is what makes large scenes feasible.
Naive: test every pair -> O(n²)
1,000 objects -> ~500,000 pair tests EVERY frame. Doesn't scale.
Two-phase collision detection:
BROAD PHASE fast, approximate: find pairs that MIGHT collide
(using bounding volumes + spatial structures, lesson 6)
-> outputs a short list of candidate pairs
NARROW PHASE exact shape-vs-shape test on those few candidates (lessons 3-4)
The broad phase turns O(n²) into ~O(n log n) or O(n) by ruling out the vast
majority of pairs cheaply. This split is the key to scalable physics.A simple, effective broad-phase technique is sweep and prune: sort object bounds along an axis, then sweep through — two objects can only collide if their intervals overlap on that axis, so you only compare neighbors. It exploits temporal coherence (objects move little between frames) to stay fast. It is a great illustration of how sorting turns an all-pairs problem into a near-linear one.
def sweep_and_prune_x(boxes):
# boxes: list of (id, min_x, max_x). Sort by min_x, then sweep.
boxes = sorted(boxes, key=lambda b: b[1])
candidates = []
active = []
for box in boxes:
_id, min_x, max_x = box
# drop actives whose max_x is behind this box's min_x (can't overlap)
active = [a for a in active if a[2] >= min_x]
for a in active:
candidates.append((a[0], _id)) # overlapping on X -> candidate pair
active.append(box)
return candidates
print(sweep_and_prune_x([(1,0,2),(2,1,3),(3,5,6)])) # [(1, 2)]
# sorting + sweeping compares only neighbors -> near-linear broad phase.Fast-moving objects can tunnel — pass entirely through a thin wall between two frames because they were on one side, then the other, never overlapping on any single step. Continuous collision detection (CCD) sweeps the object’s shape along its path and finds the first time of impact, catching these misses. You reserve CCD for fast objects (bullets) because it is costlier than discrete tests.
The tunneling problem:
frame N: bullet is LEFT of a thin wall
frame N+1: bullet is RIGHT of it
-> at no single step did they OVERLAP -> discrete collision MISSES it.
Continuous Collision Detection (CCD):
sweep the moving shape along its path this step and find the FIRST time of
impact (a "time of impact" in [0, 1]). Catches the pass-through.
Cost: CCD is more expensive than a discrete test, so enable it only for FAST,
important objects (bullets, fast projectiles) — not everything.