Grids espaciales y bucketing: del O(N²) al O(k)

0. El problema en una frase

Tienes 1000 agentes y cada uno necesita saber qué agentes están a menos de 30 píxeles. Implementación ingenua: para cada agente, comparar contra los otros 999. Total: 999.000 comparaciones por frame. A 60 FPS, eso es 60 millones de operaciones por segundo solo para una pregunta tonta.

La solución: dividir el mundo en celdas y guardar a cada agente en la celda donde cae. Ahora la pregunta “qué hay cerca de mí” toca solo las pocas celdas que tocan tu radio. Pasamos de O(N²) a O(k) donde k es lo que cabe en esas celdas — un puñado.

Brute force · O(N²)0 checks/frame

Uniform grid · O(k)0 candidatos · 0 hits · 0 cells

Cell size: 48px

Mueve el cursor sobre cualquier panel. El radio de búsqueda es fijo. Cambia el cell size y observa cómo varían los candidatos: cells muy chicas → muchas cells visitadas; cells muy grandes → muchos candidatos a filtrar.

Figura 1 — A la izquierda, brute force: cada agente compara contra todos. A la derecha, uniform grid: solo se visitan las celdas tocadas por el radio. Mueve el cursor sobre cualquier panel; cambia el cell size y observa cómo varían los candidatos.

1. Cuándo te salva la vida

Cualquier sistema que pregunte “qué hay cerca” en cada frame:

• Flocking / boids — separación, alineación y cohesión miran solo vecinos. Sin grid, 200 boids ya cuestan caro.
• Detección de enemigos — el NPC pregunta “¿hay algún rojo en mi radio de aggro?” cada tick.
• Colisiones broad-phase — antes de un check fino, descartas pares lejanos.
• Pathfinding con agentes dinámicos — A* con costo extra por proximidad a otros NPCs.
• Partículas con interacciones — fluidos SPH, pelos, telas.

2. Uniform grid: el caso simple

Una matriz fija cells[cols][rows]. Para insertar un agente en (x, y):

cx = floor(x / cellSize)
cy = floor(y / cellSize)
cells[cx][cy].add(agent)

Para preguntar “qué hay en un radio r desde (x, y)”:

minCx = floor((x - r) / cellSize)
maxCx = floor((x + r) / cellSize)
minCy = floor((y - r) / cellSize)
maxCy = floor((y + r) / cellSize)

candidates = []
for cy in minCy..maxCy:
    for cx in minCx..maxCx:
        candidates.extend(cells[cx][cy])

# filtrar por distancia real (cuadrado vs círculo)
hits = [c for c in candidates if dist(c, (x,y)) <= r]

Eso es todo. Dos pasos: broad phase (qué celdas tocan el AABB del radio) y narrow phase (cuáles candidatos están realmente dentro del círculo).

2.1 Por qué los candidatos son más que los hits

El AABB que envuelve el círculo del radio es un cuadrado. Las celdas que tocan ese cuadrado contienen agentes que pueden estar dentro o fuera del círculo. Es trabajo extra inevitable; el truco es que el cuadrado tiene O(r²/cellSize²) celdas — constante respecto a N. Esa es la victoria.

3. El sweet spot del cell size

Aquí está el botón mágico de cualquier grid: ¿qué tamaño tiene cada celda?

Cell size: 36px

111 cells ocupadas de 119·carga máx 7 items/cell·candidatos por query: 21.3

La barra inferior muestra el costo aproximado por query (cells × overhead + candidatos) en función del cell size. El mínimo es tu sweet spot — suele estar cerca del radio de búsqueda.

Figura 2 — Mismo set de agentes (semilla fija), distintos cell sizes. La curva inferior es el costo aproximado por query (cells visitadas + candidatos). El mínimo es el sweet spot.

Tres regímenes:

• Cells muy chicas (cellSize ≪ radio): para cubrir tu radio toca visitar muchas celdas vacías. Mucho overhead de iteración, pocos candidatos por celda.
• Cells muy grandes (cellSize ≫ radio): pocas celdas tocadas, pero cada una está repleta de agentes. Mucho narrow-phase inútil.
• Sweet spot (cellSize ≈ radio): las celdas tienen tamaño parecido al de tu query, así tocas 4–9 celdas con cargas moderadas.

3.1 Cuando los agentes no están bien distribuidos

El grid uniforme asume densidad pareja. Si tienes 80% de los agentes apilados en una zona pequeña (un boss fight, una capital de civilización), las celdas de esa zona se sobrecargan y vuelves a un costo cuasi-cuadrático dentro de cada celda.

Soluciones:

1. Reducir cell size localmente — pero ya no es uniforme.
2. Quadtree — celdas se subdividen donde hay densidad. Es el siguiente tutorial.
3. Spatial hash — la versión sparse del grid, ideal para mundos abiertos no acotados.

4. Sparse hash: cuando el mundo no tiene bordes

El uniform grid asume un mundo acotado (width × height). Si tu mundo es procedural infinito, o el jugador puede irse a coordenadas negativas, no puedes pre-asignar cols × rows celdas.

Solución: hash las coordenadas de la celda y usa un hashmap.

hash(cx, cy) = (cx * 73856093) XOR (cy * 19349663)
bucket = hash(cx, cy) % nBuckets

buckets[bucket].add(agent)

Ahora:

• No hay límite de mundo: cualquier (cx, cy) mapea a un bucket.
• Memoria proporcional a celdas ocupadas — los buckets vacíos no existen.
• Queries idénticas: mismo barrido del AABB, mismo lookup por celda.

26 cells reales·16 buckets · 40 items·carga máx 5

Arrastra cualquier punto: la cell que lo contiene puede cambiar, y por tanto el bucket también. Si dos cells distintas mapean al mismo bucket (colisión de hash), se conectan con una curva. Los buckets ahorran memoria — solo guardan items reales — pero las colisiones añaden ruido a las queries.

Figura 3 — Cada celda real (recuadro) mapea a un bucket (barra inferior) vía hash. Cuando dos celdas distintas caen en el mismo bucket, hay colisión: los curva las conecta en color saturado. Arrastra cualquier punto.

4.1 Colisiones: el precio del sparse

Como los buckets son pocos (16, 64, 256…), inevitablemente dos celdas distintas mapean al mismo bucket. No es un bug — es la naturaleza del hash. Lo que cambia es:

• Más buckets → menos colisiones, más memoria por buckets vacíos.
• Hash mejor → colisiones más uniformemente repartidas.
• Query → al iterar el bucket, vas a ver items de otra celda. Hay que filtrarlos por (cx, cy) real, no solo por hash.

En la práctica: con nBuckets = 4 × cellsEsperadas, las colisiones son ruido despreciable.

5. Aplicación: detección de enemigos

Caso real de combate: 60 unidades aliadas y 60 enemigas. Cada aliada pregunta “¿qué enemigos están a 35 px?” todos los frames.

Brute forceUniform grid

⏸ Pausar

0 checks/frame0 pares detectados0.00 ms/frame

Cell size: 48px

Cada agente azul consulta enemigos rojos en un radio fijo de 35px. Brute force compara contra los 120 agentes en cada query. El uniform grid solo visita las cells del cuadrado que cubre el radio.

Figura 4 — Mismo escenario en dos modos. Los checks/frame son las comparaciones de distancia que el algoritmo hace por frame. El brute force es estable en N×M; el grid se desploma a un porcentaje según el cell size.

Si subes el cell size por encima de 2× el radio, los candidatos crecen y el costo grid sube; si lo bajas mucho, se desploma — pero a expensas de memoria.

5.1 ¿Cuánto rinde realmente?

Para 1000 agentes con queries de radio 30 en un mundo 800×600:

Estructura	Checks/frame típicos	Memoria
Brute force	~1.000.000	nula extra
Uniform grid (cellSize=60)	~25.000	cols × rows listas
Sparse hash (256 buckets)	~30.000	proporcional a cells ocupadas

Diferencia de 30–40× con un cambio mínimo de código.

6. Pseudocódigo limpio

class UniformGrid<T>:
    cellSize: float
    cols, rows: int
    cells: List<List<T>>   # cols * rows

    function clear()
        for each list in cells: list.clear()

    function insert(item, x, y)
        cx = floor(x / cellSize)
        cy = floor(y / cellSize)
        if 0 <= cx < cols and 0 <= cy < rows:
            cells[cy * cols + cx].add(item)

    function queryRadius(x, y, r) -> List<T>
        minCx = floor((x - r) / cellSize) clamp 0..cols-1
        maxCx = floor((x + r) / cellSize) clamp 0..cols-1
        minCy = floor((y - r) / cellSize) clamp 0..rows-1
        maxCy = floor((y + r) / cellSize) clamp 0..rows-1

        out = []
        for cy in minCy..maxCy:
            for cx in minCx..maxCx:
                for item in cells[cy * cols + cx]:
                    if dist(item.pos, (x,y)) <= r:
                        out.add(item)
        return out

Para sparse hash, sustituye la matriz fija por un HashMap<int, List<T>> con hash(cx, cy) como clave.

7. Implementación en Unity / C#

public class UniformGrid<T> where T : IPositionable {
    readonly float cellSize;
    readonly int cols, rows;
    readonly List<T>[] cells;

    public UniformGrid(float worldW, float worldH, float cellSize) {
        this.cellSize = cellSize;
        cols = Mathf.Max(1, Mathf.CeilToInt(worldW / cellSize));
        rows = Mathf.Max(1, Mathf.CeilToInt(worldH / cellSize));
        cells = new List<T>[cols * rows];
        for (int i = 0; i < cells.Length; i++) cells[i] = new List<T>(8);
    }

    public void Clear() {
        for (int i = 0; i < cells.Length; i++) cells[i].Clear();
    }

    public void Insert(T item) {
        int cx = (int)(item.Position.x / cellSize);
        int cy = (int)(item.Position.y / cellSize);
        if ((uint)cx >= cols || (uint)cy >= rows) return;
        cells[cy * cols + cx].Add(item);
    }

    public void QueryRadius(Vector2 p, float r, List<T> result) {
        result.Clear();
        int minCx = Mathf.Clamp((int)((p.x - r) / cellSize), 0, cols - 1);
        int maxCx = Mathf.Clamp((int)((p.x + r) / cellSize), 0, cols - 1);
        int minCy = Mathf.Clamp((int)((p.y - r) / cellSize), 0, rows - 1);
        int maxCy = Mathf.Clamp((int)((p.y + r) / cellSize), 0, rows - 1);
        float r2 = r * r;
        for (int cy = minCy; cy <= maxCy; cy++) {
            for (int cx = minCx; cx <= maxCx; cx++) {
                var bucket = cells[cy * cols + cx];
                for (int i = 0; i < bucket.Count; i++) {
                    var v = (Vector2)bucket[i].Position - p;
                    if (v.sqrMagnitude <= r2) result.Add(bucket[i]);
                }
            }
        }
    }
}

Trucos importantes para producción:

• Pre-allocar result y reusarlo entre queries (evita allocs en GC).
• (uint)cx >= cols es un check de bounds con un solo comparison (signed-to-unsigned cast).
• for indexado sobre List<T> es ~2× más rápido que foreach en hot paths.

8. En otros engines

• Godot: usa PhysicsServer2D si solo necesitas colisiones; para queries custom, implementa el grid en GDScript o C#. La idea es idéntica.
• Unreal: tienes UNavigationSystemV1::GetRandomReachablePointInRadius y similares para casos comunes. Para custom: TMap<FIntPoint, TArray<FActor>> funciona como sparse hash.
• JavaScript / Canvas: usa Map<number, T[]> con cy * cols + cx como key. Tu propio motor en menos de 100 líneas.

9. Errores comunes

1. Olvidarte de clear — el grid se llena de items zombies de frames anteriores.
2. Cell size hardcoded — si cambias el radio típico de queries, hay que rebalancear.
3. No filtrar por distancia real — los candidatos del AABB no son los hits del círculo. Olvidarlo da bugs sutiles (“el enemigo me ve desde la esquina”).
4. Insertar antes de mover — orden correcto: mover agentes → clear grid → insertar todo → preguntar. Si insertas en el frame N y mueves en el N+1 sin re-insertar, las queries son del frame anterior.
5. Hash modulo demasiado chico — con 16 buckets para 500 cells ocupadas, todo colisiona. Empieza con nBuckets ≈ 4 × cellsEsperadas.

10. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. Tu radio de query es 25px. ¿Qué cell size debería ser tu primera prueba?

   • AAlrededor de 50px (≈ 2× radio).
   • BAlrededor de 5px para máxima precisión.
   • CAlrededor de 200px para visitar pocas cells.

2. Tienes un mundo procedural infinito. ¿Uniform grid o sparse hash?

   • ASparse hash — el uniform grid asume mundo acotado.
   • BUniform grid con cell size enorme.
   • CCualquiera, son intercambiables.

3. La query devuelve 40 candidatos pero solo 8 están dentro del radio real. ¿Es un bug?

   • ANo, es esperado: el grid filtra por AABB de las cells, después tú filtras por distancia.
   • BSí, debería devolver solo los 8 reales directamente.
   • CSí, el cell size está mal calibrado.

4. Al hacer profiling ves que el spatial hash tiene mucha más colisión de lo esperado. ¿Primer ajuste?

   • AAumentar el número de buckets — más slots, menos colisiones.
   • BAchicar el cell size para tener más cells.
   • CCambiar a uniform grid; el sparse hash siempre tiene colisiones.

11. Siguientes pasos

El grid es la primera capa de optimización espacial. Cuando los agentes se concentran en clusters densos, el siguiente paso son los árboles adaptativos: quadtree y octree. Subdivides donde hay densidad, dejas grandes regiones donde está vacío.