Cargando aplicación...
Preparando tu experiencia meskeIA
Partición espacial paso a paso: cómo un quadtree divide el espacio en cuadrantes para acelerar las colisiones y las consultas de rango en videojuegos
Cómo dividir el espacio en cuadrantes acelera las colisiones y las consultas espaciales
| Enfoque | Coste de consultar colisiones | Se adapta a puntos agrupados | Cuándo conviene |
|---|---|---|---|
| Fuerza bruta | O(n²): cada objeto contra todos | No | Muy pocos objetos o pruebas rápidas |
| Rejilla uniforme | Rápida si los objetos están repartidos | Mal: celdas vacías o saturadas si se agrupan | Objetos de tamaño parecido y bien distribuidos |
| Quadtree | ≈ O(n log n) en la mayoría de casos | Sí: subdivide solo donde hay densidad | Escenas 2D con zonas más pobladas que otras |
| Árbol k-d | ≈ O(log n) por consulta | Sí, divide por mediana en cada eje | Conjuntos estáticos y vecino más cercano |
En un juego con cientos de balas, enemigos y obstáculos, comparar todos contra todos es inviable. El quadtree agrupa por zonas y solo compara objetos que comparten cuadrante: es el primer filtro rápido antes de la comprobación precisa.
💡 Si los objetos se mueven cada fotograma, el árbol se reconstruye o se actualiza en cada frame.
«¿Qué tiendas hay en esta zona del mapa?» o «¿qué marcadores caben en la vista actual?» son consultas de rango. Un quadtree descarta de golpe las regiones que no se solapan con el área visible.
💡 Es la misma idea que usan los mapas web para mostrar solo los puntos del recuadro visible.
Un quadtree puede dividir una imagen en cuadrantes y dejar de subdividir donde el color es uniforme. Las zonas lisas quedan como un solo nodo grande y solo se detalla donde hay bordes, ahorrando datos.
💡 Aquí el criterio para subdividir no es la cantidad de puntos, sino la variación de color.
Para simular la gravedad entre miles de estrellas, el algoritmo de Barnes-Hut usa un quadtree (u octree en 3D) para tratar grupos lejanos de cuerpos como una sola masa, bajando el coste de O(n²) a O(n log n).
💡 Es uno de los usos más elegantes del quadtree fuera de los videojuegos.
Porque agrupa los puntos por zonas del espacio. En una consulta de rango, si un nodo no se solapa con la región buscada, se descarta entero junto con todos sus descendientes, sin mirar ni uno de sus puntos. Así solo se examinan las ramas que tocan la zona, en lugar de recorrer la lista completa.
💡 En esta app puedes ver «nodos visitados» frente a «comprobaciones por fuerza bruta»: cuantos más puntos haya, mayor es la diferencia.
Un quadtree divide siempre cada región en exactamente cuatro cuadrantes iguales: noroeste, noreste, suroeste y sureste. De ahí el «quad» del nombre. Su equivalente en tres dimensiones es el octree, que divide cada caja en ocho octantes.
💡 Un quadtree sirve para juegos y mapas 2D; un octree, para mundos y físicas 3D.
Depende de cuántos puntos manejes y de cómo estén repartidos. Una capacidad muy baja genera un árbol muy profundo con muchos nodos casi vacíos; una muy alta apenas subdivide y pierde la ventaja. Valores entre 4 y 8 suelen ir bien. Prueba el slider de esta app y observa cómo cambian los nodos y la profundidad.
💡 No existe un valor universal: ajústalo midiendo el rendimiento con tus propios datos.
Cuando los objetos cambian de posición, el árbol deja de reflejar la realidad. Lo más sencillo es reconstruirlo entero cada fotograma; con muchos objetos es preferible actualizar solo los que han cambiado de cuadrante. Esa es una de las decisiones de diseño más importantes al usar quadtrees en un juego.
💡 Reconstruir todo cada frame es válido si el número de objetos no es enorme.
Un punto cae siempre en un único cuadrante, pero una caja o un círculo grande puede cruzar la frontera entre varios. Hay dos enfoques: guardar el objeto en el nodo padre que lo contiene por completo, o insertarlo en todos los hijos que toca (con cuidado de no contarlo dos veces). Esta app trabaja con puntos para centrarse en la idea base.
💡 En motores reales se suele usar el rectángulo envolvente del objeto, no un punto.
Si tienes muy pocos objetos, la fuerza bruta es más simple y rápida. Si los objetos están repartidos de forma uniforme y son de tamaño parecido, una rejilla fija suele rendir mejor y es más fácil de actualizar. El quadtree brilla cuando hay zonas mucho más pobladas que otras, porque subdivide solo donde hace falta.
💡 Mide siempre: la estructura «teóricamente mejor» no siempre gana en tu caso concreto.
Se comprueba si el punto está dentro del rectángulo que cubre el nodo. Si no lo está, ese nodo lo rechaza y la inserción continúa por otra rama.
Si el nodo aún no se ha dividido y le caben más puntos (no llega a su capacidad), el punto se guarda ahí y termina la inserción.
Si el nodo está lleno y todavía no tiene hijos, se subdivide en cuatro cuadrantes (NO, NE, SO, SE) y reparte entre ellos los puntos que ya tenía.
El nuevo punto se inserta en el hijo que lo contiene. Es una llamada recursiva: en ese hijo se repite todo el proceso desde el paso 1.
La recursión continúa hacia abajo hasta que un nodo con hueco acepta el punto. Si hay muchos puntos muy juntos, el árbol crece en profundidad solo en esa zona.
Cuando un nodo se divide, mueve sus puntos a los hijos. Si los dejas también en el padre, los contarás dos veces y las consultas devolverán duplicados.
Decide un criterio claro de pertenencia (por ejemplo, borde izquierdo y superior incluidos, derecho e inferior excluidos) y úsalo igual en todos los cuadrantes para que ningún punto se pierda ni se duplique.
Pon un límite máximo de niveles. Si muchos puntos coinciden casi en la misma posición, un árbol sin tope intentaría subdividir sin fin y se quedaría colgado.
En una consulta de rango, descarta de inmediato cualquier nodo cuyo rectángulo no se solape con la región buscada. Ahí está casi toda la ganancia de velocidad.
No fijes la capacidad por intuición. Prueba varios valores con tus datos reales y quédate con el que dé mejor rendimiento; suele estar entre 4 y 8.
Si tu escena cambia cada fotograma, decide pronto si reconstruyes el árbol entero o lo actualizas de forma incremental. Es lo que más afecta al rendimiento real.