QuadTree para detección de colisión 2D

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 utilizo mi quadtree para seleccionar contra qué otros objetos debe probar un objeto las colisiones? No estoy seguro de cómo se hace esto.

Lo que genera 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 un buen número 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 que cada elemento está contenido en el nodo quadtree más pequeño que lo contiene por completo.

A continuación, cuando se echa las colisiones para el nodo A, se procede de esta manera:

1. actual nodo = nodo raíz
2. colisiones de verificación de A con cada elemento directamente en el nodo actual
3. si una lata estar contenido por completo en cualquiera de los subnodos del nodo actual, establecer el nodo actual en ese subnodo y volver a 2
4. finalmente, verificar 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 se ubicarán en el árbol cuádruple, por lo que se compararán con menos frecuencia.