Quadtree y Octree: el árbol que se adapta a la densidad

0. Cuando el grid uniforme se rompe

El uniform grid asume que los agentes se distribuyen parejo. En un MMO real nunca es así: el 80% de los jugadores está en la capital, el 15% en las zonas de farmeo, el 5% explorando. Las celdas de la capital se sobrecargan; las del bosque profundo están vacías y ocupan memoria.

El quadtree resuelve eso con una idea simple: divide solo donde haga falta. Empiezas con un solo nodo que cubre todo el mundo. Cuando una hoja se llena (más de N items), la divides en 4. Cuando esas 4 se llenan, las divides también. Resultado: árbol denso donde hay clusters, árbol ralo donde está vacío.

Capacidad por hoja: 4Profundidad máx: 7⏸ Pausar

0 nodos·0 hojas·profundidad máx 0·180 agentes

Las celdas se colorean según su profundidad en el árbol: más oscuras = más profundas. Donde se concentran los puntos, el quadtree se subdivide; en zonas vacías quedan celdas grandes. Sube la capacidad para ver hojas más cargadas; bájala para subdivisión más agresiva.

Figura 1 — Los agentes son atraídos hacia un punto que se mueve lento por el canvas. El quadtree se reconstruye cada frame: subdivisión agresiva donde están los puntos, celdas grandes donde no hay nada. Sube la capacidad para que las hojas aguanten más antes de partirse.

1. Estructura

Cada nodo del quadtree es:

class Quadtree
    bounds: AABB        // x, y, w, h del territorio que cubre
    items: List<T>      // items dentro de esta hoja
    children: [4]?      // si subdividido: NW, NE, SW, SE; si no: null
    capacity: int       // umbral antes de partir
    maxDepth: int       // límite duro para no infinitar

Dos invariantes:

1. Si children == null, soy hoja: tengo items. La cantidad puede superar capacity solo si llegué a maxDepth y no puedo partirme más.
2. Si children != null, soy interno: items está vacío y todo está en mis 4 hijos.

1.1 Subdivisión

Cuando una hoja excede capacidad, divide su bounds en 4 cuadrantes iguales (NW, NE, SW, SE) y reasigna sus items al hijo correspondiente:

function subdivide(node):
    hw = node.bounds.w / 2
    hh = node.bounds.h / 2
    node.children = [
        Quadtree(bounds: AABB(x,      y,      hw, hh)),  # NW
        Quadtree(bounds: AABB(x+hw,   y,      hw, hh)),  # NE
        Quadtree(bounds: AABB(x,      y+hh,   hw, hh)),  # SW
        Quadtree(bounds: AABB(x+hw,   y+hh,   hw, hh)),  # SE
    ]
    items = node.items
    node.items = []
    for it in items:
        for child in node.children:
            if child.contains(it.x, it.y):
                child.insert(it)
                break

Cada item cae en exactamente uno de los 4 hijos (los cuadrantes son disjuntos). Si un item está justo en el borde, importa que contains use [min, max) consistentemente para evitar duplicarlo.

2. Insert

function insert(node, item) -> bool
    if not node.contains(item): return false
    if node.children:
        for child in node.children:
            if child.insert(item): return true
        return false
    node.items.add(item)
    if node.items.length > capacity and node.depth < maxDepth:
        subdivide(node)
    return true

O(log N) amortizado para distribuciones razonables. Pathológicamente puede degenerar a O(N) si todos los items se apilan en un punto y el árbol llega a maxDepth.

3. Query: el corazón del ahorro

Aquí está la magia. Para preguntar “qué hay en esta región AABB”:

function queryAABB(node, region, out: List<T>):
    if not node.bounds.intersects(region):
        return  # ← rama entera descartada sin tocar items
    if node.children:
        for child in node.children:
            queryAABB(child, region, out)
    else:
        for it in node.items:
            if region.contains(it):
                out.add(it)

La línea clave es la primera: si el AABB de mi nodo no toca la región pedida, ni yo ni ninguno de mis descendientes puede tener un hit. Descarto miles de items potenciales con un solo check de AABB.

81 de 205 nodos visitados·72 hits de 220 agentes·brute force: 220 checks · quadtree: ~81 nodos

Arrastra el rectángulo (o haz click fuera para crear uno nuevo). La esquina inferior derecha lo redimensiona. El árbol descarta entera cualquier rama cuyo AABB no toca tu región — esos nodos ni siquiera se visitan. Por eso el costo es proporcional a cuánto del mundo pediste, no a cuántos agentes tenés.

Figura 2 — Arrastra el rectángulo verde. Las celdas iluminadas son los nodos visitados; las hojas no resaltadas se descartaron por su AABB. El costo del query es proporcional al tamaño de la región pedida y a cuántos clusters toca, no al N total.

3.1 Por qué es genuinamente sublinear

Para una región pequeña que toca un cluster: visitas el camino root → nodo del cluster (O(log N)), después barres ese cluster. Total: O(log N + k) donde k es el resultado.

Para una región que cubre medio mundo: visitas medio árbol. El costo escala con el área que pediste, no con N. Eso es lo que el grid uniforme nunca te da: con uniform grid pagas O(área / cellSize²) siempre, te interese o no esa área.

4. Decisiones de diseño

4.1 Capacidad por hoja

Tradeoff clásico:

• Capacidad baja (1–2): árbol profundo, muchos nodos internos, poco trabajo en cada hoja. Bueno si el costo de chequeo de AABB es barato comparado con el de items (ej. items son grandes objetos).
• Capacidad alta (8–16): árbol bajo, pocos nodos, cada hoja itera más items. Bueno si el chequeo AABB es caro o si el árbol se reconstruye seguido.

Punto de partida: capacity = 4. Ajusta según profiling.

4.2 Profundidad máxima

Sin límite, dos puntos exactamente iguales harían que el árbol intente subdividir infinitamente. Pones un maxDepth (típicamente 6–10) y aceptas que las hojas en el fondo del árbol violen capacity.

4.3 Refit vs rebuild

Cuando los items se mueven (boids, NPCs corriendo), tienes dos opciones:

• Rebuild completo cada frame: simple, garantiza balance, costo O(N log N).
• Refit incremental: re-insertas solo los items que cambiaron de hoja. Más rápido para movimientos lentos, más complicado de implementar.

Para visualizaciones y la mayoría de juegos: rebuild. La constante de un quadtree bien escrito es chica.

5. Octree: el quadtree en 3D

Mismo concepto, dimensión extra. En vez de 4 cuadrantes (NW, NE, SW, SE) tienes 8 octantes. Cada subdivisión parte el cubo del nodo en 8 sub-cubos iguales.

Cargando three.js…

Capacidad: 5Profundidad máx: 4 Mostrar octree Auto-rotar

Cubo dividido en 8 octantes recursivamente. Cada nivel del árbol tiene un color distinto. Arrastra con el mouse para rotar manualmente. Sube la capacidad: las hojas aguantan más puntos antes de subdividir; el árbol queda menos profundo. Bájala: subdivisión agresiva en cualquier zona con clusters.

Figura 3 — Octree 3D real. Los puntos están agrupados en dos clusters; el árbol se subdivide donde están y deja el resto del cubo intacto. Arrastra para rotar la cámara. Cada nivel del árbol tiene un color distinto.

Casos de uso del octree:

• Frustum culling: descarta meshes que están fuera del frustum de la cámara antes de renderizar. Sin octree, chequearías cada mesh; con octree, descartas ramas enteras.
• Particle systems 3D: queries de proximidad para fluidos, humo, partículas que interactúan.
• Voxel engines (Minecraft-like): el mundo entero es un octree; las regiones vacías colapsan a un solo nodo.
• Path planning aéreo: drones, naves espaciales que navegan en 3D.

5.1 Diferencias con el quadtree

• 8 hijos en vez de 4 → cada subdivisión cuadruplica el branching factor con respecto al quadtree.
• Profundidad máxima suele ser menor (5–6) porque el árbol crece muchísimo más rápido en memoria.
• En la práctica, los octrees solo se usan cuando la 3D es esencial. Para juegos top-down o 2D-pretendiendo-ser-3D (Hades, Hyper Light Drifter), un quadtree alcanza.

6. Comparativa con uniform grid

Aspecto	Uniform Grid	Quadtree
Memoria	O(cells totales)	O(items) aprox
Insert	O(1)	O(log N)
Query rango	O(área / cellSize²)	O(log N + k)
Distribución uniforme	Mejor (constante chica)	Buena
Distribución clusterizada	Mala (overcrowding)	Excelente
Mundos no acotados	No	Sí (con root grande)
Implementación	Trivial	Moderada

Regla simple: si tus agentes están parejos en el mundo, usa grid. Si tienen clusters densos, usa quadtree. Si en duda, perfila ambos.

7. Implementación en Unity / C#

public class Quadtree<T> where T : IPositionable {
    readonly Rect bounds;
    readonly int capacity;
    readonly int maxDepth;
    readonly int depth;
    Quadtree<T>[] children;
    readonly List<T> items = new List<T>(8);

    public Quadtree(Rect bounds, int capacity = 4, int maxDepth = 8, int depth = 0) {
        this.bounds = bounds;
        this.capacity = capacity;
        this.maxDepth = maxDepth;
        this.depth = depth;
    }

    public bool Insert(T item) {
        if (!bounds.Contains(item.Position)) return false;
        if (children != null) {
            for (int i = 0; i < 4; i++)
                if (children[i].Insert(item)) return true;
            return false;
        }
        items.Add(item);
        if (items.Count > capacity && depth < maxDepth) Subdivide();
        return true;
    }

    void Subdivide() {
        float hw = bounds.width / 2;
        float hh = bounds.height / 2;
        children = new[] {
            new Quadtree<T>(new Rect(bounds.x,        bounds.y,        hw, hh), capacity, maxDepth, depth + 1),
            new Quadtree<T>(new Rect(bounds.x + hw,   bounds.y,        hw, hh), capacity, maxDepth, depth + 1),
            new Quadtree<T>(new Rect(bounds.x,        bounds.y + hh,   hw, hh), capacity, maxDepth, depth + 1),
            new Quadtree<T>(new Rect(bounds.x + hw,   bounds.y + hh,   hw, hh), capacity, maxDepth, depth + 1),
        };
        var existing = items.ToArray();
        items.Clear();
        foreach (var it in existing) {
            for (int i = 0; i < 4; i++)
                if (children[i].Insert(it)) break;
        }
    }

    public void QueryAABB(Rect region, List<T> result) {
        if (!bounds.Overlaps(region)) return;
        if (children != null) {
            for (int i = 0; i < 4; i++) children[i].QueryAABB(region, result);
        } else {
            for (int i = 0; i < items.Count; i++)
                if (region.Contains(items[i].Position)) result.Add(items[i]);
        }
    }
}

8. En otros engines

• Godot: Area2D con shape callbacks resuelve el caso común. Para custom queries: implementa el quadtree en GDScript siguiendo la misma estructura.
• Unreal: tiene FOctree en el engine para uso de gameplay; expone FindElementsWithBoundsTest. Para 2D: rolea tu propio quadtree con TArray<TUniquePtr<FQuadtreeNode>>.
• Web / Canvas: librerías como rbush (R-tree), js-quadtree o tu propia implementación. El JS con monomorfismo y arrays planos es muy rápido.

9. Errores comunes

1. Items en bordes duplicados — si contains usa [min, max] cerrado en ambos lados, un item en x = bounds.x + bounds.w cae en dos cuadrantes. Usa [min, max) (cerrado-abierto).
2. No respetar maxDepth — sin límite, dos items en (0, 0) exactos infinitan la subdivisión. Pon un cap y acepta hojas sobrecargadas en casos patológicos.
3. Reconstruir el árbol mid-query — si una operación inserta nuevos items mientras estás iterando un query, los resultados son inconsistentes. Hazlo entre frames, no en medio.
4. Olvidar el bounds.intersects en query — la primera línea del query es la que aporta el sublineal. Sin ella, el árbol degenera a iterar todo.
5. Capacity de 1 — máximo branching, profundidad altísima, mucho overhead de nodos internos. Casi nunca es buena idea.

10. Quiz

Pon a prueba lo que entendiste

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

1. Tu juego tiene 2000 NPCs distribuidos así: 1500 en una capital pequeña, 500 dispersos por el mundo. ¿Quadtree o uniform grid?

   • AQuadtree — el grid uniforme se ahoga en la capital.
   • BUniform grid con cellSize gigante.
   • CBrute force, son solo 2000.

2. Subes la capacidad por hoja de 4 a 16. ¿Qué pasa?

   • AEl árbol queda más bajo (menos profundo) y cada hoja itera más items en queries.
   • BEl árbol queda más profundo y los queries son más rápidos.
   • CNo cambia nada — la capacidad solo afecta inserción, no queries.

3. Tu query AABB cubre toda la pantalla. ¿El quadtree te ayuda?

   • ACasi nada — tienes que visitar todo el árbol.
   • BSí, igual va sublinear.
   • CSí, porque las hojas tienen pocos items cada una.

4. El árbol crece sin parar y crashea por stack overflow. ¿Qué falló?

   • ANo respetaste maxDepth con items que caen en el mismo punto exacto.
   • BLa capacidad es demasiado alta.
   • CFaltan boundary checks en el insert.

11. Siguientes pasos

El quadtree maneja agentes como puntos. Cuando los items son objetos con tamaño (cuerpos rígidos, cajas de colisión), necesitas algo más sofisticado: BVH (Bounding Volume Hierarchies). Es lo que sigue.