Spatial Partitioning: Quadtrees and Grids

The All-Pairs Problem

Many games need to know which objects are near or touching each other: bullets hitting enemies, players colliding with walls, units detecting nearby foes. The obvious way to find collisions is to check every object against every other object. With ten objects this is trivial. With a hundred it is around five thousand checks per frame, still fine. With a thousand objects it becomes roughly half a million checks per frame, and with ten thousand it is fifty million, which no browser can sustain at sixty frames per second.

The reason is that the number of pairs grows with the square of the object count. Doubling the objects quadruples the work. This quadratic growth is why a naive collision approach that runs smoothly in a prototype falls apart the moment the game scales up, and it is one of the most common performance walls developers hit. Spatial partitioning exists to break this quadratic relationship by ensuring that most pairs are never checked at all, because objects far apart cannot possibly collide and there is no reason to compare them.

The Broad Phase Idea

Collision systems split the work into two phases. The broad phase quickly eliminates the vast majority of pairs that cannot possibly be touching, producing a small list of pairs that are close enough to warrant a real check. The narrow phase then does the precise, more expensive geometric test on just those candidate pairs. Spatial partitioning is the data structure that powers the broad phase, organizing objects by location so that finding the nearby candidates for any object is fast.

The shared principle behind every spatial partitioning structure is locality. Objects are placed into spatial buckets based on where they are, and when you want to find what might collide with a given object, you only examine the buckets it overlaps. Everything in distant buckets is skipped entirely, never entering a single comparison. The structures differ in how they divide space, but they all deliver this same essential benefit of replacing a global search with a local one.

Uniform Grids

The simplest spatial partition is a uniform grid. You overlay the world with a grid of equally sized cells, and each object is filed into the cell or cells it occupies based on its position. To find potential collisions for an object, you look only at its own cell and the immediately adjacent cells, since an object can only touch things within roughly its own size of itself. Everything outside that small neighborhood is ignored.

Grids are fast, easy to implement, and ideal when objects are spread fairly evenly across a world of known size, which describes many arcade games, shooters, and top-down games. Filing an object is a quick calculation from its coordinates, and clearing and rebuilding the grid each frame is cheap. The main weakness is uneven distribution. If most objects cluster in one small area, that area's cells become crowded while the rest of the grid sits empty, and the crowded cells degrade back toward the all-pairs problem locally. Choosing a cell size close to the typical object size keeps grids efficient, and for many web games a grid is all the spatial partitioning you will ever need.

Quadtrees

A quadtree adapts to uneven distributions by subdividing space only where it is crowded. It starts with the whole world as a single region. When a region holds more than a chosen number of objects, it splits into four equal quadrants, and the objects are distributed among them. Quadrants that are still crowded split again, recursively, so dense areas end up finely divided into many small cells while empty areas remain a single large cell. The tree's shape mirrors where the objects actually are.

This adaptivity is the quadtree's advantage over a uniform grid. In a game where objects clump unpredictably, a large open world with scattered dense battles, or a physics scene where everything piles into a corner, the quadtree keeps each region's object count bounded by subdividing exactly where needed, avoiding the crowded-cell problem that hurts grids. Querying for an object's neighbors means descending the tree to the regions it overlaps and checking only the objects there. The three-dimensional analog, the octree, applies the same idea to 3D worlds by splitting each region into eight.

The tradeoff is complexity and rebuild cost. A quadtree is more involved to implement than a grid, and because objects move every frame, the tree must be rebuilt or updated each frame, which carries overhead. For evenly distributed objects, a grid is usually faster and simpler, and reaching for a quadtree there is over-engineering. The quadtree earns its place specifically when distribution is uneven enough that a grid's worst case becomes a real problem.

Choosing and Using a Partition

The practical decision is straightforward. If your objects are spread reasonably evenly across a bounded world, start with a uniform grid, because it is simpler, faster to build, and almost always sufficient. If your objects cluster heavily and unpredictably across a large space, a quadtree or octree handles that case better by adapting its resolution. Many web games never need more than a grid, and adopting a quadtree before measuring a real distribution problem adds complexity for nothing.

Spatial partitioning connects tightly to the rest of game architecture. It is the broad phase that makes physics engines scale, so it underpins the collision detection covered in our game physics section. It pairs with object pooling, since a game with enough objects to need spatial partitioning almost certainly has enough to need pooling too. And like all performance patterns, its value should be confirmed by measurement: profile the collision step, see the quadratic cost, add the partition, and verify the frame time drops. Used at the right moment, spatial partitioning is the difference between a game that handles a handful of objects and one that handles thousands at a steady frame rate.

Keeping the Structure Up to Date

A spatial partition is only useful if it reflects where objects currently are, and in a game almost everything moves every frame. This means the structure must be kept current, and how you do that is a real performance consideration in its own right. The two broad approaches are rebuilding and updating. Rebuilding clears the structure and refills it from scratch each frame, which is simple, reliably correct, and often fast enough for a uniform grid where filing an object is just a quick coordinate calculation. Many grid-based games rebuild the whole grid every frame and never notice the cost.

Incremental updating instead moves only the objects that changed cells, leaving the rest of the structure in place. This is more efficient when most objects stay put or move slowly, but it is more complex, because the structure has to detect when an object crosses a cell boundary and re-file just that object. For a quadtree, where rebuilding the tree is more expensive than refilling a grid, incremental updates or partial rebuilds can be worth the added complexity. The right choice depends on how many objects move and how expensive your particular structure is to build, which is best settled by measuring both approaches rather than assuming.

Beyond grids and quadtrees, a few other structures suit specific needs. Spatial hashing maps cell coordinates into a hash table instead of a fixed array, which handles unbounded or very large worlds gracefully without allocating a giant grid, and it is a popular choice for open-world 2D games. Bounding volume hierarchies group objects into nested bounding boxes and are common in 3D and in physics engines for the broad phase. These are refinements on the same core idea, and most web games will never need them, but knowing they exist helps when a grid or quadtree hits a limit. As always, the discipline is to start simple, measure, and add sophistication only where the numbers show it pays off.