Spatial Hashing
Masterclass.

The Brute Force Nightmare

In a standard, naive collision or proximity system, every object checks every other object. This is O(N²) complexity. At small scales, it's fine. At game-scale, it's a death sentence.

Toggle the Spatial Hash mode above. Watch the lines collapse. By only checking objects in the same "neighborhood," we reduce the workload from thousands of checks to a handful of clustered tests.

Visualization of Proximity

Imagine 1,000 bullets and 100 enemies. A brute-force system doesn't care if a bullet is 1,000 meters away; it still runs the distance math. Spatial Hashing filters out the irrelevant noise before the math even starts.

The Grid Strategy

By dividing the world into a fixed grid of "buckets," we can map any 3D coordinate to a specific bucket in constant time. This is the foundation of almost every modern physics engine.

Tuning the Cell Size is critical. If cells are too small, objects span many buckets. If they are too large, we check too many irrelevant objects. The goal is to maximize the Optimization % shown above.

Bucket Pooling

In C#, calling new List<T>() in an Update loop creates "Garbage." When Unity's Garbage Collector runs to clean this up, your game stutters. We solve this by recycling memory.

// The internal pooling logic
private Stack<List<T>> _pool = new();

private List<T> GetNewList() {
    return _pool.Count > 0 ? _pool.Pop() : new List<T>();
}

private void RecycleList(List<T> list) {
    list.Clear(); // Critical: keep the capacity, dump the items
    _pool.Push(list);
}

The Density Heatmap

Watch how the hash populates buckets in real-time. The intensity of the color represents how many entities are fighting for attention in that specific memory address.

Flattened Arrays & Prefix Sums

For the ultimate performance (as seen in Matthias Müller's Ten Minute Physics), we ditch Dictionaries entirely. We move to Flat Arrays.

// Contiguous memory structure
NativeArray<int> cellStart;  // Offsets into the object array
NativeArray<int> sortedObjects; // Objects sorted by their CellID

// Reading a cell is now a single, contiguous memory sweep:
int start = cellStart[cellID];
int end = cellStart[cellID + 1];
for (int i = start; i < end; i++) {
    Process(sortedObjects[i]); // Ultra-fast!
}

Burst & Job System

Spatial hashing is embarrassingly parallel. By using Unity's NativeMultiHashMap and the Burst Compiler, you can move these checks off the main thread and into high-speed C++ level machine code.

[BurstCompile]
struct SpatialQueryJob : IJobParallelFor {
    [ReadOnly] public NativeMultiHashMap<int, EntityData> hash;
    public void Execute(int index) {
        // Run proximity checks at 100x speed
    }
}