DailyRNG
Login
Advanced

Finding collisions without testing every pair

Testing every object against every object grows with the square of the count. A grid of cells turns it into a lookup: an object checks only the objects sharing its cells, and the cost grows with the number of objects instead.

What you will see

The grid number should be far smaller. If it is close, the cell size is wrong.

About 1 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Put objects in a grid

1

Write the cell key

printf 'const CELL = 64; function key(x, y) { return ((x / CELL) | 0) + "," + ((y / CELL) | 0); } ' | tee game/grid.js

Before you run it, say out loud what it will print. Then open the answer.

What it prints
One string per cell. Negative coordinates must give distinct keys, which the bitwise or handles.
2

Insert covering all cells

printf 'function insert(o) { for (let cx = (o.x / CELL) | 0; cx <= ((o.x + o.w) / CELL | 0); cx++) for (let cy = (o.y / CELL) | 0; cy <= ((o.y + o.h) / CELL | 0); cy++) { const k = cx + "," + cy; (g[k] = g[k] || []).push(o); } } ' | tee -a game/grid.js

Before you run it, say out loud what it will print. Then open the answer.

What it prints
A wide object lands in every cell it overlaps, not just its centre.
3

Query the candidates

printf 'function query(o) { const out = new Set(); for (let cx = (o.x / CELL) | 0; cx <= ((o.x + o.w) / CELL | 0); cx++) for (let cy = (o.y / CELL) | 0; cy <= ((o.y + o.h) / CELL | 0); cy++) (g[cx + "," + cy] || []).forEach(x => out.add(x)); return [...out]; } ' | tee -a game/grid.js

Before you run it, say out loud what it will print. Then open the answer.

What it prints
A set with the object itself in it. Remove self before testing pairs.
4

Compare the counts

print the number of pair tests with the grid and the number without it for the same object count

Before you run it, say out loud what it will print. Then open the answer.

What it prints
The grid number should be far smaller. If it is close, the cell size is wrong.
Do not insert an object into only its centre cell. A straddling pair is then never tested and the collision is missed at random.

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Objects to a small candidate set
1 Clear the grid
↓
2 Insert each object into every cell it covers
↓
3 Query the cells of one object
↓
4 Test only the returned candidates
Why this works
When the grid is not worth it

Under a hundred objects, the pair test is faster and simpler. The grid is for when the pair test stops fitting in a frame.

Where the grid lies

Objects bigger than a cell span many cells and are inserted in all of them. Forgetting that is the bug where a large object never collides.

Examples

Cells the size of the objects

A cell about the size of a typical object means few objects per cell. Cells much bigger than the objects put everything in one cell and buy nothing.

Insert, query, clear

Each frame, clear the grid, insert every object, then query the cells an object touches. The grid is rebuilt, never patched.

Query the cells it covers

A moving object covers more than one cell. Querying only the centre cell misses the pair that straddles a boundary.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← A fixed-step machine for deterministic rules
Previous Lesson
A fixed-step machine for deterministic rules
Next Lesson
Difficulty as data, and the curve it produces
Difficulty as data, and the curve it produces →