La respuesta correcta depende un poco del juego real que estés diseñando, y elegir uno sobre el otro realmente requerirá implementar ambos y hacer un perfil para descubrir cuál es más eficiente en tiempo o espacio en tu juego específico.
La detección de cuadrícula parece aplicarse solo a la detección de colisiones entre objetos en movimiento y un fondo estático. La mayor ventaja de esto es que el fondo estático se representa como una matriz de memoria contigua, y cada búsqueda de colisión es O (1) con buena ubicación si necesita hacer varias lecturas (porque las entidades cubren más de una celda en la cuadrícula). La desventaja, si el fondo estático es grande, es que la cuadrícula puede desperdiciar bastante espacio.
Si, en cambio, representa el fondo estático como un árbol cuádruple, entonces el costo de las búsquedas individuales aumenta, pero debido a que los bloques grandes del fondo ocupan una pequeña cantidad de espacio, los requisitos de memoria disminuyen, por lo que una mayor parte del fondo puede quedar en el cache. incluso si se necesitan 10 veces más lecturas para realizar una búsqueda en una estructura de este tipo, si todo está en la memoria caché, seguirá siendo 10 veces más rápido que una sola búsqueda con una falta de memoria caché.
Si me enfrentara con la elección? Iría con la implementación de la cuadrícula, porque es estúpidamente simple de hacer, mejor paso mi tiempo en otros problemas más interesantes. Si noto que mi juego se está ejecutando un poco lento, haré un perfil y veré qué podría ayudar. Si parece que el juego pasa mucho tiempo haciendo detección de colisiones, probaría con otra implementación, como un quadtree (después de agotar todas las soluciones fáciles primero), y averiguaría si eso ayudó.
Editar: no tengo ni idea de cómo se relaciona la detección de colisión de cuadrícula con la detección de colisiones de múltiples entidades móviles, pero en su lugar, responderé cómo un índice espacial (Quadtree) mejora el rendimiento de detección sobre la solución iterativa. La solución ingenua (y típicamente perfectamente fina) se parece a esto:
foreach actor in actorList:
foreach target in actorList:
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Obviamente, esto tiene un rendimiento en torno a O (n ^ 2), con n el número de actores que están actualmente vivos en el juego, incluidas las balas y naves espaciales y extraterrestres. También puede incluir pequeños obstáculos estáticos.
Esto funciona fantásticamente bien siempre y cuando el número de tales artículos sea razonablemente pequeño, pero comienza a verse un poco pobre cuando hay más de unos cientos de objetos para verificar. 10 objetos dan como resultado solo 100 comprobaciones de colisión, 100 resultados en 10.000 comprobaciones. 1000 resultados en un millón de cheques.
Un índice espacial (como los cuadrúpedos) puede enumerar eficientemente los elementos que recopila de acuerdo con las relaciones geométricas. esto cambiaría el algoritmo de colisión a algo como esto:
foreach actor in actorList:
foreach target in actorIndex.neighbors(actor.boundingbox):
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
La eficiencia de esto (suponiendo una distribución uniforme de entidades): generalmente es O (n ^ 1.5 log (n)), ya que el índice toma alrededor de las comparaciones log (n) para atravesar, habrá alrededor de sqrt (n) vecinos para comparar , y hay n actores para verificar. Sin embargo, de manera realista, el número de vecinos siempre es bastante limitado, ya que si ocurre una colisión, la mayoría de las veces uno de los objetos se elimina o se aleja de la colisión. así obtienes solo O (n log (n)). Para 10 entidades, haces (aproximadamente) 10 comparaciones, para 100, haces 200, para 1000 haces 3000.
Un índice realmente inteligente puede incluso combinar la búsqueda de vecinos con la iteración masiva y realizar una devolución de llamada en cada entidad que se cruza. Esto dará un rendimiento de aproximadamente O (n), ya que el índice se está escaneando una vez en lugar de consultarlo n veces.
Perdón por resucitar el hilo antiguo, pero en mi humilde opinión las cuadrículas antiguas no se usan con la suficiente frecuencia para estos casos. La cuadrícula tiene muchas ventajas porque la inserción / extracción de la celda es muy barata. No tiene que molestarse en liberar una celda ya que la cuadrícula no tiene como objetivo optimizar las representaciones dispersas. Digo que habiendo reducido el tiempo para seleccionar un grupo de elementos en una base de código heredada de más de 1200 ms a 20 ms simplemente reemplazando el árbol cuádruple con una cuadrícula. Sin embargo, para ser justos, ese árbol cuádruple se implementó realmente mal, almacenando una matriz dinámica separada por nodo hoja para los elementos.
El otro que encuentro extremadamente útil es que sus algoritmos de rasterización clásicos para dibujar formas se pueden usar para realizar búsquedas en la cuadrícula. Por ejemplo, puede usar la rasterización de línea de Bresenham para buscar elementos que se crucen con una línea, la rasterización de línea de escaneo para encontrar qué celdas se cruzan con un polígono, etc. Como trabajo mucho en el procesamiento de imágenes, es realmente bueno poder usar exactamente lo mismo El código optimizado que uso para trazar píxeles a una imagen como lo hago para detectar intersecciones contra objetos en movimiento en una cuadrícula.
Dicho esto, para que una cuadrícula sea eficiente, no debería necesitar más de 32 bits por celda de cuadrícula. Debería poder almacenar un millón de celdas en menos de 4 megabytes. Cada celda de la cuadrícula puede indexar el primer elemento de la celda, y el primer elemento de la celda puede indexar el siguiente elemento de la celda. Si está almacenando algún tipo de contenedor completo con cada celda, eso se vuelve explosivo en el uso de la memoria y las asignaciones rápidamente. En cambio, solo puedes hacer:
Al igual que:
Está bien, así que a los contras. Estoy llegando a esto sin duda con un sesgo y preferencia hacia las cuadrículas, pero su principal desventaja es que no son escasas.
Acceder a una celda de cuadrícula específica dada una coordenada es de tiempo constante y no requiere descender por un árbol, lo que es más barato, pero la cuadrícula es densa, no escasa, por lo que podría tener que verificar más celdas de las necesarias. En situaciones en las que sus datos se distribuyen muy escasamente, la cuadrícula podría requerir verificar mucho más para descubrir los elementos que se cruzan, por ejemplo, una línea o un polígono relleno o un rectángulo o un círculo delimitador. La cuadrícula tiene que almacenar esa celda de 32 bits, incluso si está completamente vacía, y cuando realiza una consulta de intersección de formas, debe verificar esas celdas vacías si se cruzan con su forma.
El principal beneficio del quad-tree es, naturalmente, su capacidad de almacenar datos dispersos y solo subdividir todo lo que sea necesario. Dicho esto, es más difícil de implementar realmente bien, especialmente si tienes cosas moviéndose en cada cuadro. El árbol necesita subdividir y liberar nodos secundarios sobre la marcha de manera muy eficiente, de lo contrario se degrada en una gruesa malla que desperdicia sobrecarga para almacenar enlaces padre-> hijos. Es muy factible implementar un quad-tree eficiente utilizando técnicas muy similares a las que describí anteriormente para la cuadrícula, pero generalmente requerirá más tiempo. Y si lo hace de la manera que lo hago en la cuadrícula, tampoco es necesariamente óptimo, ya que conduciría a una pérdida en la capacidad de garantizar que los 4 hijos de un nodo de cuatro árboles se almacenen contiguamente.
Además, tanto un árbol cuádruple como una cuadrícula no hacen un trabajo magnífico si tiene una serie de elementos grandes que abarcan gran parte de toda la escena, pero al menos la cuadrícula se mantiene plana y no se subdivide en el enésimo grado en esos casos . El quad-tree debe almacenar elementos en ramas y no solo hojas para manejar razonablemente tales casos o de lo contrario querrá subdividirse como locos y degradar la calidad extremadamente rápido. Hay más casos patológicos como este que debe tratar con un árbol cuádruple si desea que maneje la gama más amplia de contenido. Por ejemplo, otro caso que realmente puede hacer tropezar un árbol cuádruple es si tiene una gran cantidad de elementos coincidentes. En ese punto, algunas personas simplemente recurren a establecer un límite de profundidad para su árbol cuádruple para evitar que se subdivida infinitamente. La grilla tiene el atractivo de que hace un trabajo decente,
La estabilidad y la previsibilidad también son beneficiosas en un contexto de juego, ya que a veces no necesariamente se quiere la solución más rápida posible para el caso común si ocasionalmente puede provocar hipo en las tasas de cuadros en escenarios de casos raros versus una solución que sea razonablemente rápida alrededor, pero nunca conduce a tales problemas y mantiene las velocidades de fotogramas suaves y predecibles. Una cuadrícula tiene ese tipo de calidad tardía.
Con todo lo dicho, realmente creo que depende del programador. Con cosas como grid vs. quad-tree u octree vs. kd-tree vs. BVH, mi voto es sobre el desarrollador más prolífico con un récord para crear soluciones muy eficientes, sin importar la estructura de datos que use. También hay mucho en el nivel micro, como multiprocesamiento, SIMD, diseños de memoria amigables con la caché y patrones de acceso. Algunas personas pueden considerar esos micro pero no necesariamente tienen un micro impacto. Tales cosas podrían hacer una diferencia de 100x de una solución a otra. A pesar de esto, si personalmente me dieron unos días y me dijeron que necesitaba implementar una estructura de datos para acelerar rápidamente la detección de colisión de elementos que se mueven alrededor de cada cuadro, sería mejor en ese corto tiempo implementar una cuadrícula que un quad -árbol.
fuente