Partición de espacio cuando todo se mueve

Fondo

Junto con un amigo, estoy trabajando en un juego 2D que se desarrolla en el espacio. Para hacerlo lo más inmersivo e interactivo posible, queremos que haya miles de objects flotando libremente, algunos agrupados, otros a la deriva en el espacio vacío.

Reto

Para download el motor de renderización y física, necesitamos implementar algún tipo de partición espacial. Hay dos desafíos que debemos superar. El primer desafío es que todo se está moviendo, por lo que la reconstrucción / actualización de la estructura de datos debe ser extremadamente económica, ya que tendrá que hacerse en cada fotogtwig. El segundo desafío es la distribución de los objects, como se dijo antes, puede haber grupos de objects juntos y grandes porciones de espacio vacío y, para hacerlo aún peor, no hay límite al espacio.

Tecnologías existentes

He analizado las técnicas existentes, como BSP-Trees, QuadTrees, kd-Trees e incluso R-Trees, pero hasta donde sé, estas estructuras de datos no encajan a la perfección desde que se actualizaron muchos objects que se movieron a otras celdas es relativamente caro

Lo que he intentado

Tomé la decisión de que necesito una estructura de datos que esté más orientada a la inserción / actualización rápida que a la devolución de la menor cantidad posible de visitas dada una consulta. Para ese propósito hice que las celdas estuvieran implícitas para que cada object, dada su position, pueda calcular en qué celda (s) debería estar. Luego uso un HashMap que correlaciona las coorderadas de celda con una ArrayList (el contenido de la celda). Esto funciona bastante bien ya que no se pierde memory en las celdas "vacías" y es fácil calcular qué celdas inspeccionar. Sin embargo, la creación de todos los ArrayList (el peor caso es N) es costoso y también lo es el crecimiento del HashMap muchas veces (aunque eso se mitiga ligeramente al otorgarle una gran capacidad inicial).

Problema

OK, así que esto funciona, pero aún así no es muy rápido. Ahora puedo intentar micro-optimizar el código JAVA. Sin embargo, no espero mucho de eso ya que el generador de perfiles me dice que se dedica más time a la creación de todos los objects que uso para almacenar las celdas. Espero que haya otros trucos / algorithms que hacen que esto sea mucho más rápido, así que aquí es donde se ve mi estructura de datos ideal:

  • La prioridad número uno es actualizar / rebuild rápidamente toda la estructura de datos
  • Es less importante dividir finamente los objects en contenedores de igual tamaño, podemos dibujar algunos objects adicionales y hacer algunos controles de colisión adicionales si eso significa que la actualización es un poco más rápida.
  • La memory no es realmente importante (juego de PC)

La técnica que está utilizando es muy similar a una técnica de física computacional llamada dinámica molecular, donde las trayectorias de los átomos (generalmente ahora en el range de partículas de 100 k a 10 M) se siguen con pasos de time muy pequeños. El principal problema es que para calcular la fuerza en una partícula, debes comparar su position con la position de cada otra partícula, que se escala muy pobremente (n al cuadrado).

Hay un truco que puedo sugerir, que requiere que elijas una distancia máxima para que las cosas puedan interactuar. Como punto de partida, comenzaría con algo así como 1/10 de la dimensión larga de su espacio, y ajustaré a gusto (corte más largo significa más precisión, pero más cálculos).

El método es recorrer cada partícula (i). (I) obtiene una matriz donde todas las partículas en el range de i se agregan a la matriz. Lo que obtienes al final es una matriz 2d, donde la i-ésima input es una matriz de la partícula en el range de i. Para calcular las fuerzas para i, solo tiene que verificar las inputs en i's array.

El arte de este método es elegir la distancia de corte y el relleno extra (por ejemplo, 20%). La ganancia de velocidad es que solo tiene que verificar algunas interacciones para cada partícula y recalcula los vecinos solo cada varios pasos. Sugeriría elegir una velocidad algo rápida, y calcular cuántos pasos de time tomaría para cruzar la región de "relleno". Hacer el relleno más grande (50% o incluso 100% del límite) le da más pasos entre el recálculo vecino, pero hace que cada paso sea un poco más lento. El equilibrio de esto es una compensación.

Otro truco para calcular las distancias es trabajar con d ^ 2 en lugar de d, eliminando un grupo de llamadas a pow () y sqrt ().

Editar: Es difícil encontrar un enlace de reference que no sea súper técnico. Este es el único que pude encontrar.

Su propia solución suena bastante bien si puede lograr build la estructura de datos en o (n) entonces yo diría que la optimization debe hacerse sobre la elección de la estructura de datos en lugar de sobre el algorithm.

Tengo una implementación similar con algunas diferencias: la estructura de datos principal es una matriz de tamaño fijo (como ArrayList) que es la mejor para el acceso directo a un elemento. Cada celda de la matriz contiene una list vinculada, que es la mejor para las inserciones y tan buena como la list de arreglos para ingresar. Más tarde necesitaremos eliminar elementos de la list vinculada, por lo que para hacer esta operación muy rápido, una idea es almacenar en cada elemento de la list un iterador que apunta a sí mismo (usted dijo que la memory no es un problema, ¿no?)

Para la initialization, cada "partícula" se inserta al final de la list vinculada que corresponde a la celda de la matriz que coincide con su position en el espacio, suponiendo que el espacio está dividido en mosaicos de tamaño fijo. Por lo tanto, todavía tenemos una complejidad o (n), pero optimizamos todo utilizando contenedores más adecuados para el uso.

Cada "partícula" tiene una reference a su list vinculada que contiene para proporcionar un acceso rápido a sus vecinos.

En cada cuadro podemos hacer la interacción entre cada partícula con su list de vecinos, y también diría que con las 8 fichas adyacentes para evitar los efectos cerca de los bordes de los mosaicos.

No es necesario volver a calcular toda la partición en cada fotogtwig; solo tenemos que eliminar y volver a colocar un elemento cuando se mueve más de una distancia dada o, por security, cada X cuadros. Una idea podría ser almacenar la position de cada artículo en el momento en que se insertó en una list vinculada, y en cada cuadro comparar la position actual con la anterior.