Sparse Spatial Hash Grids: When You Need to Find Neighbors Fast

When building physics simulations, game engines, or scientific computing applications, one problem comes up constantly: “Which entities are near this position?” Whether you’re detecting collisions between 10 million particles, finding nearby enemies in a game world, or computing gravitational forces in an N-body simulation, efficient spatial queries are critical.

The Problem: Spatial Indexing at Scale

Consider a physics simulation with 10 million particles in a 10,000³ world. Each frame, you need to:

1. Find all particles within 20 units of each particle (for collision detection)
2. Update particle positions
3. Repeat 60 times per second

The naive approach—checking every particle against every other particle—requires 100 trillion comparisons per frame. Even at 1 nanosecond per comparison, that’s over 90 seconds per frame. Not exactly real-time.

Enter: Sparse Spatial Hash Grids

A sparse spatial hash grid solves this by dividing space into a grid of cells and using a hash map to store only the occupied cells. This gives you:

• O(1) insertions (hash map lookup)
• O(k) neighbor queries where k = number of nearby entities (not total entities)
• Memory proportional to occupied cells (not total possible cells)

Why “Sparse”?

In the 10M particle example above, a dense grid with 10-unit cells would need 1 billion (1000³) cells. At 8 bytes per pointer, that’s 8 GB just for empty cells!

A sparse hash grid only stores the ~10 million occupied cells, using ~100 MB total. That’s a 60,000x memory reduction.

Architecture: Generic N-Dimensional Design

The library is built on modern C++20 concepts and generic programming:

template<typename Entity,
         std::size_t Dimensions,
         std::floating_point FloatType = float,
         std::unsigned_integral IndexType = std::size_t,
         std::size_t SmallVectorSize = 16>
class sparse_spatial_hash;

This design works for:

• 2D games (platformers, top-down shooters)
• 3D simulations (molecular dynamics, particle effects)
• 4D space-time indexing (trajectory queries)
• Any N dimensions your use case requires

Topology Support

Real-world spatial problems have different boundary conditions:

// Bounded: Traditional box with walls
grid_config<3> bounded{
    .topology_type = topology::bounded,
    .world_size = {1000.0f, 1000.0f, 1000.0f}
};

// Toroidal: Periodic wraparound (pac-man physics)
grid_config<3> toroidal{
    .topology_type = topology::toroidal,
    .world_size = {1000.0f, 1000.0f, 1000.0f}
};

// Infinite: Unbounded growth
grid_config<3> infinite{
    .topology_type = topology::infinite
};

Toroidal topology is particularly interesting - it’s essential for:

• Periodic boundary conditions in molecular dynamics
• Seamless procedural worlds in games
• Astronomical simulations (periodic universe models)

Performance: The Numbers

From real-world usage in the DigiStar physics engine (10M particles, 10000³ world):

The 40x speedup from incremental updates is crucial. In most simulations, only a small fraction of entities move between cells each frame. Why rebuild the entire grid when you can just update the movers?

Latest Optimizations (v1.1.0)

The library now uses small vector optimization - cells with ≤16 entities store them inline rather than allocating:

• 40% faster rebuilds (fewer allocations)
• 5-11% faster queries (better cache locality)
• Trade-off: +256 bytes per occupied cell

For typical workloads where most cells have <16 entities, this is a massive win.

Use Cases: Where It Shines

Game Development

Collision Detection - Broad-phase partitioning is the first step in physics engines:

sparse_spatial_hash<Entity, 2> grid(config);
grid.rebuild(entities);

// Only check entities in nearby cells
grid.for_each_pair(entities, collision_radius,
    [](std::size_t i, std::size_t j) {
        if (detailed_collision_check(i, j)) {
            handle_collision(i, j);
        }
    });

AI Pathfinding - Find cover points, enemies, or waypoints:

auto nearby_cover = grid.query_radius(
    search_radius,
    player.x, player.y
);

Scientific Computing

N-Body Simulations - Gravity, electrostatics, magnetic forces:

// Build neighbor lists for force calculations
sparse_spatial_hash<Particle, 3> grid(config);
grid.rebuild(particles);

for (auto& p : particles) {
    auto neighbors = grid.query_radius(
        cutoff_distance, p.x, p.y, p.z
    );

    for (auto neighbor_idx : neighbors) {
        apply_force(p, particles[neighbor_idx]);
    }
}

Molecular Dynamics - Bonded/non-bonded interactions in proteins:

The same data structure works for both:

• Short-range interactions (collision grid with small cells)
• Long-range interactions (coarse grid with large cells)

Robotics & SLAM

Obstacle Detection - Real-time collision avoidance:

// Index sensor readings
grid.rebuild(lidar_points);

// Check if path is clear
auto obstacles_in_path = grid.query_radius(
    robot_radius + safety_margin,
    target.x, target.y, target.z
);

Comparison with Alternatives

vs. R-tree (Boost.Geometry)

R-tree strengths:

• Hierarchical bounding volumes
• Good for static data
• O(log n + k) queries

Sparse hash advantages:

• O(1) insertions vs O(log n)
• Simpler incremental updates (no tree rebalancing)
• Native toroidal support
• Better for dynamic scenes (most entities don’t move far)

vs. Octree

Octree strengths:

• Hierarchical LOD
• Good for spatially clustered data

Sparse hash advantages:

• Lower memory (no tree nodes)
• Faster queries (direct hash lookup)
• Simpler implementation
• Predictable performance (no worst-case tree imbalance)

vs. Dense Grid

Dense grid strengths:

• Simple implementation
• Good cache locality when fully populated

Sparse hash advantages:

• 60,000x memory reduction for large sparse worlds
• Handles huge worlds without memory explosion
• Same O(1) insert and O(k) query complexity

Design Patterns: Customization Points

The library follows STL design philosophy with customization points:

Position Accessor

struct Particle {
    glm::vec3 position;
    glm::vec3 velocity;
    float mass;
};

// Customize how grid extracts positions
template<>
struct spatial::position_accessor<Particle, 3> {
    static float get(const Particle& p, std::size_t dim) {
        return p.position[dim];
    }
};

This zero-overhead abstraction means:

• No virtual calls
• No inheritance
• Optimized away at compile-time

Range Support

Works with any C++20 range:

std::vector<Particle> particles;
grid.rebuild(particles);  // Vector

std::list<Particle> list_particles;
grid.rebuild(list_particles);  // List

// Even filtered views!
auto fast_particles = particles
    | std::views::filter([](auto& p) {
        return p.speed > threshold;
      });
grid.rebuild(fast_particles);

Advanced Techniques

Multi-Resolution Grids

Use different grids for different interaction scales:

// Fine grid for collision detection (2-unit cells)
sparse_spatial_hash<Particle, 3> collision_grid({
    .cell_size = {2.0f, 2.0f, 2.0f}
});

// Coarse grid for long-range forces (50-unit cells)
sparse_spatial_hash<Particle, 3> force_grid({
    .cell_size = {50.0f, 50.0f, 50.0f}
});

// Different physics at different scales!

Parallel Processing

Process cells independently:

#pragma omp parallel for
for (const auto& [cell_idx, entities] : grid.cell_contents()) {
    // Thread-safe: Each cell independent
    for (std::size_t i = 0; i < entities.size(); ++i) {
        for (std::size_t j = i + 1; j < entities.size(); ++j) {
            handle_interaction(entities[i], entities[j]);
        }
    }
}

Or use standard parallel algorithms:

std::for_each(std::execution::par_unseq,
    grid.cells().begin(), grid.cells().end(),
    [&](const auto& cell) {
        process_cell(cell);
    });

Implementation Insights

Morton Encoding (Z-Order Curve)

The grid uses Morton encoding to convert multi-dimensional cell coordinates into a single hash key:

// (x, y, z) -> single integer with spatial locality
hash_key = morton_encode(cell_x, cell_y, cell_z);

Why?: Nearby cells in 3D space have nearby hash keys, improving cache locality during traversal.

Incremental Updates

The magic behind 40x speedups:

// Track which cell each entity was in
std::vector<CellIndex> prev_cells;

// On update:
for (std::size_t i = 0; i < entities.size(); ++i) {
    auto new_cell = compute_cell(entities[i]);
    if (new_cell != prev_cells[i]) {
        // Only update entities that moved cells
        remove_from_cell(prev_cells[i], i);
        add_to_cell(new_cell, i);
        prev_cells[i] = new_cell;
    }
}

Typical movement patterns:

• ~99% of particles stay in their cell each frame
• ~1% move to adjacent cells
• Update cost scales with movers, not total count

Getting Started

Installation

Using CMake FetchContent:

include(FetchContent)

FetchContent_Declare(
  sparse_spatial_hash
  GIT_REPOSITORY https://github.com/queelius/sparse_spatial_hash.git
  GIT_TAG        v1.2.0
)
FetchContent_MakeAvailable(sparse_spatial_hash)

target_link_libraries(your_target
  PRIVATE sparse_spatial_hash::sparse_spatial_hash)

Minimal Example

#include <spatial/sparse_spatial_hash.hpp>

struct Particle {
    float x, y, z;
};

// Specialize position accessor
template<>
struct spatial::position_accessor<Particle, 3> {
    static float get(const Particle& p, std::size_t dim) {
        switch(dim) {
            case 0: return p.x;
            case 1: return p.y;
            case 2: return p.z;
            default: return 0.0f;
        }
    }
};

int main() {
    using namespace spatial;

    // Configure grid
    grid_config<3> cfg{
        .cell_size = {10.0f, 10.0f, 10.0f},
        .world_size = {1000.0f, 1000.0f, 1000.0f},
        .topology_type = topology::toroidal
    };

    sparse_spatial_hash<Particle, 3> grid(cfg);

    // Create particles
    std::vector<Particle> particles(10000);
    // ... initialize ...

    // Build index
    grid.rebuild(particles);

    // Query neighbors
    auto neighbors = grid.query_radius(
        50.0f,  // radius
        100.0f, 200.0f, 300.0f  // query position
    );

    // Process pairs
    grid.for_each_pair(particles, 20.0f,
        [&](std::size_t i, std::size_t j) {
            // Handle interaction
        });
}

Future Directions

The library continues to evolve:

• GPU Support: CUDA/OpenCL backend for massive parallelism
• Lazy Evaluation: Generator-based query results
• Custom Distance Metrics: Support for non-Euclidean distances
• Adaptive Grids: Dynamic cell size adjustment based on density
• Serialization: Save/load grid state for checkpointing

Conclusion

Sparse spatial hash grids hit a sweet spot in the spatial indexing landscape:

• Simple enough to understand and debug
• Fast enough for real-time applications (2ms updates!)
• Memory-efficient enough for huge sparse worlds (60,000x reduction)
• Generic enough for 2D/3D/4D and beyond
• Battle-tested in production physics engines

If you’re building a game, simulation, or spatial application, consider trying sparse spatial hashing. It might just be the perfect fit.

Learn More

• Repository: github.com/queelius/sparse_spatial_hash
• Documentation: Full API reference and tutorials
• Examples: See examples/ directory for collision detection, molecular dynamics, and more
• License: Boost Software License (very permissive)

The library is extracted from the DigiStar physics engine, where it enables 10M+ particle simulations at 60 FPS.

Give it a try, and let me know how it works for your use case!

This post covers the sparse spatial hash grid library - a C++20 header-only library for high-performance spatial indexing. If you’re working with spatial data at scale, check out the repository and documentation.