Wie kann ich eine deterministische Physiksimulation durchführen?

43

Ich erstelle ein Physikspiel mit starren Körpern, in dem Spieler Teile und Teile bewegen, um ein Puzzle / eine Karte zu lösen. Ein äußerst wichtiger Aspekt des Spiels ist, dass beim Starten einer Simulation diese überall gleich abläuft , unabhängig von Betriebssystem, Prozessor usw.

Es gibt Raum für viel Komplexität, und Simulationen können über einen langen Zeitraum ausgeführt werden. Daher ist es wichtig, dass die Physik-Engine in Bezug auf ihre Gleitkommaoperationen vollständig deterministisch ist "scheitern" an einem anderen.

Wie kann ich diesen Determinismus in meinem Spiel erreichen? Ich bin bereit, eine Vielzahl von Frameworks und Sprachen zu verwenden, einschließlich Javascript, C ++, Java, Python und C #.

Box2D (C ++) und seine Entsprechungen in anderen Sprachen haben mich in Versuchung geführt, da es meine Bedürfnisse zu erfüllen scheint, aber es fehlt ein Gleitkomma-Determinismus, insbesondere bei trigonometrischen Funktionen.

Die beste Option, die ich bisher gesehen habe, war das Java-Äquivalent (JBox2D) von Box2D. Es scheint einen Versuch zu geben, Fließkomma-Determinismus zu verwenden, StrictMathanstatt Mathfür viele Operationen, aber es ist unklar, ob diese Engine alles garantieren wird, was ich brauche, da ich das Spiel noch nicht erstellt habe.

Ist es möglich, einen vorhandenen Motor zu verwenden oder zu modifizieren, um ihn meinen Bedürfnissen anzupassen? Oder muss ich selbst einen Motor bauen?

BEARBEITEN: Überspringen Sie den Rest dieses Beitrags, wenn Sie sich nicht darum kümmern, warum jemand eine solche Präzision benötigt. Einzelpersonen in Kommentaren und Antworten scheinen zu glauben, ich suche nach etwas, das ich nicht sollte, und als solches erkläre ich weiter, wie das Spiel funktionieren soll.

Der Spieler erhält ein Puzzle oder Level, das Hindernisse und ein Ziel enthält. Eine Simulation läuft zunächst nicht. Sie können dann Teile oder Werkzeuge verwenden, um eine Maschine zu bauen. Sobald sie auf Start drücken, beginnt die Simulation und sie können ihre Maschine nicht mehr bearbeiten. Wenn die Maschine die Karte löst, hat der Spieler das Level geschlagen. Andernfalls müssen sie die Stopp-Taste drücken, den Computer wechseln und es erneut versuchen.

Der Grund, warum alles deterministisch sein muss, ist, dass ich vorhabe, Code zu erstellen, der jede Maschine (eine Reihe von Teilen und Werkzeugen, mit denen versucht wird, eine Ebene zu lösen) einer XML- oder JSON-Datei zuordnet, indem Position, Größe und Drehung jedes Teils aufgezeichnet werden. Es ist dann für Spieler möglich, Lösungen (die durch diese Dateien dargestellt werden) gemeinsam zu nutzen, um sie zu überprüfen, voneinander zu lernen, Wettbewerbe abzuhalten, zusammenzuarbeiten usw. Bei den meisten Lösungen handelt es sich natürlich um einfache oder schnelle Lösungen diejenigen, werden nicht von einem Mangel an Determinismus betroffen sein. Aber die langsamen oder komplexen Designs, die wirklich schwierige Levels lösen, sind wahrscheinlich die interessantesten und die es wert sind, geteilt zu werden.

jvn91173
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben . Wenn Sie der Meinung sind, dass Sie eine Lösung für das Problem gefunden haben, können Sie diese eher als Antwort als als Kommentar veröffentlichen. Dies erleichtert die Bearbeitung, die Bewertung per Abstimmung / Markierung oder die direkte Kommentierung des Vorschlags als Feedback Antworten in einen längeren Konversationsfaden verweben.
DMGregory

Antworten:

45

Zum deterministischen Umgang mit Gleitkommazahlen

Fließkomma ist deterministisch. Nun, das sollte es sein. Es ist kompliziert.

Es gibt reichlich Literatur zu Fließkommazahlen:

Und wie problematisch sie sind:

Für abstrakte. Zumindest in einem einzelnen Thread sollten dieselben Vorgänge mit denselben Daten in derselben Reihenfolge deterministisch sein. Wir können also damit beginnen, uns Gedanken über Eingaben zu machen und die Reihenfolge zu ändern.


Eine solche Eingabe, die Probleme verursacht, ist die Zeit.

Zunächst sollten Sie immer den gleichen Zeitschritt berechnen. Ich sage nicht, um die Zeit nicht zu messen, ich sage, dass Sie keine Zeit an die Physiksimulation weitergeben werden, da zeitliche Schwankungen eine Rauschquelle in der Simulation sind.

Warum messen Sie die Zeit, wenn Sie sie nicht an die Physiksimulation weitergeben? Sie möchten die verstrichene Zeit messen, um zu wissen, wann ein Simulationsschritt aufgerufen werden soll, und - vorausgesetzt, Sie verwenden Schlaf - wie viel Zeit zum Schlafen.

Somit:

  • Zeit messen: Ja
  • Zeit in der Simulation verwenden: Nein

Nun, Anweisung neu anordnen.

Der Compiler könnte entscheiden, dass dies f * a + bdasselbe ist b + f * a, jedoch kann dies zu einem anderen Ergebnis führen. Es könnte auch kompiliert werden, um fmadd zu erstellen , oder es könnte entscheiden, dass mehrere Zeilen, die zusammen auftreten, mit SIMD oder einer anderen Optimierung, die mir derzeit nicht in den Sinn kommt , geschrieben werden . Und denken Sie daran, wir möchten, dass die gleichen Vorgänge in der gleichen Reihenfolge ausgeführt werden. Es liegt nahe, dass wir steuern möchten, welche Vorgänge ausgeführt werden.

Und nein, mit double werden Sie nicht gerettet.

Sie müssen sich Gedanken über den Compiler und seine Konfiguration machen, insbesondere um Gleitkommazahlen im Netzwerk zu synchronisieren. Sie müssen die Builds dazu bringen, zuzustimmen, dasselbe zu tun.

Eine Schreibanordnung wäre wohl ideal. Auf diese Weise entscheiden Sie, welche Operation durchgeführt werden soll. Dies könnte jedoch ein Problem für die Unterstützung mehrerer Plattformen sein.

Somit:


Der Fall für Festkommazahlen

Aufgrund der Art und Weise, wie Floats im Speicher dargestellt werden, werden große Werte an Genauigkeit verlieren. Es liegt nahe, Ihre Werte klein zu halten (Clamp), um das Problem zu mindern. Somit keine großen Geschwindigkeiten und keine großen Räume. Dies bedeutet auch, dass Sie diskrete Physik verwenden können, da Sie ein geringeres Tunnelungsrisiko haben.

Andererseits häufen sich kleine Fehler an. Also abschneiden. Ich meine, skalieren und auf einen ganzzahligen Typ umwandeln. Auf diese Weise wissen Sie, dass sich nichts aufbaut. Es wird Operationen geben, die Sie mit dem Integer-Typ durchführen können. Wenn Sie zum Gleitkomma zurückkehren müssen, können Sie die Skalierung umwandeln und rückgängig machen.

Beachten Sie, dass ich Skala sage. Die Idee ist, dass 1 Einheit tatsächlich als Zweierpotenz dargestellt wird (zum Beispiel 16384). Was auch immer es ist, mach es zu einer Konstanten und benutze es. Sie verwenden es grundsätzlich als Festkommazahl. In der Tat, wenn Sie richtige Festkommazahlen aus einer zuverlässigen Bibliothek viel besser verwenden können.

Ich sage abgeschnitten. In Bezug auf das Rundungsproblem bedeutet dies, dass Sie dem letzten Teil des Wertes, den Sie nach der Besetzung erhalten haben, nicht vertrauen können. Also, bevor die Besetzungsskala ein bisschen mehr als Sie brauchen, und kürzen Sie es danach.

Somit:

  • Werte klein halten: Ja
  • Sorgfältige Rundung: Ja
  • Festkommazahlen wenn möglich: Ja

Warten Sie, warum brauchen Sie Gleitkomma? Könnten Sie nicht nur mit einem Integer-Typ arbeiten? Oh, richtig. Trigonometrie und Bestrahlung. Sie können Tabellen für Trigonometrie und Radikation berechnen und in Ihrer Quelle backen lassen. Sie können auch die Algorithmen implementieren, mit denen sie mit Gleitkommazahlen berechnet werden, außer mit Festkommazahlen. Ja, Sie müssen Speicher, Leistung und Präzision in Einklang bringen. Sie könnten sich jedoch von Gleitkommazahlen fernhalten und deterministisch bleiben.

Wusstest du, dass sie so etwas für die ursprüngliche PlayStation gemacht haben? Bitte treffen Sie meinen Hund, Flecken .

Übrigens sage ich nicht, Fließkomma für Grafiken nicht zu verwenden. Nur für die Physik. Ich meine, klar, die Positionen werden von der Physik abhängen. Wie Sie wissen, muss ein Collider jedoch nicht mit einem Modell übereinstimmen. Wir wollen die Ergebnisse der Kürzung der Modelle nicht sehen.

Also: FESTE PUNKTNUMMERN VERWENDEN.


Um es klar auszudrücken: Wenn Sie einen Compiler verwenden können, mit dem Sie die Funktionsweise von Fließkommazahlen festlegen können und der für Sie ausreicht, können Sie dies tun. Das ist nicht immer eine Option. Außerdem tun wir dies für den Determinismus. Festkommazahlen bedeuten nicht, dass es keine Fehler gibt, schließlich haben sie eine begrenzte Genauigkeit.

Ich denke nicht, dass "Festkommazahlen hart sind" ein guter Grund ist, sie nicht zu verwenden. Und wenn Sie einen guten Grund haben möchten, sie zu verwenden, dann ist es Determinismus, insbesondere Determinismus über Plattformen hinweg.


Siehe auch:


Nachtrag : Ich schlage vor, die Größe der Welt klein zu halten. Trotzdem bringen sowohl OP als auch Jibb Smart den Punkt auf den Punkt, dass die Bewegung von den Ursprungs-Floats weniger genau ist. Das wird Auswirkungen auf die Physik haben, die weit früher als der Rand der Welt zu sehen sein wird. Festkommazahlen haben eine feste Genauigkeit und sind überall gleich gut (oder schlecht, wenn Sie es vorziehen). Was gut ist, wenn wir Determinismus wollen. Ich möchte auch erwähnen, dass die Art und Weise, wie wir normalerweise Physik betreiben, die Eigenschaft hat, kleine Variationen zu verstärken. Siehe Der Schmetterlingseffekt - Deterministische Physik in The Incredible Machine und Contraption Maker .


Ein anderer Weg, um Physik zu machen

Ich habe nachgedacht, der Grund, warum sich der kleine Fehler in der Genauigkeit von Gleitkommazahlen verstärkt, ist, dass wir Iterationen mit diesen Zahlen durchführen. In jedem Simulationsschritt nehmen wir die Ergebnisse des letzten Simulationsschritts und bearbeiten sie. Häufen sich Fehler auf Fehler. Das ist dein Schmetterlingseffekt.

Ich glaube nicht, dass wir einen einzelnen Build mit einem einzelnen Thread auf demselben Computer sehen werden, der bei derselben Eingabe unterschiedliche Ausgaben liefert. Aber auf einer anderen Maschine könnte es sein, oder ein anderer Build könnte es.

Es gibt ein Argument, um dort zu testen. Wenn wir genau entscheiden, wie die Dinge funktionieren sollen, und auf der Zielhardware testen können, sollten wir keine Builds veröffentlichen, die ein anderes Verhalten aufweisen.


Es gibt jedoch auch ein Argument dafür, nicht wegzuarbeiten, das so viele Fehler ansammelt. Vielleicht ist dies eine Gelegenheit, Physik auf eine andere Art und Weise zu betreiben.

Wie Sie vielleicht wissen, gibt es eine kontinuierliche und eine diskrete Physik. Beide arbeiten daran, wie weit jedes Objekt im Zeitschritt vorrücken würde. Die kontinuierliche Physik hat jedoch die Möglichkeit, den Zeitpunkt der Kollision herauszufinden, anstatt verschiedene mögliche Zeitpunkte zu untersuchen, um festzustellen, ob eine Kollision stattgefunden hat.

Daher schlage ich Folgendes vor: Verwenden Sie die Techniken der kontinuierlichen Physik, um herauszufinden, wann die nächste Kollision jedes Objekts mit einem großen Zeitschritt stattfinden wird, der viel größer ist als der eines einzelnen Simulationsschritts. Dann nehmen Sie den nächsten Kollisionszeitpunkt und finden heraus, wo sich in diesem Moment alles befinden wird.

Ja, das ist viel Arbeit in einem einzigen Simulationsschritt. Das bedeutet, dass die Simulation nicht sofort startet ...

... Sie können jedoch die nächsten Simulationsschritte simulieren, ohne jedes Mal die Kollision zu überprüfen, da Sie bereits wissen, wann die nächste Kollision stattfinden wird (oder dass im großen Zeitschritt keine Kollision auftritt). Darüber hinaus sind die in dieser Simulation akkumulierten Fehler irrelevant, da wir, sobald die Simulation den großen Zeitschritt erreicht, nur die zuvor berechneten Positionen platzieren.

Jetzt können wir das Zeitbudget verwenden, das wir verwendet hätten, um jeden Simulationsschritt auf Kollisionen zu überprüfen, um die nächste Kollision nach der gefundenen zu berechnen. Das heißt, wir können voraussimulieren, indem wir den großen Zeitschritt verwenden. Unter der Annahme, dass der Umfang einer Welt begrenzt ist (dies funktioniert nicht für große Spiele), sollte es eine Warteschlange zukünftiger Zustände für die Simulation geben, und dann sollte jeder Frame, den Sie gerade interpolieren, vom letzten Zustand zum nächsten.


Ich würde für Interpolation argumentieren. Da es jedoch Beschleunigungen gibt, können wir nicht einfach alles auf die gleiche Weise interpolieren. Stattdessen müssen wir unter Berücksichtigung der Beschleunigung jedes Objekts interpolieren. In diesem Fall können wir die Position genauso aktualisieren wie für den großen Zeitschritt (was auch bedeutet, dass dies weniger fehleranfällig ist, da wir nicht zwei verschiedene Implementierungen für dieselbe Bewegung verwenden würden).


Hinweis : Wenn wir diese Gleitkommazahlen verwenden, löst dieser Ansatz nicht das Problem, dass sich Objekte unterschiedlich verhalten, je weiter sie vom Ursprung entfernt sind. Es ist zwar richtig, dass die Präzision verloren geht, je weiter Sie sich vom Ursprung entfernen, aber das ist immer noch deterministisch. In der Tat, das ist der Grund, warum ich das ursprünglich nicht erwähnt habe.


Nachtrag

Vom OP im Kommentar :

Die Idee ist, dass die Spieler ihre Maschinen in einem bestimmten Format (wie xml oder json) speichern können, so dass die Position und Rotation der einzelnen Teile aufgezeichnet werden. Diese XML- oder JSON-Datei wird dann verwendet, um das Gerät auf dem Computer eines anderen Players zu reproduzieren.

Also kein Binärformat, oder? Das bedeutet, dass wir uns auch Sorgen machen müssen, ob die wiederhergestellten Gleitkommazahlen mit dem Original übereinstimmen oder nicht. Siehe: Überarbeitete Float-Präzision: Portabilität mit neun Stellen

Theraot
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Vaillancourt
2
Gute Antwort! 2 weitere Punkte zugunsten von Festpunkten: 1. Gleitkomma verhält sich näher oder weiter vom Ursprung entfernt (wenn Sie dasselbe Rätsel an einer anderen Stelle haben), Festkomma jedoch nicht; 2. Festpunkt hat für den größten Teil seines Bereichs tatsächlich mehr Präzision als Fließkomma - Sie können Präzision gewinnen, indem Sie Festpunkt gut verwenden
Jibb Smart
Es ist möglich, Binärdaten sowohl in XML als auch in JSON mithilfe von base64Elementen zu codieren . Es ist kein effizienter Weg, große Mengen solcher Daten darzustellen, aber es ist falsch zu implizieren, dass sie die Verwendung von binären Darstellungen verhindern.
Pikalek
1
@Pikalek Mir ist bekannt, dass OP mich zu Kommentaren gefragt hat. Ich erwähnte base64 als eine Option, unter anderem hexadezimal, interpretiere cast als int neu und verwende das protobuf-Format, da diese Dateien sowieso niemand versteht, sie sind nicht (ungeübt) ) menschenlesbar. Dann - nehme ich an - hat ein Mod die Kommentare entfernt (nein, es steht nicht im oben verlinkten Chat). Wird das nochmal passieren? Sollte ich das aus der Antwort streichen? Soll ich es länger machen?
Theraot
@Theraot Ah, ich kann sehen, wie ich das im Kontext von seitdem gelöschten Kommentaren anders interpretiert haben könnte. (FWIW, ich habe die Chats sowohl zu dieser Antwort als auch zur Frage durchgelesen). Und selbst wenn es eine systemeigene, effiziente Methode zum Codieren der Daten gab, muss immer noch sichergestellt werden, dass sie plattformübergreifend dasselbe bedeuten. In Anbetracht der Abwanderung ist es vielleicht am besten, es so zu lassen, wie es ist. Danke fürs klarstellen!
Pikalek
6

Ich arbeite für ein Unternehmen, das ein bekanntes Echtzeit-Strategiespiel herstellt, und ich kann Ihnen sagen, dass Gleitkommadeterminismus möglich ist.

Die Verwendung unterschiedlicher Compiler oder desselben Compilers mit unterschiedlichen Einstellungen oder sogar unterschiedlicher Versionen desselben Compilers kann den Determinismus aufheben.

Wenn Sie ein Crossplay zwischen Plattformen oder Spielversionen benötigen, müssen Sie, wie ich finde, auf Fixed Point umsteigen - das einzige mögliche Crossplay, das mir bei Floating Point bekannt ist, ist zwischen PC und XBox1, aber das ist ziemlich verrückt.

Sie müssen entweder eine Physik-Engine finden, die vollständig deterministisch ist, oder eine Open-Source-Engine nehmen und deterministisch machen, oder Ihre eigene Engine rollen. Ich habe das Gefühl, dass Unity of all things eine deterministische Physik-Engine hinzugefügt hat, aber ich bin mir nicht sicher, ob sie nur auf derselben Maschine oder auf allen Maschinen deterministisch ist.

Wenn Sie versuchen, Ihre eigenen Sachen zu rollen, können ein paar Dinge helfen:

  • IEE754-Floats sind deterministisch, wenn Sie nichts zu fruchtiges tun (google "IEE754-Determinismus" für weitere Informationen darüber, was abgedeckt wird oder nicht)
  • Sie müssen sicherstellen, dass für jeden Client der Rundungsmodus und die Genauigkeit identisch festgelegt sind (verwenden Sie controlfp, um sie festzulegen).
  • Rundungsmodus und Genauigkeit können von bestimmten Mathematikbibliotheken geändert werden. Wenn Sie also geschlossene Bibliotheken verwenden, möchten Sie diese möglicherweise nach dem Tätigen von Aufrufen überprüfen (erneut mit controlfp).
  • Einige SIMD-Anweisungen sind deterministisch, viele nicht. Seien Sie vorsichtig
  • Wie oben erwähnt, benötigen Sie zur Sicherstellung des Determinismus auch dieselbe Plattform, dieselbe exakte Version desselben Compilers, der dieselbe Konfiguration mit denselben Compilereinstellungen kompiliert
  • Bauen Sie einige Tools ein, um Status-Desynchronisierungen zu erkennen und zu diagnostizieren - z. B. CRC des Spielstatus in jedem Frame, um zu erkennen, wann eine Desynchronisierung auftritt, und verfügen Sie über einen ausführlichen Protokollierungsmodus, den Sie aktivieren können, wenn Änderungen am Spielstatus mühsam in einer Datei protokolliert werden. Nehmen Sie dann 2 Dateien aus Simulationen, die nicht mehr miteinander synchronisiert sind, und vergleichen Sie sie in einem Diff-Tool, um festzustellen, wo ein Fehler aufgetreten ist
  • Initialisieren Sie alle Variablen im Spielstatus, der Hauptquelle für Desyncs
  • Die gesamte Spielsimulation muss jedes Mal in genau der gleichen Reihenfolge ablaufen, um Desyncs zu vermeiden. Es ist unglaublich einfach, dies falsch zu verstehen. Es ist ratsam, Ihre Spielsimulation so zu strukturieren, dass dies minimiert wird. Ich bin wirklich kein Typ für Software-Designmuster, aber in diesem Fall ist es wahrscheinlich eine gute Idee - Sie könnten eine Art Muster in Betracht ziehen, bei dem die Spielsimulation wie eine sichere Box wirkt und der einzige Weg, den Spielstatus zu ändern, das Einfügen ist "Nachrichten" oder "Befehle", bei denen nur konstanten Zugriff auf Objekte außerhalb des Spielstatus gewährt wird (z. B. Rendern, Vernetzen usw.). Wenn Sie die Simulation für ein Multiplayer-Spiel vernetzen, müssen Sie diese Befehle über das Netzwerk senden, oder wenn Sie dieselbe Simulation wiederholen, müssen Sie den Befehlsstrom beim ersten Mal aufzeichnen.
Joe
quelle
1
Unity arbeitet in der Tat an einem plattformübergreifenden Determinismus mit dem neuen Unity Physics-System für den datenorientierten Technologie-Stack. Soweit ich weiß, befindet es sich noch in Arbeit und ist noch nicht fertig.
DMGregory
Was ist ein Beispiel für einen nicht deterministischen SIMD-Befehl? Denken Sie über ungefähre Werte nach rsqrtps?
Ruslan
@DMGregory muss es dann in der Vorschau sein, da du es schon benutzen kannst - aber wie du sagst, ist es vielleicht noch nicht fertig.
Joe
@ Ruslan ja rsqrtps / rcpps die Ergebnisse sind implementierungsabhängig
Joe
5

Ich bin nicht sicher, ob dies die Art der Antwort ist, die Sie suchen, aber eine Alternative könnte sein, die Berechnungen auf einem zentralen Server auszuführen. Lassen Sie die Clients die Konfiguration an Ihren Server senden, die Simulation ausführen (oder eine zwischengespeicherte Konfiguration abrufen) und die Ergebnisse zurücksenden, die dann vom Client interpretiert und in Grafiken verarbeitet werden.

Dies schließt natürlich alle Pläne aus, die Sie möglicherweise haben, um den Client im Offlinemodus auszuführen, und je nachdem, wie rechenintensiv die Simulationen sind, benötigen Sie möglicherweise einen sehr leistungsstarken Server. Oder mehrere, aber dann haben Sie die Möglichkeit, sicherzustellen, dass sie dieselbe Hard- und Softwarekonfiguration haben. Eine Echtzeitsimulation mag schwierig, aber nicht unmöglich sein (denken Sie an Live-Videostreams - sie funktionieren, aber mit einer leichten Verzögerung).

Glorfindel
quelle
1
Ich stimme vollkommen zu. Auf diese Weise garantieren Sie eine gemeinsame Erfahrung mit allen Benutzern. gamedev.stackexchange.com/questions/6645/… diskutiert ein ähnliches Thema und vergleicht den Unterschied zwischen clientseitiger und serverseitiger Physik.
Tim Holt
1

Ich werde einen kontraintuitiven Vorschlag machen, der, obwohl er nicht 100% zuverlässig ist, die meiste Zeit gut funktionieren sollte und sehr einfach zu implementieren ist.

Präzision reduzieren.

Verwenden Sie eine festgelegte konstante Zeitschrittgröße, führen Sie die Physik über jeden Zeitschritt in einem standardmäßigen Gleitkomma mit doppelter Genauigkeit durch und quantisieren Sie dann die Auflösung aller Variablen nach jedem Schritt auf einfache Genauigkeit (oder etwas noch Schlimmeres). Dann werden die meisten möglichen Abweichungen, die durch die Gleitkomma-Neuordnung möglicherweise entstehen (im Vergleich zu einer Referenzfahrt desselben Programms), abgeschnitten, da diese Abweichungen in Ziffern auftreten, die in der reduzierten Genauigkeit nicht einmal vorhanden sind. Daher besteht für die Abweichung nicht die Möglichkeit eines Lyapunov-Aufbaus (Schmetterlingseffekt), der sich irgendwann bemerkbar machen würde.

Natürlich ist die Simulation etwas ungenauer als sie sein könnte (im Vergleich zur realen Physik), aber das ist nicht wirklich bemerkenswert, solange alle Ihre Programmläufe auf die gleiche Weise ungenau sind .

Technisch gesehen ist es natürlich möglich, dass eine Neuordnung zu einer Abweichung führt, die bis zu einer höherwertigen Ziffer reicht. Wenn die Abweichungen jedoch tatsächlich nur durch Schwebungen verursacht werden und Ihre Werte kontinuierliche physikalische Größen darstellen, ist dies äußerst unwahrscheinlich. Beachten Sie, dass es doublezwischen zwei Werten eine halbe Milliarde singlegibt, sodass erwartet werden kann, dass die meisten Zeitschritte in den meisten Simulationen zwischen den Simulationsläufen genau gleich sind. Die wenigen Fälle, in denen es eine Abweichung durch Quantisierung schafft, sind hoffentlich Simulationen, die nicht so lange dauern (zumindest nicht mit chaotischer Dynamik).


Ich würde Ihnen auch empfehlen, das Gegenteil von dem zu erwägen, wonach Sie fragen: Nehmen Sie die Unsicherheit in Kauf ! Wenn das Verhalten leicht nicht deterministisch ist, ist dies tatsächlich näher an tatsächlichen physikalischen Experimenten. Warum also nicht die Startparameter für jeden Simulationslauf absichtlich nach dem Zufallsprinzip ordnen und es zur Voraussetzung machen, dass die Simulation über mehrere Versuche hinweg durchgehend erfolgreich ist ? Das wird viel mehr über die Physik und darüber lehren, wie die Maschinen so konstruiert werden, dass sie robust / linear genug sind, anstatt überempfindliche Maschinen, die nur in einer Simulation realistisch sind.

links herum
quelle
Abrunden hilft nicht, denn wenn das hochpräzise Ergebnis nicht deterministisch ist, wird das Ergebnis auf einem System auf eine und auf ein anderes System auf eine Weise gerundet. Sie könnten zum Beispiel immer auf die nächste Ganzzahl abrunden, aber dann berechnet ein Systemcomputer 1.0 und der andere 0,999999999999999999999999999999999999999999 und sie runden unterschiedlich ab.
Yoyo
Ja das ist möglich, wie ich bereits in der Antwort gesagt habe. Aber es kommt äußerst selten vor , genauso wie andere Störungen in der Spielphysik. So Runden tut Hilfe. (Ich würde nicht Abrundungs obwohl; Runde auf den nächstliegenden Vorspannung zu vermeiden.)
leftaroundabout
0

Erstelle deine eigene Klasse zum Speichern von Zahlen!

Sie können ein deterministisches Verhalten erzwingen, wenn Sie genau wissen, wie die Berechnungen ausgeführt werden. Wenn Sie sich beispielsweise nur mit Multiplikation, Division, Addition und Subtraktion befassen, ist es ausreichend, alle Zahlen nur als rationale Zahl darzustellen. Zu diesem Zweck wäre eine einfache Rational-Klasse in Ordnung.

Wenn Sie sich jedoch mit komplizierteren Berechnungen befassen möchten (beispielsweise mit trigonometrischen Funktionen), müssen Sie solche Funktionen selbst schreiben. Wenn Sie in der Lage sein möchten, den Sinus einer Zahl zu nehmen, müssen Sie in der Lage sein, eine Funktion zu schreiben, die sich dem Sinus einer Zahl annähert, während Sie nur die oben genannten Operationen verwenden. Dies ist alles machbar, und meiner Meinung nach werden viele der haarigen Details in anderen Antworten umgangen. Der Nachteil ist, dass Sie sich stattdessen mit etwas Mathe auseinandersetzen müssen.

Hahahh Jaddy Amal
quelle
3
Rationale Arithmetik ist für jede Art von numerischer Integration völlig unpraktisch. Selbst wenn jeder Zeitschritt nur * / + -so ist, werden die Nenner mit der Zeit immer größer.
links um
Ich würde erwarten, dass dies auch ohne Berücksichtigung der Integration keine gute Lösung wäre, da die Zahlen, die Ihren Zähler und Nenner darstellen, nach nur wenigen Multiplikationen oder Teilungen eine 64-Bit-Ganzzahl überlaufen würden.
jvn91173
0

Hier gibt es einige terminologische Unklarheiten. Ein physikalisches System kann vollständig deterministisch sein, es kann jedoch nicht für einen nützlichen Zeitraum modelliert werden, da sein Verhalten gegenüber den Anfangsbedingungen äußerst empfindlich ist und eine geringfügige Änderung der Anfangsbedingungen zu völlig unterschiedlichen Verhaltensweisen führt.

Hier ist ein Video eines realen Geräts, dessen Verhalten absichtlich nicht vorhersehbar ist, außer im statistischen Sinne:

https://www.youtube.com/watch?v=EvHiee7gs9Y

Es ist einfach, einfache mathematische Systeme zu konstruieren (nur mit Addition und Multiplikation), bei denen das Ergebnis nach N Schritten von der N-ten Dezimalstelle der Startbedingungen abhängt. Es ist nahezu unmöglich, Software für die konsistente Modellierung eines solchen Systems auf jeder Computerhardware und -software zu schreiben - selbst wenn Sie ein ausreichendes Budget haben, um die Anwendung auf jeder wahrscheinlichen Kombination von Hardware und Software zu testen .

Der beste Weg, dies zu beheben, besteht darin, das Problem an der Quelle anzugreifen: Machen Sie die Physik Ihres Spiels so deterministisch, wie es sein muss, um reproduzierbare Ergebnisse zu erzielen.

Die Alternative besteht darin, zu versuchen, es deterministisch zu machen, indem die Computersoftware so angepasst wird, dass etwas modelliert wird, das nicht den Vorgaben der Physik entspricht. Das Problem ist, dass Sie im Vergleich zu einer expliziten Änderung der Physik mehrere Komplexitätsebenen in das System eingeführt haben.

Angenommen, Ihr Spiel beinhaltet Kollisionen der starren Körper. Selbst wenn Sie Reibung ignorieren, ist die exakte Modellierung von Kollisionen zwischen beliebig geformten Objekten, die sich möglicherweise drehen, während sie sich bewegen, in der Praxis unmöglich. Aber wenn Sie die Situation so ändern, dass die einzigen Objekte nicht rotierende rechteckige Steine ​​sind, wird das Leben sehr viel einfacher. Wenn die Objekte in Ihrem Spiel nicht wie Ziegel aussehen, verbergen Sie diese Tatsache mit einigen "nicht-physischen" Grafiken - zum Beispiel verstecken Sie buchstäblich den Moment der Kollision hinter Rauch oder Flammen oder einer Cartoon-Text-Blase "Autsch". oder Wasauchimmer.

Der Spieler muss die Spielphysik entdecken , indem er das Spiel spielt. Es spielt keine Rolle, ob es nicht "völlig realistisch" ist, solange es sich selbst widerspiegelt und der Erfahrung des gesunden Menschenverstands ähnlich genug ist, um plausibel zu sein.

Wenn Sie dafür sorgen, dass sich die Physik selbst stabil verhält, kann auch ein Computermodell stabile Ergebnisse liefern, zumindest in dem Sinne, dass Rundungsfehler irrelevant sind.

Alephzero
quelle
1
Ich sehe keine Verwirrung in der Terminologie. Das OP will deterministisches Verhalten von einem potentiell chaotischen System. Das ist völlig machbar.
Mark
Durch die Verwendung einfacherer Formen (wie Kreise und Rechtecke) ändert sich das Problem überhaupt nicht. Sie benötigen noch viele trigonometrische Funktionen, sqrt, etc ...
jvn91173
-1

Verwenden Sie die doppelte Gleitkommapräzision anstelle der einfachen Gleitkommapräzision . Obwohl es nicht perfekt ist, ist es genau genug, um in Ihrer Physik als deterministisch angesehen zu werden. Sie können eine Rakete mit doppelter Gleitkommapräzision zum Mond schicken, aber nicht mit einfacher Gleitkommapräzision.

Wenn Sie wirklich perfekten Determinismus brauchen, verwenden Sie Festkomma-Mathematik . Dies führt zu einer geringeren Genauigkeit (vorausgesetzt, Sie verwenden die gleiche Anzahl von Bits), aber zu deterministischen Ergebnissen. Ich kenne keine Physik-Engines, die Festkomma-Mathematik verwenden, daher müssen Sie möglicherweise Ihre eigene schreiben, wenn Sie diesen Weg gehen möchten. (Etwas, von dem ich abraten würde.)

Evorlor
quelle
11
Der Ansatz mit doppelter Präzision läuft dem Schmetterlingseffekt zuwider . In einem dynamischen System (wie einer Physiksimulation) kann sich selbst eine geringfügige Abweichung der Anfangsbedingungen durch Rückkopplung verstärken und zu einem wahrnehmbaren Fehler führen. Die zusätzlichen Ziffern verzögern dies nur ein wenig und zwingen den Schneeball, etwas weiter zu rollen, bevor er groß genug wird, um Probleme zu verursachen.
DMGregory
2
Zwei Fehler gleichzeitig: 1) Doppelte Gleitkommazahlen haben die gleichen Probleme und verschieben das Problem normalerweise nur in eine immer schwieriger zu debuggende Zukunft. 2) Es gibt keine Regel, die besagt, dass ein fester Punkt weniger genau sein muss als ein Gleitkomma. Abhängig von der Skala und dem vorliegenden Problem oder von dem Speicher, den Sie pro Festkommazahl verwenden können, können sie weniger genau, gleich genau oder genauer sein. Es macht keinen Sinn zu sagen "sie sind weniger genau".
Phresnel
@phresnel, als Beispiel für Festkomma-Genauigkeit, verwendete die IBM 1400-Serie Festkomma-Dezimal-Mathematik mit willkürlicher Genauigkeit. Ordnen Sie jeder Zahl 624 Stellen zu, und Sie haben den Bereich und die Genauigkeit von Gleitkommazahlen mit doppelter Genauigkeit überschritten .
Mark
@phresnel (2) Guter Punkt. Ich habe meine Antwort aktualisiert, um die gleiche Anzahl von Bits anzunehmen.
Evorlor
-2

Verwenden Sie das Memento-Muster .

Speichern Sie in Ihrem ersten Lauf die Positionsdaten für jeden Frame oder die von Ihnen benötigten Benchmarks. Wenn dies zu unperformant ist, machen Sie es nur alle n Frames.

Folgen Sie dann beim Reproduzieren der Simulation der beliebigen Physik, aktualisieren Sie jedoch die Positionsdaten alle n Frames.

Übermäßig vereinfachter Pseudocode:

function Update():
    if(firstRun) then (SaveData(frame, position));
    else if(reproducedRun) then (this.position = GetData(frame));
Evorlor
quelle
9
Ich denke nicht, dass dies für OPs Fall funktioniert. Angenommen, Sie und ich spielen das Spiel auf verschiedenen Systemen. Jeder von uns platziert die Puzzleteile auf dieselbe Weise - eine Lösung, die vom Entwickler nicht im Voraus vorhergesagt wurde. Wenn Sie auf "Start" klicken, simuliert Ihr PC die Physik so, dass die Lösung erfolgreich ist. Wenn ich das gleiche mache, führt ein kleiner Unterschied in der Simulation dazu, dass meine (identische) Lösung nicht als erfolgreich eingestuft wird. Hier habe ich nicht die Möglichkeit, das Erinnerungsstück von Ihrem erfolgreichen Lauf zu konsultieren, da es auf Ihrem Computer stattfand, nicht zur Entwicklungszeit.
DMGregory
@DMGregory Das stimmt. Danke.
jvn91173