Broad phase: spatial grids and quadtrees for many collisions

Checking whether two objects touch is fast. The problem arises when there are many of them. With 10 objects there are 45 possible pairs; with 100 there are 4,950; with 1,000 almost half a million. In a shooter full of bullets or a simulation with many particles, comparing everything with everything every frame quickly becomes unsustainable. The solution is to split the work into two phases.

Broad phase and narrow phase

• The broad phase cheaply discards pairs that cannot collide because they are too far apart, producing a reduced list of candidate pairs.
• The narrow phase applies the precise test, for example AABB versus AABB or circle versus circle, only to those candidates.

The number of pairs grows with the square of the number of objects: n × (n − 1) / 2. A good broad phase reduces this cost to something much closer to linear growth, provided the objects are spread out in space rather than all piled up in the same spot.

The uniform spatial grid

This is the simplest technique and it is surprisingly effective. You divide the world into square cells of fixed size and register each object in the cells it occupies. Two objects can only collide if they share at least one cell.

cell_size = 64

for each object o:
    cx0 = floor(o.x / cell_size)
    cx1 = floor((o.x + o.width) / cell_size)
    cy0 = floor(o.y / cell_size)
    cy1 = floor((o.y + o.height) / cell_size)
    for cx from cx0 to cx1, cy from cy0 to cy1:
        grid[cx, cy].add(o)

for each non-empty cell:
    compare the objects in the cell with each other

Choosing the cell size

Cell size is the decisive parameter:

• cells that are too small: each object occupies many cells, insertions and duplicates increase;
• cells that are too large: too many objects per cell, and you are back to near-complete comparison.

A practical rule is to use cells about as large as the typical object or a little bigger, for example one to two times the size of the most common enemies.

Avoiding duplicate checks

An object straddling four cells would be compared with the same neighbour up to four times. You can store a set of pairs already checked this frame, or compare a pair only in the cell containing, say, the top-left corner of their intersection.

The quadtree

A quadtree divides space adaptively. You start with a node covering the whole world; when it contains more than a certain number of objects, it is split into four quadrants, and so on recursively up to a maximum depth.

Its advantage over the uniform grid is that it adapts to density: crowded areas are subdivided finely, empty areas remain a single large node. It is useful when objects vary greatly in size or cluster in a few areas of the map.

The downsides are greater complexity and the update cost when objects move a lot: it is often better to rebuild the tree from scratch every frame, which with well-written structures stays reasonably fast. Objects straddling quadrant boundaries need careful handling, for example by keeping them in the parent node.

Sweep and prune

This technique relies on one observation: two AABBs can only overlap if their projections on the x axis overlap. You sort objects by their left edge and walk the list while maintaining a set of «active» objects:

1. sort objects by minimum x;
2. for each object, remove from the active set those whose maximum x is less than its minimum x;
3. the remaining active objects are candidates and must be checked with the full test;
4. add the current object to the active set.

Because objects move little from one frame to the next, the list is almost already sorted, and an insertion sort fixes it very quickly. It works well when objects are spread along the chosen axis, as in a horizontally scrolling shooter.

Which one to choose

For most independent 2D games a well-sized uniform grid is the best choice: simple to write, easy to verify and fast. Professional physics engines often use more refined structures, such as dynamic bounding volume trees, but the principle is the same.

Further useful optimisations

• Collision groups: the player's bullets do not need to be compared with each other or with the player. Filtering by category removes many pairs before the broad phase even starts.
• Separate static objects: walls and platforms do not move; they can go into a structure built just once.

In short

• Comparing every pair costs an amount that grows with the square of the number of objects.
• The broad phase quickly discards distant pairs, the narrow phase checks those left.
• A uniform grid is simple and effective if the cells have the right size.
• Quadtrees and sweep and prune suit particular object distributions.
• Collision groups and static structures reduce the work even further.