Spatial queries

“Who is near me?” is the core question of most simulations. Checking every pair is O(n²); a spatial grid answers it by looking only at nearby cells.

The built-in grid

Turn it on with a cell size near your usual query radius:

#![allow(unused)]
fn main() {
Game::new("Boids", 1280, 720)
    .spatial_grid(24.0)
    .sim_system(flock);
}

At the start of every tick, every entity with a Transform2D is indexed into ctx.spatial. Query it from any sim system:

#![allow(unused)]
fn main() {
struct Neighbors(usize);

fn count_neighbors(ctx: &mut Ctx) {
    let grid = &ctx.spatial;
    ctx.world
        .query::<(Entity, &Transform2D, &mut Neighbors)>()
        .par_for_each(|(me, t, n)| {
            n.0 = 0;
            grid.for_each_in_radius(t.position, 10.0, |o| {
                if o.entity != me { n.0 += 1; }
            });
        });
}
}

// crabby::game("Boids", 1280, 720).spatial_grid(24).sim_system(count_neighbors);
static void count_neighbors(crabby::ctx& ctx) {
    const auto grid = ctx.spatial_view();
    ctx.world().each_par([&](crabby::entity me, const crabby::transform2d& t, Neighbors& n) {
        n.count = 0;
        grid.for_each_in_radius(t.position, 10, [&](const crabby::grid_hit& o) {
            if (crabby::bits(o.entity) != me) ++n.count;
        });
    });
}

The grid is read-only while you query the world, so this runs on all cores. In C++, ctx.spatial_view() gives a view that walks the grid inline (no call into the engine per query); ctx.spatial_radius(center, r, hits) fills a vector instead, which is simpler but slower in hot loops.

Method	Visits
`for_each_in_radius(center, r, f)`	entries within `r` of `center`
`for_each_in_rect(min, max, f)`	entries inside the rectangle
`count_in_radius(center, r)`	how many entries are within `r`
`nearest(center, max_r, accept)`	the closest entry `accept` agrees to

Each visit gives a GridEntry with entity and position.

Every 32 ticks (SPATIAL_SORT_EVERY) the built-in system also reorders entities by grid cell (World::sort_by with spatial_key), so neighbors in space are neighbors in memory. With a million boids this cut a tick from 62 ms to 41 ms.

Your own grid, with data

The built-in grid stores only entity and position. When neighbors need more data, for example a boid’s velocity, keep your own SpatialGrid<T> inside the system and fill it with rebuild_with_data:

#![allow(unused)]
fn main() {
/// The flocking system. It owns a grid that stores each boid's velocity, so
/// neighbors' velocities can be read while the world is busy with the query.
fn flocking(bounds: Vec2) -> impl FnMut(&mut Ctx) {
    let mut grid = SpatialGrid::with_data(RADIUS);
    move |ctx: &mut Ctx| {
        let dt = ctx.dt();
        // Keep boids that are close in space close in memory, so neighbor
        // lookups hit the cache (1M boids: 62 -> 40 ms/tick).
        if ctx.sim_tick().is_multiple_of(SPATIAL_SORT_EVERY) {
            ctx.world.sort_by::<Transform2D>(|t| spatial_key(t.position, RADIUS));
        }
        grid.rebuild_with_data(
            ctx.world
                .query::<(Entity, &Transform2D, &Vel)>()
                .iter()
                .map(|(e, t, v)| (e, t.position, v.0)),
        );
        let grid = &grid;
        ctx.world
            .query::<(Entity, &mut Transform2D, &mut Vel)>()
            .par_for_each(|(me, t, v)| {
                let (mut away, mut heading, mut center, mut n) = (Vec2::ZERO, Vec2::ZERO, Vec2::ZERO, 0.0);
                grid.for_each_in_radius(t.position, RADIUS, |o| {
                    if o.entity == me {
                        return;
                    }
                    let d = t.position - o.position;
                    away += d / d.length_squared().max(1.0);
                    heading += o.data;
                    center += o.position;
                    n += 1.0;
                });
                let mut steer = away * 900.0;
                if n > 0.0 {
                    steer += (heading / n - v.0) * 1.5 + (center / n - t.position) * 1.2;
                }
                let speed = (v.0 + steer * dt).length().clamp(MIN_SPEED, MAX_SPEED);
                v.0 = (v.0 + steer * dt).normalize_or(Vec2::X) * speed;
                t.position = (t.position + v.0 * dt).rem_euclid(bounds);
                t.rotation = v.0.to_angle();
            });
    }
}
}

// The flocking system. Its grid stores each boid's index into `velocities`,
// so neighbors' velocities can be read while the query borrows the world.
struct Flocking {
    explicit Flocking(vec2 world_size) : bounds(world_size) {}
    vec2 bounds;
    std::shared_ptr<crabby::grid> grid = std::make_shared<crabby::grid>(RADIUS);
    std::shared_ptr<std::vector<crabby::grid_item>> items = std::make_shared<std::vector<crabby::grid_item>>();
    std::shared_ptr<std::vector<vec2>> velocities = std::make_shared<std::vector<vec2>>();

    void operator()(crabby::ctx& ctx) {
        auto world = ctx.world();
        const float dt = ctx.dt();
        // Keep boids that are close in space close in memory (cache hits).
        if (ctx.sim_tick() % SPATIAL_SORT_EVERY == 0) world.sort_spatial(RADIUS);
        items->clear();
        velocities->clear();
        world.each([&](crabby::entity e, const crabby::transform2d& t, const Vel& v) {
            items->push_back({crabby::entity_of(e), t.position, std::uint32_t(velocities->size())});
            velocities->push_back(v.v);
        });
        grid->rebuild(*items);

        const auto view = grid->view();
        const auto& vels = *velocities;
        const vec2 b = bounds;
        world.each_par([&](crabby::entity me, crabby::transform2d& t, Vel& v) {
            vec2 away{0, 0}, heading{0, 0}, center{0, 0};
            float n = 0;
            view.for_each_in_radius(t.position, RADIUS, [&](const crabby::grid_item& o) {
                if (crabby::bits(o.entity) == me) return;
                const vec2 d = t.position - o.position;
                away += d / std::max(crabby::length_squared(d), 1.0f);
                heading += vels[o.data];
                center += o.position;
                n += 1;
            });
            vec2 steer = away * 900.0f;
            if (n > 0) steer += (heading / n - v.v) * 1.5f + (center / n - t.position) * 1.2f;
            const vec2 next = v.v + steer * dt;
            const float speed = std::min(std::max(crabby::length(next), MIN_SPEED), MAX_SPEED);
            v.v = crabby::normalize_or(next, {1, 0}) * speed;
            t.position = crabby::rem_euclid(t.position + v.v * dt, b);
            t.rotation = crabby::to_angle(v.v);
        });
    }
};

C++ uses a crabby::grid, whose items carry a uint32_t of your own (here an index into a velocity array), and walks it with grid->view().

Choosing a cell size

About your query radius is a good start: a radius query then reads a 3×3 block of cells.
Much smaller cells mean more cells to visit; much larger means more entries per cell to reject.
Queries much larger than the world fall back to a plain scan, so huge radii stay correct and don’t get slow.

Keyboard shortcuts

Ponko

Spatial queries

The built-in grid

Your own grid, with data

Choosing a cell size