Steigerung der Effizienz der N-Body-Schwerkraftsimulation

Ich mache ein Spiel vom Typ Weltraumforschung, es wird viele Planeten und andere Objekte haben, die alle eine realistische Schwerkraft haben werden. Ich habe derzeit ein System, das funktioniert, aber wenn die Anzahl der Planeten über 70 steigt, verringert sich die FPS um praktisch exponentielle Raten. Ich mache es in C # und XNA.

Ich vermute, dass ich in der Lage sein sollte, Schwerkraftberechnungen zwischen 100 Objekten ohne diese Art von Belastung durchzuführen, daher ist meine Methode eindeutig nicht so effizient, wie sie sein sollte.

Ich habe zwei Dateien, Gravity.cs und EntityEngine.cs. Gravity verwaltet NUR die Gravitationsberechnungen. EntityEngine erstellt eine Instanz von Gravity und führt sie zusammen mit anderen entitätsbezogenen Methoden aus.

EntityEngine.cs

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

            gravity.Update();
        }

(Nur relevanter Code von EntityEngine, selbsterklärend. Wenn eine Instanz der Schwerkraft in entityEngine erstellt wird, übergibt sie sich selbst (diese), damit die Schwerkraft auf entityEngine.Entities (ein Wörterbuch aller Planetenobjekte) zugreifen kann.)

Gravity.cs

namespace ExplorationEngine
{
    public class Gravity
    {
        private EntityEngine entityEngine;
        private Vector2 Force;
        private Vector2 VecForce;
        private float distance;
        private float mult;

        public Gravity(EntityEngine e)
        {
            entityEngine = e;
        }


        public void Update()
        {
            //First loop
            foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
            {
            //Reset the force vector
            Force = new Vector2();

                //Second loop
                foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
                {
                    //Make sure the second value is not the current value from the first loop
                    if (e2.Value != e.Value )
                    {
                        //Find the distance between the two objects. Because Fg = G * ((M1 * M2) / r^2), using Vector2.Distance() and then squaring it
                        //is pointless and inefficient because distance uses a sqrt, squaring the result simple cancels that sqrt.
                        distance = Vector2.DistanceSquared(e2.Value.Position, e.Value.Position);

                        //This makes sure that two planets do not attract eachother if they are touching, completely unnecessary when I add collision,
                        //For now it just makes it so that the planets are not glitchy, performance is not significantly improved by removing this IF
                        if (Math.Sqrt(distance) > (e.Value.Texture.Width / 2 + e2.Value.Texture.Width / 2))
                        {
                            //Calculate the magnitude of Fg (I'm using my own gravitational constant (G) for the sake of time (I know it's 1 at the moment, but I've been changing it)
                            mult = 1.0f * ((e.Value.Mass * e2.Value.Mass) / distance);

                            //Calculate the direction of the force, simply subtracting the positions and normalizing works, this fixes diagonal vectors
                            //from having a larger value, and basically makes VecForce a direction.
                            VecForce = e2.Value.Position - e.Value.Position;
                            VecForce.Normalize();

                            //Add the vector for each planet in the second loop to a force var.
                            Force = Vector2.Add(Force, VecForce * mult);
                            //I have tried Force += VecForce * mult, and have not noticed much of an increase in speed.
                        }
                    }
                }

                //Add that force to the first loop's planet's position (later on I'll instead add to acceleration, to account for inertia)
                e.Value.Position += Force;
            }

        }

    }
}

Ich habe verschiedene Tipps (zur Schwerkraftoptimierung, nicht zum Einfädeln) aus DIESER Frage (die ich gestern gemacht habe) verwendet. Ich habe diese Schwerkraftmethode (Gravity.Update) so effizient gemacht, wie ich es machen kann. Dieser O (N ^ 2) -Algorithmus scheint jedoch immer noch meine gesamte CPU-Leistung zu verbrauchen.

Hier ist ein Link (Google Drive, gehe zu Datei> Herunterladen, behalte .Exe mit dem Inhaltsordner, du brauchst XNA Framework 4.0 Redist. Wenn du es noch nicht hast) zur aktuellen Version meines Spiels. Ein Linksklick macht einen Planeten, ein Rechtsklick entfernt den letzten Planeten. Die Maus bewegt die Kamera, das Scrollrad zoomt hinein und heraus. Sehen Sie sich FPS und Planet Count an, um zu sehen, was ich mit Leistungsproblemen nach 70 Planeten meine. (ALLE 70 Planeten müssen sich bewegen, ich hatte 100 stationäre Planeten und nur 5 oder so bewegte Planeten, während ich noch 300 fps habe. Das Problem tritt auf, wenn sich 70+ bewegen.)

Nach 70 Planeten werden Leistungstanks exponentiell hergestellt. Mit <70 Planeten bekomme ich 330 fps (ich habe es auf 300 begrenzt). Bei 90 Planeten beträgt die FPS ungefähr 2, mehr als das, und sie bleibt bei 0 FPS. Seltsamerweise steigt die FPS, wenn alle Planeten stationär sind, wieder auf etwa 300 an, aber sobald sich etwas bewegt, geht es wieder auf das zurück, was es war. Ich habe keine Systeme, um dies zu ermöglichen.

Ich habe über Multithreading nachgedacht, aber diese vorherige Frage hat mir ein oder zwei Dinge beigebracht, und ich sehe jetzt, dass dies keine praktikable Option ist.

Ich habe auch gedacht, ich könnte stattdessen die Berechnungen auf meiner GPU durchführen, obwohl ich nicht denke, dass dies notwendig sein sollte. Ich weiß auch nicht, wie ich das machen soll, es ist kein einfaches Konzept und ich möchte es vermeiden, es sei denn, jemand kennt eine wirklich noobfreundliche einfache Methode, die für eine n-Körper-Schwerkraftberechnung funktioniert. (Ich habe eine NVidia GTX 660)

Zuletzt habe ich überlegt, ein Quadtree-System zu verwenden. (Barnes Hut-Simulation) Mir wurde (in der vorherigen Frage) gesagt, dass dies eine gute Methode ist, die häufig verwendet wird, und sie scheint logisch und unkompliziert zu sein. Die Implementierung ist jedoch weit über meinem Kopf und ich habe keine gute gefunden Tutorial für C #, das es jedoch auf eine Weise erklärt, die ich verstehen kann, oder Code verwendet, den ich eventuell herausfinden kann.

Meine Frage lautet also: Wie kann ich meine Schwerkraftmethode effizienter gestalten, indem ich mehr als 100 Objekte verwenden kann (ich kann 1000 Planeten mit konstanten 300 FPS ohne Schwerkraftberechnungen rendern) und ob ich nicht viel tun kann, um mich zu verbessern Kann ich meine GPU für die Berechnungen verwenden (einschließlich einer Art Quadtree-System)?

Ihr Ansatz und Ihre Implementierung sind gültig (ohne Berücksichtigung dieser position += forceLinie). Solange es nur eine Instanz von gibt gravity. Der von Ihnen bereitgestellte Code enthält nichts, was zu einer Laufzeit von über O (n²) führt. Daher ist es vernünftig, bei 100 Planeten einen Rückgang der Framerate um die Hälfte zu erwarten. Das sind 100 Planeten mit 150 fps. 200 Planeten mit 30 fps. usw.

Da dies nicht mit Ihren Beobachtungen übereinstimmt, stellen sich einige Fragen. Am prominentesten: Sind Sie sicher, dass die fps verloren gehen gravity.Update? Haben Sie es mit einem Profiler gemessen ? Welche Aussage ist der Täter? Gibt es einen bemerkenswerten Unterschied im Speicherverbrauch? Ist der Müllsammler beschäftigt? Können Sie 100-200 Planeten mit 300 fps rendern, wenn es keine Schwerkraft gibt?

Sie können Ihre Geschwindigkeit leicht verdoppeln, indem Sie die berechnete Schwerkraft auf BEIDE beteiligten Objekte addieren.

Sie berechnen die Kraft zwischen A & B und später die Kraft zwischen B & A, aber natürlich ist es in beiden Fällen dieselbe Kraft. Sie müssen es nicht zweimal berechnen.

Dazu müssen Sie Ihre Schleifen so umstrukturieren, dass Sie die Schwerkraft zwischen e1 und nur den Objekten NACH e1 in Ihrer Entitätsliste berechnen.

//pseudo code
for(i=0 to num_objects){
    for(j=i+1 to num_objects){ //inner loop starts just after position in outer loop 
        f=calc_force_between_objects(i,j)
        i.forces+=f;
        j.forces+=-f; // same force, opposite direction
    }
}

Wenn Ihr Universum in natürliche Cluster unterteilt ist (z. B. eine Reihe von Sonnensystemen), können Sie jeden Cluster für die Zwecke der Schwerkraftsimulation als einen einzelnen Gravitationskörper behandeln (summieren Sie einfach die Massen der Objekte im Cluster und führen Sie a aus gewichtet (!) mitteln ihre Positionen, um den Schwerpunkt des Clusters zu erhalten). Wenn der Cluster von einem großen Körper dominiert wird, z. B. einer Sonne, verwenden Sie diesen einfach als Schwerpunkt.

Dies funktioniert ziemlich genau für Körper, die den Cluster nicht schließen.

Sie können auch Cluster innerhalb von Clustern haben. zB Jupiter und seine Monde sind ein Cluster innerhalb des Sonnensystems.

Ok, ich werde Ihnen hier eine vereinfachte Antwort geben. Beginnen Sie mit der Erstellung einer räumlichen Struktur wie einem Quadtree. Es gibt viele C # -Dokumente dazu online.

Die Hauptidee ist, Ihre Galaxie in ein Gitter zu teilen. Sie beginnen mit einer großen Zelle und teilen sie in 4 gleichmäßig große Zellen und so weiter. Hier ist ein Artikel über QT in C # , aber bitte versuchen Sie, das Konzept zu verstehen und nicht zu kopieren und einzufügen, da Ihr Problem eine ganz besondere Implementierung erfordert.

Nach dem Lesen des Artikels sollten Sie sich eines Mechanismus bewusst sein, mit dem sich Partikel bei Zellen registrieren können, wenn sie sich bewegen. Wenn sich also Teilchen A von Zelle [1,1] zu Zelle [2,1] bewegt, muss es sich in der ersten Zelle abmelden und sich in der zweiten Zelle registrieren.

Mit dieser Struktur erhalten Sie einen Baum mit unterschiedlicher Granularität. Sie können jetzt eine Detailebene für Ihre Massenpunkte erstellen. Auf der feinsten Ebene (den Blättern des Baumes) hat jedes Teilchen seine eigene Masse und sein eigenes Zentrum. Wenn Sie jetzt eine Stufe höher gehen, haben Sie einen Knoten, der eine Reihe von Blättern (Planeten) enthält. Sie berechnen nun den Massenschwerpunkt und die Masse für alle Planeten zusammen (indem Sie die mittlere Position aller Planeten * berechnen und die Masse addieren ).

Jetzt steigen Sie noch einmal auf und erhalten einen Knoten mit einer Reihe von Unterknoten (die wir gerade berechnet haben). Jetzt machen Sie dasselbe noch einmal und erzeugen einen neuen Massenschwerpunkt und eine neue hinzugefügte Masse. Fahren Sie mit diesem Vorgang fort, bis Sie den Stammknoten erreichen. Sie haben jetzt einen Baum, in dem alle Planeten Einzelblätter sind und jeder Knoten das mittlere Zentrum und die kumulierte Masse aller darunter liegenden Planeten enthält.

In deiner Update-Logik wirst du jetzt nicht mehr gegen jeden einzelnen Planeten prüfen. Sie berechnen die genaue Kraft für Planeten in der Nähe des Objekts (möglicherweise dieselbe Knotenebene). Bei weiter entfernten Planeten treten Sie erst dann in den Baum ein, wenn Sie Blätter erreichen. Stattdessen verwenden Sie die zuvor berechneten Medianwerte, um eine Kraft zu erzeugen und zu approximieren .

Immer wenn ein Planet / Objekt seine Baumzelle ändert , müssen Sie den Baum von dort nach oben neu berechnen , aber es sollte Ihre Berechnungen dennoch um eine große Menge reduzieren.

Versuchen Sie, ein solches System zu implementieren und spielen Sie mit den Parametern. Mit diesen Tools sollten Sie in der Lage sein, ein recht leistungsfähiges System zu erstellen.

Dies ist eine Menge Text, versuchen Sie, Ihren Kopf darum zu wickeln und zögern Sie nicht, für Fragen zurück zu kommentieren :)

PS: Es verwirrt mich, dass Ihre Bewegungsplaneten einen so großen Tropfen erzeugen, da Sie die Schwerkraft auch für statische berechnen (nicht wahr?). Vielleicht gibt es auch ein Problem im Bewegungscode.

PS2: Vielleicht versuchen Sie es zu ändern if (Math.Sqrt(distance) > (e.Value.Texture.Width / 2 + e2.Value.Texture.Width / 2))

in

if (distance > ((e.Value.Texture.Width * e.Value.Texture.Width ) / 2 + (e2.Value.Texture.Width * e2.Value.Texture.Width) / 2)). Dies ist zwar nicht die Ursache Ihres Problems, sollte aber die Geschwindigkeit etwas erhöhen;)

Das Problem ist definitiv die N ^ 2-Reihenfolge der Komplexität. Mein Vorschlag ist, Oktrees und Approximationen zu kombinieren, um so viel Berechnung wie möglich zu vermeiden. Einige Bereiche, in denen eine Annäherung verwendet werden könnte, sind:

• Wenn m / r ^ 2 zu niedrig ist, ignorieren Sie den Beitrag als zu klein.
• Alle Massen in einem ausreichend kleinen, ausreichend weit entfernten Bereich können als einzelne Masse betrachtet werden.

Ich habe noch keinen Algorithmus, aber ein Octree würde es Ihnen ermöglichen, einen ganzen Knoten zu ignorieren, der zu wenig beiträgt, und es würde Ihnen auch ermöglichen, einen ausreichend konzentrierten Knoten als eine einzelne Masse zu behandeln, ohne tiefer zu erforschen. "Konzentriert genug" könnte auf viele Arten bewertet werden, aber eine einfache Formel könnte nur die Fläche des Knotens geteilt durch den Abstand zum Knoten sein.

Diese Antwort ähnelt den Quad / Oct-Baum-Ideen, ist aber nicht ganz dieselbe.

Ich vermute, dass es einen massiven Gewinn gibt, wenn die Kraftvektoren zwischen Körperpaaren anhand ihrer Nähe neu bewertet werden.

Das heißt, jeder Körper muss eine Prioritätsliste der Kräfte führen, die von jedem anderen Körper ausgeübt werden. [Dies ist nicht wirklich so viel Speicherplatz für ein paar hundert Leichen.]

Nachdem Sie die Entfernung berechnet haben, berechnen Sie auch die Relativgeschwindigkeit und bestimmen Sie eine "Gut für" -Zeit für die Kraft. Zum Beispiel ist eine Kraft gut, solange sich ihre Richtung nicht um mehr als 1e-5 Bogenmaß oder ihr relativer Abstand um mehr als 1e-5 ändert.

class Force
    {
        public Vector2 force;
        public Time    validUntil;
        public Entity  otherBody;
    };

UpdateEntfernen Sie dann in Forces die s aus dem Kopf der Prioritätswarteschlange, deren validUntilAblauf abgelaufen ist (weniger als die aktuelle Simulationszeit). Subtrahieren Sie für jedes dieser Elemente die Kraft, die derzeit auf die Entität ausgeübt wird. Berechnen Sie die Kraft mit dem otherBody; füge das wieder der Entität hinzu; Berechnen Sie das validUntilund fügen Sie es erneut ein.

Dies sollte die Häufigkeit, mit der entfernte Objekte ihre Kraft neu berechnen, erheblich reduzieren. In der Tat sollten Sie feststellen, dass zwei entfernte effektiv auf natürliche Weise konstante Kraft aufeinander ausüben.

Ein zweites Problem betrifft Objekte in der Nähe. Verwenden Sie das Äquivalent von s = ut + at^2/2:

Position oldP;
Velocity oldV;
Acceleration a;
Time dt;

Velocity newV = oldV + dt*a;
Position newApprox = oldP + dt * oldV + 0.5*dt*dt*a;

Dies gibt Ihnen ein viel besseres Verhalten als Ihr aktueller Ausdruck, wodurch Sie sich steigern können dt.

Beim Erstellen eines Schwerkraftmodells wende ich gerne verschiedene Tests an.

Am einfachsten ist es zu überprüfen, ob Sie tatsächlich eine Kreisbahn für so etwas wie ein Erde-Sonne-System erhalten.

Anspruchsvoller ist es, Dinge wie den Gesamtimpuls und den Gesamtdrehimpuls zu berechnen und zu überprüfen, ob diese ausreichend konstant bleiben.