Ich arbeite an der Implementierung eines Beflockungsalgorithmus in ein größeres System. OGRE wird für das Rendering verwendet, luabind wird verwendet, um von LUA, yatta yatta, kommunizieren zu können, was nicht so wichtig sein sollte.
Ich implementierte den Algorithmus grundsätzlich nach dem Reynolds-Boids-Modell. Das heißt, ein Boid (wie in "Ein Fisch in einem Schwarm") bewegt sich entsprechend seinen Nachbarn in einem bestimmten Radius. So wie die Dinge sind, ist die grundlegende Komplexität davon O (n²), da jeder Körper alle seine Schwarmgenossen überprüfen muss, wenn sie in Reichweite sind und dann einige Faktoren berücksichtigen, um die eigene Bewegung zu berechnen.
Der Algorithmus selbst ist implementiert und läuft reibungslos. Es akzeptiert Modelle aller Größen, es funktioniert im 2D- und 3D-Raum, es schart sich schön usw., ich arbeite schon eine Weile daran.
Mein Problem ist, dass der Algorithmus zur Laufzeit abstürzt, sobald ich auf eine Art "Barriere" in Boid-Zahlen stoße, die ungefähr 200-250 ist und sogar variiert. Nun, wenn es langsamer und langsamer werden würde, bis ich auf 1 fps gebrochen bin, könnte ich verstehen, dass einfach die Leistung des Algorithmus das Problem ist. Zum Beispiel funktionieren 199 Boids perfekt, 201 funktionieren überhaupt nicht und stürzen zur Laufzeit ab. Das ist sehr überraschend für mich.
Ich habe 2 Klassen implementiert: "Swarm" und "Boid". Swarm wird verwendet, um Zeiger auf alle Boids eines Schwarms zu halten, aber berechnet nicht viel, Bewegung geschieht in Boid.
swarm.h:
%Vor%boid.h:
%Vor%Wie Sie sehen, verwende ich einen Zeigervektor, um Objekte im Schwarm zu knoten. Zur Laufzeit wird swarm :: move () aufgerufen, das durch den Vektor iteriert und für jede Datei boid :: move () aufruft.
%Vor%boid :: move ist sehr komplex, da es die Bewegung basierend auf vielen Dingen berechnet. Ich werde die Punkte posten, die - imo - tatsächlich wichtig sind für hier, nicht jede einzelne Multiplikation, da ich dich nicht mit unnötigem Zeug langweilen will. Bearbeitet: Okay, jetzt haben Sie den Großteil des Codes hier.
%Vor%Wie Sie sehen können, ist der Basisalgorithmus ziemlich stark, angenehm. Ich laufe durch einen Vektor von Boids, rufe eine Methode von jedem boid auf, die dann wiederum durch den Vektor läuft. Die anderen Berechnungen sind einfach und werfen Variablen um, so dass alles gut aussieht, nichts, was die Komplexität exponentiell erhöht.
Nun, wie bereits erwähnt, würde ich erwarten, dass das Rendering bei einer großen Menge von Boids langsam wird. Ich würde erwarten, dass Frameraten fallen und so weiter, aber das passiert einfach nicht. Stattdessen läuft der Algorithmus perfekt mit hohen und flüssigen Frameraten, bis ich ungefähr bei 200 Boids +/- bin, und stürzt sofort ab, sobald swarm :: move () aufgerufen wird.
Ich habe schon einige lose Enden überprüft. Der Vektorcontainer hat genug Platz für & gt; 1 Milliarde Elemente, also ist es nicht so. Ich kann auch alles mit 10000, 20000 Boids initialisieren, also ist es auch kein grundlegendes Speicherzuweisungsproblem. Es stürzt einfach ab, sobald swarm :: move () aufgerufen wird.
Also, warum stürzt das mit einer Anzahl von 200 und ein paar Boids? Warum sinkt die Framerate nicht im Laufe der Zeit? Danke für jede Hilfe zu diesem Thema. Ich denke, ich habe alle notwendigen Informationen bereitgestellt, aber wenn Sie zusätzlichen Code (oder was auch immer) benötigen, zögern Sie nicht zu fragen.
Zusätzliche Informationen über Bearbeiten: Es ändert sich nicht, wenn ich swarm :: move manuell über Klick statt über Framerate auslöse. Es funktioniert immer noch mit & lt; 200ish boids, es funktioniert immer noch nicht mit mehr.
Bearbeiten²: Bearbeitete die Methode boid :: move () und notierte, wo der Debugger den Absturz abfängt. Allerdings wird der Absturz bei boid 1, was für mich sinnvoll wäre, nicht erfasst, sondern in boid 314 (in diesem Fall). Also läuft der Algorithmus 313 mal perfekt durch denselben Vektor und stürzt dann zum 314sten Mal ab. Macht das irgendeinen Sinn?
Bearbeiten³: Interessanterweise verwirrt mich Debugging-Material weit mehr als nur darauf hin, wo das Problem liegt. Ich habe boid :: move () erneut aktualisiert und ich werde den Code für swarm :: getFlockMates einwerfen, ich werde in einer Sekunde erklären, warum.
%Vor%Was mich verwirrt, ist folgendes. Nachdem ich die Berechnung der Entfernung auf das geändert hatte, was Ben voigt vorgeschlagen hatte, stürzte der Code bei der finalisierten Bewegung mit Werten ab, die ihn nicht zum Absturz bringen sollten. Stattdessen hatte ich einen cohesionCount von 1.x Millionen, während alignementCount und separationCount immer noch 0 waren. Das macht wieder keinen Sinn für mich. cohesionCount kann nicht höher sein als die Gesamtmenge von boids, die momentan 1000 ist (und daher abstürzt). Selbst wenn alle Boids im Bereich der Kohäsion wären (Abstand & lt; 10 * boidSize), könnte das Maximum davon nicht höher sein als die Gesamtmenge von Boids, die in Flock gespeichert sind.
Wie gesagt, gibt es ein Problem, wie ich meine Herde iteriere?
Es stellt sich heraus, dass der hier vorgeschlagene Algorithmus keine Fehler hat, die zu diesem Problem geführt haben. Das Speicherleck befand sich in einer der Lua-Files, die ich verwenden musste, da diese Engine (und damit auch dieser Algorithmus) damit benutzt wird. Danke für die Hilfe trotzdem an euch alle!
In Kapitel 6.14 seines Buches schlägt Daniel Shiffman einige Algorithmen vor, um die Leistungsfähigkeit zu steigern. Es schlägt vor, dass sie nicht für alle anderen existierenden Boids, sondern nur für diejenigen, die sich in der Nähe befinden, ähnlich wie mit einem Quadtree arbeiten sollten.
Dies ist mehr ein Kommentar als eine Antwort, aber ich kann keine Kommentare schreiben ... Ich vermute, dass Ihr Problem nicht in swarm::move() , sondern davor ist. Ein Absturz wäre am sinnvollsten, wenn einer Ihrer Zeiger nicht auf boid zeigt, sondern auf einen anderen Speicher.
Allerdings kann ich nur raten, weil ich Ihren Code nicht kenne oder welche Art von Absturz Ihr Programm beendet. Übrigens sollten Sie mit einem Debugger überprüfen, die meisten Debugger zeigen Ihnen genau, wo der Absturz passiert und manchmal sogar warum.
Viele Algorithmen haben einen Konvergenzradius. Ist Ihr Parameter timeSinceLastFrame an die Renderrate gebunden? Wenn dies der Fall ist, beeinflusst wiederum die Populationsgröße durch die Beeinflussung der Renderrate das Konvergenzverhalten Ihres Algorithmus grundlegend. Wenn Sie Stabilitätsprobleme haben, könnten Sie auch Gleitkommaausnahmen auslösen.
Versuchen Sie, timeSinceLastFrame konstant zu machen, jetzt laufen Sie langsamer als in Echtzeit, aber die Konvergenz wird nicht mehr von den Berechnungs- und Renderzeiten beeinflusst.
Tags und Links c++