Back to sparse_spatial_hash

Tutorials

Step-by-step guides for using sparse_spatial_hash.

Getting Started with sparse_spatial_hash

This tutorial walks you through building spatial queries and collision detection systems using the sparse_spatial_hash library.

Prerequisites

  • C++20 Compiler: GCC 10+, Clang 12+, or MSVC 2019+
  • CMake (optional): 3.15+ for build system integration
  • No external dependencies required

Tutorial 1: Your First Spatial Hash Grid

Step 1: Include the Header

#include <spatial/sparse_spatial_hash.hpp>
#include <vector>
#include <iostream>

using namespace spatial;

Step 2: Define Your Entity

struct Particle {
    float x, y;
    float vx, vy;
    int id;
};

Step 3: Teach the Grid How to Read Positions

template<>
struct spatial::position_accessor<Particle, 2> {
    static float get(const Particle& p, std::size_t dim) {
        return dim == 0 ? p.x : p.y;
    }
};

Pro Tip: If your entity uses std::array<float, N> for position, skip this step - it works automatically!

struct Particle {
    std::array<float, 2> position;  // No accessor needed!
};

Step 4: Configure and Create the Grid

grid_config<2> cfg{
    .cell_size = {10.0f, 10.0f},       // 10-unit cells
    .world_size = {1000.0f, 1000.0f},  // 1000x1000 world
    .topology_type = topology::bounded  // Clamp to edges
};

sparse_spatial_hash<Particle, 2> grid(cfg);

Step 5: Populate and Build

std::vector<Particle> particles;
for (int i = 0; i < 1000; ++i) {
    particles.push_back({
        .x = static_cast<float>(rand() % 1000),
        .y = static_cast<float>(rand() % 1000),
        .vx = (rand() % 100 - 50) / 10.0f,
        .vy = (rand() % 100 - 50) / 10.0f,
        .id = i
    });
}

grid.rebuild(particles);
std::cout << "Indexed " << grid.entity_count() << " particles in "
          << grid.cell_count() << " cells\n";

Step 6: Query for Neighbors

// Find particles within 50 units of (500, 500)
auto neighbors = grid.query_radius(50.0f, 500.0f, 500.0f);

std::cout << "Found " << neighbors.size() << " candidates\n";

// Filter by exact distance
for (auto idx : neighbors) {
    const auto& p = particles[idx];
    float dx = p.x - 500.0f;
    float dy = p.y - 500.0f;
    float dist = std::sqrt(dx*dx + dy*dy);

    if (dist < 50.0f) {
        std::cout << "Particle " << p.id << " at distance " << dist << "\n";
    }
}

Tutorial 2: Collision Detection

The for_each_pair method is optimized for collision detection.

// Find all pairs within 20 units of each other
grid.for_each_pair(particles, 20.0f,
    [&](std::size_t i, std::size_t j) {
        // Guaranteed: i < j (no duplicates)
        const auto& p1 = particles[i];
        const auto& p2 = particles[j];

        float dx = p2.x - p1.x;
        float dy = p2.y - p1.y;
        float dist = std::sqrt(dx*dx + dy*dy);

        if (dist < 20.0f) {
            resolve_collision(p1, p2);
        }
    });

Tutorial 3: Real-Time Simulation Loop

The killer feature: incremental updates are 40x faster than full rebuilds.

// Initial build
grid.rebuild(particles);

// Simulation loop
for (int frame = 0; frame < 1000; ++frame) {
    // Update positions
    for (auto& p : particles) {
        p.x += p.vx;
        p.y += p.vy;

        // Bounce off walls
        if (p.x < 0 || p.x >= 1000) p.vx = -p.vx;
        if (p.y < 0 || p.y >= 1000) p.vy = -p.vy;
    }

    // Incremental update - only processes entities that changed cells
    grid.update(particles);  // 40x faster than rebuild!

    // Process collisions
    grid.for_each_pair(particles, 20.0f, handle_collision);
}

Tutorial 4: Toroidal (Wraparound) Worlds

For periodic boundaries like Pac-Man or N-body simulations:

grid_config<2> cfg{
    .cell_size = {10.0f, 10.0f},
    .world_size = {1000.0f, 1000.0f},
    .topology_type = topology::toroidal  // Wraparound!
};

sparse_spatial_hash<Particle, 2> grid(cfg);

// Entities near edges will find neighbors on the opposite side
// No manual wraparound checking needed!

Tutorial 5: Multi-Resolution Grids

Use different grids for different purposes:

// Fine grid for precise collision detection
grid_config<3> fine_cfg{
    .cell_size = {2.0f, 2.0f, 2.0f},
    .world_size = {1000.0f, 1000.0f, 1000.0f}
};
sparse_spatial_hash<Entity, 3> collision_grid(fine_cfg);

// Coarse grid for AI awareness (larger range)
grid_config<3> coarse_cfg{
    .cell_size = {50.0f, 50.0f, 50.0f},
    .world_size = {1000.0f, 1000.0f, 1000.0f}
};
sparse_spatial_hash<Entity, 3> awareness_grid(coarse_cfg);

// Rebuild both (can be parallelized)
collision_grid.rebuild(entities);
awareness_grid.rebuild(entities);

// Fine-grained collision detection
collision_grid.for_each_pair(entities, 2.0f, handle_collision);

// Coarse AI awareness queries
auto nearby = awareness_grid.query_radius(100.0f, player_pos);
for (auto idx : nearby) {
    ai_entities[idx].update_awareness(player);
}

Common Pitfalls

Cell Size Selection

Too small: Many cells, high memory and iteration overhead

// BAD: 0.1 unit cells in 1000 unit world = 10^9 potential cells!
.cell_size = {0.1f, 0.1f, 0.1f}

Too large: Many entities per cell, lots of false positives

// BAD: Only one cell!
.cell_size = {1000.0f, 1000.0f, 1000.0f}

Just right: Match your typical query radius

// GOOD: If typical query is 20 units
.cell_size = {20.0f, 20.0f, 20.0f}

Always Filter by Exact Distance

query_radius returns entities in cells that intersect the query sphere:

// WRONG: Assumes all candidates are within radius
auto neighbors = grid.query_radius(5.0f, x, y, z);
for (auto idx : neighbors) {
    process(entities[idx]);  // May include false positives!
}

// RIGHT: Filter by exact distance
for (auto idx : neighbors) {
    if (exact_distance(entities[idx], pos) < 5.0f) {
        process(entities[idx]);
    }
}

Next Steps