Tutorial 76: Spatial Partitioning

CNA Tutorials  ·  Performance

Why spatial partitioning?

Without spatial partitioning, every query against the game world (collision detection, AI line-of-sight, frustum culling) is O(n) in the number of objects. With 10,000 objects and 60 queries per frame, that is 600,000 comparisons per second. Spatial partitioning reduces the per-query cost to O(log n) or better by organising objects into a structure that lets you skip large portions of the world based on spatial proximity.

Uniform grid

The simplest spatial data structure is a uniform grid: divide the world into a regular array of cells and keep a list of objects in each cell. Insertion is O(1) (compute the cell index, push to its list). Range query visits only the cells that overlap the query region.

// UniformGrid.hpp
#pragma once
#include "Microsoft/Xna/Framework/Vector2.hpp"
#include "Microsoft/Xna/Framework/Vector3.hpp"
#include <algorithm>   // std::clamp
#include <vector>
#include <cmath>
#include <functional>

using namespace Microsoft::Xna::Framework;

template <typename T>
class UniformGrid {
public:
    // worldMin/Max: axis-aligned world bounds
    // cellSize:     size of each grid cell in world units
    UniformGrid(Vector2 worldMin, Vector2 worldMax, float cellSize)
        : worldMin_(worldMin)
        , cellSize_(cellSize)
    {
        cols_ = static_cast<int>(
            std::ceil((worldMax.X - worldMin.X) / cellSize_));
        rows_ = static_cast<int>(
            std::ceil((worldMax.Y - worldMin.Y) / cellSize_));
        cells_.resize(static_cast<size_t>(cols_ * rows_));
    }

    void Clear() {
        for (auto& cell : cells_) cell.clear();
    }

    // Insert an item at position (x, z)
    void Insert(float x, float z, const T& item) {
        int ci = CellIndex(x, z);
        if (ci >= 0) cells_[ci].push_back(item);
    }

    // Broad phase: returns every item stored in a cell that overlaps the query
    // square around (x, z). It does NOT filter by exact distance; the narrow phase does that.
    void QueryRadius(float x, float z, float radius,
                     std::vector<T>& results) const {
        int cx0 = ToCell(x - radius, worldMin_.X);
        int cx1 = ToCell(x + radius, worldMin_.X);
        int cy0 = ToCell(z - radius, worldMin_.Y);
        int cy1 = ToCell(z + radius, worldMin_.Y);

        cx0 = std::clamp(cx0, 0, cols_ - 1);
        cx1 = std::clamp(cx1, 0, cols_ - 1);
        cy0 = std::clamp(cy0, 0, rows_ - 1);
        cy1 = std::clamp(cy1, 0, rows_ - 1);

        for (int cy = cy0; cy <= cy1; ++cy) {
            for (int cx = cx0; cx <= cx1; ++cx) {
                for (const T& item : cells_[cy * cols_ + cx]) {
                    results.push_back(item);
                }
            }
        }
    }

private:
    int ToCell(float v, float origin) const {
        // floor, not a plain cast: truncation would map values just below the origin to cell 0
        return static_cast<int>(std::floor((v - origin) / cellSize_));
    }

    int CellIndex(float x, float z) const {
        int cx = ToCell(x, worldMin_.X);
        int cy = ToCell(z, worldMin_.Y);
        if (cx < 0 || cx >= cols_ || cy < 0 || cy >= rows_) return -1;
        return cy * cols_ + cx;
    }

    Vector2              worldMin_;
    float                cellSize_;
    int                  cols_ = 0;
    int                  rows_ = 0;
    std::vector<std::vector<T>> cells_;
};

This grid stores each item in one cell, so it suits objects that are small relative to cellSize. Objects that span several cells must be inserted into every cell they overlap (and de-duplicated in query results).

Using UniformGrid for collision neighbour queries

// In Game::LoadContent or level load:
// World spans (-500, -500) to (500, 500) with 10-metre cells
grid_ = std::make_unique<UniformGrid<int>>(
    Vector2(-500.0f, -500.0f),
    Vector2( 500.0f,  500.0f),
    10.0f);

// In Game::Update — rebuild the grid every frame (or incrementally)
grid_->Clear();
for (int i = 0; i < static_cast<int>(entities_.size()); ++i) {
    grid_->Insert(entities_[i].position.X,
                  entities_[i].position.Z, i);
}

// Per-entity narrow-phase: only check entities in nearby cells
std::vector<int> neighbours;
for (auto& e : entities_) {
    neighbours.clear();
    grid_->QueryRadius(e.position.X, e.position.Z,
                       e.collisionRadius * 2.0f, neighbours);
    for (int ni : neighbours) {
        if (&entities_[ni] == &e) continue;
        CheckCollision(e, entities_[ni]);
    }
}

Quadtree (2D)

A quadtree recursively subdivides a 2D area into four equal quadrants when a cell contains more objects than a threshold. It adapts better to non-uniform object distributions than a uniform grid:

• Cells with many objects are subdivided further (fine granularity where needed).
• Empty areas use a single large cell (no wasted memory).

The tradeoff is higher insertion/deletion cost compared to a uniform grid, and a more complex implementation. Use a quadtree when your world has highly variable object density (e.g. dense city centre surrounded by sparse countryside).

Octree (3D)

An octree is the 3D equivalent of a quadtree — each node subdivides into eight child octants instead of four. Use an octree when objects occupy a significant 3D volume (e.g. flying enemies, 3D asteroids). For mostly flat worlds (terrain-based games), a quadtree over the XZ plane is cheaper and sufficient.

A minimal recursive octree of point objects. Each leaf keeps the objects it holds together with their positions, so a leaf that grows past MAX_OBJECTS can subdivide and hand its objects down to the eight children. BoundingBox::Contains(Vector3) returns a ContainmentType (not a bool), so the test is written against ContainmentType::Disjoint:

#include "Microsoft/Xna/Framework/BoundingBox.hpp"
#include "Microsoft/Xna/Framework/BoundingFrustum.hpp"
#include <memory>

struct OctreeNode {
    struct Item { int index; Vector3 position; };

    BoundingBox       bounds;
    std::vector<Item> items;                 // leaf payload: scene-object index + position
    std::unique_ptr<OctreeNode> children[8];
    bool isLeaf = true;

    static constexpr int MAX_OBJECTS = 8;
    static constexpr int MAX_DEPTH   = 6;

    explicit OctreeNode(const BoundingBox& b) : bounds(b) {}

    // Returns true if this subtree stored the object.
    bool Insert(int idx, const Vector3& pos, int depth = 0) {
        if (bounds.Contains(pos) == ContainmentType::Disjoint) return false;
        if (isLeaf) {
            items.push_back({idx, pos});
            if (static_cast<int>(items.size()) > MAX_OBJECTS && depth < MAX_DEPTH)
                Subdivide(depth);
            return true;
        }
        // A point on a shared face is accepted by several children; the first one wins,
        // so the object is stored exactly once.
        for (auto& child : children)
            if (child && child->Insert(idx, pos, depth + 1)) return true;
        return false;
    }

    void FrustumQuery(const BoundingFrustum& frustum,
                      std::vector<int>& results) const {
        if (frustum.Contains(bounds) == ContainmentType::Disjoint)
            return;
        if (isLeaf) {
            for (const Item& it : items) results.push_back(it.index);
        } else {
            for (auto& child : children)
                if (child) child->FrustumQuery(frustum, results);
        }
    }

    void Subdivide(int depth) {
        const Vector3 c = (bounds.Min + bounds.Max) * 0.5f;
        for (int i = 0; i < 8; ++i) {   // bit 0 = x half, bit 1 = y half, bit 2 = z half
            Vector3 lo((i & 1) ? c.X : bounds.Min.X,
                       (i & 2) ? c.Y : bounds.Min.Y,
                       (i & 4) ? c.Z : bounds.Min.Z);
            Vector3 hi((i & 1) ? bounds.Max.X : c.X,
                       (i & 2) ? bounds.Max.Y : c.Y,
                       (i & 4) ? bounds.Max.Z : c.Z);
            children[i] = std::make_unique<OctreeNode>(BoundingBox(lo, hi));
        }
        isLeaf = false;
        std::vector<Item> moved;
        moved.swap(items);
        for (const Item& it : moved) Insert(it.index, it.position, depth);
    }
};

BVH overview

A Bounding Volume Hierarchy (BVH) is a tree where each internal node stores a bounding volume that encloses all objects in its subtree. Unlike an octree (fixed spatial subdivision), a BVH subdivides based on the actual object geometry, giving tighter bounds. BVHs are the standard acceleration structure for ray tracing and are used in Vulkan's ray tracing extension. For real-time game collision they are more expensive to build but give fewer false positives than a uniform grid.

Query types: range, ray, frustum

CNA BoundingFrustum integration

The octree's FrustumQuery method integrates directly with CNA's BoundingFrustum — the same object you construct from your view-projection matrix in Tutorial 74. Pass it to the tree and receive back only the object indices that might be visible, skipping the rest entirely:

BoundingFrustum frustum(view_ * proj_);
std::vector<int> visibleObjects;
octree_->FrustumQuery(frustum, visibleObjects);   // octree_ is a std::unique_ptr<OctreeNode>

for (int idx : visibleObjects) {
    DrawObject(sceneObjects_[idx]);
}