Estructura de datos efectiva para áreas espaciales superpuestas

Question

Estoy escribiendo un juego donde una gran cantidad de objetos tendrán "efectos de área" sobre una región de un mapa en mosaico en 2D.

características requeridas:

• Varios de estos efectos de área pueden solaparse y afectar a la misma baldosa
• Debe ser posible acceder de manera muy eficiente la lista de efectos de cualquier baldosa dada
• Los efectos de área puede tener formas arbitrarias, pero normalmente tendrá la forma "hasta X distancia de las teselas del objeto que causa el efecto" donde X es un entero pequeño, generalmente 1-10
• Los efectos de área cambiarán con frecuencia, por ejemplo como los objetos se mueven a diferentes lugares en el mapa
• mapas podría ser potencialmente grandes (por ejemplo, 1000 x 1000 azulejos)

Qué estructura de datos que funciona mejor para esto?

Answer 1

Siempre que realmente tienen una gran cantidad de efectos de área ocurriendo simultáneamente, y que van a tener formas arbitrarias, me gustaría hacerlo de esta manera:

• cuando se crea un nuevo efecto, es almacena en una lista global de efectos (no necesariamente una variable global, sólo algo que se aplica a todo el juego o la corriente de juego-mapa)
• se calcula qué azulejos afecta, y almacena una lista de los azulejos contra el efecto
• cada uno de los azulejos es notificado del nuevo efecto, y almacena una referencia de nuevo a él en una lista por losa (en C++ que haría uso de un std :: vector para esto, algo con almacenamiento contiguo , no un ligado lista)
• terminando un efecto es manejado por iteración a través de los azulejos interesados ​​y la eliminación de las referencias a ella, antes de destruirlo
• moverlo o cambiar su forma, se maneja mediante la eliminación de las referencias como más arriba, realizando los cálculos de cambio, y luego volviendo a unir las referencias en las teselas ahora afectadas
• también debe tener una verificación invariante solo de depuración que recorre todo el mapa y verifica que la lista de teselas del efecto coincide exactamente con las teselas del mapa que la referencia.

Answer 2

Generalmente BSP-Trees (o quadtrees o octrees).

Answer 3

Algunas soluciones de fuerza bruta que no se basan en la informática de lujo:

1000 x 1000 no es demasiado grande - sólo un meg. Las computadoras tienen Gigs. Podrías tener una matriz 2d. Cada bit en los bytes podría ser un 'tipo de área'. El 'área afectada' que es más grande podría ser otro poco. Si tiene una cantidad razonable de diferentes tipos de áreas, puede usar una máscara de bits de varios bytes. Si eso resulta ridículo, puede hacer que los elementos de la matriz apunten a listas de objetos de tipo de área superpuestos. Pero luego pierdes eficiencia.

También podría implementar una matriz dispersa utilizando una tabla hash fuera de las coordenadas (por ejemplo, clave = 1000 * x + y), pero esto es mucho más lento.

Si por supuesto si no te importa codificar las formas sofisticadas de informática, ¡generalmente funcionan mucho mejor!

Answer 4

Por lo general, depende de la densidad de su mapa.

Si sabes que cada tesela (o parte principal de las teselas) contiene al menos un efecto, deberías usar una cuadrícula regular: una matriz 2D simple de mosaicos.

Si su mapa está débilmente lleno y hay un montón de mosaicos vacíos, tiene sentido usar algunos spatial indexes como árboles cuádruples o árboles R-BSP.

Answer 5

Si tiene un rango máximo conocido de cada efecto de área, puede usar una estructura de datos de su elección y almacenar las fuentes reales, que están optimizadas para la Prueba de colisión 2D normal.

Luego, cuando compruebe los efectos en un mosaico, simplemente verifique (estilo de detección de colisión optimizado para su estructura de datos) todas las fuentes de efectos dentro del rango máximo y luego aplique una función de prueba definida (por ejemplo, si el área un círculo, verifique si la distancia es menor que una constante; si es un cuadrado, verifique si las distancias xey están cada una dentro de una constante).

Si tiene una cantidad pequeña (< 10) de formas de "campos" de efectos, puede incluso hacer una detección de colisión única para cada tipo de campo de efecto, dentro de su rango máximo precalculado.