Collision Detection

Once your game has multiple moving things, you need to know when they touch. The most fundamental shape pair:

AABB (Axis-Aligned Bounding Box)

A box defined by (x, y, w, h) with sides parallel to the axes. Cheap to test:

Four comparisons; no trig; SIMD-friendly. The "or" chain is the separating axis theorem specialized for axis-aligned boxes: if any axis can fit a gap between them, they don't overlap.

Broadphase vs narrowphase

Brute-force pairwise tests are O(n^2). With 1000 entities that's half a million tests per frame.

Broadphase prunes obvious non-collisions cheaply:

• Spatial hash: bucket entities by grid cell; only test pairs in the same bucket.
• Quadtree / octree: recursive AABB subdivision; query a region in O(log n) on average.
• Sweep and prune (SAP): sort intervals on each axis; collisions show up as adjacent pairs.

Narrowphase does the precise per-pair test (AABB-AABB, circle-circle, AABB-circle, polygon-polygon via SAT or GJK).

Tunneling

If a ball moves 100 units per frame but the wall is 1 unit thick, a discrete test sees the ball before and after the wall — never inside it. The fix:

• Continuous collision detection (CCD): solve for the time-of-impact along the swept volume between frames.
• Engines like Box2D and Bullet expose CCD as an option for fast-moving bodies (bullets, projectiles).

The Practice problem

You'll register AABBs and emit all overlapping pairs. This is the heart of any 2D physics engine's broadphase + narrowphase step.