Cálculos de gravedad 2D de subprocesos múltiples

Estoy construyendo un juego de exploración espacial y actualmente he comenzado a trabajar en la gravedad (en C # con XNA).

La gravedad aún necesita ajustes, pero antes de que pueda hacer eso, necesito abordar algunos problemas de rendimiento con mis cálculos físicos.

Esto está usando 100 objetos, normalmente representando 1000 de ellos sin cálculos físicos, supera los 300 FPS (que es mi límite de FPS), pero con más de 10 objetos trae el juego (y el hilo único en el que se ejecuta) a su rodillas al hacer cálculos físicos.

Verifiqué el uso de mi hilo y el primer hilo se estaba matando a sí mismo por todo el trabajo, así que pensé que solo necesitaba hacer el cálculo físico en otro hilo. Sin embargo, cuando trato de ejecutar el método de actualización de la clase Gravity.cs en otro hilo, incluso si el método de actualización de Gravity no contiene nada, el juego aún se reduce a 2 FPS.

Gravity.cs

public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
        {
            Vector2 Force = new Vector2();

            foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
            {
                if (e2.Key != e.Key)
                {
                    float distance = Vector2.Distance(entityEngine.Entities[e.Key].Position, entityEngine.Entities[e2.Key].Position);
                    if (distance > (entityEngine.Entities[e.Key].Texture.Width / 2 + entityEngine.Entities[e2.Key].Texture.Width / 2))
                    {
                        double angle = Math.Atan2(entityEngine.Entities[e2.Key].Position.Y - entityEngine.Entities[e.Key].Position.Y, entityEngine.Entities[e2.Key].Position.X - entityEngine.Entities[e.Key].Position.X);

                        float mult = 0.1f *
                            (entityEngine.Entities[e.Key].Mass * entityEngine.Entities[e2.Key].Mass) / distance * distance;

                        Vector2 VecForce = new Vector2((float)Math.Cos(angle), (float)Math.Sin(angle));
                        VecForce.Normalize();

                        Force = Vector2.Add(Force, VecForce * mult);
                    }
                }
            }

            entityEngine.Entities[e.Key].Position += Force;
        }

    }

Si lo se. Es un bucle foreach anidado, pero no sé cómo hacer el cálculo de la gravedad, y esto parece funcionar, es tan intenso que necesita su propio hilo. (Incluso si alguien conoce una forma súper eficiente de hacer estos cálculos, aún me gustaría saber cómo PODRÍA hacerlo en múltiples hilos)

EntityEngine.cs (administra una instancia de Gravity.cs)

public class EntityEngine
{
    public Dictionary<string, Entity> Entities = new Dictionary<string, Entity>();
    public Gravity gravity;
    private Thread T;


    public EntityEngine()
    {
        gravity = new Gravity(this);
    }


    public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in Entities)
        {
            Entities[e.Key].Update();
        }

        T = new Thread(new ThreadStart(gravity.Update));
        T.IsBackground = true;
        T.Start();
    }

}

EntityEngine se crea en Game1.cs, y su método Update () se llama dentro de Game1.cs.

Necesito que mi cálculo de física en Gravity.cs se ejecute cada vez que se actualiza el juego, en un hilo separado para que el cálculo no ralentice el juego a FPS horriblemente bajo (0-2).

¿Cómo haría para que este hilo funcione? (cualquier sugerencia para un sistema de gravedad planetaria mejorado es bienvenida si alguien los tiene)

Tampoco estoy buscando una lección de por qué no debería usar el enhebrado o los peligros de usarlo incorrectamente, estoy buscando una respuesta directa sobre cómo hacerlo. Ya pasé una hora buscando en Google esta misma pregunta con pocos resultados que entendí o que fueron útiles. No quiero decir que sea grosero, pero siempre parece difícil como un novato en programación obtener una respuesta directa y significativa, por lo general prefiero obtener una respuesta tan compleja que fácilmente podría resolver mi problema si lo entendiera, o alguien diciendo por qué no debería hacer lo que quiero hacer y sin ofrecer alternativas (que son útiles).

¡Gracias por la ayuda!

EDITAR : Después de leer las respuestas que he recibido, veo que a ustedes realmente les importa y no solo están tratando de decir una respuesta que podría funcionar. Quería matar dos pájaros de un tiro (mejorando el rendimiento y aprendiendo algunos conceptos básicos de subprocesos múltiples), pero parece que la mayor parte del problema radica en mis cálculos y que enhebrar es más complicado de lo que vale para aumentar el rendimiento. Gracias a todos, volveré a leer sus respuestas y probaré sus soluciones cuando termine la escuela. ¡Gracias de nuevo!

Lo que tienes aquí es un algoritmo clásico de O (n²) . La causa raíz de su problema no tiene nada que ver con el enhebrado y todo que ver con el hecho de que su algoritmo tiene una alta complejidad.

Si no se ha encontrado con la notación "Big O" antes, básicamente significa la cantidad de operaciones requeridas para trabajar en n elementos (esta es la explicación súper simplificada). Sus 100 elementos ejecutan la parte interna de su bucle 10000 veces .

En el desarrollo del juego, generalmente desea evitar los algoritmos O (n²) , a menos que tenga una cantidad pequeña (y preferiblemente fija o limitada) de datos y un algoritmo muy rápido.

Si cada entidad afectara a todas las demás entidades, necesitaría necesariamente un algoritmo O (n²). Pero parece que solo unas pocas entidades están realmente interactuando (debido a if (distance < ...)), por lo que podría reducir significativamente su número de operaciones utilizando algo llamado " Particionamiento espacial ".

Debido a que este es un tema bastante detallado y algo específico del juego, le recomiendo que haga una nueva pregunta para obtener más detalles. Vamonos...

Uno de los principales problemas de rendimiento con su código es bastante simple. Esto es muy lento :

foreach (KeyValuePair<string, Entity> e in Entities)
{
    Entities[e.Key].Update();
}

¡Está haciendo una búsqueda de diccionario por cadena, cada iteración (varias veces en sus otros bucles), para un objeto que ya tiene!

Podrías hacer esto:

foreach (KeyValuePair<string, Entity> e in Entities)
{
    e.Value.Update();
}

O podría hacer esto: (Personalmente me gusta más, ambos deberían tener la misma velocidad)

foreach (Entity e in Entities.Values)
{
    e.Update();
}

La búsqueda de un diccionario por cadena es bastante lenta. Iterar directamente será significativamente más rápido.

Aunque, ¿con qué frecuencia realmente necesita buscar objetos por su nombre? En comparación con la frecuencia con la que debe iterar a través de todos ellos? Si solo realiza búsquedas de nombres en raras ocasiones, considere almacenar sus entidades en un List(dele unName miembro).

El código que realmente tienes allí es relativamente trivial. No lo he perfilado, pero apuesto a que la mayor parte de su tiempo de ejecución va a las búsquedas repetidas del diccionario . Su código puede ser "lo suficientemente rápido" simplemente solucionando este problema.

EDITAR: El siguiente problema más grande es probablemente llamar Atan2y luego convertirlo inmediatamente en un vector con Siny Cos! Solo usa el vector directamente.

Finalmente, abordemos el enhebrado y los principales problemas en su código:

Primero y más obvio: ¡No cree un nuevo hilo en cada cuadro! Los objetos de hilo son bastante "pesados". La solución más simple a esto sería simplemente usar ThreadPoolen su lugar.

Por supuesto, no es tan simple. Pasemos al problema número dos: ¡No toque los datos en dos hilos a la vez! (Sin agregar la infraestructura de seguridad de hilos adecuada).

Básicamente estás pisoteando la memoria aquí de la manera más horrible . No hay seguridad de hilo aquí. Cualquiera de los múltiples " gravity.Update" subprocesos que está iniciando puede sobrescribir los datos que se usan en otro subproceso en momentos inesperados. Mientras tanto, su hilo principal, sin duda, tocará todas estas estructuras de datos. No me sorprendería si este código produjera infracciones de acceso a la memoria difíciles de reproducir.

Hacer que algo como este hilo sea seguro es difícil y puede agregar una sobrecarga de rendimiento significativa de modo que a menudo no valga la pena el esfuerzo.

Pero, ya que de todas formas preguntaste (no tan) cómo hacerlo, hablemos de eso ...

Normalmente recomendaría comenzar practicando algo simple, donde su hilo es básicamente "disparar y olvidar". Reproducción de audio, escritura de algo en el disco, etc. Las cosas se complican cuando tiene que enviar el resultado al hilo principal.

Básicamente hay tres enfoques para su problema:

1) Coloque bloqueos alrededor de todos los datos que usa en los subprocesos. En C # esto se hace bastante simple con la lockdeclaración.

En general, se crea (¡y se retiene!) new objectEspecíficamente para el bloqueo para proteger algunos conjuntos de datos (es por razones de seguridad que generalmente solo aparecen cuando se escriben API públicas, pero de todos modos es un buen estilo). ¡Luego debe bloquear su objeto de bloqueo en todas partes donde acceda a los datos que protege!

Por supuesto, si algo está "bloqueado" por un subproceso porque está en uso y otro subproceso intenta acceder a él, ese segundo subproceso se verá obligado a esperar hasta que finalice el primer subproceso. Entonces, a menos que seleccione cuidadosamente las tareas que se pueden hacer en paralelo, básicamente obtendrá un rendimiento de subproceso único (o peor).

Entonces, en su caso, no tiene sentido hacer esto a menos que pueda diseñar su juego de manera que se ejecute algún otro código en paralelo que no toque su colección de entidades.

2) Copie los datos en el hilo, déjelos procesar y luego retire el resultado nuevamente cuando haya terminado.

La forma exacta en que implemente esto dependerá de lo que esté haciendo. Pero, obviamente, esto implicará una operación de copia potencialmente costosa (o dos) que en muchos casos será más lenta que simplemente hacer las cosas con un solo subproceso.

Y, por supuesto, todavía tiene que tener otro trabajo que hacer en segundo plano, de lo contrario, su hilo principal estará sentado esperando que su otro hilo termine para que pueda copiar los datos nuevamente.

3) Utilice estructuras de datos seguras para subprocesos.

Estos son bastante más lentos que sus contrapartes de un solo hilo y, a menudo, son más difíciles de usar que el simple bloqueo. Todavía pueden exhibir los problemas de bloqueo (reduciendo el rendimiento a un solo hilo) a menos que los use con cuidado.

Finalmente, debido a que esta es una simulación basada en cuadros, necesitará que el hilo principal espere a que otros hilos proporcionen sus resultados, para que el cuadro se pueda representar y la simulación pueda continuar. Una explicación completa es realmente demasiado larga para poner aquí, pero básicamente querrás aprender a usar Monitor.Waity Monitor.Pulse. Aquí hay un artículo para comenzar .

Sé que no he dado detalles de implementación específicos (excepto el último bit) o ​​código para ninguno de estos enfoques. En primer lugar, habría mucho que cubrir. Y, en segundo lugar, ninguno de ellos es aplicable a su código por sí solo: debe acercarse a toda su arquitectura con el objetivo de agregar subprocesos.

El enhebrado no hará mágicamente el código que tienes allí más rápido, ¡solo te permite hacer otra cosa al mismo tiempo!

Ok a primera vista hay algunas cosas que deberías probar. Al principio, debe intentar reducir sus comprobaciones de colisión, puede hacerlo utilizando algún tipo de estructura espacial como un quadtree . Esto le permitirá reducir el segundo recuento foreach, ya que solo consultará a las entidades que cierren el primero.

Con respecto a sus hilos: intente no crear un hilo cada turno de actualización. Esta sobrecarga puede estar ralentizando su velocidad más que acelerando las cosas. En su lugar, intente crear un único hilo de colisión y deje que haga el trabajo por usted. No tengo un enfoque concreto de copiar-pegar-este-código , pero hay artículos sobre sincronización de subprocesos y trabajo en segundo plano para C #.

Otro punto es que en el bucle foreach no es necesario hacerlo entityEngine.Entities[e.Key].Textureporque ya accedió al dict en su encabezado foreach. En cambio, solo puedes escribir e.Texture. Realmente no sé sobre el impacto de esto, solo quería avisarte;)

Una última cosa: en este momento está revisando cada entidad, porque se consulta en el primer bucle foreach.

Ejemplo con 2 entidades A y B:

pick A in first foreach loop
   pick A in second foreach loop
      skip A because keys are the same
   pick B in second foreach loop
      collision stuff
pick B in first foreach loop
   pick A in second foreach loop
      collision stuff
   pick B in second foreach loop
      skip B because keys are the same

Si bien este es un enfoque posible, tal vez pueda manejar A y B en un turno, omitiendo la mitad de sus controles de colisión

Espero que esto te ayude a comenzar =)

PD: Incluso si dijiste que no quieres escucharlo: intenta mantener la detección de colisión en el mismo hilo y simplemente acelera lo suficiente. Enhebrarlo parece una buena idea, pero con esto viene la necesidad de sincronizar como el infierno. Si su verificación de colisión es más lenta que su actualización (razón para enhebrarla), recibirá fallas y errores, porque la colisión se disparará después de que las naves ya se hayan movido y viceversa. No quiero desanimarte, esto es solo una experiencia personal.

EDIT1: Enlaces con el tutorial de QuadTree (Java): http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect- probably-collisions-in-2d-space/

Honestamente, lo primero que debe hacer es cambiar a un algoritmo mejor.

Paralelizar su simulación puede, incluso en el mejor caso posible, acelerarla solo por un factor igual al número de CPU × núcleos por CPU × hilos por núcleo disponible en su sistema, es decir, entre 4 y 16 para una PC moderna. (Mover su código a la GPU puede producir factores de paralelización mucho más impresionantes, a costa de una complejidad de desarrollo adicional y una velocidad de cálculo de línea de base más baja por subproceso). Con un algoritmo O (n²), como su código de ejemplo, esto le permitiría use de 2 a 4 veces la cantidad de partículas que tiene actualmente.

Por el contrario, cambiar a un algoritmo más eficiente podría acelerar fácilmente su simulación, por ejemplo, por un factor de 100 a 10000 (números estimados puramente). La complejidad temporal de los buenos algoritmos de simulación de n cuerpos usando subdivisión espacial se escala aproximadamente como O (n log n), que es "casi lineal", por lo que puede esperar casi el mismo factor de aumento en el número de partículas que puede manejar. También, que aún sería utilizar sólo un hilo, por lo que todavía habría espacio para la paralelización por encima de eso .

De todos modos, como han señalado las otras respuestas, el truco general para simular eficientemente un gran número de partículas que interactúan es organizarlas en un quadtree (en 2D) o un octree (en 3D). En particular, para simular la gravedad, el algoritmo básico que desea utilizar es el algoritmo de simulación de Barnes-Hut , en el que almacena la masa total (y el centro de masa) de todas las partículas contenidas en cada celda de su quad / octree y use eso para aproximar el efecto gravitacional promedio de las partículas en esa celda sobre otras partículas distantes.

Puede encontrar muchas descripciones y tutoriales sobre el algoritmo Barnes-Hut buscando en Google , pero aquí hay una buena y simple para comenzar , mientras que aquí hay una descripción de una implementación avanzada utilizada para la simulación de colisiones de galaxias por GPU.

Otra respuesta de optimización que no tiene nada que ver con hilos. Lo siento por eso.

Estás calculando la distancia () de cada par. Esto implica tomar una raíz cuadrada, que es lenta. También implica varias búsquedas de objetos para obtener los tamaños reales.

Puede optimizar esto usando la función DistanceSquared () en su lugar. Precalcule la distancia máxima a la que dos objetos pueden interactuar, cuadrátela y luego compárela con el DistanceSquared (). Si y solo si la distancia al cuadrado está dentro del máximo, tome la raíz cuadrada y compárela con los tamaños reales de los objetos.

EDITAR : Esta optimización es principalmente para cuando estás probando colisiones, lo que ahora noté que en realidad no es lo que estás haciendo (aunque seguramente lo harás en algún momento). Sin embargo, aún puede ser aplicable a su situación, si todas las partículas son de tamaño / masa similar.

No sé mucho sobre subprocesos, pero parece que sus bucles requieren mucho tiempo, por lo que tal vez cambiar de esto

i = 0; i < count; i++
  j = 0; j < count; j++

  object_i += force(object_j);

a esto

i = 0; i < count-1; i++
  j = i+1; j < count; j++

  object_i += force(object_j);
  object_j += force(object_i);

podría ayudar

Si ya tiene problemas tan grandes con 10 objetos simulados, ¡deberá optimizar el código! Su bucle anidado causaría solo 10 * 10 iteraciones de las cuales se omiten 10 iteraciones (mismo objeto), lo que da como resultado 90 iteraciones del bucle interno. Si solo logra 2 FPS, esto significaría que su rendimiento es tan malo, que solo logra 180 iteraciones del bucle interno por segundo.

Te sugiero que hagas lo siguiente:

1. PREPARACIÓN / REFERENCIA: Para saber con certeza que esta rutina es el problema, escriba una pequeña rutina de referencia. Ejecutará el Update()método de la gravedad varias veces, por ejemplo, 1000 veces y medirá su tiempo. Si desea lograr 30 FPS con 100 objetos, debe simular 100 objetos y medir el tiempo para 30 ejecuciones. Debería ser menos de 1 segundo. El uso de este punto de referencia es necesario para hacer optimizaciones razonables. De lo contrario, probablemente lograrás lo contrario y harás que el código se ejecute más lentamente porque piensas que debe ser más rápido ... ¡Así que realmente te animo a que hagas esto!

2. OPTIMIZACIONES: Si bien no puede hacer mucho sobre el problema del esfuerzo O (N²) (es decir: el tiempo de cálculo aumenta cuadráticamente con el número de objetos simulados N), puede mejorar el código en sí.

   a) Utiliza muchas búsquedas de "matriz asociativa" (Diccionario) dentro de su código. Estos son lentos! Por ejemplo entityEngine.Entities[e.Key].Position. ¿No puedes usarlo?e.Value.Position ? Esto ahorra una búsqueda. Hace esto en todas partes en todo el bucle interno para acceder a las propiedades de los objetos a los que hace referencia e y e2 ... ¡Cambie esto! b) Crea un nuevo Vector dentro del bucle new Vector2( .... ). Todas las llamadas "nuevas" implican alguna asignación de memoria (y más tarde: desasignación). Estos son incluso mucho más lentos que las búsquedas de diccionarios. Si solo necesita este Vector temporalmente, asígnelo fuera de los bucles Y -reutilícelo- reinicializando sus valores a los nuevos valores en lugar de crear un nuevo objeto. c) Utiliza muchas funciones trigonométricas (p. ej.atan2 ycos) dentro del bucle. Si su precisión no necesita ser realmente exacta, puede intentar usar una tabla de búsqueda en su lugar. Para hacer esto, escala su valor a un rango definido, redondee a un valor entero y búsquelo en una tabla de resultados calculados previamente. Si necesita ayuda con eso, solo pregunte. d) Usas a menudo .Texture.Width / 2. Puede precalcular esto y almacenar el resultado como .Texture.HalfWidtho, si este es siempre un valor entero positivo, puede usar el bit de la operación de desplazamiento>> 1 dividir por dos.

¡Realice solo uno de los cambios a la vez y mida el cambio según el punto de referencia para ver cómo afectó su tiempo de ejecución! Tal vez una cosa es buena, mientras que la otra idea era mala (¡incluso las propuse arriba!) ...

¡Creo que estas optimizaciones serán mucho mejores que tratar de lograr un mejor rendimiento utilizando múltiples hilos! Tendrá muchos problemas para coordinar los hilos, de modo que no sobrescriban los demás valores. También entrarán en conflicto al acceder a regiones de memoria similares también. Si utiliza 4 CPU / subprocesos para este trabajo, puede esperar solo una velocidad de 2 a 3 para la velocidad de fotogramas.

¿Puede volver a trabajar sin las líneas de creación de objetos?

Vector2 Force = nuevo Vector2 ();

Vector2 VecForce = nuevo Vector2 ((flotante) Math.Cos (ángulo), (flotante) Math.Sin (ángulo));

Si quizás pudiera colocar el valor de fuerza en la entidad en lugar de crear dos objetos nuevos cada vez, puede ayudar a mejorar el rendimiento.