Optimizando los cálculos de gravedad

Tengo un montón de objetos de diferentes tamaños y velocidades que gravitan uno hacia el otro. En cada actualización, tengo que revisar cada objeto y sumar las fuerzas debido a la gravedad de cada otro objeto. No escala muy bien, es uno de los dos grandes cuellos de botella que he encontrado en mi juego, y no estoy seguro de qué hacer para mejorar el rendimiento.

Se siente como que debería ser capaz de mejorar el rendimiento. En un momento dado, probablemente el 99% de los objetos en el sistema solo tendrán una influencia insignificante en un objeto. Por supuesto, no puedo ordenar los objetos por masa y solo considero los 10 objetos más grandes o algo así, porque la fuerza varía más con la distancia que con la masa (la ecuación está en la línea de force = mass1 * mass2 / distance^2). Creo que una buena aproximación sería considerar los objetos más grandes y los objetos más cercanos, ignorando los cientos de pequeños fragmentos de roca en el otro lado del mundo que no pueden afectar nada, pero para descubrir qué objetos son más cercano tengo que iterar sobre todos los objetos, y sus posiciones cambian constantemente, así que no es que pueda hacerlo solo una vez.

Actualmente estoy haciendo algo como esto:

private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...

public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }

    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

(tenga en cuenta que he eliminado mucho código; por ejemplo, las pruebas de colisión, no repito los objetos por segunda vez para detectar colisiones).

Por lo tanto, no siempre estoy iterando sobre toda la lista: solo hago eso para el primer objeto, y cada vez que el objeto encuentra la fuerza que siente hacia otro objeto, ese otro objeto siente la misma fuerza, por lo que solo actualiza ambos ellos, y luego ese primer objeto no tiene que ser considerado nuevamente para el resto de la actualización.

Las funciones Gravity.ForceUnderGravity(...)y Motion.Velocity(...), etc., solo usan un poco de matemática vectorial incorporada de XNA.

Cuando dos objetos chocan, crean escombros sin masa. Se mantiene en una lista separada y los objetos masivos no iteran sobre los escombros como parte de su cálculo de velocidad, pero cada pieza de escombros debe iterar sobre las partículas masivas.

Esto no tiene que escalar a límites increíbles. El mundo no es ilimitado, contiene un borde que destruye los objetos que lo cruzan; me gustaría poder manejar unos mil objetos, actualmente el juego comienza a ahogarse alrededor de 200.

¿Alguna idea sobre cómo podría mejorar esto? ¿Alguna heurística que pueda usar para reducir la longitud del bucle de cientos a solo unos pocos? ¿Algún código que puedo ejecutar con menos frecuencia que cada actualización? ¿Debería simplemente multiprocesarlo hasta que sea lo suficientemente rápido como para permitir un mundo de tamaño decente? ¿Debería intentar descargar los cálculos de velocidad a la GPU? Si es así, ¿cómo diseñaría eso? ¿Puedo mantener datos estáticos compartidos en la GPU? ¿Puedo crear funciones HLSL en la GPU y llamarlas arbitrariamente (usando XNA) o tienen que ser parte del proceso de extracción?

Esto suena como un trabajo para una cuadrícula. Divide tu espacio de juego en una cuadrícula y para cada celda de la cuadrícula mantén una lista de los objetos que hay actualmente en ella. Cuando los objetos se mueven a través de un límite de celda, actualice en qué lista están. Al actualizar un objeto y buscar otros con los que interactuar, puede mirar solo la celda de la cuadrícula actual y algunas vecinas. Puede ajustar el tamaño de la cuadrícula para obtener el mejor rendimiento (equilibrar el costo de actualizar las celdas de la cuadrícula, que es mayor cuando las celdas de la cuadrícula son demasiado pequeñas) con el costo de hacer las búsquedas, que es mayor cuando las celdas de la cuadrícula también grande).

Esto, por supuesto, hará que los objetos que están más separados que un par de celdas de la cuadrícula no interactúen en absoluto, lo que probablemente sea un problema porque una gran acumulación de masa (ya sea un objeto grande o un grupo de muchos objetos pequeños) debería , como mencionó, tiene una región de influencia más grande.

Una cosa que podría hacer es realizar un seguimiento de la masa total dentro de cada celda de la cuadrícula y tratar la celda completa como un solo objeto a los efectos de interacciones más alejadas. Es decir: cuando calcula la fuerza sobre un objeto, calcule la aceleración directa de objeto a objeto para los objetos en unas pocas celdas de cuadrícula cercanas, luego agregue una aceleración de celda a celda para cada celda de cuadrícula más alejada (o tal vez solo los que tienen una cantidad de masa no despreciable). Por aceleración de celda a celda, me refiero a un vector calculado usando las masas totales de las dos celdas y la distancia entre sus centros. Eso debería dar una aproximación razonable de la gravedad sumada de todos los objetos en esa celda de la cuadrícula, pero mucho más barato.

Si el mundo del juego es muy grande, incluso podría usar una cuadrícula jerárquica , como un quadtree (2D) u octree (3D), y aplicar principios similares. Las interacciones de mayor distancia corresponderían a niveles más altos de la jerarquía.

El algoritmo de Barnes-Hut es el camino a seguir con este. Se ha utilizado en simulaciones de supercomputadora para resolver su problema exacto. No es demasiado difícil de codificar, y es muy eficiente. De hecho, escribí un applet de Java no hace mucho para resolver este problema.

Visite http://mathandcode.com/programs/javagrav/ y presione "inicio" y "mostrar quadtree".

En la pestaña de opciones, puede ver que el recuento de partículas puede llegar hasta 200,000. En mi computadora, el cálculo finaliza en aproximadamente 2 segundos (el dibujo de 200,000 puntos toma aproximadamente 1 segundo, pero el cálculo se ejecuta en un hilo separado).

Así es como funciona mi applet:

1. Cree una lista de partículas aleatorias, con masas aleatorias, posiciones y velocidades iniciales.
2. Construya un árbol cuádruple a partir de estas partículas. Cada nodo quadtree contiene el centro de masa de cada subnodo. Básicamente, para cada nodo tiene tres valores: massx, massy y mass. Cada vez que agrega una partícula a un nodo dado, aumenta massx y massy por la partícula.x * partículas.masas y la partícula.y * partículas.masas respectivamente. La posición (massx / mass, massy / mass) terminará como el centro de masa del nodo.
3. Para cada partícula, calcule las fuerzas (completamente descritas aquí ). Esto se hace comenzando en el nodo superior y recurriendo a través de cada subnodo del quadtree hasta que el subnodo dado sea lo suficientemente pequeño. Una vez que deja de recurrir, puede calcular la distancia desde la partícula hasta el centro de masa del nodo, y luego puede calcular la fuerza utilizando la masa del nodo y la masa de la partícula.

Tu juego debería ser capaz de manejar miles de objetos que se atraen mutuamente. Si cada objeto es "tonto" (como las partículas de huesos desnudos en mi applet), debería poder obtener de 8000 a 9000 partículas, tal vez más. Y esto supone un subproceso único. Con aplicaciones informáticas de subprocesos múltiples o paralelas, puede obtener muchas más partículas que las que se actualizan en tiempo real.

Consulte también: http://www.youtube.com/watch?v=XAlzniN6L94 para obtener una gran representación de esto

Nathan Reed tiene una excelente respuesta. La versión corta es usar una técnica de fase ancha que se ajuste a la topología de su simulación y solo ejecutar los cálculos de gravedad en pares de objetos que tendrán un efecto notable entre sí. Realmente no es diferente de lo que haría para la detección de colisión de fase ancha.

Sin embargo, a partir de eso, otra posibilidad es actualizar solo objetos de forma intermitente. Básicamente, cada paso de tiempo (cuadro) solo actualiza una fracción de todos los objetos y deja la velocidad (o aceleración, según su preferencia) igual para los otros objetos. Es poco probable que el usuario note algún retraso en las actualizaciones de este, siempre y cuando los intervalos no sean demasiado largos. Esto le dará una aceleración lineal del algoritmo, así que definitivamente investigue las técnicas de broadphase como sugirió Nathan también, que pueden proporcionar aceleraciones mucho más significativas si tiene una tonelada de objetos. Si bien no se modeló de la misma manera en lo más mínimo, es como tener "ondas de gravedad". :)

Además, podría generar un campo de gravedad en una pasada y luego actualizar los objetos en una segunda pasada. La primera pasada básicamente está llenando una cuadrícula (o una estructura de datos espaciales más compleja) con las influencias de gravedad de cada objeto. El resultado ahora es un campo de gravedad que incluso puede renderizar (se ve muy bien) para ver qué aceleración se aplicará a un objeto en una ubicación determinada. Luego, itera sobre los objetos y simplemente aplica los efectos del campo de gravedad a ese objeto. Aún más genial, puede hacer esto en una GPU al representar los objetos como círculos / esferas en una textura, luego leer la textura (o usar otro pase de transformación-retroalimentación en la GPU) para modificar las velocidades del objeto.

Recomendaría usar un árbol cuádruple. Le permiten buscar rápida y eficientemente todos los objetos en un área rectangular arbitraria. Aquí está el artículo wiki sobre ellos: http://en.wikipedia.org/wiki/Quadtree

Y un enlace descarado a mi propio proyecto XNA Quad Tree en SourceForge: http://sourceforge.net/projects/quadtree/

También mantendría una lista de todos los objetos grandes para que puedan interactuar con todo sin importar la distancia.

Solo un poco de entrada (posiblemente ingenua). No hago programación de juegos, pero lo que siento es que tu cuello de botella fundamental es el cálculo de la gravedad debida a la gravedad. En lugar de iterar sobre cada objeto X y luego encontrar el efecto gravitacional de cada objeto Y y agregarlo, puede tomar cada par X, Y y encontrar la fuerza entre ellos. Eso debería reducir el número de cálculos de gravedad de O (n ^ 2). Entonces hará muchas adiciones (O (n ^ 2)), pero esto normalmente es menos costoso.

También en este punto puede implementar reglas como "si la fuerza gravitacional será menor que \ epsilon porque estos cuerpos son demasiado pequeños, establezca la fuerza en cero". Puede ser ventajoso tener esta estructura también para otros fines (incluida la detección de colisiones).

Al extender la respuesta de seanmiddleditch, pensé que podría arrojar algo de luz (¿ironía?) Sobre la idea del campo de gravedad.

En primer lugar, no lo piense como una textura, sino como un campo discreto de valores que pueden modificarse (una matriz bidimensional, por así decirlo); y la precisión posterior de la simulación podría ser la resolución de ese campo.

Cuando introduce un objeto en el campo, su potencial de gravitación se puede calcular para todos los valores circundantes; creando así un sumidero de gravitación en el campo.

Pero, ¿cuántos de estos puntos debe calcular antes de que se vuelva más o tan ineficaz como antes? Probablemente no muchos, incluso 32x32 es un campo sustancial para iterar para cada objeto. Por lo tanto, divida todo el proceso en múltiples pases; cada uno con diferentes resoluciones (o precisión).

Es decir, la primera pasada puede calcular la gravedad de los objetos representados en una cuadrícula de 4x4, con cada valor de celda representando una coordenada 2D en el espacio. Dando una complejidad subtotal O (n * 4 * 4).

La segunda pasada puede ser más precisa, con un campo de gravedad de resolución de 64x64, con cada valor de celda que representa una coordenada 2D en el espacio. Sin embargo, como la complejidad es muy alta, puede restringir el radio de las celdas circundantes afectadas (quizás, solo se actualizan las celdas circundantes de 5x5).

Se podría usar una tercera pasada adicional para cálculos de alta precisión, con quizás una resolución de 1024x1024. Recuerde que en ningún momento está realizando cálculos separados 1024x1024, pero opera solo en partes de este campo (quizás subsecciones 6x6).

De esa manera, su complejidad general para la actualización es O (n * (4 * 4 + 5 * 5 + 6 * 6)).

Para calcular los cambios de velocidad en cada uno de sus objetos, para cada campo de gravedad (4x4, 64x64, 1024x1024) solo debe mapear la posición de las masas de puntos a una celda de la cuadrícula, aplicar el vector de potencial gravitacional general de las celdas de la cuadrícula a un nuevo vector; repita para cada "capa" o "pase"; luego agréguelos juntos. Esto debería darle un buen vector de fuerza gravitacional resultante.

Por lo tanto, la complejidad general es: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). Lo que realmente cuenta (para la complejidad) es cuántas celdas circundantes actualiza al calcular el potencial gravitacional en los pases, no la resolución general de los campos de gravedad.

La razón de los campos de baja resolución (primeros pasos) es obviamente abarcar el universo en su conjunto y garantizar que las masas periféricas sean atraídas a áreas más densas a pesar de la distancia. Luego use campos de mayor resolución como capas separadas para aumentar la precisión de los planetas vecinos.

Espero que esto tenga sentido.

¿Qué tal otro enfoque:

Asigne un área de influencia a los objetos en función de su masa: simplemente son demasiado pequeños para tener un efecto medible más allá de ese rango.

Ahora divide tu mundo en una cuadrícula y coloca cada objeto en una lista de todas las celdas en las que tiene influencia.

Haga sus cálculos de gravedad solo en los objetos de la lista adjunta a la celda en la que se encuentra un objeto.

Solo tiene que actualizar las listas cuando un objeto se mueve a una nueva celda de cuadrícula.

Cuanto más pequeñas sean las celdas de la cuadrícula, menos cálculos realizará por actualización, pero más trabajo realizará para actualizar las listas.