Part 4's tests each looked at one pair of shapes. To find every collision in a scene, the simple way is to test every shape against every other. For the handful of shapes in Part 4's demos, that was fine. For thousands, it's hopeless: ten thousand balls make fifty million pairs, every frame. This chapter is about never testing most of those pairs. It's spatial partitioning: sorting things by where they are, so that each one is tested only against the few that are near it.
It's one of the ideas that let a game have a lot in it: crowds, swarms of particles, a screen full of bullets. We'll count the cost of testing every pair, and time it. Then we'll build three ways to find the pairs worth testing: a uniform grid, a spatial hash and a quadtree. And we'll time the grid and the quadtree against every pair, on the same ten thousand balls.
In this chapter, we will:
- Count and time the cost of testing every pair
- Split collision into a cheap broad phase and an exact narrow phase
- Build a uniform grid, and find the cell size it needs to be correct
- Sketch a spatial hash, a grid with no edges
- Build a quadtree, which divides space finely only where things crowd
- Build 10000 Balls, which times them all on the same swarm
We'll start by counting.
Every Pair
The simple way to find every touching pair among n balls is to test each ball against every ball after it in the list. Its cost is easy to count, and easy to measure.
The Count
The first ball is tested against n − 1 others, and the second against n − 2. And so on, down to the last ball, which has none left to test. That adds up to:
pairs = n × (n - 1) / 2For 1,000 balls, that's 499,500 pairs. For 2,000 balls it's 1,999,000. Ten thousand balls make 49,995,000: fifty million tests every frame. Doubling the balls doubles both n and n − 1, so it multiplies the pairs by about four. Work that grows as the square of what it's given is written O(n²), said "order n squared", and it's the mark of something that won't scale.
The Time
Each test is quick: a subtraction, a squared length and a comparison, since nearly every pair is far apart. But fifty million of anything takes time. Here's how long 10000 Balls takes to test every pair once, on the machine this chapter was measured on. Visual Studio builds a project in its Debug configuration unless it's told otherwise, and Debug code is slower, so both are given, in milliseconds:
balls Release Debug
1,000 0.50 3.1
2,000 1.9 12.6
5,000 11.7 78
10,000 46 307A frame lasts 16.7 milliseconds at 60 frames a second. In a Debug build, 2,000 balls already take most of it. And 5,000 take nearly five frames' worth. Even in Release, 10,000 balls take 46 milliseconds, which caps the game at about 21 frames a second before anything is drawn. And nearly all of that time goes on proving that balls on opposite sides of the window don't touch.
Broad Phase and Narrow Phase
The way out is to split collision into two steps. The narrow phase is the exact test for one pair, as Part 4 built them. The broad phase comes first. It's a cheap way to find the pairs worth testing exactly, and to leave out the rest without testing them at all. It may hand over a few pairs that don't touch, since the narrow phase sorts those out. But it must never leave out a pair that does touch.
Each ball is a position and a velocity:
// A ball: where it is, and its velocity.
struct Ball
{
Vec2 pos;
Vec2 vel;
};The narrow phase is one function, the same whatever the broad phase:
// The narrow phase, for one pair. If the balls overlap, each is pushed out
// by half the depth, along the line between their centers, as Chapter 18
// pushed a ball out of a wall. Then, if they're closing, they swap the
// parts of their velocities along that line: a perfect bounce between
// equal masses. Centers in the same place give no line, so they're left.
bool collide(Ball& a, Ball& b)
{
Vec2 d = b.pos - a.pos;
float distSq = d.lengthSquared();
float reach = 2.0f * RADIUS;
if (distSq > reach * reach || distSq < 0.000001f) return false;
float dist = std::sqrt(distSq);
Vec2 n = d / dist;
float depth = reach - dist;
a.pos -= n * (0.5f * depth);
b.pos += n * (0.5f * depth);
float va = a.vel.dot(n);
float vb = b.vel.dot(n);
if (va > vb)
{
a.vel += n * (vb - va);
b.vel += n * (va - vb);
}
return true;
}In the preceding code, the squared distance comes first, as in Chapter 15. So the pairs that are far apart, which are nearly all of them, need no square root. A pair that overlaps gets Chapter 18's push, split half and half, since neither ball is a wall. Then, if the two are closing along the line between their centers, they swap their speeds along it. For equal masses, that's a perfect bounce, and Chapter 20 handles any masses. The function returns whether the balls touched, for the readout.
A collision pass reports what it did:
// What a collision pass did: the pairs it tested, and how many touched.
struct PassCounts
{
long checks;
long contacts;
};And brute force, the pass to beat, is the double loop:
// Brute force: every ball against every ball after it in the list.
PassCounts bruteForce(std::vector<Ball>& balls)
{
PassCounts counts = { 0, 0 };
for (size_t i = 0; i < balls.size(); ++i)
for (size_t j = i + 1; j < balls.size(); ++j)
{
++counts.checks;
if (collide(balls[i], balls[j])) ++counts.contacts;
}
return counts;
}The inner loop starts just after i, so each pair is tested once, and no ball is tested against itself.
Uniform Grids
Picture graph paper laid over the window. Each square is a cell, and each ball goes in the cell its center is in. A ball can only touch balls whose centers are near its own. So if the cells are big enough, every ball it could touch is in its own cell or the eight around it, and those are the only balls it's tested against. The next image shows a ball, its nine cells, and what's in them.
On a window full of balls, those nine cells hold a few balls, out of thousands.
Filling the Cells
The grid is a list of cells, row by row. Each cell is a list of balls, held by their places in the list of balls:
// A uniform grid: its columns and rows, and its cells, each holding the
// balls whose centers are in it, by their places in the list of balls.
struct Grid
{
int cols;
int rows;
std::vector<std::vector<int>> cells;
};The cell for a point is its coordinates divided by the cell's size, rounded down:
// The grid's column or row for a coordinate, kept inside the grid, since
// a push can leave a ball a hair outside the window.
int cellIndex(float v, int count)
{
return std::clamp((int)(v / CELL), 0, count - 1);
}Casting a float to int rounds it toward zero, which is rounding down for anything from 0 up, and so for anything in the window. Then std::clamp keeps the cell inside the grid. The grid itself is made once, with a cell for every square of the window:
// A grid over the window, with no balls in it yet.
Grid makeGrid()
{
int cols = (int)std::ceil(WINDOW_WIDTH / CELL);
int rows = (int)std::ceil(WINDOW_HEIGHT / CELL);
return { cols, rows, std::vector<std::vector<int>>((size_t)(cols * rows)) };
}With cells 6 pixels across, that's 167 columns and 117 rows: 19,539 cells.
Searching Nine Cells
Each frame, the grid is filled, and then each ball searches its nine cells:
// The grid: put each ball in the cell its center is in, then test each
// ball against the balls in its own cell and the eight around it, after
// it in the list, so that each pair is tested once.
PassCounts gridPass(std::vector<Ball>& balls, Grid& grid)
{
for (std::vector<int>& cell : grid.cells) cell.clear();
for (int i = 0; i < (int)balls.size(); ++i)
{
int cx = cellIndex(balls[i].pos.x, grid.cols);
int cy = cellIndex(balls[i].pos.y, grid.rows);
grid.cells[cy * grid.cols + cx].push_back(i);
}
PassCounts counts = { 0, 0 };
for (int i = 0; i < (int)balls.size(); ++i)
{
int cx = cellIndex(balls[i].pos.x, grid.cols);
int cy = cellIndex(balls[i].pos.y, grid.rows);
int x0 = std::max(cx - 1, 0);
int x1 = std::min(cx + 1, grid.cols - 1);
int y0 = std::max(cy - 1, 0);
int y1 = std::min(cy + 1, grid.rows - 1);
for (int y = y0; y <= y1; ++y)
for (int x = x0; x <= x1; ++x)
for (int j : grid.cells[y * grid.cols + x])
if (j > i)
{
++counts.checks;
if (collide(balls[i], balls[j])) ++counts.contacts;
}
}
return counts;
}In the preceding code, clear empties each cell, but keeps the memory each cell's list already has, so that refilling it next frame costs no allocations. A cell at column x and row y is at y * grid.cols + x in the list. The search runs over the columns and rows either side of the ball's own, clamped to the grid's edges, so a ball at an edge searches six cells, or four in a corner. Two balls in neighboring cells each find the other, so j > i keeps just one of the two tests, as brute force does.
How Big a Cell?
The search trusts that every ball a ball can touch is in its nine cells. Two balls touch when their centers are no more than a diameter apart. If the cells are at least a diameter across, a center a diameter away can be at most one cell over, so it's always in the nine. That's why 10000 Balls makes its cells exactly a diameter across.
If the cells are smaller, a touching pair can be two cells apart, and the search never reaches it. The next image shows one such pair.
It's not a rare case. With the balls scattered at random, cells half a diameter across miss 31% of touching pairs. At 0.6 of a diameter they miss 15%, and at three quarters, 3.6%. At a full diameter, they miss none. A missed pair gets no push and no bounce, so the two balls slide into each other as if the other weren't there.
Bigger cells are always correct, but they cost more. Each holds more balls, and the nine around a ball cover more of the window. Doubling a cell's width puts four times as many balls in it, on average. So the best size is the smallest that's correct: one diameter.
What It Saves
A rough count shows what the grid saves. Each ball is tested against the balls in nine cells of 6 by 6 pixels, which cover 324 square pixels. The window is 700,000 square pixels. So the nine cells hold about 1 in 2,160 of the balls, and the grid tests about 1 in 2,160 of the pairs. At 10,000 balls, the grid tests 19,095 pairs. Brute force tests 49,995,000: 2,618 times as many. That's a little better than the estimate, since the balls push each other apart, and so are spread more evenly than at random.
The time saved is less. At 10,000 balls, the grid's pass takes 0.90 milliseconds in Release, against brute force's 46. That's 51 times faster, not 2,618. The grid has work of its own. It clears 19,539 cells and files 10,000 balls in them. Then it looks in nine cells for each ball. That work grows with the number of balls, not with its square, so the grid's lead grows as the balls do. At 1,000 balls it's 12 times faster than brute force, and at 10,000 it's 51 times faster.
Spatial Hashing
A grid needs bounds: one cell for every square of the world, whether anything's in it or not. In a world much bigger than the screen, most cells would sit empty, taking memory. A spatial hash keeps only the cells that hold something, in a hash map, keyed by each cell's column and row. Here's a sketch of one, for 10000 Balls' balls:
// A spatial hash: a grid with no edges, whose cells are kept in a hash
// map, so that only cells with balls in them take any memory. A cell's
// key packs its column and its row into one 64-bit number.
using SpatialHash = std::unordered_map<std::uint64_t, std::vector<int>>;
int cellOf(float v)
{
return (int)std::floor(v / CELL);
}
std::uint64_t cellKey(int cx, int cy)
{
return ((std::uint64_t)(std::uint32_t)cx << 32) | (std::uint32_t)cy;
}
void fillHash(SpatialHash& hash, const std::vector<Ball>& balls)
{
hash.clear();
for (int i = 0; i < (int)balls.size(); ++i)
{
Vec2 p = balls[i].pos;
hash[cellKey(cellOf(p.x), cellOf(p.y))].push_back(i);
}
}
// The balls in the nine cells around a point. A cell with no balls has
// no entry, which find reports by returning end.
void nearby(const SpatialHash& hash, Vec2 p, std::vector<int>& found)
{
int cx = cellOf(p.x);
int cy = cellOf(p.y);
for (int y = cy - 1; y <= cy + 1; ++y)
for (int x = cx - 1; x <= cx + 1; ++x)
{
auto cell = hash.find(cellKey(x, y));
if (cell != hash.end())
for (int i : cell->second) found.push_back(i);
}
}In the preceding code, the search is the grid's, with find in place of indexing. An empty cell costs a lookup, and no memory at all.
Two details matter, and both are about negative coordinates, which an unbounded world has. The first is std::floor. A cast to int rounds toward zero, so it would put everything from −6 to 6 in cell 0: one cell twice as wide as the rest, holding twice its share of balls. The std::floor function rounds down, so −1 goes to cell −1, and every cell is the same size.
The second is the casts to std::uint32_t in cellKey. The key puts the column in its top 32 bits and the row in its bottom 32. Without the casts, a negative row would be widened to 64 bits with its sign, which fills the top half with ones. Then every cell in a negative row would have the same key, whatever its column. A lookup in a hash map costs more than an index into a list, so for a world the size of the window, the grid is faster. The hash pays off when the world is big and mostly empty.
Quadtrees
A grid's cells are all one size. A quadtree sizes them to the crowd. It starts with one box, the whole window, and splits a box into four quarters whenever too many balls arrive in it, and so on down. Crowded places end up with small boxes, and empty places with big ones. The next image shows a quadtree, and a search through it.
The search needs only the boxes it overlaps. Every other box is skipped whole, along with all the boxes and points inside it.
Boxes in a List
Each box is a node of the tree. A box that hasn't split is a leaf, and holds balls. A box that has split holds none itself, and has four children:
// One box of a quadtree: its bounds, the balls in it while it's a leaf,
// and where its four children start in the tree's list of boxes, or -1
// while it has none.
struct QuadNode
{
AABB bounds;
std::vector<int> balls;
int firstChild;
};
// A quadtree: all its boxes in one list, the whole window first. A box
// finds its children by their place in the list, not by a reference,
// since a reference into a vector dangles when the vector grows.
struct QuadTree
{
std::vector<QuadNode> nodes;
};Every box lives in one std::vector, the whole window first, and a box's four children sit side by side in it. A box finds them by firstChild, their place in the list, rather than by a reference or a pointer. That's because push_back can move the vector's contents to a bigger block of memory as it grows, which would leave a reference pointing at memory that's been freed. A place in the list stays right however the list grows.
Splitting
A point's child box depends on which side of the box's middle it's on, across and down:
// The child of a box that a point falls in. A point at or past the middle
// goes right, or down, so one on a dividing line goes one way only.
int childFor(const QuadTree& tree, int node, Vec2 p)
{
const QuadNode& box = tree.nodes[node];
Vec2 mid = lerp(box.bounds.min, box.bounds.max, 0.5f);
int quarter = (p.x >= mid.x ? 1 : 0) + (p.y >= mid.y ? 2 : 0);
return box.firstChild + quarter;
}The quarter's number is 0 to 3: 1 for the right half, plus 2 for the bottom half. That matches the order in which a split adds the quarters. The >= sends a point on a dividing line one way only, by Chapter 15's half-open rule, so that every point is in exactly one box. A split adds the four quarters to the end of the list:
// Split a leaf into its four quarters, added to the end of the list: top
// left, top right, bottom left and bottom right.
void split(QuadTree& tree, int node)
{
AABB b = tree.nodes[node].bounds;
Vec2 mid = lerp(b.min, b.max, 0.5f);
AABB quarters[4] = { { b.min, mid },
{ { mid.x, b.min.y }, { b.max.x, mid.y } },
{ { b.min.x, mid.y }, { mid.x, b.max.y } },
{ mid, b.max } };
int first = (int)tree.nodes.size();
for (const AABB& q : quarters) tree.nodes.push_back({ q, {}, -1 });
tree.nodes[node].firstChild = first;
}The bounds b are copied out before the four push_back calls, since the calls may move the list.
Inserting
Adding a ball starts at the top, and works down:
// Add ball i to the tree, starting at a box: into the child it falls in,
// if the box has split; into the box itself, if it has room or is as deep
// as boxes go; and otherwise, split the box, and move its balls down.
void insert(QuadTree& tree, int node, int depth, int i,
const std::vector<Ball>& balls)
{
if (tree.nodes[node].firstChild >= 0)
{
insert(tree, childFor(tree, node, balls[i].pos), depth + 1, i, balls);
return;
}
if ((int)tree.nodes[node].balls.size() < CAPACITY || depth == MAX_DEPTH)
{
tree.nodes[node].balls.push_back(i);
return;
}
split(tree, node);
std::vector<int> moving = tree.nodes[node].balls;
tree.nodes[node].balls.clear();
for (int j : moving) insert(tree, node, depth, j, balls);
insert(tree, node, depth, i, balls);
}In the preceding code, there are three cases. A box that has split passes the ball to the child it falls in, one level deeper. A leaf with room keeps it. And a full leaf splits. Then its balls and the new one are inserted again from the same box, which now sends each down to a child. The balls are copied out first, since inserting adds to the boxes' lists. A child that's full in turn splits too, so a crowd keeps splitting until it's spread over boxes with room.
The limits are CAPACITY and MAX_DEPTH. A leaf splits when a ball arrives and it already holds 8. Without a depth limit, nine balls in the same spot would split boxes forever, since no split could ever separate them. So a box 8 levels down keeps whatever arrives. At that depth, a box is a 256th of the window across: 3.9 by 2.7 pixels.
Searching a Range
A search finds every ball whose center is in a range, a box:
// Every ball whose center is in a range. A box the range misses is skipped
// whole, with everything under it, and only the leaves the range reaches
// are searched, ball by ball.
void query(const QuadTree& tree, int node, const AABB& range,
const std::vector<Ball>& balls, std::vector<int>& found)
{
const QuadNode& box = tree.nodes[node];
if (!boxesOverlap(box.bounds, range)) return;
if (box.firstChild < 0)
{
for (int i : box.balls)
if (pointInBox(balls[i].pos, range)) found.push_back(i);
return;
}
for (int c = 0; c < 4; ++c)
query(tree, box.firstChild + c, range, balls, found);
}Chapter 15's boxesOverlap decides whether a box is worth entering at all. A box the range misses is skipped, with everything under it, which is where the time is saved. Only the leaves the range reaches are searched, ball by ball, with Chapter 15's pointInBox.
The quadtree's pass builds the tree afresh, then searches around each ball:
// The quadtree: build it afresh, then search a box around each ball that
// reaches a diameter each way, which holds every ball it could touch.
// Each pair is tested once, from the ball earlier in the list.
PassCounts quadtreePass(std::vector<Ball>& balls, QuadTree& tree)
{
AABB window = { { 0, 0 }, { WINDOW_WIDTH, WINDOW_HEIGHT } };
tree.nodes.clear();
tree.nodes.push_back({ window, {}, -1 });
for (int i = 0; i < (int)balls.size(); ++i) insert(tree, 0, 0, i, balls);
PassCounts counts = { 0, 0 };
std::vector<int> found;
Vec2 reach = { 2.0f * RADIUS, 2.0f * RADIUS };
for (int i = 0; i < (int)balls.size(); ++i)
{
found.clear();
query(tree, 0, { balls[i].pos - reach, balls[i].pos + reach }, balls,
found);
for (int j : found)
if (j > i)
{
++counts.checks;
if (collide(balls[i], balls[j])) ++counts.contacts;
}
}
return counts;
}In the preceding code, the range around each ball reaches a diameter each way, so it holds every center within a diameter: every ball it could touch. As in the grid, j > i tests each pair once. The tree is rebuilt every frame, since the balls move, which is far simpler than finding each ball's new box.
Choosing a Structure
Here are all three, measured in Release on the same balls, scattered over the window, in milliseconds for one pass:
balls brute force grid quadtree
1,000 0.50 0.04 0.23
2,000 1.9 0.08 0.55
5,000 11.7 0.28 1.6
10,000 46 0.90 4.1For balls all the same size, in a world the size of the window, the grid wins easily: it's about 4.6 times faster than the quadtree at 10,000 balls. In a Debug build, the gap is wider, 3.7 milliseconds against 21. The quadtree spends its time building. At 10,000 balls it makes 4,513 boxes every frame, each with its own list. And each search walks down from the top. It tests fewer pairs than the grid: 5,801 against 19,095. That's because its range is tighter than nine cells. But the pairs were never the expensive part.
Crowding doesn't change the order, either. With the balls pulled into a clump, the grid's pass at 10,000 balls rises from 0.90 milliseconds to 1.2, and the quadtree's from 4.1 to 5.9. Balls that push each other apart can't pile up, so a cell a diameter across never holds more than a ball or two, however crowded the clump is.
So each structure has its place:
- A uniform grid suits objects of about one size, in a world of known size. It's the simplest and, for that case, the fastest.
- A spatial hash is the grid for a world that's huge, or has no edges, and is mostly empty.
- A quadtree suits objects of very different sizes, since a grid must size its cells for the largest, and then each cell holds many of the small ones. It also suits things that really can pile up, such as particles that pass through each other, and worlds whose crowds come and go.
Whichever you choose, measure it as this chapter did. Time the collision pass itself, not the whole frame, which vsync holds to the screen's rate. And measure in Release, since Debug code can be ten times slower.
Building 10000 Balls
10000 Balls fills the window with small balls that bounce and collide. Space switches the broad phase between brute force, the grid and the quadtree. Up and Down change the number of balls, from 1,000 to 10,000. C pulls them into a clump, and V shows the grid's cells or the quadtree's boxes. The readout gives the pairs tested, and the time the collision pass takes.
Get the code. The complete project is in the
10000 Ballsfolder of the book's repository.
10000 Balls starts from the skeleton, with its timing, and leaves out the mouse. It reuses fmt2 and setColor, Chapter 9's generator and randRange, and Chapter 15's pointInBox, boxesOverlap and rectOf. Its Vec2.h is Walls and Slides', since this chapter adds nothing to it. Here are its includes, its colors and its constants:
#include <algorithm>
#include <cmath>
#include <random>
#include <string>
#include <vector>
#include "Vec2.h"
constexpr int WINDOW_WIDTH = 1000;
constexpr int WINDOW_HEIGHT = 700;
constexpr SDL_Color TEXT = { 235, 238, 242, 255 };
constexpr SDL_Color GREY = { 90, 100, 112, 255 };
constexpr SDL_Color BLUE = { 47, 111, 235, 255 };
constexpr SDL_Color AMBER = { 232, 89, 12, 255 };
constexpr SDL_Color FAINT = { 58, 64, 74, 255 };
constexpr SDL_Color PANEL = { 24, 26, 30, 220 };
// The balls' radius, and the grid's cell size: one diameter, the smallest
// size at which a search of the cells around a ball can be trusted.
constexpr float RADIUS = 3.0f;
constexpr float CELL = 2.0f * RADIUS;
// The quadtree's limits: a box splits when a ball arrives and it already
// holds CAPACITY, unless it's MAX_DEPTH levels down.
constexpr int CAPACITY = 8;
constexpr int MAX_DEPTH = 8;
// How hard the clump pulls the balls toward the middle, in pixels a second,
// every second.
constexpr float PULL = 400.0f;
// The three broad phases.
enum BroadPhase { BRUTE_FORCE, GRID, QUADTREE };
const char* const PHASE_NAMES[] = { "brute force", "uniform grid", "quadtree" };In the preceding code, the balls' radius is 3 pixels, so that 10,000 of them cover 40% of the window and still have room to move. The cell is a diameter, 6 pixels, as the grid needs. The quadtree's limits are 8 balls a leaf and 8 levels. The broad phases are numbered 0 to 2, in an enum, so that Space can step through them, and PHASE_NAMES gives each a name for the readout.
Next comes Chapter 11's box, for the quadtree's bounds:
// An axis-aligned box: its smallest and largest corners. Neither of min's
// coordinates is ever more than max's.
struct AABB
{
Vec2 min;
Vec2 max;
};The random numbers come from Chapter 9's generator, with its randRange, unchanged:
// A random float from lo to hi. The generator is made once, and seeded
// from the system, so that every run is different.
std::mt19937 rng{ std::random_device{}() };Three small helpers come before the passes. The first writes a count with commas, since 49995000 is hard to read:
// A whole number with commas every three digits, such as 1,999,000.
std::string withCommas(long n)
{
std::string digits = std::to_string(n);
std::string out;
for (size_t i = 0; i < digits.size(); ++i)
{
if (i > 0 && (digits.size() - i) % 3 == 0) out += ',';
out += digits[i];
}
return out;
}It copies the digits one by one, and puts a comma before each digit that has a multiple of three digits after it. The second scatters a fresh set of balls:
// A fresh set of balls, scattered over the window, each heading a random
// way at from 40 to 160 pixels a second.
std::vector<Ball> scatter(int count)
{
std::vector<Ball> balls;
for (int i = 0; i < count; ++i)
{
Vec2 pos = { randRange(RADIUS, WINDOW_WIDTH - RADIUS),
randRange(RADIUS, WINDOW_HEIGHT - RADIUS) };
float speed = randRange(40.0f, 160.0f);
balls.push_back({ pos, Vec2::fromAngle(randRange(0, 2 * PI), speed) });
}
return balls;
}Each ball gets a place anywhere in the window and a heading anywhere around the circle, by Chapter 5's fromAngle. The third bounces a ball off the window's edges:
// Keep a ball in the window, bouncing it off the edges.
void keepInWindow(Ball& b)
{
if (b.pos.x < RADIUS)
{
b.pos.x = RADIUS;
b.vel.x = std::fabs(b.vel.x);
}
if (b.pos.x > WINDOW_WIDTH - RADIUS)
{
b.pos.x = WINDOW_WIDTH - RADIUS;
b.vel.x = -std::fabs(b.vel.x);
}
if (b.pos.y < RADIUS)
{
b.pos.y = RADIUS;
b.vel.y = std::fabs(b.vel.y);
}
if (b.pos.y > WINDOW_HEIGHT - RADIUS)
{
b.pos.y = WINDOW_HEIGHT - RADIUS;
b.vel.y = -std::fabs(b.vel.y);
}
}In the preceding code, a ball past an edge is put back on it, and its velocity is made to point back in. Then come this chapter's narrow phase and its three broad phases.
The State
The state goes after the font is loaded:
// The balls, the broad phase in use, the clump, whether to show the
// outlines, and the grid and the quadtree, kept between frames.
int count = 2000;
std::vector<Ball> balls = scatter(count);
int phase = GRID;
bool clump = false;
bool outlines = false;
Grid grid = makeGrid();
QuadTree tree;
// The readout's timings: sums over each half second, and the averages
// last shown. Translucent panels behind the text need blending.
float frameSum = 0.0f;
float passSum = 0.0f;
int frames = 0;
float shownFrameMs = 0.0f;
float shownPassMs = 0.0f;
PassCounts counts = { 0, 0 };
SDL_SetRenderDrawBlendMode(renderer, SDL_BLENDMODE_BLEND);The demo starts with 2,000 balls, on the grid. The grid and the quadtree are kept from frame to frame, so that their memory is reused. The readout's timings are summed over half a second, then shown as averages, since a number that changes every frame can't be read. The panels behind the readout are translucent, so the renderer blends, as in Chapter 15.
The skeleton's timing gains one line, just after previous = now;. It keeps the frame's time before the clamp, so that a slow frame shows as slow:
float frameSeconds = dt; // Before the clamp, for the readout.The readout's frame time comes from that, while everything that moves still uses the clamped dt.
The Events
Space, C and V change the settings, and Up and Down the number of balls:
// Events: quitting, and the keys and clicks that happen once.
SDL_Event event;
while (SDL_PollEvent(&event))
{
if (event.type == SDL_EVENT_QUIT) running = false;
else if (event.type == SDL_EVENT_KEY_DOWN)
{
if (event.key.key == SDLK_ESCAPE) running = false;
else if (event.key.key == SDLK_SPACE) phase = (phase + 1) % 3;
else if (event.key.key == SDLK_C) clump = !clump;
else if (event.key.key == SDLK_V) outlines = !outlines;
else if (event.key.key == SDLK_UP ||
event.key.key == SDLK_DOWN)
{
int change = (event.key.key == SDLK_UP) ? 1000 : -1000;
count = std::clamp(count + change, 1000, 10000);
balls = scatter(count);
}
}
}In the preceding code, Space adds 1 to the broad phase's number, and % 3 wraps it from 2 back to 0. A new number of balls scatters a fresh set, kept from 1,000 to 10,000 by std::clamp.
Each Frame's Work
The balls move first:
// Each ball moves, pulled toward the middle while clumping, and
// bounces off the window's edges.
Vec2 middle = { WINDOW_WIDTH / 2.0f, WINDOW_HEIGHT / 2.0f };
for (Ball& b : balls)
{
if (clump) b.vel += (middle - b.pos).normalized() * (PULL * dt);
b.pos += b.vel * dt;
keepInWindow(b);
}While clumping, each ball is pulled toward the middle of the window, at 400 pixels a second, every second. The collisions never take energy away, so the balls don't settle into a heap. They swarm around the middle, densest at its center. Then comes the collision pass, timed:
// The collision pass, timed by SDL's counter: the broad phase in
// use, and the narrow phase for each pair it finds.
Uint64 passStart = SDL_GetPerformanceCounter();
if (phase == BRUTE_FORCE) counts = bruteForce(balls);
else if (phase == GRID) counts = gridPass(balls, grid);
else counts = quadtreePass(balls, tree);
Uint64 passEnd = SDL_GetPerformanceCounter();
// The timings, averaged over each half second, so they can be read.
frameSum += frameSeconds * 1000.0f;
passSum += (float)((passEnd - passStart) * 1000.0 / frequency);
++frames;
if (frameSum >= 500.0f)
{
shownFrameMs = frameSum / frames;
shownPassMs = passSum / frames;
frameSum = passSum = 0.0f;
frames = 0;
}SDL's counter is read on each side of the pass, as the skeleton reads it for dt. The difference divided by the counter's frequency is in seconds, and 1,000 times that is milliseconds. The frame's time and the pass's time are added up, and every half second, their averages are shown, and the sums start again.
Drawing
First come the outlines, if V has turned them on:
// The outlines, if they're shown: the grid's lines, one by one, or
// the quadtree's boxes, all in one call.
if (outlines)
{
setColor(renderer, FAINT);
if (phase == GRID)
{
for (int x = 0; x <= grid.cols; ++x)
SDL_RenderLine(renderer, x * CELL, 0, x * CELL,
WINDOW_HEIGHT);
for (int y = 0; y <= grid.rows; ++y)
SDL_RenderLine(renderer, 0, y * CELL, WINDOW_WIDTH,
y * CELL);
}
else if (phase == QUADTREE)
{
std::vector<SDL_FRect> boxes;
for (const QuadNode& node : tree.nodes)
boxes.push_back(rectOf(node.bounds));
SDL_RenderRects(renderer, boxes.data(), (int)boxes.size());
}
}In the preceding code, the grid's lines are drawn one by one. The quadtree's boxes, often thousands, are gathered into a list of rectangles by Chapter 15's rectOf. Then SDL_RenderRects draws them all in one call. The balls are drawn the same way:
// The balls, as squares a diameter across, all in one call, so that
// drawing them costs little beside the collisions.
std::vector<SDL_FRect> squares;
for (const Ball& b : balls)
squares.push_back({ b.pos.x - RADIUS, b.pos.y - RADIUS,
2.0f * RADIUS, 2.0f * RADIUS });
setColor(renderer, BLUE);
SDL_RenderFillRects(renderer, squares.data(), (int)squares.size());Each ball is drawn as a square a diameter across, all of them in one call to SDL_RenderFillRects. Ten thousand of Chapter 3's fillCircle calls, each a stack of lines, would make the frame's time mostly a measure of drawing. Last come the readout and the controls, on their panels:
// The readout, on panels the balls show faintly through.
setColor(renderer, PANEL);
SDL_FRect top = { 0, 0, WINDOW_WIDTH, 52 };
SDL_FRect bottom = { 0, WINDOW_HEIGHT - 32, WINDOW_WIDTH, 32 };
SDL_RenderFillRect(renderer, &top);
SDL_RenderFillRect(renderer, &bottom);
drawText(renderer, font,
std::string(PHASE_NAMES[phase]) + ": " + withCommas(count) +
" balls, " + withCommas(counts.checks) + " pairs tested, " +
withCommas(counts.contacts) + " touching",
12, 10, (phase == BRUTE_FORCE) ? AMBER : TEXT);
drawText(renderer, font,
"collision pass " + fmt2(shownPassMs) + " ms frame " +
fmt2(shownFrameMs) + " ms clump " +
(clump ? "on" : "off"),
12, 30, TEXT);
drawText(renderer, font,
"[Space] broad phase [Up] [Down] balls [C] clump "
"[V] view [Esc] quit", 12, WINDOW_HEIGHT - 26, GREY);The first line names the broad phase, in amber for brute force, and gives the pairs it tested and how many touched. The second gives the collision pass's average time and the frame's.
Trying It Out
Run the demo. It starts on the grid, with 2,000 balls. The next image shows it three seconds in.
The grid tested 687 pairs to find the 46 that touched, and the pass took about a millisecond in this Debug build. The timings on your machine will differ, but the pairs tested won't, by much.
Then try it, step by step:
- Test every pair. Press Space twice, for brute force. The readout turns amber, and the pairs tested jump to 1,999,000. About the same number touch as before. In a Debug build, the pass takes about 13 milliseconds.
- Add balls. Press Up three times, for 5,000 balls. The pairs tested rise to 12,497,500, and the pass to about 78 milliseconds. The frame's time rises with it, and the balls move in jumps.
- Back to the grid. Press Space. The pairs tested drop to a few thousand, and the pass to about a millisecond. The balls move smoothly again.
- Try the quadtree. Press Space again, and V to see its boxes. They're about the same size all over, since the balls are spread evenly.
- Clump them. Press C. The balls swarm toward the middle, and the boxes there split, and split again, while those near the edges grow back.
The next image shows step 5, with 2,000 balls.
The boxes are smallest where the balls crowd, and largest in the corners, where few balls stray. The quadtree tested only 320 pairs to find 188 touching. Yet its pass took 2.28 milliseconds, several times what the grid takes on the same clump, since it built its boxes from nothing to do it.
That's spatial partitioning, measured. Any broad phase turns fifty million pairs into thousands, and the simplest one, sized to the balls, is the fastest here.
FAQ
Q) Why does the quadtree test fewer pairs than the grid, yet take longer?
A) Its range around a ball is tighter than the grid's nine cells, so fewer of the balls it finds are far from the ball. But testing a pair is the cheap part. The quadtree's cost is in building: thousands of boxes every frame, each with its own list, and a walk down from the top for every search. The grid's cells are one list, made once, and a ball's cell is one division away.
Q) What if my objects come in very different sizes?
A) A grid must make its cells as wide as the largest object, and then each cell holds many of the small ones. One answer is to file each object in every cell its bounding box overlaps, and drop the pairs found twice. Another is a quadtree that keeps each object in the smallest box that holds it whole, and searches the boxes above a leaf as well as the leaf. A third is two grids, one sized for the small objects and one for the large.
Q) Do I really rebuild the grid every frame?
A) Yes, since the balls move. Filling it is one pass over the balls, so it costs as much as moving them, and clear keeps each cell's memory for the next frame. Moving each ball between cells only when it crosses into a new one is possible, but it's more code, and rarely faster.
Q) Why are my timings different from the book's?
A) They depend on the machine, on whether the build is Debug or Release, and on what else is running. Your numbers will differ, but the shape won't: brute force grows four times over when the balls double, and the grid and the quadtree two to three times over. More balls in the same window means more crowding, so even the grid's pairs grow four times over. There are so few of them that its time grows far more slowly.
Exercises
The first three exercises need only a pencil. The others change 10000 Balls.
- Count the pairs (paper). How many pairs does brute force test for 3,000 balls, and for 6,000? By what factor does the count grow?
- Size the cells (paper). Balls have a radius of 4. What's the smallest cell size that the nine-cell search can trust? If the cells were only 4 pixels across, how many cells around a ball would a search need, to be safe?
- A quadtree by hand (paper). A box runs from
(0, 0)to(8, 8), and a leaf splits when a point arrives and it already holds 2. Insert the points(1, 1),(2, 3),(6, 1),(3, 2)and(7, 7)in that order. How many boxes are there at the end, and which points share a leaf? - A spatial hash (code). Add a fourth broad phase, built on this chapter's spatial hash sketch, and time it against the grid.
- Mixed sizes (code). Give each ball its own radius, from 3 to 12, and make
collideuse the two radii. What must the grid's cell size become, and what happens to the pairs it tests, and to its time?
For the code exercises, work on a copy of the demo's folder, so that the original stays as the chapter describes it.
AI Exercise (Optional)
A grid finds more than collisions. It finds neighbors, which is just what a flock of birds needs. With an AI's help, you can turn 10000 Balls into a flock of thousands, each bird steering by its neighbors, as Chapter 9's critters steered. Open your AI chatbot of choice, and try a prompt like this:
"I have a C++ demo using SDL3, with a Vec2 struct (dot, length, normalized, truncated), a Ball struct with a pos and a vel, and a uniform grid: a Grid struct with cols, rows and cells, a std::vector of std::vector<int>, made by makeGrid() with cells CELL pixels square, and cellIndex(v, count), which gives a coordinate's column or row. Please make a flock of 3,000 birds in a 1000 by 700 window, steering by Craig Reynolds' three rules: separation, alignment and cohesion, counting only the birds within 30 pixels as neighbors. Set CELL to 30, and find each bird's neighbors by searching the nine cells around it. Draw each bird as a small triangle pointing along its velocity, with a top speed of 150 pixels a second, wrapping around the window's edges. Add a key that switches to finding neighbors by brute force, and show the time the neighbor search takes. Explain why the cells must be at least as wide as the neighbor distance."
That prompt describes your grid and what each function does, so the AI builds on them, rather than writing a partition of its own. It ties the cell size to the neighbor distance, which is this chapter's rule for correctness in a new setting. And it asks for brute force too, so that you can measure what the grid saves.
Then play with the three rules' weights, and watch the flock change. Then make the neighbor distance 60 without changing the cells, and see what goes wrong.
Summary
Testing every pair of n objects takes n × (n − 1) / 2 tests, which grows as n squared: fifty million for ten thousand balls, every frame. The cure is a broad phase, which finds the pairs worth testing, ahead of the narrow phase's exact test, and never leaves out a pair that touches. A uniform grid files each object in the cell its center is in, and tests it only against the cells around it. With cells at least a diameter across, the nine cells around a ball hold every ball it could touch, and smaller cells miss pairs: 31% of them at half a diameter. A spatial hash keeps a grid's occupied cells in a hash map, for worlds with no edges, with std::floor for negative coordinates. A quadtree splits a box into four whenever too many objects arrive, to a depth limit, so its boxes are small where things crowd, and a search skips every box it misses. At its full 10,000 balls, the demo's grid tests 2,618 times fewer pairs than brute force. It runs 51 times faster. The quadtree tests fewer pairs still, but takes 4.6 times longer than the grid, since it rebuilds its boxes every frame. It earns its place when sizes vary, or when things really pile up. Measure in Release, and time the pass itself. Chapter 20 builds a small physics engine, with mass and forces, and a fixed timestep that keeps it steady whatever the frame rate.