Broad Phase

An exact collision test between two shapes is expensive, and a scene has far too many pairs to test them all. The broad phase is a cheap filter that throws away pairs that obviously cannot touch. After this lesson your program will take a list of bounding boxes and produce the candidate pairs two different ways: with a spatial grid and with sweep and prune.

Why not test every pair?

n bodies have n * (n - 1) / 2 pairs. At 1,000 bodies that is 499,500 tests per step, 30 million per second at 60 Hz, and the count grows with the square of the scene. Almost all of those pairs are far apart. The broad phase works on bounding boxes only, so each test is a handful of comparisons, and it hands the narrow phase just the pairs that might touch. It is allowed to be wrong in one direction: it may report a pair that does not touch (a false positive, the narrow phase will reject it), but it must never miss a pair that does.

The spatial grid

Cut the world into square cells of side s. A coordinate v lives in cell floor(v / s). A body's box covers every cell from floor(min / s) to floor(max / s) on each axis, so a body can sit in many cells. Two bodies are candidates when they share at least one cell.

Worked trace, s = 4, three bodies with boxes (1,1)-(3,3), (3,1)-(6,3) and (9,9)-(10,10):

body 0: x cells 0..0, y cells 0..0   -> cell (0,0)
body 1: x cells 0..1, y cells 0..0   -> cells (0,0) (1,0)
body 2: x cells 2..2, y cells 2..2   -> cell (2,2)

Cell (0,0) holds bodies 0 and 1, so (0, 1) is a candidate. Body 2 is alone. Out of 3 possible pairs, 1 reaches the narrow phase.

To build the pairs without a hash map: list one entry (cell x, cell y, body) per body per cell it covers, sort the entries, and walk each run of equal cells emitting every pair inside it. Two bodies that share several cells appear in several runs, so sort the pair list and remove duplicates.

Details that decide correctness:

• Negative coordinates. floor(-0.5) is -1, but truncating toward zero gives 0. Many languages truncate when you cast to an integer. Use a real floor, or bodies on the negative side of the origin land in the wrong cell and pairs vanish.
• A box edge exactly on a cell line belongs to the next cell: floor(10 / 10) = 1. The box is treated as covering that cell, which is conservative.
• Cell size. Too small and each body fills many cells; too large and a cell holds many bodies. A size close to the typical body is a good start.

Sweep and prune

Sort the bodies by the left edge of their box. Take them in order; for each body, walk forward through the later bodies and stop as soon as one starts to the right of the current body's right edge, because everything after it starts even further right. For the bodies you did visit, the x intervals overlap, so only a y comparison is left. What remains are pairs whose boxes overlap exactly, with no false positives.

Sweep and prune exploits temporal coherence: between steps the sorted order barely changes, so re-sorting is cheap. Grids need no sorting and handle uniform scenes well; trees (quadtrees, BVH) adapt better to scenes with very different object sizes. Real engines pick one per use case.

Common mistakes

• Truncating instead of flooring negative coordinates.
• Inserting a body only into the cell of its centre. Two bodies straddling a cell border then never meet.
• Reporting a pair once per shared cell instead of once.
• Reporting (1, 0) and (0, 1) as two pairs. Always order a pair as (smaller, larger).
• In the sweep, stopping the inner loop on a y mismatch. Only an x start beyond the current right edge allows the early exit.

Your exercise

The starter reads the scene, calls your two functions and prints the pairs. You write both pair builders. The most likely mistake is the floor of a negative coordinate.