data-structures - algoritmo - quadtree c++

Quadtree para detección de colisiones 2D

Question

Intento usar un quadtree para la detección de colisiones 2D, pero estoy un poco perplejo sobre cómo implementarlo. En primer lugar, tendría un quadtree que contiene cuatro subárboles (uno que representa cada cuadrante), así como una colección de objetos que no encajan en un solo subárbol.

Cuando revise un objeto en busca de colisiones en el árbol, haría algo como esto (gracias a QuadTree para la detección de colisiones 2D ):

1. Verifique si el objeto tiene colisiones con cualquier objeto en el nodo actual.
2. Para cualquier subárbol cuyo espacio se superpone con el objeto, recurse.

Para encontrar todas las colisiones dentro de un árbol quadtree:

1. Compruebe cada objeto en el nodo actual contra cada otro objeto en el nodo actual.
2. Compruebe cada objeto en el nodo actual contra cada subárbol.

Para insertar en un quadtree:

1. Si el objeto encaja en múltiples subárboles, agréguelo al nodo actual y vuelva.
2. De lo contrario, recurse en el subárbol que lo contenga.

Para actualizar un quadtree:

1. Recurse a cada subárbol.
2. Si algún elemento en el nodo actual ya no cabe completamente en el árbol actual, muévalo al padre.
3. Si algún elemento en el nodo actual cabe en un subárbol, insértelo en el subárbol.

¿Está bien? ¿Se puede mejorar?

Answer 1

Los árboles cuádruples no siempre son la mejor estructura de datos para la detección de colisiones. La parte superior de un quadtree puede ser potencialmente ilimitada (si no se limita la profundidad del árbol) y, en el peor de los casos, no da ninguna velocidad. En su lugar, es posible que desee considerar el uso de una grilla dispersa, que ofrece un mejor rendimiento que un quadtree solo sin la sobrecarga adicional de atravesar varios niveles de árbol.

También hay otros enfoques completamente diferentes que podrían ser incluso mejores. Por ejemplo, podrías intentar implementar el algoritmo de Zomorodian y Edelsbrunner, como hice en el siguiente módulo:

• https://github.com/mikolalysenko/box-intersect

Aquí también hay algunos artículos que escribí que discuten estos temas con más detalle:

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

En particular, si nos fijamos en los puntos de referencia de la última sección, verá que de todas las bibliotecas encuestadas, los quadtrees tendían a funcionar bastante mal en comparación con otros métodos de detección de colisiones como R-Trees, grids o segment arboles.

Answer 2

No estoy seguro de qué tan efectivo es todavía, pero parece estar funcionando bien en mi dúo central en eclipse, todavía funciona a más de 2400 fps lol ..

Básicamente, agregué una lista a objetos colisibles para almacenar referencias a los objetos de nodo quadtree con los que he asociado el objeto (mediante la inserción en el árbol cuádruple). También agregué una lista a cada nodo quadtree, que almacena referencias a cualquier objeto considerado dentro de los límites de ese nodo. Entonces cada nodo solo tendrá una ocurrencia de cada objeto. cada nodo también almacena una referencia a su nodo padre, para la navegación a nodos cercanos si quiero verificar cualquiera de ellos después del nodo inicial para una mayor precisión de colisión.

es muy fácil obtener referencias a todos los demás objetos en una celda:

list temp_checklist = object.cells[cell_index].objects
//(''objects'' being some sort of array or list of object references as described above)

espero que ayude a alguien;)

Answer 3

Tu estructura de quadtree no es óptima. Tiene razón para almacenar 4 subárboles por nodo, pero los objetos reales solo deben almacenarse dentro de las hojas, no en los nodos internos. Por lo tanto, la colección que contiene los objetos reales debe moverse a las hojas.

Echemos un vistazo a la implementación de las operaciones :

1. Inserta un objeto en el quadtree :
   Verifica si el objeto se cruza con el nodo actual. Si es así, recurse. Si alcanzó el nivel de la hoja, inserte el objeto en la colección.
2. Eliminar un objeto del quadtree :
   Ejecute exactamente los mismos pasos que si insertara el objeto, pero cuando haya alcanzado el nivel de hoja elimínelo de la colección.
3. Pruebe si un objeto intersecta cualquier objeto dentro del quadtree :
   Ejecute exactamente los mismos pasos que si insertara el objeto, pero cuando haya alcanzado el nivel de hoja, compruebe si hay colisión con todos los objetos de la colección.
4. Prueba de todas las colisiones entre todos los objetos dentro del quadtree :
   Para cada objeto en el quadtree, ejecute la prueba de colisión de un solo objeto.
5. Actualiza el quadtree :
   Borre todos los objetos del quadtree cuya posición haya sido modificada e insértelos nuevamente.

Esto tiene varias ventajas :

• Al solo almacenar objetos en las hojas, es muy fácil manejar las operaciones en el árbol cuádruple (menos casos especiales)
• El quadtree puede tener hojas con diferente profundidad, lo que le permite adaptar la densidad del quadtree dependiendo de la región espacial que cubre. Esta adaptación puede ocurrir en tiempo de ejecución, manteniendo así la relación objeto / nodo óptima.

Solo desventaja :

• Los objetos pueden pertenecer a varias colecciones dentro del quadtree. Necesitará una colección lineal adicional fuera del quadtree para enumerar todos los objetos sin duplicados.