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 <vector>
#include <cmath>
#include <functional>

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);
    }

    // Query all items within radius of (x, z)
    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);

        float r2 = radius * radius;
        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 {
        return static_cast<int>((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_;
};

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 node:

struct OctreeNode {
    BoundingBox       bounds;
    std::vector<int>  objectIndices;  // indices into scene object array
    std::unique_ptr<OctreeNode> children[8];
    bool isLeaf = true;

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

    void Insert(int idx, const Vector3& pos, int depth = 0) {
        if (!bounds.Contains(pos)) return;
        if (isLeaf) {
            objectIndices.push_back(idx);
            if (static_cast<int>(objectIndices.size()) > MAX_OBJECTS
                && depth < MAX_DEPTH) {
                Subdivide();
            }
        } else {
            for (auto& child : children)
                if (child) child->Insert(idx, pos, depth + 1);
        }
    }

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

    void Subdivide();  // splits bounds into 8 children
};

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);

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