Applying Spatial Partitioning for Proximity Queries

Utilize grid-based spatial partitioning to efficiently track and query nearby NPCs, significantly reducing the overhead of distance-based sensory calculations.

In this lesson, you will learn how to optimize your AI’s perception system by replacing expensive "check-every-agent" loops with grid-based spatial partitioning.

The Problem: O(n²) Complexity

When you have dozens of NPCs, checking every agent to see if a target is nearby becomes a performance bottleneck. If you use Vector3.Distance between every possible pair of NPCs every frame, your CPU usage will skyrocket as your population grows. This is known as an $O(n^2)$ operation—it scales poorly because every new agent exponentially increases the number of checks.

The Solution: Grid-Based Partitioning

Instead of checking everyone, we divide the game world into a 2D grid of "cells." Each NPC is assigned to a specific cell based on their current transform.position. When an AI needs to perform a proximity query (e.g., "Find all nearby enemies"), it only checks its own cell and the eight immediate neighbors.

By ignoring agents in distant cells, you instantly discard the vast majority of irrelevant calculations.

Implementation Concept

You can represent the world grid using a Dictionary<Vector2Int, List<NPC>>. Each key is a coordinate, and the value is a list of agents currently standing there.

// Simplified update logic
void UpdateCellAssignment(NPC npc) {
    Vector2Int newCell = GetCellFromPosition(npc.transform.position);
    if (newCell != npc.currentCell) {
        grid[npc.currentCell].Remove(npc);
        grid[newCell].Add(npc);
        npc.currentCell = newCell;
    }
}

When an NPC performs a sensory check, they simply query their local grid vicinity:

foreach (var neighbor in GetNeighbors(myCell)) {
    float dist = Vector3.Distance(myPosition, neighbor.transform.position);
    if (dist < detectionRadius) {
        // Trigger perception logic
    }
}

This approach drastically reduces the number of distance checks, ensuring that your AI logic remains performant regardless of how many agents are roaming far away from the player. It shifts the overhead from constant distance calculations to a lightweight cell-update step that only happens when an agent moves across a boundary.

Key Takeaway: By constraining proximity queries to local spatial cells, you reduce the workload from checking every agent in the scene to only those within immediate range, allowing your AI systems to scale efficiently.