AgentFarm Spatial Indexing System

Executive Summary

The AgentFarm spatial indexing system provides efficient proximity queries and spatial reasoning capabilities essential for scalable multi-agent simulations. The system implements multiple spatial indexing strategies — KD-tree, Quadtree, and Spatial Hash Grid — to enable fast proximity queries for entity detection and spatial awareness, optimized for different query patterns.

System Overview
Spatial Indexing Strategies
Performance Characteristics
Configuration
Integration & Usage
Use Cases & Examples
References & Technical Details

System Overview

Mission & Requirements

The spatial indexing system enables:

Efficient proximity queries for agent-agent and agent-resource interactions
Scalable entity detection within perception radii
Real-time spatial awareness for hundreds to thousands of agents
Multiple indexing strategies optimized for different use cases
Memory-efficient storage with configurable performance trade-offs

Core Components

Spatial Index Implementation:

KD-Tree Indexing: O(log n) queries using scipy.spatial.cKDTree with optimized change detection
Quadtree Indexing: Hierarchical spatial partitioning for efficient range queries and dynamic updates
Spatial Hash Grid: Uniform bucket grid for near-constant-time neighborhood queries and efficient dynamic updates
Multiple Index Support: Choose index per use case; enable additional indices alongside defaults
Dynamic Updates: Efficient position updates without full index rebuilds

Spatial Indexing Strategies

1. KD-Tree Based Indexing

Purpose: Provides efficient continuous-space proximity queries using scientific computing libraries.

Technical Implementation:

from scipy.spatial import cKDTree
import numpy as np

# Spatial index maintains separate KD-trees for agents and resources
self.agent_kdtree = cKDTree(agent_positions)      # O(n log n) build
self.resource_kdtree = cKDTree(resource_positions) # O(m log m) build

# Query operations
nearby_agents = spatial_index.get_nearby(position, radius, ["agents"])  # O(log n)
nearest_resource = spatial_index.get_nearest(position, ["resources"])   # O(log n)

Key Features:

Continuous Position Support: Handles floating-point coordinates
Multi-Entity Type Queries: Separate trees for agents and resources
Automatic Cache Invalidation: Rebuilds when positions change significantly

2. Quadtree Based Indexing

Purpose: Provides hierarchical spatial partitioning for efficient range queries and dynamic entity updates.

Technical Implementation:

from farm.core.spatial import Quadtree

# Create quadtree with environment bounds
bounds = (0, 0, width, height)
quadtree = Quadtree(bounds, capacity=4)

# Insert entities
for entity in entities:
    position = entity.position
    quadtree.insert(entity, position)

# Query operations
nearby_entities = quadtree.query_radius(center, radius)  # O(log n) average
range_entities = quadtree.query_range((x, y, w, h))     # O(log n) average

Key Features:

Hierarchical Subdivision: Automatically divides space into quadrants when capacity exceeded
Rectangular Range Queries: Highly efficient for finding entities within rectangular regions
Dynamic Updates: Efficient position updates without full tree rebuilds
Memory Efficient: Hierarchical structure reduces cache misses for range queries
Spatial Locality: Nearby entities are grouped together in the hierarchy

When to Use Quadtree Indexing:

Rectangular or area-of-effect queries (combat, vision cones, territory analysis)
High-frequency position updates (agent movement, dynamic environments)
Range-based spatial operations (crowd density, group formations)
Scenarios requiring hierarchical spatial reasoning

3. Spatial Hash Grid Indexing

Purpose: Provides grid-based bucketing for O(1)-ish average neighborhood queries and fast dynamic updates.

Technical Implementation:

from farm.core.environment import Environment

env = Environment(width=100, height=100, resource_distribution="uniform")
env.enable_spatial_hash_indices(cell_size=5.0)  # optional cell size override

# Queries
nearby = env.spatial_index.get_nearby((50, 50), 10, ["agents_hash"])  # uses spatial hash
nearest = env.spatial_index.get_nearest((42, 18), ["resources_hash"])  # hash nearest

Key Features:

Uniform Grid Buckets: Entities stored in integer (ix, iy) buckets
Bounded Query Cost: Only checks buckets overlapping the query region
Fast Dynamic Updates: O(1) remove/insert on moves
Hotspot Robustness: Performs well under non-uniform distributions

When to Use Spatial Hashing:

Large, dynamic populations where rebuild cost is high
Frequent radius/neighbor queries with moderate radii
Non-uniform distributions (clusters, crowds) where locality helps

Performance Characteristics

Query Performance Characteristics

Strategy	Build Time	Query Time	Memory Usage	Best For
KD-Tree	O(n log n)	O(log n)	Implementation-dependent	Radial queries, nearest neighbor
Quadtree	O(n log n)	O(log n) average	Implementation-dependent	Range queries, dynamic updates
Spatial Hash	O(n)	~O(1) average neighborhood lookups	Implementation-dependent	Frequent neighbor queries, dynamic updates

Scaling Analysis

For KD-Tree Implementation:

Build Time: O(n log n) for n entities
Query Time: O(log n) per proximity query
Update Frequency: Only when positions change significantly
Memory Usage: ~200 KB per 100 agents/resources

For Quadtree Implementation:

Build Time: O(n log n) for n entities (with hierarchical subdivision)
Query Time: O(log n) average for range queries, O(log n) for radius queries
Update Frequency: Incremental updates for position changes
Memory Usage: ~150 KB per 100 agents (more efficient for range queries)
Subdivision: Automatic quadrant division based on entity density

Optimization Strategies

Change Detection: Only rebuild when positions actually change
Batch Updates: Queue and flush position updates in batches
Dirty Region Tracking: Restrict update work to touched regions
Partial Flushing: Process a bounded number of pending updates for responsiveness
Dual/Named Indexing: Mix KD-tree, Quadtree, and Spatial Hash indices by query type

Configuration

Configure spatial indexing through SimulationConfig.environment.spatial_index using SpatialIndexConfig:

from farm.config.config import SpatialIndexConfig

spatial_config = SpatialIndexConfig(
    enable_batch_updates=True,
    region_size=50.0,
    max_batch_size=100,
    max_regions=1000,
    enable_quadtree_indices=False,
    enable_spatial_hash_indices=True,
    spatial_hash_cell_size=15.0,
    performance_monitoring=True,
    debug_queries=False,
    dirty_region_batch_size=10,
)

If config.environment.spatial_index is not set, the environment initializes SpatialIndex with default batch-update settings.

When to Use KD-Tree Indexing

KD-Tree indexing is ideal when:

Environment uses continuous coordinates
Agents have large perception radii
High precision is required for spatial queries
Memory budget allows for tree storage
You need efficient proximity queries for hundreds to thousands of agents

Note: The system supports both KD-tree and Quadtree indexing. KD-trees are the default for their superior performance on radial queries. Quadtree indices can be enabled for specific use cases requiring efficient range queries and dynamic updates.

Integration & Usage

Basic Usage

from farm.core.spatial import SpatialIndex
from farm.core.environment import Environment

# Create environment with spatial indexing
env = Environment(
    width=100,
    height=100,
    resource_distribution="uniform",
)

# Access spatial index
spatial_index = env.spatial_index

# Query nearby agents
nearby = spatial_index.get_nearby(agent.position, 5.0, ["agents"])
nearby_agents = nearby.get("agents", [])

# Query nearest resource
nearest = spatial_index.get_nearest(agent.position, ["resources"])
nearest_resource = nearest.get("resources")

Enabling Quadtree Indices

# Enable Quadtree indices for range queries and dynamic updates
env.enable_quadtree_indices()

# Now you can use Quadtree-optimized queries
nearby_in_range = spatial_index.get_nearby_range(
    (x, y, width, height),  # Rectangular bounds
    ["agents_quadtree"]     # Use Quadtree index
)

# Dynamic position updates are more efficient with Quadtrees
spatial_index.update_entity_position(
    agent, old_position, new_position
)

# Get detailed Quadtree statistics
quadtree_stats = spatial_index.get_quadtree_stats("agents_quadtree")
print(f"Quadtree depth: {quadtree_stats}")

Enabling Spatial Hash Indices

# Enable Spatial Hash indices for fast neighborhood queries and dynamic updates
env.enable_spatial_hash_indices(cell_size=5.0)  # optional; uses heuristic if None

# Use spatial-hash-backed indices
nearby = spatial_index.get_nearby((x, y), radius, ["agents_hash"])  # bucketed radius query
nearest = spatial_index.get_nearest((x, y), ["resources_hash"])     # nearest via grid expansion

# Range queries
in_rect = spatial_index.get_nearby_range((rx, ry, rw, rh), ["agents_hash"])

Advanced Usage with Custom Queries

# Multi-type proximity query
nearby_entities = spatial_index.get_nearby(
    agent.position,
    10.0,
    ["agents", "resources"]
)
nearby_agents = nearby_entities.get("agents", [])
nearby_resources = nearby_entities.get("resources", [])

# Filtered queries with custom conditions
nearby_allies = [
    aid for aid in nearby_agents
    if env.get_agent(aid).team == agent.team
]

# Spatial analysis for decision making
def evaluate_position_safety(self, position):
    """Evaluate safety of a position based on nearby threats."""
    threats_result = spatial_index.get_nearby(position, self.threat_radius, ["agents"])
    allies_result = spatial_index.get_nearby(position, self.support_radius, ["agents"])
    threats = [a for a in threats_result.get("agents", []) if a.team != self.team]
    allies = [a for a in allies_result.get("agents", []) if a.team == self.team]

    threat_score = len(threats) * self.threat_weight
    support_score = len(allies) * self.support_weight

    return support_score - threat_score

Environment Integration

# Environment updates spatial index when agents/resources change
self.spatial_index.set_references(self._agent_objects.values(), self.resources)
self.spatial_index.update()  # Rebuilds KD-trees as needed

# AgentObservation queries spatial index for entity detection
nearby = spatial_index.get_nearby(agent.position, config.fov_radius, ["agents"])
computed_allies, computed_enemies = process_nearby_agents(nearby["agents"])

Coordinate Transformation

# World coordinates → Local observation coordinates
world_y, world_x = entity.position
local_y = config.R + (world_y - agent_y)
local_x = config.R + (world_x - agent_x)

# Handle boundary conditions
local_y = max(0, min(2*config.R, local_y))
local_x = max(0, min(2*config.R, local_x))

Use Cases & Examples

1. Combat Simulation

Spatial Index Usage in Combat:

Target Acquisition: Find nearest enemies within attack range
Formation Analysis: Identify allies within support radius
Threat Assessment: Count enemies within danger zone

# Combat target selection using spatial index
def find_combat_target(self, agent, max_range):
    """Find closest enemy within attack range."""
    nearby_result = spatial_index.get_nearby(
        agent.position,
        max_range,
        ["agents"]
    )
    nearby_enemies = [
        other for other in nearby_result.get("agents", [])
        if other is not agent and other.agent_type != agent.agent_type
    ]

    if nearby_enemies:
        # Get actual distance to closest enemy
        closest_enemy = min(
            nearby_enemies,
            key=lambda eid: self.distance(agent.position, env.get_agent(eid).position)
        )
        return closest_enemy

    return None

2. Resource Gathering

Spatial Index Usage in Resource Management:

Resource Discovery: Find nearest resources of specific types
Competition Analysis: Identify other agents targeting same resources
Path Optimization: Plan routes avoiding contested resources

# Resource gathering with spatial awareness
def find_optimal_resource(self, agent, resource_type):
    """Find best resource considering competition."""
    nearby_result = spatial_index.get_nearby(
        agent.position,
        self.search_radius,
        [resource_type]
    )
    nearby_resources = nearby_result.get(resource_type, [])

    # Filter out heavily contested resources
    optimal_resources = []
    for resource in nearby_resources:
        competitors_result = spatial_index.get_nearby(
            resource.position,
            self.competition_radius,
            ["agents"]
        )
        competitors = competitors_result.get("agents", [])
        if len(competitors) < self.max_competitors:
            optimal_resources.append(resource)

    return optimal_resources[0] if optimal_resources else None

Spatial Index Usage in Social Interactions:

Ally Detection: Find nearby allies for coordination
Group Formation: Identify agents for flocking behavior
Communication Networks: Establish local communication links

# Social behavior using spatial awareness
def find_social_partners(self, agent):
    """Find nearby allies for social interactions."""
    nearby_result = spatial_index.get_nearby(
        agent.position,
        self.social_radius,
        ["agents"]
    )
    nearby_allies = [
        other for other in nearby_result.get("agents", [])
        if other is not agent and other.agent_type == agent.agent_type
    ]

    # Prioritize based on relationship strength and distance
    potential_partners = []
    for ally_id in nearby_allies:
        ally = env.get_agent(ally_id)
        distance = self.distance(agent.position, ally.position)
        relationship = self.get_relationship_strength(agent, ally)

        score = relationship / (1 + distance)  # Closer, stronger relationships preferred
        potential_partners.append((ally_id, score))

    return sorted(potential_partners, key=lambda x: x[1], reverse=True)

Spatial Index Usage in Navigation:

Obstacle Avoidance: Identify obstacles in planned paths
Goal-directed Movement: Find waypoints toward objectives
Terrain Analysis: Evaluate movement costs in different areas

# Navigation assistance using spatial index
def plan_navigation_path(self, start_pos, goal_pos):
    """Plan path considering spatial obstacles."""
    # If you register an "obstacles" named index, query it directly.
    path_result = spatial_index.get_nearby(
        start_pos,
        self.path_lookahead,
        ["obstacles"]
    )
    path_obstacles = path_result.get("obstacles", [])

    # Adjust path based on obstacle positions
    adjusted_path = self.adjust_path_for_obstacles(
        start_pos, goal_pos, path_obstacles
    )

    return adjusted_path

References & Technical Details

📖 Detailed Technical Documentation

For in-depth technical information, refer to:

Core Implementation:

Perception System Design - Complete spatial index implementation details
Spatial indexing - Performance and backend details
Architecture - System integration patterns

Performance & optimization:

Configuration Guide - Complete spatial indexing configuration reference
Batch spatial updates - Dirty regions and batched updates
Spatial module performance - Benchmarks and scaling notes

Related topics:

Redis agent memory - Optional distributed memory for agents

🔧 Implementation Files

Key implementation modules:

farm/core/spatial/ - Spatial index implementations (index.py, quadtree.py, hash_grid.py, dirty_regions.py)
farm/core/environment.py - Environment integration
farm/core/observations.py - Observation system integration

⚙️ Configuration Examples

See Configuration Guide for:

Complete configuration options
Performance tuning recommendations
Environment-specific settings

📊 Performance Benchmarks

For detailed performance characteristics:

Query latency benchmarks
Memory usage patterns by strategy
Scaling performance with agent count
Optimization recommendations

Batch Spatial Updates with Dirty Region Tracking

Overview

The spatial indexing system now includes batch spatial updates with dirty region tracking, a performance optimization feature that significantly improves efficiency in dynamic simulations by only updating regions that have actually changed.

Key Features

Dirty Region Tracking: Only regions that have changed are marked for updates
Batch Processing: Multiple position updates are collected and processed together
Partial Flushing: Process only a subset of pending updates for fine-grained control
Priority-Based Updates: Higher priority regions are updated first
Automatic Cleanup: Old regions are automatically cleaned up to prevent memory bloat
Performance Monitoring: Detailed statistics about update efficiency

Benefits

Reduced Update Overhead: Up to 70% reduction in computational overhead for dynamic simulations
Improved Scalability: Performance improvements scale with simulation size
Data Integrity: Ensures all regions reflect current state without stale data
Memory Efficiency: Better memory usage patterns through batched processing
Fine-Grained Control: Partial flushing enables responsive applications with high throughput

Configuration

from farm.config import SimulationConfig
from farm.config.config import SpatialIndexConfig
from farm.core.environment import Environment

spatial_config = SpatialIndexConfig(
    enable_batch_updates=True,      # Enable batch updates
    region_size=50.0,               # Size of each region
    max_batch_size=100,             # Maximum updates per batch
    max_regions=1000,               # Maximum regions to track
    performance_monitoring=True,    # Enable performance monitoring
)

sim_config = SimulationConfig.from_centralized_config(environment="development")
sim_config.environment.spatial_index = spatial_config
sim_config.environment.width = 200
sim_config.environment.height = 200

Usage

# Batch updates follow SimulationConfig.environment.spatial_index when the environment is constructed
env = Environment(
    width=sim_config.environment.width,
    height=sim_config.environment.height,
    resource_distribution="uniform",
    config=sim_config,
)

# For fine-grained control, use partial flushing
spatial_index = env.spatial_index

# Process only a subset of pending updates
processed = spatial_index.flush_partial_updates(max_updates=25)
print(f"Processed {processed} updates")

# Check remaining pending updates
pending = len(spatial_index._pending_position_updates)
print(f"Remaining updates: {pending}")

# Monitor performance
stats = env.get_spatial_performance_stats()
print(f"Batch updates processed: {stats['batch_updates']['total_batch_updates']}")
print(f"Average batch size: {stats['batch_updates']['average_batch_size']}")

Partial Flushing

For advanced applications requiring fine-grained control over update timing, the system supports partial flushing of pending updates:

# Process updates in chunks for responsive applications
total_processed = 0
while len(spatial_index._pending_position_updates) > 0:
    processed = spatial_index.flush_partial_updates(max_updates=10)
    total_processed += processed
    # Yield control or perform other tasks here
    time.sleep(0.001)  # Brief pause to maintain responsiveness

print(f"Total updates processed: {total_processed}")

When to Use Partial Flushing:

Real-time applications requiring consistent frame rates
Systems with tight latency requirements
High-throughput scenarios where full batch processing causes unacceptable pauses
Progressive update strategies for large simulations

Conclusion

The AgentFarm spatial indexing system provides the foundation for efficient spatial reasoning in multi-agent simulations. The system now includes advanced batch spatial updates with dirty region tracking, offering optimal performance for different query patterns in continuous-space environments.

The spatial indexing system enables:

Efficient proximity queries for real-time agent interactions
Multiple indexing strategies: KD-tree, Quadtree, and Spatial Hash
Scalable spatial awareness supporting thousands of agents with optimized change detection
Memory-efficient storage with intelligent cache invalidation and position tracking
Dynamic updates: Efficient position changes without full index rebuilds
Flexible named indices for custom spatial data sources and filtering
Batch spatial updates: Only update regions that have changed for maximum efficiency
Partial flushing: Fine-grained control over update timing for responsive applications
Dirty region tracking: Systematic approach to ensure data integrity and performance

Choosing the Right Index:

Use KD-trees for: Nearest neighbor searches, radial proximity queries, static or slowly changing environments
Use Quadtrees for: Rectangular range queries, area-of-effect operations, frequently moving entities, hierarchical spatial analysis
Use Spatial Hash for: Large dynamic populations, frequent neighborhood queries, and hotspot-heavy distributions
Use Batch Updates for: Dynamic simulations with frequent position changes, large-scale environments, performance-critical applications
Use Partial Flushing for: Real-time applications, high-throughput scenarios, systems with latency requirements

This enhanced spatial foundation is essential for creating realistic multi-agent behaviors, from combat and resource gathering to social interactions and navigation, making it a critical component of the AgentFarm simulation framework. The batch spatial updates feature ensures that the system can scale efficiently to handle complex, dynamic simulations with thousands of agents while maintaining optimal performance.

AgentFarm Spatial Indexing System

Executive Summary

Table of Contents

System Overview

Mission & Requirements

Core Components

Spatial Indexing Strategies

1. KD-Tree Based Indexing

2. Quadtree Based Indexing

3. Spatial Hash Grid Indexing

Performance Characteristics

Query Performance Characteristics

Scaling Analysis

Optimization Strategies

Configuration

When to Use KD-Tree Indexing

Integration & Usage

Basic Usage

Enabling Quadtree Indices

Enabling Spatial Hash Indices

Advanced Usage with Custom Queries

Environment Integration

Coordinate Transformation

Use Cases & Examples

1. Combat Simulation

2. Resource Gathering

4. Navigation and Pathfinding

References & Technical Details

📖 Detailed Technical Documentation

🔧 Implementation Files

⚙️ Configuration Examples

📊 Performance Benchmarks

Batch Spatial Updates with Dirty Region Tracking

Overview

Key Features

Benefits

Configuration

Usage

Partial Flushing

Conclusion

Executive Summary

Table of Contents

System Overview

Mission & Requirements

Core Components

Spatial Indexing Strategies

1. KD-Tree Based Indexing

2. Quadtree Based Indexing

3. Spatial Hash Grid Indexing

Performance Characteristics

Query Performance Characteristics

Scaling Analysis

Optimization Strategies

Configuration

When to Use KD-Tree Indexing

Integration & Usage

Basic Usage

Enabling Quadtree Indices

Enabling Spatial Hash Indices

Advanced Usage with Custom Queries

Environment Integration

Coordinate Transformation

Use Cases & Examples

1. Combat Simulation

2. Resource Gathering

3. Social Behavior

4. Navigation and Pathfinding

References & Technical Details

📖 Detailed Technical Documentation

🔧 Implementation Files

⚙️ Configuration Examples

📊 Performance Benchmarks

Batch Spatial Updates with Dirty Region Tracking

Overview

Key Features

Benefits

Configuration

Usage

Partial Flushing

Conclusion