Spatial Queries

Spatial Queries

The PathfindingEngine includes a QuadTree-based spatial index for efficient O(log n) queries. This is useful for combat systems, AI awareness, and finding nearby objects.

Overview

Two separate QuadTrees are maintained:

• Node spatial index - For finding nearby waypoints
• Entity spatial index - For finding nearby entities

Both are automatically updated as entities move.

Entity Queries

Find Entities in Radius

var buffer: [64]u64 = undefined;
const nearby = engine.getEntitiesInRadius(center_x, center_y, radius, &buffer);

for (nearby) |entity_id| {
    // Process each nearby entity
}

Use cases:

• Attack range detection
• Explosion damage
• AI awareness radius
• Proximity triggers

Find Entities in Rectangle

var buffer: [64]u64 = undefined;
const in_area = engine.getEntitiesInRect(x, y, width, height, &buffer);

for (in_area) |entity_id| {
    // Process each entity in rectangle
}

Use cases:

• Room detection
• Zone triggers
• Selection boxes
• Camera culling

Node Queries

Find Nodes in Radius

var buffer: [32]u32 = undefined;
const nearby_nodes = engine.getNodesInRadius(x, y, radius, &buffer);

for (nearby_nodes) |node_id| {
    // Process each nearby node
}

Use cases:

• Finding spawn points
• Patrol waypoints
• Cover positions

Find Entities at Node

var buffer: [16]u64 = undefined;
const at_node = engine.getEntitiesAtNode(node_id, &buffer);

for (at_node) |entity_id| {
    // Entity is at this waypoint
}

Use cases:

• Checking if node is occupied
• Triggering node-based events

Combat Example

fn attackNearbyEnemies(engine: *Engine, game: *Game, attacker: u64, damage: u32) void {
    const pos = engine.getPosition(attacker) orelse return;
    const attack_range: f32 = 50.0;
    
    var nearby: [32]u64 = undefined;
    const targets = engine.getEntitiesInRadius(pos.x, pos.y, attack_range, &nearby);
    
    for (targets) |target| {
        if (target == attacker) continue;  // Don't hit self
        
        if (game.isEnemy(target)) {
            game.applyDamage(target, damage);
        }
    }
}

AI Awareness Example

fn updateAI(engine: *Engine, game: *Game, enemy: u64) void {
    const pos = engine.getPosition(enemy) orelse return;
    const sight_range: f32 = 200.0;
    
    var nearby: [64]u64 = undefined;
    const visible = engine.getEntitiesInRadius(pos.x, pos.y, sight_range, &nearby);
    
    for (visible) |entity| {
        if (game.isPlayer(entity)) {
            // Player spotted! Chase them
            if (engine.getCurrentNode(entity)) |player_node| {
                engine.requestPath(enemy, player_node) catch {};
            }
            break;
        }
    }
}

Performance

The QuadTree provides O(log n) average-case performance for spatial queries, compared to O(n) for brute-force distance checks.

Operation	QuadTree	Brute Force
Radius query	O(log n + k)	O(n)
Rectangle query	O(log n + k)	O(n)

Where n is total entities and k is result count.

Buffer Sizing

All query methods write to a caller-provided buffer. Size the buffer appropriately:

// Small area, few expected results
var small_buffer: [8]u64 = undefined;

// Large area, many possible results
var large_buffer: [256]u64 = undefined;

If more entities exist than buffer size, only the first buffer.len are returned.

Automatic Updates

Entity positions in the spatial index are automatically updated during tick(). No manual update is needed.

// Movement updates spatial index automatically
engine.tick(&game, delta);

// Queries reflect current positions
const nearby = engine.getEntitiesInRadius(x, y, r, &buffer);