La principal ventaja de un árbol cuádruple es que le permite descartar grupos enteros de depósitos de manera muy rápida.
Por ejemplo, supongamos que tengo un árbol cuádruple con seis niveles. En su nivel más bajo, son 32x32 cajas; 1024 cajas que comprenden ese nivel inferior y más detallado. A modo de comparación, también consideraremos un "hash espacial": una cuadrícula plana que también contiene 32x32 cajas, 1024 cajas en total. (el árbol cuádruple tiene más de 1024 cajas en total, ya que también contiene cajas más grandes en sus niveles más altos)
Supongamos que no hay objetos colisionables en el sistema: todas las cajas de nuestro árbol cuádruple y nuestra cuadrícula plana están completamente vacías.
Si está probando las colisiones de algo que es lo suficientemente grande como para que su cuadro delimitador se cruza con todos esos cuadros, y está utilizando una cuadrícula plana, debe marcar cada uno de esos 1024 cuadros para ver si hay algo en ellos.
Pero si está utilizando un árbol cuádruple anidado, el nivel más alto puede decirle que no hay otros objetos en el sistema, por lo que solo tiene que mirar esa única casilla para saber que no encontrará colisiones. más profundo en el árbol: puede detener la prueba de inmediato.
Del mismo modo, si los objetos solo existen en ciertas regiones del árbol cuádruple, el árbol cuádruple naturalmente guiará su búsqueda a través de solo cuadros potencialmente relevantes, mientras que la cuadrícula requiere que marque cada cuadro intersectado, porque no tiene forma de saber de antemano qué cuadrículas tendrán objetos en ellas. Si gran parte de su árbol cuádruple está vacío y está haciendo consultas grandes y complicadas (por ejemplo, enormes frustums de cámara en lugar de rectángulos pequeños y simples), entonces puede encontrar que está iterando sobre muchas menos cajas en total si hace su prueba contra algo usando una estructura de árbol, en lugar de una cuadrícula plana. Y eso puede hacer una gran diferencia.
Todo lo cual no implica que una estructura de árbol sea siempre la opción correcta, por supuesto. Las cuadrículas planas son ideales para la situación que tiene en su ejemplo: densas nubes de objetos se extienden de manera uniforme en todas partes del mundo, y estamos haciendo pruebas de colisión simples y económicas. ¡Es probable que una cuadrícula sea el enfoque óptimo en ese caso!
