Quadtree: 2D Spatial Partitioning
Every game developer hits the same wall. Your particle system runs beautifully with 100 particles, struggles at 1,000, and dies at 10,000. The culprit is almost always collision detection: checking...
Key Insights
- Quadtrees reduce collision detection from O(n²) to O(n log n) by recursively partitioning 2D space, allowing you to skip entire regions that can’t possibly contain relevant objects.
- The key design decision is choosing between point quadtrees (storing objects at exact positions) and region quadtrees (storing objects in leaf nodes), with the latter being more practical for game development and simulations.
- For dynamic scenes with moving objects, rebuilding the entire quadtree each frame often outperforms incremental updates due to cache efficiency and simpler code—don’t over-engineer until profiling proves you need to.
The Problem of Spatial Queries
Every game developer hits the same wall. Your particle system runs beautifully with 100 particles, struggles at 1,000, and dies at 10,000. The culprit is almost always collision detection: checking every object against every other object gives you O(n²) complexity. Double your objects, quadruple your collision checks.
This isn’t just a game development problem. Geographic information systems need to find all restaurants within a mile. Image compression algorithms identify regions of similar color. Physics simulations track particle interactions. All of these require answering the same fundamental question: “What objects exist in this region of space?”
You have options. Uniform grids work well when objects distribute evenly, but waste memory on sparse regions and struggle when object sizes vary wildly. BSP trees excel at static geometry but become expensive to maintain with moving objects. R-trees optimize for disk-based queries in databases. Quadtrees hit a sweet spot for in-memory 2D spatial queries with dynamic objects—they’re simple to implement, adapt to non-uniform distributions, and provide consistent performance.
Quadtree Fundamentals
A quadtree recursively subdivides 2D space into four quadrants. Start with a rectangle covering your entire world. When that region contains too many objects, split it into four equal rectangles: northwest, northeast, southwest, southeast. Repeat recursively until each leaf node contains a manageable number of objects.
This creates a tree where each internal node has exactly four children, and objects live in leaf nodes. The depth varies across the tree—dense areas subdivide more than sparse ones, automatically adapting to your data distribution.
from dataclasses import dataclass, field
from typing import List, Optional
@dataclass
class Rectangle:
x: float
y: float
width: float
height: float
def contains(self, px: float, py: float) -> bool:
return (self.x <= px < self.x + self.width and
self.y <= py < self.y + self.height)
def intersects(self, other: 'Rectangle') -> bool:
return not (other.x >= self.x + self.width or
other.x + other.width <= self.x or
other.y >= self.y + self.height or
other.y + other.height <= self.y)
@dataclass
class Point:
x: float
y: float
data: any = None # Attach game objects, particle data, etc.
@dataclass
class QuadtreeNode:
bounds: Rectangle
capacity: int = 4
points: List[Point] = field(default_factory=list)
divided: bool = False
nw: Optional['QuadtreeNode'] = None
ne: Optional['QuadtreeNode'] = None
sw: Optional['QuadtreeNode'] = None
se: Optional['QuadtreeNode'] = None
The distinction between point quadtrees and region quadtrees matters. Point quadtrees store one point per internal node, using that point’s position to determine the split location. Region quadtrees always split at the center, storing multiple points in leaf nodes. Region quadtrees are simpler and more practical for most applications—that’s what we’ll build.
Insertion Algorithm
Insertion follows a simple recursive pattern: if the current node has room and isn’t subdivided, store the point here. Otherwise, subdivide if necessary, then insert into the appropriate child.
def insert(self, point: Point) -> bool:
# Ignore points outside our bounds
if not self.bounds.contains(point.x, point.y):
return False
# If we have room and haven't subdivided, store here
if len(self.points) < self.capacity and not self.divided:
self.points.append(point)
return True
# Subdivide if we haven't already
if not self.divided:
self._subdivide()
# Insert into appropriate child
if self.nw.insert(point): return True
if self.ne.insert(point): return True
if self.sw.insert(point): return True
if self.se.insert(point): return True
# Should never reach here if bounds checking is correct
return False
def _subdivide(self):
x, y = self.bounds.x, self.bounds.y
hw, hh = self.bounds.width / 2, self.bounds.height / 2
self.nw = QuadtreeNode(Rectangle(x, y, hw, hh), self.capacity)
self.ne = QuadtreeNode(Rectangle(x + hw, y, hw, hh), self.capacity)
self.sw = QuadtreeNode(Rectangle(x, y + hh, hw, hh), self.capacity)
self.se = QuadtreeNode(Rectangle(x + hw, y + hh, hw, hh), self.capacity)
# Redistribute existing points to children
for point in self.points:
self.nw.insert(point) or self.ne.insert(point) or \
self.sw.insert(point) or self.se.insert(point)
self.points = []
self.divided = True
The capacity threshold controls the tree’s granularity. Lower values create deeper trees with fewer points per node—faster queries but more memory and insertion overhead. Values between 4 and 16 work well for most applications. Profile with your actual data.
Querying the Quadtree
Range queries find all points within a given rectangle. The power of quadtrees comes from pruning: if a node’s bounds don’t intersect the search area, skip that entire subtree.
def query_range(self, search_area: Rectangle,
found: List[Point] = None) -> List[Point]:
if found is None:
found = []
# Prune branches that don't intersect
if not self.bounds.intersects(search_area):
return found
# Check points in this node
for point in self.points:
if search_area.contains(point.x, point.y):
found.append(point)
# Recurse into children
if self.divided:
self.nw.query_range(search_area, found)
self.ne.query_range(search_area, found)
self.sw.query_range(search_area, found)
self.se.query_range(search_area, found)
return found
Average-case complexity is O(log n) for small search areas, degrading toward O(n) as the search area approaches the entire world. The key insight: you’re not searching the whole tree, just the branches that might contain relevant points.
Collision Detection Implementation
Game collision detection typically happens in two phases. Broad-phase quickly identifies pairs that might collide using spatial structures. Narrow-phase performs precise geometric tests on those candidates.
Quadtrees excel at broad-phase. For each object, query the tree for nearby objects, then run your actual collision geometry against only those candidates.
def find_collision_candidates(self, obj_bounds: Rectangle) -> List[Point]:
"""Find all points that might collide with an object's bounding box."""
# Expand search area slightly for moving objects
search = Rectangle(
obj_bounds.x - 1,
obj_bounds.y - 1,
obj_bounds.width + 2,
obj_bounds.height + 2
)
return self.query_range(search)
def detect_all_collisions(quadtree: QuadtreeNode,
objects: List[Point]) -> List[tuple]:
"""Broad-phase collision detection for all objects."""
collisions = []
checked = set()
for obj in objects:
# Query area around this object
nearby = quadtree.find_collision_candidates(
Rectangle(obj.x - 5, obj.y - 5, 10, 10)
)
for other in nearby:
if other is obj:
continue
# Avoid duplicate pairs
pair = (id(obj), id(other)) if id(obj) < id(other) \
else (id(other), id(obj))
if pair in checked:
continue
checked.add(pair)
# Narrow-phase: actual collision test
if distance(obj, other) < COLLISION_RADIUS:
collisions.append((obj, other))
return collisions
With 10,000 objects, brute-force checks 50 million pairs. A quadtree might reduce each object’s candidates to 10-20, dropping total checks to under 200,000—a 250x improvement.
Optimization Techniques
Loose quadtrees solve a common problem: objects with physical size that span quadrant boundaries. Instead of storing an object in multiple nodes or always in the parent, expand each node’s bounds by a factor (typically 2x). Objects insert into the smallest node that fully contains them. Queries must check slightly more nodes, but insertion becomes simpler and objects have a single canonical location.
Object pooling matters for dynamic scenes. Creating and destroying QuadtreeNode objects every frame generates garbage collection pressure. Pre-allocate a pool of nodes and reset them instead of reallocating.
Rebuild vs. update: The intuitive approach for moving objects is incremental updates—remove from old position, insert at new position. In practice, rebuilding the entire tree each frame often performs better. Modern CPUs love predictable memory access patterns, and a clean rebuild is more cache-friendly than scattered removals and insertions. Benchmark both approaches with your specific workload.
Depth limits prevent pathological cases where many objects cluster at one point, causing infinite subdivision. Set a maximum depth (8-12 levels typically) and let leaf nodes exceed capacity rather than subdivide further.
Practical Demo: Particle Simulation
Here’s a complete working example that demonstrates the performance difference:
import random
import time
def benchmark_collision_detection(num_particles: int, iterations: int = 100):
# Create random particles
particles = [
Point(random.uniform(0, 1000), random.uniform(0, 1000))
for _ in range(num_particles)
]
# Brute-force approach
start = time.perf_counter()
for _ in range(iterations):
brute_collisions = []
for i, p1 in enumerate(particles):
for p2 in particles[i+1:]:
if abs(p1.x - p2.x) < 10 and abs(p1.y - p2.y) < 10:
brute_collisions.append((p1, p2))
brute_time = time.perf_counter() - start
# Quadtree approach
start = time.perf_counter()
for _ in range(iterations):
qt = QuadtreeNode(Rectangle(0, 0, 1000, 1000), capacity=8)
for p in particles:
qt.insert(p)
qt_collisions = []
for p in particles:
candidates = qt.query_range(
Rectangle(p.x - 10, p.y - 10, 20, 20)
)
for other in candidates:
if other is not p and id(p) < id(other):
if abs(p.x - other.x) < 10 and abs(p.y - other.y) < 10:
qt_collisions.append((p, other))
qt_time = time.perf_counter() - start
print(f"Particles: {num_particles}")
print(f"Brute-force: {brute_time:.3f}s")
print(f"Quadtree: {qt_time:.3f}s")
print(f"Speedup: {brute_time/qt_time:.1f}x\n")
# Run benchmarks
for n in [100, 500, 1000, 5000]:
benchmark_collision_detection(n)
Typical results show quadtrees breaking even around 100-200 objects, then pulling dramatically ahead. At 5,000 particles, expect 20-50x speedup depending on distribution.
Quadtrees aren’t always the answer. For very small object counts (under 100), brute-force wins due to lower overhead. For 3D applications, use octrees. For objects with highly variable sizes, R-trees may perform better. For uniform distributions, simple grids offer better cache performance.
But for the common case—thousands of similarly-sized objects in 2D with non-uniform distribution—quadtrees deliver excellent performance with straightforward implementation. Start here, profile, and optimize only when the data tells you to.