Examples
Practical examples demonstrating sparse_spatial_hash capabilities.
Example 1: Complete Particle Simulation
A full working example with collision detection and bouncing particles.
#include <spatial/sparse_spatial_hash.hpp>
#include <vector>
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace spatial;
struct Particle {
float x, y;
float vx, vy;
int id;
};
template<>
struct spatial::position_accessor<Particle, 2> {
static float get(const Particle& p, std::size_t dim) {
return dim == 0 ? p.x : p.y;
}
};
int main() {
// Configure grid
grid_config<2> cfg{
.cell_size = {10.0f, 10.0f},
.world_size = {1000.0f, 1000.0f},
.topology_type = topology::bounded
};
// Create grid and particles
sparse_spatial_hash<Particle, 2> grid(cfg);
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
});
}
// Build spatial index
grid.rebuild(particles);
std::cout << "Indexed " << grid.entity_count() << " particles\n";
// Simulation loop
for (int frame = 0; frame < 100; ++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;
}
// Fast incremental update
grid.update(particles);
// Process collisions
if (frame % 10 == 0) {
int collisions = 0;
grid.for_each_pair(particles, 20.0f,
[&](std::size_t i, std::size_t j) {
collisions++;
});
std::cout << "Frame " << frame << ": " << collisions
<< " potential collisions\n";
}
}
// Print statistics
auto stats = grid.stats();
std::cout << "\nFinal statistics:\n"
<< " Occupied cells: " << stats.occupied_cells << "\n"
<< " Avg entities/cell: " << stats.avg_entities_per_cell << "\n"
<< " Occupancy ratio: " << (stats.occupancy_ratio * 100) << "%\n";
return 0;
}
Example 2: Game Collision Detection
Efficient collision detection for game objects.
struct GameObject {
std::array<float, 2> position;
float radius;
int type; // 0 = player, 1 = enemy, 2 = projectile
};
// Position accessor works automatically with std::array!
void game_loop(std::vector<GameObject>& objects) {
grid_config<2> cfg{
.cell_size = {50.0f, 50.0f}, // Match max collision radius
.world_size = {1920.0f, 1080.0f},
.topology_type = topology::bounded
};
sparse_spatial_hash<GameObject, 2> grid(cfg);
grid.rebuild(objects);
// Check player-enemy collisions
auto player_pos = objects[0].position;
auto nearby = grid.query_radius(100.0f, player_pos[0], player_pos[1]);
for (auto idx : nearby) {
if (objects[idx].type == 1) { // Enemy
float dx = objects[idx].position[0] - player_pos[0];
float dy = objects[idx].position[1] - player_pos[1];
float dist = std::sqrt(dx*dx + dy*dy);
if (dist < objects[0].radius + objects[idx].radius) {
handle_player_enemy_collision(objects[0], objects[idx]);
}
}
}
// Check projectile-enemy collisions
grid.for_each_pair(objects, 30.0f,
[&](std::size_t i, std::size_t j) {
auto& a = objects[i];
auto& b = objects[j];
// Projectile hitting enemy
if ((a.type == 2 && b.type == 1) || (a.type == 1 && b.type == 2)) {
float dx = b.position[0] - a.position[0];
float dy = b.position[1] - a.position[1];
float dist = std::sqrt(dx*dx + dy*dy);
if (dist < a.radius + b.radius) {
handle_projectile_hit(a, b);
}
}
});
}
Example 3: Physics Force Calculation
N-body style force calculations with cutoff radius.
struct Particle3D {
std::array<float, 3> position;
std::array<float, 3> velocity;
std::array<float, 3> force;
float mass;
};
void compute_forces(std::vector<Particle3D>& particles,
sparse_spatial_hash<Particle3D, 3>& grid,
float cutoff) {
// Reset forces
for (auto& p : particles) {
p.force = {0.0f, 0.0f, 0.0f};
}
// Compute pairwise forces
grid.for_each_pair(particles, cutoff,
[&](std::size_t i, std::size_t j) {
auto& pi = particles[i];
auto& pj = particles[j];
float dx = pj.position[0] - pi.position[0];
float dy = pj.position[1] - pi.position[1];
float dz = pj.position[2] - pi.position[2];
float r2 = dx*dx + dy*dy + dz*dz;
if (r2 < cutoff * cutoff && r2 > 0.0001f) {
float r = std::sqrt(r2);
// Lennard-Jones style force
float r6 = r2 * r2 * r2;
float force_mag = 24.0f * (2.0f / (r6 * r6 * r) - 1.0f / (r6 * r));
float fx = force_mag * dx / r;
float fy = force_mag * dy / r;
float fz = force_mag * dz / r;
// Newton's third law
pi.force[0] += fx;
pi.force[1] += fy;
pi.force[2] += fz;
pj.force[0] -= fx;
pj.force[1] -= fy;
pj.force[2] -= fz;
}
});
}
Example 4: AI Awareness System
Using a coarse grid for AI entity awareness.
struct AIAgent {
std::array<float, 2> position;
float awareness_radius;
std::vector<size_t> visible_entities;
};
void update_ai_awareness(std::vector<AIAgent>& agents,
sparse_spatial_hash<AIAgent, 2>& grid) {
for (size_t i = 0; i < agents.size(); ++i) {
auto& agent = agents[i];
agent.visible_entities.clear();
// Query nearby agents
auto nearby = grid.query_radius(
agent.awareness_radius,
agent.position[0],
agent.position[1]
);
for (auto idx : nearby) {
if (idx == i) continue; // Skip self
float dx = agents[idx].position[0] - agent.position[0];
float dy = agents[idx].position[1] - agent.position[1];
float dist = std::sqrt(dx*dx + dy*dy);
if (dist < agent.awareness_radius) {
agent.visible_entities.push_back(idx);
}
}
}
}
Example 5: Toroidal World (Asteroids-style)
Periodic boundaries where entities wrap around.
struct Asteroid {
std::array<float, 2> position;
std::array<float, 2> velocity;
float radius;
};
void asteroids_simulation() {
const float world_size = 800.0f;
grid_config<2> cfg{
.cell_size = {50.0f, 50.0f},
.world_size = {world_size, world_size},
.topology_type = topology::toroidal // Wraparound!
};
sparse_spatial_hash<Asteroid, 2> grid(cfg);
std::vector<Asteroid> asteroids(50);
// Initialize asteroids
for (auto& a : asteroids) {
a.position = {
static_cast<float>(rand() % 800),
static_cast<float>(rand() % 800)
};
a.velocity = {
(rand() % 100 - 50) / 50.0f,
(rand() % 100 - 50) / 50.0f
};
a.radius = 10.0f + rand() % 20;
}
grid.rebuild(asteroids);
// Game loop
while (true) {
// Update positions (wrapping handled by toroidal topology)
for (auto& a : asteroids) {
a.position[0] += a.velocity[0];
a.position[1] += a.velocity[1];
// Manual wrap for position (grid handles query wrapping)
if (a.position[0] < 0) a.position[0] += world_size;
if (a.position[0] >= world_size) a.position[0] -= world_size;
if (a.position[1] < 0) a.position[1] += world_size;
if (a.position[1] >= world_size) a.position[1] -= world_size;
}
grid.update(asteroids);
// Collision detection works across boundaries!
grid.for_each_pair(asteroids, 40.0f,
[&](std::size_t i, std::size_t j) {
// Toroidal distance is handled automatically
handle_asteroid_collision(asteroids[i], asteroids[j]);
});
// ... render frame ...
}
}
Example 6: Benchmark Performance
Measure build and query performance.
#include <chrono>
void benchmark() {
const size_t N = 1000000; // 1 million particles
struct Point { std::array<float, 3> pos; };
std::vector<Point> points(N);
// Random distribution
for (auto& p : points) {
p.pos = {
static_cast<float>(rand() % 10000),
static_cast<float>(rand() % 10000),
static_cast<float>(rand() % 10000)
};
}
grid_config<3> cfg{
.cell_size = {100.0f, 100.0f, 100.0f},
.world_size = {10000.0f, 10000.0f, 10000.0f},
.topology_type = topology::bounded
};
sparse_spatial_hash<Point, 3> grid(cfg);
// Benchmark rebuild
auto start = std::chrono::high_resolution_clock::now();
grid.rebuild(points);
auto end = std::chrono::high_resolution_clock::now();
auto rebuild_ms = std::chrono::duration<double, std::milli>(end - start).count();
std::cout << "Rebuild " << N << " points: " << rebuild_ms << " ms\n";
std::cout << "Throughput: " << (N / rebuild_ms * 1000) << " points/sec\n";
// Benchmark queries
start = std::chrono::high_resolution_clock::now();
size_t total_neighbors = 0;
for (int i = 0; i < 10000; ++i) {
auto neighbors = grid.query_radius(200.0f,
static_cast<float>(rand() % 10000),
static_cast<float>(rand() % 10000),
static_cast<float>(rand() % 10000));
total_neighbors += neighbors.size();
}
end = std::chrono::high_resolution_clock::now();
auto query_ms = std::chrono::duration<double, std::milli>(end - start).count();
std::cout << "10000 queries: " << query_ms << " ms\n";
std::cout << "Avg query time: " << (query_ms / 10000 * 1000) << " us\n";
std::cout << "Avg neighbors/query: " << (total_neighbors / 10000) << "\n";
}
More Examples
For additional examples including:
- Custom allocators for better performance
- Integration with physics engines
- Hierarchical multi-resolution grids
See the examples directory on GitHub.