Multithreading-2D-Schwerkraftberechnungen

24

Ich baue ein Weltraum-Erkundungsspiel und arbeite gerade an der Schwerkraft (In C # mit XNA).

Die Schwerkraft muss noch optimiert werden, aber bevor ich das tun kann, muss ich einige Leistungsprobleme mit meinen physikalischen Berechnungen beheben.

Hierbei werden 100 Objekte verwendet. Normalerweise werden 1000 davon ohne physische Berechnungen mit mehr als 300 FPS (was meine Obergrenze für FPS ist) gerendert. Bei mehr als 10 Objekten wird jedoch das Spiel (und der einzelne Thread, auf dem es ausgeführt wird) auf die Obergrenze gebracht Knie beim Berechnen der Physik.

Ich habe meine Thread-Nutzung überprüft und der erste Thread hat sich von der ganzen Arbeit selbst erledigt, also dachte ich, ich müsste nur die Physikberechnung für einen anderen Thread durchführen. Wenn ich jedoch versuche, die Update-Methode der Gravity.cs-Klasse in einem anderen Thread auszuführen, ist das Spiel immer noch auf 2 FPS beschränkt, auch wenn die Update-Methode von Gravity nichts enthält.

Schwerkraft.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;
        }

    }

Ja ich weiß. Es ist eine verschachtelte foreach-Schleife, aber ich weiß nicht, wie ich die Gravitationsberechnung ausführen soll, und das scheint zu funktionieren, es ist nur so intensiv, dass es einen eigenen Thread benötigt. (Auch wenn jemand eine super effiziente Methode kennt, um diese Berechnungen durchzuführen, möchte ich trotzdem wissen, wie ich es stattdessen auf mehreren Threads machen KÖNNTE.)

EntityEngine.cs (verwaltet eine Instanz von 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 wird in Game1.cs erstellt und die Update () -Methode in Game1.cs aufgerufen.

Ich benötige meine Physikberechnung in Gravity.cs, um jedes Mal, wenn das Spiel aktualisiert wird, in einem separaten Thread ausgeführt zu werden, damit die Berechnung das Spiel nicht auf schrecklich niedrige (0-2) FPS verlangsamt.

Wie würde ich vorgehen, damit dieses Einfädeln funktioniert? (Vorschläge für ein verbessertes Planetary Gravity-System sind willkommen, wenn jemand sie hat.)

Ich bin auch nicht auf der Suche nach einer Lektion, warum ich das Einfädeln nicht verwenden sollte oder die Gefahren einer falschen Verwendung. Ich suche nach einer klaren Antwort, wie das geht. Ich habe bereits eine Stunde damit verbracht, genau diese Frage mit kleinen Ergebnissen zu googeln, die ich verstand oder die hilfreich waren. Ich möchte nicht unhöflich abschneiden, aber es scheint für einen Programmierer immer schwierig zu sein, eine eindeutige und aussagekräftige Antwort zu erhalten. Normalerweise bekomme ich eine Antwort, die so komplex ist, dass ich mein Problem leicht lösen kann, wenn ich es verstehe, oder Jemand sagt, warum ich nicht tun sollte, was ich tun möchte, und bietet keine Alternativen an (die hilfreich sind).

Danke für die Hilfe!

EDIT : Nachdem ich die Antworten gelesen habe, sehe ich, dass es euch wirklich interessiert und ihr nicht nur versucht, eine Antwort herauszuspucken, die funktionieren könnte. Ich wollte zwei Fliegen mit einer Klappe schlagen (Verbesserung der Leistung und Erlernen einiger Grundlagen des Multlthreading), aber es scheint, dass das meiste Problem in meinen Berechnungen liegt und dass das Einfädeln mühsamer ist, als es sich für Leistungssteigerungen lohnt. Ich danke Ihnen allen, ich werde Ihre Antworten noch einmal durchlesen und Ihre Lösungen ausprobieren, wenn ich mit der Schule fertig bin. Nochmals vielen Dank!

Postbote
quelle
Was macht es jetzt (funktioniert es)? Übrigens würde ich es so schnell wie möglich im Spielzyklus starten - z. B. bevor die Entitäten aktualisiert werden.
ThorinII
2
Die Trig-Aufrufe im Inneren Ihrer verschachtelten Schleifen sind wahrscheinlich der größte Hit. Wenn Sie einen Weg finden, diese zu beseitigen, wird kdies das O(n^2)Problem erheblich verringern .
RBarryYoung
1
Tatsächlich sind die Trigger-Aufrufe völlig unnötig : Sie berechnen zuerst einen Winkel aus einem Vektor und generieren dann mit diesem einen weiteren Vektor, der in die angegebene Richtung zeigt. Dann normalisierst du diesen Vektor, aber da sin² + cos² ≡ 1ist er sowieso schon normalisiert! Sie hätten einfach den ursprünglichen Vektor verwenden können, der die beiden Objekte verbindet, an denen Sie interessiert sind, und diesen normalisiert. Es werden keinerlei Trigger-Anrufe benötigt.
linksum den
Ist XNA nicht veraltet?
JCORA
@yannbane Diese Frage fügt der Diskussion nichts Hilfreiches hinzu. Und nein, der Status von XNA entspricht keiner Definition von veraltet.
Seth Battin

Antworten:

36

Was Sie hier haben, ist ein klassischer O (n²) -Algorithmus. Die Hauptursache Ihres Problems hat nichts mit Threading zu tun und alles damit, dass Ihr Algorithmus eine hohe Komplexität aufweist.

Wenn Sie noch nie auf die "Big O" -Notation gestoßen sind, bedeutet dies im Grunde die Anzahl der Operationen, die erforderlich sind, um mit n Elementen zu arbeiten (dies ist die stark vereinfachte Erklärung). Ihre 100 Elemente führen den inneren Teil Ihrer Schleife 10000 Mal aus .

In der Spieleentwicklung möchten Sie im Allgemeinen O (n²) -Algorithmen vermeiden , es sei denn, Sie haben eine kleine (und vorzugsweise feste oder begrenzte) Datenmenge und einen sehr schnellen Algorithmus.

Wenn sich jede Entität auf jede andere Entität auswirken würde, wäre zwangsläufig ein O (n²) -Algorithmus erforderlich. Es sieht jedoch so aus, als würden (aufgrund von if (distance < ...)) nur wenige Entitäten tatsächlich interagieren. Sie könnten also die Anzahl der Operationen erheblich reduzieren, indem Sie die so genannte räumliche Partitionierung verwenden .

Da dies ein ziemlich detailliertes und etwas spielspezifisches Thema ist, empfehle ich Ihnen, eine neue Frage zu stellen, um weitere Einzelheiten zu erfahren. Lass uns weitermachen...


Eines der größten Leistungsprobleme bei Ihrem Code ist recht einfach. Das ist verdammt langsam :

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

Sie führen bei jeder Iteration (mehrmals in Ihren anderen Schleifen) eine Wörterbuchsuche nach Zeichenfolge für ein Objekt durch, das Sie bereits haben!

Sie könnten dies tun:

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

Oder Sie könnten dies tun: (Mir persönlich gefällt das besser, beide sollten ungefähr gleich schnell sein.)

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

Eine Wörterbuchsuche nach Zeichenfolge ist ziemlich langsam. Direktes Iterieren ist erheblich schneller.

Obwohl, wie oft Sie tatsächlich benötigen Elemente nach Namen suchen? Verglichen damit, wie oft Sie alle durchlaufen müssen? Wenn Sie nur selten nach Namen suchen, ziehen Sie in Betracht, Ihre Entitäten in a zu speichern List(geben Sie ihnen ein NameMitglied).

Der Code, den Sie tatsächlich dort haben, ist relativ trivial. Ich habe es nicht profiliert, aber ich wette, die meiste Ausführungszeit wird für die wiederholten Nachschlagevorgänge im Wörterbuch verwendet . Ihr Code ist möglicherweise "schnell genug", wenn Sie dieses Problem beheben.

BEARBEITEN: Das nächstgrößere Problem besteht wahrscheinlich darin, Atan2es mit Sinund aufzurufen und dann sofort wieder in einen Vektor umzuwandeln Cos! Verwenden Sie einfach den Vektor direkt.


Lassen Sie uns abschließend das Threading und die Hauptprobleme in Ihrem Code ansprechen:

Zuerst und am offensichtlichsten: Erstelle nicht bei jedem Frame einen neuen Thread! Thread-Objekte sind ziemlich "schwer". Die einfachste Lösung hierfür wäre, ThreadPoolstattdessen einfach zu verwenden .

Natürlich ist es nicht so einfach. Fahren wir mit Problem Nummer zwei fort: Berühren Sie nicht Daten auf zwei Threads gleichzeitig! (Ohne Hinzufügen der entsprechenden Thread-Sicherheitsinfrastruktur.)

Sie stampfen hier im Grunde auf die schrecklichste Weise in der Erinnerung herum . Hier gibt es keine Fadensicherheit. Jeder der " gravity.Update" mehreren Threads, die Sie starten, kann Daten überschreiben, die zu unerwarteten Zeiten in einem anderen Thread verwendet werden. Ihr Hauptthema wird in der Zwischenzeit zweifellos auch alle diese Datenstrukturen berühren. Es würde mich nicht wundern, wenn dieser Code schwer reproduzierbare Speicherzugriffsverletzungen hervorrufen würde.

Es ist schwierig, so etwas sicher zu machen, und es kann einen erheblichen Mehraufwand für die Leistung bedeuten, sodass sich der Aufwand oft nicht lohnt.


Aber, da Sie (nicht so) nett gefragt haben, wie es überhaupt geht, lassen Sie uns darüber sprechen ...

Normalerweise würde ich empfehlen, zunächst etwas Einfaches zu üben, bei dem es sich im Grunde genommen um "Feuer und Vergessen" handelt. Audio abspielen, etwas auf die Festplatte schreiben usw. Es wird kompliziert, wenn Sie das Ergebnis in den Haupt-Thread zurückspeisen müssen.

Grundsätzlich gibt es drei Ansätze für Ihr Problem:

1) Setzen Sie Sperren um alle Daten, die Sie über Threads hinweg verwenden. In C # wird dies mit der lockAnweisung ziemlich einfach gemacht .

Im Allgemeinen erstellen (und behalten!) Sie ein new objectspezielles Sperren, um bestimmte Datenmengen zu schützen (dies ist aus Sicherheitsgründen im Allgemeinen nur beim Schreiben öffentlicher APIs der Fall - aber trotzdem mit gutem Stil). Sie müssen Ihr Sperrobjekt dann überall dort sperren, wo Sie auf die Daten zugreifen, die es schützt!

Wenn etwas von einem Thread "gesperrt" wird, weil es gerade verwendet wird, und ein anderer Thread versucht, darauf zuzugreifen, muss dieser zweite Thread natürlich warten, bis der erste Thread fertig ist. Wenn Sie also nicht sorgfältig Aufgaben auswählen, die parallel ausgeführt werden können, erhalten Sie im Grunde eine Single-Thread-Leistung (oder eine schlechtere Leistung).

In Ihrem Fall hat dies keinen Sinn, es sei denn, Sie können Ihr Spiel so entwickeln, dass ein anderer Code parallel ausgeführt wird, der Ihre Entitätssammlung nicht berührt.

2) Kopieren Sie die Daten in den Thread, lassen Sie sie verarbeiten und nehmen Sie das Ergebnis anschließend wieder heraus.

Wie Sie dies umsetzen, hängt davon ab, was Sie tun. Dies ist jedoch offensichtlich mit einem potenziell teuren Kopiervorgang (oder zwei) verbunden, der in vielen Fällen langsamer ist als das einfache Ausführen von Single-Thread-Vorgängen.

Und natürlich müssen Sie noch etwas anderes im Hintergrund erledigen, sonst wartet Ihr Haupt-Thread nur darauf, dass Ihr anderer Thread fertig ist, damit er die Daten zurückkopieren kann!

3) Verwenden Sie thread-sichere Datenstrukturen.

Diese sind etwas langsamer als ihre Gegenstücke mit einem Gewinde und oft schwerer zu bedienen als einfache Verriegelungen. Sie können immer noch Probleme beim Sperren aufweisen (Leistung auf einen einzelnen Thread reduzieren), es sei denn, Sie verwenden sie vorsichtig.


Da es sich um eine rahmenbasierte Simulation handelt, muss der Hauptthread darauf warten, dass andere Threads ihre Ergebnisse liefern, damit der Rahmen gerendert und die Simulation fortgesetzt werden kann. Eine vollständige Erklärung ist wirklich zu lang, um sie hier einzufügen, aber im Grunde möchten Sie lernen, wie man Monitor.Waitund verwendet Monitor.Pulse. Hier ist ein Artikel, um Sie anzufangen .


Ich weiß, dass ich für keinen dieser Ansätze spezifische Implementierungsdetails (mit Ausnahme des letzten Bits) oder Code angegeben habe. Zuallererst gäbe es viel zu besprechen. Und zweitens ist keine davon für Ihren Code geeignet - Sie müssen sich Ihrer gesamten Architektur mit dem Ziel nähern, Threading hinzuzufügen.

Durch das Threading wird der Code, den Sie dort haben, nicht schneller - Sie können nur gleichzeitig etwas anderes tun!

Andrew Russell
quelle
8
+10 wenn ich könnte. Vielleicht können Sie den letzten Satz einleitend nach oben verschieben, da er das Kernproblem hier zusammenfasst. Das Ausführen von Code in einem anderen Thread beschleunigt das Rendern nicht auf magische Weise, wenn Sie gleichzeitig nichts anderes zu tun haben. Und der Renderer wartet wahrscheinlich darauf, dass der Thread beendet wird, aber wenn dies nicht der Fall ist (und woher weiß er das?), Wird ein inkonsistenter Spielstatus gezeichnet, bei dem einige Entitätsphysik noch aktualisiert werden müssen.
LearnCocos2D
Ich bin fest davon überzeugt, dass das Einfädeln nicht das ist, was ich brauche. Vielen Dank für die ausführlichen und sachkundigen Informationen! In Bezug auf die Leistungsverbesserungen habe ich die von Ihnen (und anderen) vorgeschlagenen Änderungen vorgenommen, aber ich erhalte immer noch eine schlechte Leistung, wenn ich mit> 60 Objekten arbeite. Ich denke, es wäre das Beste für mich, eine weitere Frage zu stellen, die sich mehr auf die Effizienz der N-Body-Simulation konzentriert. Dafür bekommst du meine Antwort. Vielen Dank!
Postbote
1
Gern geschehen, froh, dass es geholfen hat :) Wenn Sie Ihre neue Frage posten, fügen Sie bitte hier einen Link ein, damit ich und alle anderen, die mitmachen, ihn sehen können.
Andrew Russell
@Postman Obwohl ich der Antwort im Allgemeinen zustimme, vermisse ich völlig die Tatsache, dass dies im Grunde der PERFECT-Algorithmus ist, um das Threading zu nutzen. Es gibt einen Grund, warum sie dies auf der GPU tun, und es ist ein trivial paralleler Algorithmus, wenn Sie die Schreibvorgänge in einen zweiten Schritt verschieben. Sperren, Kopieren oder Thread-Sichern von Datenstrukturen ist nicht erforderlich. Eine einfache Parallel.ForEach und es ist ohne Probleme erledigt.
Chewy Gumball
@ChewyGumball Ein sehr gültiger Punkt! Und während Postman seinen Algorithmus zweiphasig machen müsste, sollte er dennoch zweiphasig sein. Es sollte jedoch darauf hingewiesen werden, dass dies Parallelnicht ohne Overhead möglich ist. Daher ist es auf jeden Fall ein Profil zu erstellen - insbesondere für solche kleinen Datenmengen und (was sollte es sein) einen relativ schnellen Code. Und natürlich ist es in diesem Fall immer noch besser, die Komplexität des Algorithmus zu reduzieren, als einfach nur Parallelität zu erzeugen.
Andrew Russell
22

Ok, auf den ersten Blick gibt es einige Dinge, die Sie ausprobieren sollten. Zuerst sollten Sie versuchen, Ihre Kollisionsprüfungen zu reduzieren. Sie können dies tun, indem Sie eine Art räumliche Struktur wie einen Quadtree verwenden . Auf diese Weise können Sie die Anzahl der zweiten foreach-Elemente verringern, da Sie nur die ersten abfragen.

In Bezug auf das Threading: Versuchen Sie nicht, bei jedem Update einen Thread zu erstellen. Dieser Overhead verlangsamt Ihre Geschwindigkeit vielleicht mehr als er die Dinge beschleunigt. Versuchen Sie stattdessen, einen einzelnen Kollisionsthread zu erstellen, und lassen Sie ihn die Arbeit für Sie erledigen. Ich habe keinen konkreten Copy-Paste-This-Code- Ansatz, aber es gibt Artikel über Thread-Synchronisierung und Background Worker für C #.

Ein weiterer Punkt ist, dass Sie in der foreach-Schleife nichts tun müssen, entityEngine.Entities[e.Key].Textureweil Sie bereits auf das Diktat in Ihrem foreach-Header zugegriffen haben. Stattdessen kannst du einfach schreiben e.Texture. Ich weiß nicht so recht, wie sich das auswirkt, wollte dich nur wissen lassen;)

Eine letzte Sache: Im Moment überprüfen Sie jede Entität doppelt, da sie in der ersten UND der zweiten foreach-Schleife abgefragt wird.

Beispiel mit 2 Entitäten A und 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

Obwohl dies ein möglicher Ansatz ist, können Sie A und B möglicherweise in einer Runde handhaben und die Hälfte Ihrer Kollisionsprüfungen überspringen

Hoffe das bringt dich zum Laufen =)

PS: Auch wenn Sie sagten, dass Sie es nicht hören möchten: Versuchen Sie, die Kollisionserkennung im selben Thread zu belassen und sie nur ausreichend zu beschleunigen. Threading scheint eine gute Idee zu sein, aber damit einher geht die Notwendigkeit, wie zum Teufel zu synchronisieren. Wenn Sie die Kollisionsprüfung langsamer als Ihr Update durchführen (Grund für das Einfädeln), erhalten Sie Störungen und Fehler, da die Kollision ausgelöst wird, nachdem sich Schiffe bereits bewegt haben und umgekehrt. Ich möchte Sie nicht entmutigen, dies ist nur eine persönliche Erfahrung.

EDIT1: Links mit QuadTree Tutorial (Java): http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

floAr
quelle
10
Das Schöne an der Verwendung von Quad / Octrees für die Gravitationssimulation ist, dass Sie nicht nur entfernte Partikel ignorieren, sondern die Gesamtmasse und den Massenmittelpunkt aller Partikel in jedem Ast Ihres Baumes speichern und daraus den durchschnittlichen Gravitationseffekt berechnen können aller Teilchen in diesem Zweig auf andere, entfernte Teilchen. Dies ist als Barnes-Hut-Algorithmus bekannt und wird von den Profis verwendet .
Ilmari Karonen
10

Ehrlich gesagt, das erste , was Sie tun sollten , ist , Umschalten auf einen besseren Algorithmus.

Durch die Parallelisierung Ihrer Simulation kann sie selbst im besten Fall nur um den Faktor beschleunigt werden, der der Anzahl der CPUs × Kerne pro CPU × Threads pro Kern entspricht, die auf Ihrem System verfügbar sind - dh zwischen 4 und 16 für einen modernen PC. (Wenn Sie Ihren Code auf die GPU verschieben, können Sie viel beeindruckendere Parallelisierungsfaktoren erzielen, was zu einer höheren Entwicklungskomplexität und einer geringeren Berechnungsgeschwindigkeit pro Thread führt.) Mit einem O (n²) -Algorithmus wie Ihrem Beispielcode können Sie dies Verwenden Sie 2 bis 4 Mal so viele Partikel wie Sie derzeit haben.

Umgekehrt könnte die Umstellung auf einen effizienteren Algorithmus Ihre Simulation leicht beschleunigen, beispielsweise um einen Faktor von 100 bis 10000 (Zahlen rein geschätzt). Die zeitliche Komplexität guter n-Körpersimulationsalgorithmen unter Verwendung einer räumlichen Unterteilung skaliert ungefähr auf O (n log n), was "fast linear" ist, so dass Sie fast den gleichen Faktor für die Erhöhung der Anzahl der Partikel erwarten können, die Sie handhaben können. Auch würde, dass nach wie vor nur einen Thread mit, so gäbe es noch sein Zimmer für Parallelisierung obendrein .

Wie die anderen Antworten bereits angemerkt haben, besteht der allgemeine Trick zur effizienten Simulation einer großen Anzahl wechselwirkender Partikel darin, sie in einem Quadtree (in 2D) oder einem Octree (in 3D) zu organisieren. Insbesondere für die Simulation der Schwerkraft möchten Sie als Basisalgorithmus den Barnes-Hut-Simulationsalgorithmus verwenden , in dem Sie die Gesamtmasse (und den Massenmittelpunkt) aller in jeder Zelle Ihres Quadrates / Oktrates und enthaltenen Partikel speichern Verwenden Sie dies, um den durchschnittlichen Gravitationseffekt der Partikel in dieser Zelle auf andere, entfernte Partikel zu approximieren.

Sie können viele Beschreibungen und Anleitungen auf dem Barnes-Hut - Algorithmus finden Googeln für sie, aber hier ist ein schönes und einfaches zum Einstieg , während hier eine Beschreibung einer erweiterten Implementierung für GPU - Simulation von Galaxienkollisionen verwendet.

Ilmari Karonen
quelle
6

Eine weitere Optimierungsantwort, die nichts mit Threads zu tun hat. Das tut mir leid.

Sie berechnen die Distanz () jedes Paares. Dies beinhaltet eine Quadratwurzel, die langsam ist. Es sind auch mehrere Objekt-Lookups erforderlich, um die tatsächlichen Größen zu ermitteln.

Sie können dies stattdessen mit der Funktion DistanceSquared () optimieren. Berechnen Sie den maximalen Abstand, in dem zwei Objekte interagieren können, quadrieren Sie ihn und vergleichen Sie ihn dann mit DistanceSquared (). Wenn und nur wenn der Abstand zum Quadrat innerhalb des Maximums liegt, dann nimm die Quadratwurzel und vergleiche sie mit den tatsächlichen Objektgrößen.

BEARBEITEN : Diese Optimierung ist hauptsächlich für das Testen auf Kollisionen gedacht. Ich habe festgestellt, dass dies nicht das ist, was Sie tun (obwohl Sie es sicherlich irgendwann tun werden). Es kann jedoch trotzdem auf Ihre Situation zutreffen, wenn alle Partikel eine ähnliche Größe / Masse haben.

Alistair Buxton
quelle
Ja. Diese Lösung mag in Ordnung sein (nur vernachlässigbarer Genauigkeitsverlust), gerät jedoch in Schwierigkeiten, wenn sich die Masse der Objekte stark unterscheidet. Wenn die Masse einiger Objekte sehr groß ist, während einige Objekte sehr klein sind, ist der maximale Abstand für vernünftig höher. Beispielsweise ist der Einfluss der Erdschwerkraft auf ein kleines Staubpartikel für die Erde vernachlässigbar, nicht jedoch für das Staubpartikel (über eine größere Entfernung). Tatsächlich beeinflussen sich jedoch zwei Staubpartikel im gleichen Abstand nicht wesentlich.
SDwarfs
Eigentlich ist das ein sehr guter Punkt. Ich habe das als Kollisionstest falsch verstanden, aber es macht genau das Gegenteil: Partikel beeinflussen sich gegenseitig, wenn sie sich nicht berühren.
Alistair Buxton
3

Ich weiß nicht viel über das Threading, aber es scheint, als ob Ihre Schleifen zeitaufwändig sind

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

  object_i += force(object_j);

dazu

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

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

könnte helfen

Buksy
quelle
1
warum sollte das helfen?
1
Weil die ersten beiden Schleifen 10 000 Iterationen ausführen, während die zweiten Schleifen nur 4 950 Iterationen ausführen.
Buksy
1

Wenn Sie mit 10 simulierten Objekten bereits so große Probleme haben, müssen Sie den Code optimieren! Ihre verschachtelte Schleife würde nur 10 * 10 Iterationen verursachen, von denen 10 Iterationen übersprungen werden (dasselbe Objekt), was zu 90 Iterationen der inneren Schleife führt. Wenn Sie nur 2 FPS erreichen, bedeutet dies, dass Ihre Leistung so schlecht ist, dass Sie nur 180 Iterationen der inneren Schleife pro Sekunde erreichen.

Ich schlage vor, dass Sie Folgendes tun:

  1. VORBEREITUNG / BENCHMARKING: Um sicher zu wissen, dass diese Routine das Problem ist, schreiben Sie eine kleine Benchmark-Routine. Es soll die Update()Methode der Schwerkraft mehrere Male für zB 1000 Male ausführen und seine Zeit messen. Wenn Sie 30 FPS mit 100 Objekten erzielen möchten, sollten Sie 100 Objekte simulieren und die Zeit für 30 Ausführungen messen. Es sollte weniger als 1 Sekunde sein. Die Verwendung eines solchen Benchmarks ist erforderlich, um sinnvolle Optimierungen vorzunehmen. Sonst werden Sie wahrscheinlich das Gegenteil erreichen und den Code langsamer laufen lassen, weil Sie einfach denken, dass er schneller sein muss ... Ich empfehle Ihnen also, dies zu tun!

  2. OPTIMIERUNGEN: Während Sie nicht viel gegen das O (N²) -Aufwandsproblem unternehmen können (was bedeutet, dass sich die Rechenzeit quadratisch mit der Anzahl der simulierten Objekte N erhöht), können Sie den Code selbst verbessern.

    a) Sie verwenden in Ihrem Code viele "assoziative Array" -Suchvorgänge (Dictionary). Diese sind langsam! Zum Beispiel entityEngine.Entities[e.Key].Position. Kannst du nicht einfach benutzen e.Value.Position? Dies erspart eine Suche. Sie tun dies überall in der gesamten inneren Schleife, um auf die Eigenschaften der Objekte zuzugreifen, auf die e und e2 verweisen ... Ändern Sie dies! b) Sie erstellen einen neuen Vektor innerhalb der Schleife new Vector2( .... ). Alle "neuen" Aufrufe implizieren eine gewisse Speicherzuweisung (und später: Freigabe). Diese sind sogar viel langsamer als das Nachschlagen von Wörterbüchern. Wenn Sie diesen Vektor nur vorübergehend benötigen, ordnen Sie ihn außerhalb der Schleifen zu, UND verwenden Sie ihn erneut, indem Sie seine Werte für die neuen Werte neu initialisieren, anstatt ein neues Objekt zu erstellen. c) Sie verwenden viele trigonometrische Funktionen (z. B. atan2undcos) innerhalb der Schleife. Wenn Ihre Genauigkeit nicht wirklich genau sein muss, können Sie stattdessen eine Nachschlagetabelle verwenden. Dazu skalieren Sie Ihren Wert auf einen definierten Bereich, runden ihn auf einen ganzzahligen Wert und schlagen ihn in einer Tabelle mit vorberechneten Ergebnissen nach. Wenn Sie dabei Hilfe benötigen, fragen Sie einfach. d) Sie verwenden häufig.Texture.Width / 2 . Sie können dies vorberechnen und das Ergebnis speichern als .Texture.HalfWidthoder - wenn dies immer ein geradzahliger positiver ganzzahliger Wert ist - Sie können die Verschiebeoperation verwenden >> 1, um zwei zu teilen.

Nehmen Sie jeweils nur eine Änderung vor und messen Sie die Änderung anhand des Benchmarks, um festzustellen, wie sich dies auf Ihre Laufzeit ausgewirkt hat! Vielleicht ist eine Sache gut, während die andere Idee schlecht war (sogar ich habe sie oben vorgeschlagen!) ...

Ich denke, diese Optimierungen sind viel besser als der Versuch, mit mehreren Threads eine bessere Leistung zu erzielen! Es ist schwierig, die Threads zu koordinieren, sodass die anderen Werte nicht überschrieben werden. Auch beim Zugriff auf ähnliche Speicherbereiche treten Konflikte auf. Wenn Sie für diesen Job 4 CPUs / Threads verwenden, können Sie nur eine Geschwindigkeitssteigerung von 2 bis 3 für die Bildrate erwarten.

SDwarfs
quelle
0

Können Sie es ohne die Objekterstellungslinien überarbeiten?

Vector2 Force = new Vector2 ();

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

Wenn Sie möglicherweise den Force-Wert in die Entität einfügen können, anstatt jedes Mal zwei neue Objekte zu erstellen, kann dies zur Leistungsverbesserung beitragen.

nejinx
quelle
4
Vector2in XNA ist ein Werttyp . Es gibt keinen GC-Aufwand und der Konstruktionsaufwand ist vernachlässigbar gering. Dies ist nicht die Ursache des Problems.
Andrew Russell
@ Andrew Russell: Ich bin mir nicht sicher, aber ist das wirklich immer noch der Fall, wenn Sie "new Vector2" verwenden? Wenn Sie Vector2 (....) ohne "new" verwenden, ist dies wahrscheinlich anders.
SDwarfs
1
@StefanK. In C # kann man das nicht machen. Benötigt das Neue. Denken Sie an C ++?
MrKWatkins