c++ - QuadTree para detección de colisiones 2D

quadtree c++

Question

Actualmente estoy trabajando en un juego de disparos en 2D, y estoy usando un quad para mis detecciones de colisión. Escribí un cuadriciclo en funcionamiento que empuja correctamente a mis actores hacia los nodos / hojas a los que pertenecen en el árbol. Sin embargo, tengo algunos problemas.

En primer lugar, ¿cómo uso realmente mi quadtree para seleccionar contra qué otros objetos debería probar un objeto las colisiones? No estoy seguro de cómo se hace esto.

Lo cual trae una segunda pregunta. Digamos que tengo un objeto en un nodo que no es vecino de otro nodo, pero que el objeto es lo suficientemente grande como para abarcar algunos nodos, ¿cómo puedo verificar una colisión real, ya que supongo que el árbol podría considerar que no es lo suficientemente cerca como para colisionar con objetos en un nodo "lejano"? ¿Deberían mantenerse los objetos que no encajan por completo en un nodo en el nodo padre?

En mi juego, la mayoría de los objetos son de diferentes tamaños y se mueven.

He leído una buena cantidad de blogs / artículos sobre quadtrees, pero la mayoría solo explica cómo construir un árbol que no es realmente lo que estoy buscando.

Cualquier ayuda / información es bienvenida.

Answer 1

Puede establecer una convención de que cada elemento está contenido en el nodo quadtree más pequeño que lo contiene por completo .

Luego, cuando compruebes las colisiones del nodo A, sigues así:

1. nodo actual = nodo raíz
2. verificar las colisiones de A con cada elemento directamente en el nodo actual
3. si A puede estar contenido por completo en cualquiera de los nodos secundarios del nodo actual, configure el nodo actual en ese subnodo y vaya a 2 nuevamente
4. finalmente, compruebe las colisiones de A con todos los elementos en los nodos hijos del nodo actual, recursivamente.

Tenga en cuenta que cuanto más pequeños sean los objetos, más profundos estarán ubicados en el árbol cuádruple, por lo tanto, se compararán con menos frecuencia.