Quadtree vs Red-Black tree para un juego en C++?

Question

He estado buscando una implementación de nodo quadtree/quadtree en la red por edades. Hay algunas cosas básicas, pero nada de lo que realmente podría usarlo es un juego.

Mi propósito es almacenar objetos en un juego para procesar cosas como la detección de colisiones. No estoy 100% seguro de que un quadtree sea la mejor estructura de datos para usar, pero por lo que he leído. Ya he codificado un árbol Rojo-Negro, pero realmente no sé si el rendimiento sería lo suficientemente bueno para mi juego (que será un juego de tercera persona de aventura como Ankh).

¿Cómo escribiría una clase quadtree básica (pero completa) en C++? ¿Cómo usarías el árbol cuádruple para colisiones?

Answer 1

Los Quadtrees se utilizan cuando solo necesita almacenar cosas que están efectivamente en un avión. Al igual que las unidades en un RTS clásico donde están todos en el suelo o un poco por encima. Esencialmente, cada nodo tiene enlaces a 4 niños que dividen el espacio del nodo en cuartos distribuidos uniformemente.

Los octrees hacen lo mismo pero en las tres dimensiones en lugar de solo dos, y así tienen 8 nodos secundarios y dividen el espacio en ochos. Deben usarse cuando las entidades del juego se distribuyen de manera más uniforme entre las tres dimensiones.

Si está buscando un árbol binario, como un árbol rojo-negro, querrá usar una estructura de datos llamada árbol de particionamiento de espacio binario (árbol BSP) o una versión llamada árbol KD. Estos espacios de partición en mitades utilizando un plano, en el árbol KD los planos son ortogonales (en los ejes XZ, XY, ZY) por lo que a veces funciona mejor en una escena 3D. Los árboles BSP dividen la escena usando planos en cualquier orientación, pero pueden ser bastante útiles, y se usaron desde Doom.

Ahora porque has dividido el espacio del juego, ahora no tienes que probar cada entidad de juego contra cada otra entidad del juego para ver si colisionan, que es un algoritmo O (n^2) en el mejor de los casos. En su lugar, consulta la estructura de datos para devolver las entidades del juego dentro de una subregión del espacio del juego, y solo realiza la detección de colisión para esos nodos uno contra el otro.

Esto significa que la detección de colisiones para todas las entidades del juego debe ser n operación O (nlogn) (en el peor de los casos).

Un par de cosas adicionales a tener en cuenta:

• asegúrese de probar entidades juego de nodos adyacentes, no sólo los que están en el nodo actual, ya que todavía podrían colisionar.
• Reequilibre la estructura de datos después de que las entidades se hayan movido ya que puede tener nodos vacíos en la estructura de datos o demasiados para un buen rendimiento (también el caso degenerado de todas las entidades en el mismo nodo).

Answer 2

La razón para usar un quadtree es porque puedes dividir en coordenadas xey, un octárbol en x, y y z, haciendo que la detección de colisiones sea trivial.

Quadtree: si un elemento no está en el topleft, no colisionará con uno hacia adentro, abajo o abajo.

Es una clase muy básica, por lo que no entiendo lo que le falta en las implementaciones que ha encontrado.

No escribiría una clase de este tipo, solo la tomaría de un proyecto con una licencia adecuada.

Answer 3

Un árbol rojo-negro no es un índice espacial; solo puede ordenar en una sola tecla ordinal. Un quadtree es (para dos dimensiones) un índice espacial que permite una búsqueda rápida y la eliminación de puntos. Un octree hace lo mismo para tres dimensiones.

Answer 4

Los árboles en general son problemáticos para esto ya que cualquier elemento insertado puede encontrarse en un límite, y todos los métodos para tratar con esa situación son bastante insatisfactorios.

Lo más probable es que desee ordenar los objetos en movibles y estáticos, y comprobar todo lo que se movió en un marco determinado contra los objetos estáticos.

BSP Los árboles son la solución aceptada para la geometría estática (casos de límite manejados dividiendo el objeto en dos partes), para un intento dinámico como Sort and Sweep (también conocido como Sweep and Prune).

Answer 5

Le sugiero encarecidamente que utilice un motor de representación, Ogre3D, por ejemplo. Hasta donde yo sé, admite a los octrees para la gestión de escena. Pero puede extender la clase basada en Octree como lo desee. Solía ​​codificar las cosas que necesitaba solo, pero para proyectos complejos, simplemente no es el camino correcto.

Answer 6

En este momento STANN es la mejor implementación de fuente abierta.

http://sites.google.com/a/compgeom.com/stann/