Optimizando los cálculos de gravedad

23

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?

Carson Myers
fuente
1
Solo una nota, usted dijo que "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". Tengo la impresión de eso, que estás asumiendo que es más eficiente. Sin embargo, iterar 100 objetos de escombros 10 veces cada uno, sigue siendo lo mismo que iterar 10 objetos masivos 100 veces. Tal vez, sería una buena idea iterar cada objeto de escombros en el bucle de objetos masivos para que no lo haga por segunda vez.
Richard Marskell - Drackir el
¿Qué precisión necesita una simulación? ¿Realmente necesitas que todo se acelere el uno hacia el otro? ¿Y realmente necesitas usar un verdadero cálculo de gravitación? ¿O puede apartarse de esas convenciones por lo que está tratando de lograr?
chaosTechnician
@Drackir Creo que tienes razón. Parte de la razón por la que están separados es porque las matemáticas son diferentes para los objetos sin masa, y parte es porque originalmente no obedecían a la gravedad, por lo que fue más eficiente no incluirlos. Así que es vestigial
Carson Myers, el
@chaosTechnician no tiene que ser muy preciso; de hecho, si solo representa las pocas fuerzas más dominantes, un sistema sería más estable, lo cual es ideal. Pero está descubriendo cuáles de las fuerzas son más dominantes de una manera eficiente con la que estoy teniendo problemas. Además, el cálculo de la gravitación ya es aproximado, es justo G * m1 * m2 / r^2, donde G es solo para modificar el comportamiento. (aunque no puedo simplemente hacer que sigan un camino, porque el usuario puede alterar el sistema)
Carson Myers
¿Por qué cada pieza de escombros tiene que iterar sobre las partículas masivas si no tiene masa? Colisiones?
sam hocevar el

Respuestas:

26

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.

Nathan Reed
fuente
1
+1 para la idea de cuadrícula. Sugeriría también rastrear el centro de masa de la cuadrícula para mantener los cálculos un poco más puros (si es necesario).
chaosTechnician
Me gusta mucho esta idea. Había considerado contener los objetos en las celdas, pero lo abandoné al considerar dos objetos cercanos que estaban técnicamente en celdas diferentes, pero no hice el salto mental para considerar algunas celdas adyacentes, así como considerar la masa combinada de otros Células. Creo que esto debería funcionar realmente bien si lo hago bien.
Carson Myers, el
8
Este es esencialmente el algoritmo Barnes-Hut: en.wikipedia.org/wiki/Barnes –Hut_simulation
Russell Borogove
Incluso suena similar a cómo se supone que la gravedad debe funcionar en física: la flexión del espacio-tiempo.
Zan Lynx el
Me gusta la idea, pero honestamente creo que necesita un poco más de refinamiento, ¿qué sucede si dos objetos están muy cerca el uno del otro pero en celdas separadas? Pude ver cómo podría ayudar su tercer párrafo, pero ¿por qué no hacer una selección circular en los objetos que interactúan?
Jonathan Dickinson el
16

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


fuente
El primer enlace está muerto. ¿El applet está alojado en otro lugar?
Anko
1
¡Fijo! lo siento, olvidé pagar el alquiler en ese dominio, y alguien lo compró automáticamente: \ Además, 3 minutos es un tiempo de respuesta bastante bueno en una publicación 8D de 1.3 años
Y debo agregar: no tengo el código fuente. Si está buscando algún código fuente, consulte parte-nd (escrito en c). Estoy seguro de que también hay otros por ahí.
3

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.

Sean Middleditch
fuente
Separar el proceso en pases es una excelente idea, ya que el intervalo de actualización es (hasta donde yo sé) una fracción muy pequeña de un segundo. La textura del campo de gravedad es IMPRESIONANTE, pero tal vez un poco más allá de mi alcance en este momento.
Carson Myers, el
1
No olvide multiplicar las fuerzas aplicadas por la cantidad de intervalos de tiempo que se han omitido desde la última actualización.
Zan Lynx el
@seanmiddlemitch: ¿Podría explicar un poco más sobre la textura del campo de gravedad? Lo siento, no soy un programador de gráficos, pero esto suena realmente interesante; Simplemente no entiendo cómo se supone que funciona. ¿Y / o tal vez tienes un enlace a una descripción de la técnica?
Felix Dombek
@FelixDombek: renderiza tus objetos como círculos que representan el área de influencia. El sombreador de fragmentos escribe un vector apuntando al centro del objeto y con la magnitud apropiada (según la distancia desde el centro y la masa del objeto). La combinación de hardware puede manejar la suma de estos vectores en modo aditivo. El resultado no serán campos de gravedad precisos, pero seguramente será lo suficientemente bueno para las necesidades de un juego. Como otro enfoque más usando la GPU, vea esta técnica de simulación de gravedad de cuerpo N basada en CUDA: http.developer.nvidia.com/GPUGems3/gpugems3_ch31.html
Sean Middleditch
3

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.

John McDonald
fuente
0

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).

Alex Hirzel
fuente
Esto es fundamentalmente lo que estoy haciendo. Después de obtener todos los pares que involucran X, no vuelvo a iterar sobre X nuevamente. Encuentro la fuerza entre X e Y, X y Z, etc., y aplico esa fuerza a ambos objetos en el par. Una vez que se completa el ciclo, el ForceOfGravityvector es la suma de todas las fuerzas, y luego se convierte en una velocidad y una nueva posición. No estoy seguro de que el cálculo de la gravedad es especialmente caro, y comprobar si supera un umbral primero gustaría no ahorrar una cantidad apreciable de tiempo, no creo
Carson Myers
0

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.

caviar desacelerado
fuente
0

¿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.

Loren Pechtel
fuente