Schwerkraftberechnungen optimieren

Ich habe eine Reihe von Objekten unterschiedlicher Größe und Geschwindigkeit, die sich gegenseitig anziehen. Bei jedem Update muss ich jedes Objekt überprüfen und die Kräfte aufgrund der Schwerkraft jedes anderen Objekts addieren. Es lässt sich nicht sehr gut skalieren, ist einer der beiden großen Engpässe, die ich in meinem Spiel festgestellt habe, und ich bin nicht sicher, was ich tun soll, um die Leistung zu verbessern.

Es fühlt sich an, als könnte ich die Leistung verbessern. Zu jedem Zeitpunkt haben wahrscheinlich 99% der Objekte im System nur einen vernachlässigbaren Einfluss auf ein Objekt. Ich kann die Objekte natürlich nicht nach Masse sortieren und berücksichtige nur die 10 größten Objekte oder ähnliches, da die Kraft mit der Entfernung mehr variiert als mit der Masse (die Gleichung ist in der Richtung von force = mass1 * mass2 / distance^2). Ich denke, eine gute Annäherung wäre, die größten Objekte und die nächsten Objekte zu betrachten und dabei die Hunderte winziger Gesteinsbrocken auf der anderen Seite der Welt zu ignorieren, die möglicherweise nichts bewirken können - aber um herauszufinden, welche Objekte es sind Am nächsten muss ich alle Objekte durchlaufen , und ihre Positionen ändern sich ständigEs ist also nicht so, dass ich es nur einmal machen kann.

Momentan mache ich so etwas:

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);
}

(Beachten Sie, dass ich viel Code entfernt habe - zum Beispiel bei den Kollisionstests. Ich durchlaufe die Objekte nicht ein zweites Mal, um Kollisionen zu erkennen.)

Ich iteriere also nicht immer über die gesamte Liste - ich mache das nur für das erste Objekt, und jedes Mal, wenn das Objekt die Kraft findet, die es auf ein anderes Objekt ausübt, fühlt dieses andere Objekt die gleiche Kraft, so dass es nur beide aktualisiert sie - und dann muss das erste Objekt für den Rest des Updates nicht erneut berücksichtigt werden.

Für die Funktionen Gravity.ForceUnderGravity(...)und Motion.Velocity(...)usw. wird nur ein Teil der in der Vektormathematik integrierten XNA verwendet.

Wenn zwei Objekte kollidieren, entstehen massenlose Trümmer. Es wird in einer separaten Liste aufbewahrt und die massiven Objekte durchlaufen die Trümmer nicht als Teil ihrer Geschwindigkeitsberechnung, sondern jedes Trümmerstück muss die massiven Partikel durchlaufen.

Dies muss nicht an unglaubliche Grenzen stoßen. Die Welt ist nicht unbegrenzt, sie enthält eine Grenze, die Objekte zerstört, die sie überqueren. Ich möchte in der Lage sein, mit etwa tausend Objekten umzugehen. Derzeit fängt das Spiel an, an 200 zu ersticken.

Irgendwelche Gedanken, wie ich das verbessern könnte? Eine Heuristik, mit der ich die Schleifenlänge von Hunderten auf wenige reduzieren kann? Code, den ich seltener als jedes Update ausführen kann? Sollte ich es einfach multithreaden, bis es schnell genug ist, um eine Welt von annehmbarer Größe zu ermöglichen? Sollte ich versuchen, die Geschwindigkeitsberechnungen auf die GPU zu übertragen? Wenn ja, wie würde ich das errichten? Kann ich statische, gemeinsam genutzte Daten auf der GPU behalten? Kann ich HLSL-Funktionen auf der GPU erstellen und sie willkürlich aufrufen (mit XNA) oder müssen sie Teil des Zeichenprozesses sein?

Das klingt nach einem Job für ein Grid. Teilen Sie Ihren Spielraum in ein Raster und führen Sie für jede Rasterzelle eine Liste der Objekte auf, die sich aktuell darin befinden. Wenn sich Objekte über eine Zellgrenze bewegen, aktualisieren Sie die Liste, in der sie sich befinden. Wenn Sie ein Objekt aktualisieren und nach anderen Objekten suchen, mit denen Sie interagieren möchten, können Sie nur die aktuelle Gitterzelle und einige benachbarte Zellen anzeigen. Sie können die Größe des Rasters optimieren, um die bestmögliche Leistung zu erzielen (Ausgleich zwischen den Kosten für die Aktualisierung der Rasterzellen - die höher sind, wenn die Rasterzellen zu klein sind - und den Kosten für die Suche, die höher sind, wenn die Rasterzellen ebenfalls vorhanden sind) groß).

Dies wird natürlich dazu führen, dass Objekte, die weiter voneinander entfernt sind als ein paar Gitterzellen, überhaupt nicht miteinander interagieren. Dies ist wahrscheinlich ein Problem, da eine große Ansammlung von Masse (entweder ein großes Objekt oder eine Ansammlung vieler kleiner Objekte) dies tun sollte Wie Sie bereits sagten, haben Sie einen größeren Einflussbereich.

Sie können beispielsweise die Gesamtmasse in jeder Gitterzelle verfolgen und die gesamte Zelle für weiter entfernte Interaktionen als ein einziges Objekt behandeln. Das heißt: Wenn Sie die Kraft auf ein Objekt berechnen, berechnen Sie die direkte Objekt-zu-Objekt-Beschleunigung für die Objekte in einigen nahe gelegenen Gitterzellen und addieren Sie dann für jede weiter entfernte Gitterzelle (oder vielleicht nur diejenigen mit einer nicht zu vernachlässigenden Masse). Mit einer Beschleunigung von Zelle zu Zelle meine ich einen Vektor, der aus den Gesamtmassen der beiden Zellen und dem Abstand zwischen ihren Zentren berechnet wird. Das sollte eine vernünftige Annäherung an die summierte Schwerkraft aller Objekte in dieser Gitterzelle ergeben, aber viel billiger.

Wenn die Spielwelt sehr groß ist, können Sie sogar ein hierarchisches Gitter wie einen Quadtree (2D) oder einen Octree (3D) verwenden und ähnliche Prinzipien anwenden. Ferninteraktionen würden höheren Hierarchieebenen entsprechen.

Der Barnes-Hut-Algorithmus ist der richtige Weg dazu. Es wurde in Supercomputersimulationen verwendet, um Ihr genaues Problem zu lösen. Es ist nicht zu schwer zu programmieren und es ist sehr effizient. Ich habe vor nicht allzu langer Zeit ein Java-Applet geschrieben, um dieses Problem zu lösen.

Besuchen Sie http://mathandcode.com/programs/javagrav/ und drücken Sie "start" und "show quadtree".

Auf der Registerkarte "Optionen" können Sie sehen, dass die Partikelanzahl bis zu 200.000 betragen kann. Auf meinem Computer ist die Berechnung in ca. 2 Sekunden abgeschlossen (das Zeichnen von 200.000 Punkten dauert ca. 1 Sekunde, die Berechnung wird jedoch in einem separaten Thread ausgeführt).

So funktioniert mein Applet:

1. Erstellen Sie eine Liste von zufälligen Partikeln mit zufälligen Massen, Positionen und Startgeschwindigkeiten.
2. Konstruieren Sie aus diesen Partikeln einen Quadtree. Jeder Quadtree-Knoten enthält den Massenmittelpunkt jedes Unterknotens. Grundsätzlich haben Sie für jeden Knoten drei Werte: massx, massy und mass. Jedes Mal, wenn Sie einem bestimmten Knoten ein Partikel hinzufügen, erhöhen Sie Massx und Massy um Particle.x * Particle.Mass bzw. Particle.y * Particle.Mass. Die Position (massx / mass, massy / mass) wird zum Massenmittelpunkt des Knotens.
3. Zu jedem Teilchen berechnet die Kräfte (vollständig beschrieben hier ). Beginnen Sie dazu am obersten Knoten und durchlaufen Sie jeden Unterknoten des Quadtrees, bis der angegebene Unterknoten klein genug ist. Sobald Sie aufhören zu rekursieren, können Sie den Abstand zwischen dem Partikel und dem Massenmittelpunkt des Knotens berechnen und anschließend die Kraft anhand der Masse des Knotens und der Masse des Partikels berechnen.

Ihr Spiel sollte problemlos in der Lage sein, mit tausend sich gegenseitig anziehenden Objekten umzugehen. Wenn jedes Objekt "dumm" ist (wie die nackten Knochenpartikel in meinem Applet), sollten Sie in der Lage sein, 8000 bis 9000 Partikel zu erhalten, möglicherweise mehr. Und das setzt Single-Threading voraus. Mit Multithread- oder Parallel-Computing-Anwendungen können Sie viel mehr Partikel als in Echtzeit aktualisieren.

Siehe auch: http://www.youtube.com/watch?v=XAlzniN6L94 für ein umfangreiches Rendering

Nathan Reed hat eine ausgezeichnete Antwort. Die Kurzversion besteht darin, eine Breitphasentechnik zu verwenden, die zur Topologie Ihrer Simulation passt, und die Schwerkraftberechnungen nur für Objektpaare auszuführen, die sich gegenseitig spürbar beeinflussen. Es ist wirklich nichts anderes als das, was Sie für die Broadphase der regulären Kollisionserkennung tun würden.

Davon ausgehend besteht eine andere Möglichkeit darin, Objekte nur zeitweise zu aktualisieren. Grundsätzlich aktualisiert jeder Zeitschritt (Frame) nur einen Bruchteil aller Objekte und lässt die Geschwindigkeit (oder Beschleunigung, je nach Ihren Vorlieben) für die anderen Objekte gleich. Es ist unwahrscheinlich, dass der Benutzer eine Verzögerung der Aktualisierungen bemerkt, solange die Intervalle nicht zu lang sind. Dies gibt Ihnen eine lineare Beschleunigung des Algorithmus. Sehen Sie sich also auf jeden Fall die von Nathan vorgeschlagenen Breitphasentechniken an, die bei einer Vielzahl von Objekten zu einer deutlich höheren Beschleunigung führen können. Obwohl es nicht im geringsten das gleiche Modell hat, ist es so, als hätte man "Gravitationswellen". :)

Außerdem können Sie in einem Durchgang ein Gravitationsfeld erzeugen und die Objekte in einem zweiten Durchgang aktualisieren. Im ersten Durchgang füllen Sie im Grunde genommen ein Gitter (oder eine komplexere räumliche Datenstruktur) mit den Gravitationseinflüssen jedes Objekts. Das Ergebnis ist jetzt ein Gravitationsfeld, das Sie sogar rendern können (es sieht ziemlich cool aus), um zu sehen, welche Beschleunigung auf ein Objekt an einer bestimmten Stelle angewendet wird. Dann iterieren Sie über die Objekte und wenden einfach die Effekte des Schwerefelds auf dieses Objekt an. Noch cooler ist, dass Sie dies auf einer GPU tun können, indem Sie die Objekte als Kreise / Kugeln in eine Textur rendern und dann die Textur lesen (oder einen anderen Transformations-Feedback-Durchgang auf der GPU verwenden), um die Geschwindigkeiten des Objekts zu ändern.

Ich würde empfehlen, einen Quad Tree zu verwenden. Mit ihnen können Sie schnell und effizient alle Objekte in einem beliebigen rechteckigen Bereich nachschlagen. Hier ist der Wiki-Artikel dazu: http://en.wikipedia.org/wiki/Quadtree

Und ein schamloser Link zu meinem eigenen XNA Quad Tree-Projekt auf SourceForge: http://sourceforge.net/projects/quadtree/

Ich würde auch eine Liste aller großen Objekte führen, damit sie unabhängig von der Entfernung mit allem interagieren können.

Nur ein bisschen (möglicherweise naiver) Input. Ich programmiere keine Spiele, aber ich habe das Gefühl, dass Ihr grundlegender Engpass die Berechnung der Schwerkraft aufgrund der Schwerkraft ist. Anstatt über jedes Objekt X zu iterieren und dann den Gravitationseffekt von jedem Objekt Y zu finden und zu addieren, können Sie jedes Paar X, Y nehmen und die Kraft zwischen ihnen finden. Das sollte die Anzahl der Schwerkraftberechnungen von O (n ^ 2) abschneiden. Dann werden Sie viel addieren (O (n ^ 2)), aber dies ist normalerweise weniger teuer.

Außerdem können Sie an dieser Stelle Regeln implementieren, z. B. "Wenn die Gravitationskraft geringer als \ epsilon ist, weil diese Körper zu klein sind, setzen Sie die Kraft auf Null". Es kann vorteilhaft sein, diese Struktur auch für andere Zwecke (einschließlich Kollisionserkennung) zu haben.

Als ich die Antwort von SeanMiddleditch erweiterte, dachte ich, ich könnte ein bisschen Licht in die Idee des Gravitationsfeldes bringen (Ironie?).

Stellen Sie sich das nicht als Textur vor, sondern als diskretes Feld von Werten, die geändert werden können (sozusagen ein zweidimensionales Array). und die nachfolgende Genauigkeit der Simulation könnte die Auflösung dieses Feldes sein.

Wenn Sie ein Objekt in das Feld einführen, kann dessen Gravitationspotential für alle Umgebungswerte berechnet werden. eine Gravitations wodurch die Schaffung Enke in dem Feld.

Aber wie viele dieser Punkte sollten Sie berechnen, bevor sie mehr oder weniger effektiv sind als zuvor? Wahrscheinlich nicht viele, selbst 32x32 ist ein umfangreiches Feld, das für jedes Objekt durchlaufen werden muss. Brechen Sie daher den gesamten Prozess in mehrere Durchgänge auf. jeweils mit unterschiedlicher Auflösung (oder Genauigkeit).

Das heißt, der erste Durchgang kann die in einem 4 × 4-Gitter dargestellte Objektgravitation berechnen, wobei jeder Zellenwert eine 2D-Koordinate im Raum darstellt. Geben einer O (n * 4 * 4) -Zwischensumme Komplexität.

Der zweite Durchgang kann mit einem Gravitationsfeld mit einer Auflösung von 64 × 64 genauer sein, wobei jeder Zellenwert eine 2D-Koordinate im Raum darstellt. Da die Komplexität jedoch sehr hoch ist, können Sie den Radius der betroffenen umgebenden Zellen einschränken (möglicherweise werden nur die umgebenden 5 x 5-Zellen aktualisiert).

Ein zusätzlicher dritter Durchgang könnte für hochgenaue Berechnungen mit einer Auflösung von 1024 x 1024 verwendet werden. Denken Sie daran, dass Sie zu keinem Zeitpunkt separate Berechnungen im Format 1024 x 1024 ausführen, sondern nur Teile dieses Felds (möglicherweise 6 x 6 Unterabschnitte) bearbeiten.

Auf diese Weise ist Ihre Gesamtkomplexität für das Update O (n * (4 * 4 + 5 * 5 + 6 * 6)).

Um dann die Geschwindigkeitsänderungen für jedes Ihrer Objekte zu berechnen, ordnen Sie für jedes Gravitationsfeld (4x4, 64x64, 1024x1024) einfach die Position der Punktmassen einer Gitterzelle zu und wenden diesen Vektor des gesamten Gravitationspotentials der Gitterzellen auf einen neuen Vektor an. Wiederholen Sie für jede "Schicht" oder "Pass"; dann addiere sie zusammen. Dies sollte einen guten resultierenden Gravitationskraftvektor ergeben.

Daher ist die Gesamtkomplexität: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). Was wirklich zählt (für die Komplexität), ist, wie viele umgebende Zellen Sie aktualisieren, wenn Sie das Gravitationspotential in den Durchgängen berechnen, nicht die Gesamtauflösung der Gravitationsfelder.

Der Grund für Felder mit niedriger Auflösung (erste Durchgänge) ist offensichtlich, das Universum als Ganzes zu erfassen und sicherzustellen, dass abgelegene Massen trotz der Entfernung zu dichteren Gebieten hingezogen werden. Verwenden Sie dann Felder mit höherer Auflösung als separate Ebenen, um die Genauigkeit für benachbarte Planeten zu erhöhen.

Ich hoffe das hat Sinn ergeben.

Wie wäre es mit einem anderen Ansatz:

Weisen Sie Objekten anhand ihrer Masse einen Einflussbereich zu - sie sind einfach zu klein, um einen messbaren Effekt außerhalb dieses Bereichs zu erzielen.

Teilen Sie nun Ihre Welt in ein Raster auf und stellen Sie jedes Objekt in eine Liste aller Zellen, auf die es Einfluss hat.

Führen Sie Ihre Schwerkraftberechnungen nur für Objekte in der Liste durch, die an die Zelle angehängt ist, in der sich ein Objekt befindet.

Sie müssen die Listen nur aktualisieren, wenn ein Objekt in eine neue Rasterzelle verschoben wird.

Je kleiner die Rasterzellen sind, desto weniger Berechnungen werden pro Aktualisierung durchgeführt, aber desto mehr Arbeit wird für die Aktualisierung von Listen aufgewendet.