Warum ist RK4 besser als die Euler-Integration? [geschlossen]

20

Am Ende dieser tollen Folien vergleicht der Autor alle vorgestellten Integratoren. Auf die eine oder andere Weise sind sie alle unzureichend, mit Ausnahme von " Verbesserte Euler-Integration" und " Runge Kutta 4-Integration" , die beide alle Tests bestehen.

Ich sollte wohl erwähnen, dass ich an einem 2D-Spiel arbeite, das nicht sehr physikintensiv ist. Ich bin nur gespannt, wo die verbesserte Euler-Integration zu kurz kommen würde und stattdessen RK4 verwendet werden müsste.

Mein Spiel besteht hauptsächlich aus einfacher Schwerkraft (Springen und Fallen), Bewegung entlang der X- und Y-Achse und Bounding-Box-Kollision. Lohnt sich die Implementierung von RK4 oder würde Improved Euler ausreichen? Ich sehe viele Diskussionen, in denen die Benutzer von Euler Integration gezüchtigt werden, aber soweit ich sehen kann, ist Improved Euler in einfachen 2D-Angelegenheiten gleichwertig. Ich stelle mir vor, es wäre auch schneller.

John Tyler
quelle
offtopic, aber das sind tolle Folien, sehr übersichtlich mit den Beispielen und allem. Danke für diesen Link!
Roy T.
Wenn dies hier tatsächlich nicht zum Thema gehört, passt es wahrscheinlich gut zu Computational Science .
David Z
Außerdem: Zeitkorrigierte Verlet-Integration - ähnelt Improved Euler: zu faul, um herauszufinden, ob es genau dasselbe ist. TCV ist großartig, weil Sie mit Ihrem festen Zeitschritt schonen können (andere Integratoren wollen einen garantierten festen Zeitschritt).
Jonathan Dickinson
1
Kann nicht bearbeiten: Ich sehe, er erwähnt es. Ich bin mir nicht sicher, ob seine Implementierung in Bezug auf die im Artikel beschriebenen Anforderungen an die Anfangsbedingungen fehlerhaft ist. Ich habe dieses Problem mit der Schwerkraft bei der Implementierung von TCV jedoch nie gesehen, wenn ich die Anfangsbedingungen korrekt berechnet habe.
Jonathan Dickinson

Antworten:

15

Ich persönlich bevorzuge Velocity Verlet für die meisten Simulationen. Nach meiner Erfahrung mit dieser Methode eignet sie sich sehr gut für ziemlich steife Gleichungen. Diese "verbesserte Euler" -Methode scheint der Velocity Verlet-Methode ziemlich ähnlich zu sein und basiert auf einer Klasse von Integrationsmethoden, die als Predictor-Corrector bekannt sind . Man kann heutzutage viel über diese Methoden lesen, angefangen mit David Baraffs "Großen Schritten in der Stoffsimulation", in denen die Kraft impliziter Methoden wirklich zum Tragen kommt. Ihr Untergang ist, dass Sie:

  1. müssen Jacobians oder Hessians approximieren und dann müssen,
  2. Berechnen Sie eine angemessene Anzahl von Matrix-Inversen pro Frame.

Wenn Sie also kein Mathe-Guru sind, können Sie sich die Finger stecken lassen. Experimentieren Sie einfach mit der von Ihnen gewünschten Methode und geben Sie sich dann mit der für Sie am besten geeigneten zufrieden. Einfach ist nicht immer besser, aber für interaktive Frameraten kenne ich nur ein Wort: Kompromiss.

Einige zusätzliche Ressourcen, die Sie sich ansehen sollten:

Jakobsen ist eine Art Genie, wenn es darum geht, eine so einfache Idee für ein prätentiöses Problem zu entwickeln (seine Spezialität ist Kryptographie, wenn nicht Irrtum, aber es ist ihm gelungen, die mathematische Gleichwertigkeit seiner Methode mit einer Klasse von Gauß-Seidel-Iterationsalgorithmen zu beweisen, die konvergent sind ). Machen Sie dies der Einfachheit halber zuerst, bevor Sie sich eingehend mit impliziten Methoden befassen.

SPÄTERE BEARBEITUNG : Ich habe kürzlich ein Papier über die Verwendung expliziter Integratoren für die Simulation von weichen oder halbstarren Körpern erhalten und über deren Auswirkungen auf Leistung und Qualität. Dieses Dokument sollte je nach Szenario als Leitfaden für die Auswahl eines bestimmten Integrators dienen.

Teodron
quelle
1
+1 Dies war tatsächlich eine qualitativ wirklich gute Antwort in Bezug auf den Inhalt: aber es war ein bisschen zu schwer zu verdauen (Textwand). Ich fand, dass eine gute Formatierung immer dazu beiträgt, Stimmen zu bekommen. Ich habe es verbessert und hoffe, dass Sie die Stimmen bekommen, die Sie verdienen.
Jonathan Dickinson
Danke Jonathan, ich habe es hastig gemacht, ohne das "leserfreundliche" Verfahren zu beachten, aber ich musste diese wenigen Quellen erwähnen, da sie auch heute noch sehr häufig verwendet werden.
Teodron
10

F: Warum den fortgeschrittenen Runge Kutta verwenden?
A: Weil es sehr genau ist.

F: Warum nicht?
A: Weil du ein Spiel machst und eine sehr genaue Physik-Engine keine Rolle spielt, muss sie nur gut genug sein, um den Spieler zum Narren zu halten.

Übrigens, wenn Sie bei einer Kollision eine starke Dämpfung haben, wie es die meisten Plattformfahrer tun würden, ist ein einfacher Euler in Ordnung.

Ich empfehle Ihnen nachdrücklich, im Gegensatz zum Code in der Präsentation die feste Schrittphysik zu verwenden, die Ihnen einige potenzielle Störungen erspart und es Ihnen ermöglicht, das Problem, dass der Ball Energie gewinnt oder verliert, auf sehr einfache Weise zu lösen. Gehen Sie einfach auf den Mittelweg zwischen expliziter und impliziter Integration:

velocity += 0.5 * acceleration;
position += velocity;
velocity += 0.5 * acceleration;

In der Präsentation wird nicht gezeigt, wie mit Kollisionen umgegangen wird, damit Objekte scheinbar nicht über die Grenzen hinausgehen. Die einfache Lösung für dieses Problem ist die Verwendung einer hohen Aktualisierungsfrequenz. Eine komplexere, aber möglicherweise leistungsfähigere Lösung besteht darin, Objekte zum Zeitpunkt der Kollision zurückzubewegen. Die genaue Implementierung hängt vom gewünschten Verhalten der Physik ab.

aaaaaaaaaaa
quelle
1
+1 für "den Spieler zum Narren halten" - aber ich persönlich habe "sehr einfache" Systeme wegen der Euler-Integration explodieren lassen.
Jonathan Dickinson
@JonathanDickinson Ich würde sagen, dass dies nicht auf die Integration von Euler zurückzuführen ist, sondern auf eine Mischung von Umständen. Die Integration von Euler ist nur einer von ihnen. Wenn Sie ein Beispiel haben, bin ich sicher, dass ich einen Weg finden kann, explodierende Systeme zu vermeiden.
aaaaaaaaaaa
Oh, es ist auf ein paar wirklich alten VB6-Sachen (als ich buchstäblich 14 Jahre alt war) von mir, bevor ich von RK / Verlet erfahren habe. Ich habe nicht einmal mehr den Code in der Mischung :).
Jonathan Dickinson
1
Ich denke, ich sollte hinzufügen, dass es für mich vernünftig erscheint, die Integrationsmethode zu verstärken, sobald Sie anfangen, mit der Anziehung zwischen Objekten und nicht nur mit der einfachen Schwerkraft herumzuspielen Einziger Nachteil ist etwas komplexerer Code.
aaaaaaaaaaa
1

Die Präsentation ist fehlerhaft. Die vom Vortragenden als "Verbesserter Euler" bezeichnete Methode ist die Velocity-Verlet-Methode!

Weitere maßgebliche Quellen finden Sie hier: http://www.physics.udel.edu/~bnikolic/teaching/phys660/numerical_ode/node5.html

Gleiche Gleichungen gibt es auch in Wikipedia .

Eine übliche sofortige Verbesserung gegenüber Eulers Methode ist die Midpoint-Methode, die der Moderator wahrscheinlich im Sinn hatte, aber am Ende Velocity Verlet als verbesserten Euler verwechselte. Der einzige Unterschied zwischen der Midpoint-Methode und Velocity Verlet besteht darin, dass die Geschwindigkeit der Durchschnitt der letzten und der nächsten Beschleunigung ist und nicht nur von der letzten Beschleunigung abhängt.

Shital Shah
quelle