Wie sind deterministische Spiele angesichts des Gleitkomma-Nicht-Determinismus möglich?

52

Um ein Spiel wie ein RTS-Netzwerk zu machen, habe ich hier eine Reihe von Antworten gesehen, die vorschlagen, das Spiel vollständig deterministisch zu machen. dann müssen Sie nur noch die Aktionen der Benutzer aufeinander übertragen und die Anzeige etwas verzögern, um die Eingaben aller zu "sperren", bevor der nächste Frame gerendert wird. Dann müssen die Positionen, die Gesundheit usw. der Einheiten nicht ständig über das Netzwerk aktualisiert werden, da die Simulation jedes Spielers genau gleich ist. Ich habe auch die gleichen Vorschläge für Wiederholungen gehört.

Ist dies jedoch wirklich möglich , da Gleitkommaberechnungen zwischen Maschinen oder sogar zwischen verschiedenen Kompilierungen desselben Programms auf derselben Maschine nicht deterministisch sind ? Wie verhindern wir, dass diese Tatsache zu kleinen Unterschieden zwischen Spielern (oder Wiederholungen) führt, die sich im Laufe des Spiels ändern ?

Ich habe gehört, einige Leute schlagen vor, Gleitkommazahlen zu vermeiden und intden Quotienten eines Bruchs darzustellen, aber das klingt für mich nicht praktisch - was ist, wenn ich zum Beispiel den Cosinus eines Winkels nehmen muss? Muss ich wirklich eine ganze Mathematikbibliothek umschreiben?

Beachten Sie, dass ich hauptsächlich an C # interessiert bin, was meines Erachtens genau die gleichen Probleme wie C ++ in dieser Hinsicht hat.

BlueRaja - Danny Pflughoeft
quelle
5
Dies ist keine Antwort auf Ihre Frage, aber um das RTS-Netzwerkproblem zu lösen, würde ich empfehlen, die Positionen und den Zustand der Einheiten gelegentlich zu synchronisieren, um Abweichungen zu korrigieren. Welche Informationen synchronisiert werden müssen, hängt vom Spiel ab. Sie können die Bandbreitennutzung optimieren, indem Sie sich nicht die Mühe machen, Dinge wie Statuseffekte zu synchronisieren.
jhocking
@jhocking Trotzdem ist es wohl die beste Antwort.
Jonathan Connell
starcraft II infacti nur jedes mal genau synchronisieren, ich habe mir die spielwiedergabe mit meinen freunden auf jedem rechner nebeneinander angeschaut und dabei unterschiede (auch bedeutende) besonders mit hoher verzögerung (1 sek) festgestellt. Ich hatte einige Einheiten, bei denen 6/7
Kartenquadrate

Antworten:

15

Sind Gleitkommazahlen deterministisch?

Ich habe vor ein paar Jahren viel zu diesem Thema gelesen, als ich ein RTS mit der gleichen Lockstep-Architektur wie Sie schreiben wollte.

Meine Schlussfolgerungen zu Hardware-Gleitkommawerten waren:

  • Der gleiche native Assembly-Code ist höchstwahrscheinlich deterministisch, vorausgesetzt, Sie gehen vorsichtig mit Gleitkomma-Flags und Compiler-Einstellungen um.
  • Es gab ein Open-Source-RTS-Projekt, das behauptete, sie hätten deterministische C / C ++ - Kompilierungen über verschiedene Compiler hinweg unter Verwendung einer Wrapper-Bibliothek erhalten. Ich habe diese Behauptung nicht bestätigt. (Wenn ich mich richtig erinnere, handelte es sich um die STREFLOPBibliothek)
  • Dem .net JIT wird einiges an Spielraum eingeräumt. Insbesondere ist es erlaubt, eine höhere Genauigkeit als erforderlich zu verwenden. Außerdem werden auf x86 und AMD64 unterschiedliche Befehlssätze verwendet (ich denke, auf x86 wird x87 verwendet, auf AMD64 werden einige SSE-Befehle verwendet, deren Verhalten sich für Denorms unterscheidet).
  • Komplexe Anweisungen (einschließlich trigonometrischer Funktion, Exponentialen, Logarithmen) sind besonders problematisch.

Ich kam zu dem Schluss, dass es unmöglich ist, die eingebauten Gleitkommatypen in .net deterministisch zu verwenden.

Mögliche Problemumgehungen

Also brauchte ich Workarounds. Ich überlegte:

  1. Implementieren Sie FixedPoint32in C #. Dies ist zwar nicht allzu schwierig (ich habe die Implementierung zur Hälfte abgeschlossen), aber der sehr kleine Wertebereich macht es ärgerlich, ihn zu verwenden. Sie müssen immer vorsichtig sein, damit Sie weder überlaufen, noch zu viel Präzision verlieren. Am Ende fand ich das nicht einfacher als die direkte Verwendung von ganzen Zahlen.
  2. Implementieren Sie FixedPoint64in C #. Ich fand das ziemlich schwierig. Für einige Operationen wären Intermediate Integer von 128 Bit sinnvoll. Aber .net bietet so einen Typ nicht an.
  3. Verwenden Sie für die auf einer Plattform deterministischen Rechenoperationen systemeigenen Code. Verursacht den Overhead eines Delegiertenaufrufs bei jeder Rechenoperation. Verliert die Fähigkeit, plattformübergreifend zu laufen.
  4. Verwenden Sie Decimal. Aber es ist langsam, nimmt viel Speicherplatz in Anspruch und löst leicht Ausnahmen aus (Division durch 0, Überläufe). Es ist sehr gut für den finanziellen Gebrauch, aber nicht gut für Spiele geeignet.
  5. Implementieren Sie ein benutzerdefiniertes 32-Bit-Gleitkomma. Hört sich anfangs ziemlich schwierig an. Das Fehlen eines BitScanReverse-Eigensinns verursacht einige Ärger bei der Implementierung.

Mein SoftFloat

Inspiriert von Ihrem Beitrag zu StackOverflow habe ich gerade damit begonnen, einen 32-Bit-Gleitkommatyp in Software zu implementieren. Die Ergebnisse sind vielversprechend.

  • Die Speicherdarstellung ist mit IEEE-Floats binär kompatibel, sodass ich die Umwandlung bei der Ausgabe in Grafikcode neu interpretieren kann.
  • Es unterstützt SubNorms, Infinities und NaNs.
  • Die genauen Ergebnisse stimmen nicht mit den IEEE-Ergebnissen überein, aber für Spiele ist das normalerweise egal. Bei dieser Art von Code ist es nur wichtig, dass das Ergebnis für alle Benutzer gleich ist, nicht dass es auf die letzte Ziffer genau ist.
  • Leistung ist anständig. Ein trivialer Test zeigte, dass es ungefähr 75MFLOPS im Vergleich zu 220-260MFLOPS floatfür Addition / Multiplikation (Single Thread auf einem 2,66 GHz i3) leisten kann. Wenn jemand gute Gleitkomma-Benchmarks für .net hat, senden Sie diese bitte an mich, da mein aktueller Test sehr rudimentär ist.
  • Die Rundung kann verbessert werden. Derzeit wird abgeschnitten, was in etwa einer Rundung gegen Null entspricht.
  • Es ist immer noch sehr unvollständig. Derzeit fehlen Teilung, Besetzungen und komplexe mathematische Operationen.

Wenn jemand Tests beisteuern oder den Code verbessern möchte, kontaktiere mich einfach oder sende eine Pull-Anfrage an github. https://github.com/CodesInChaos/SoftFloat

Andere Quellen des Indeterminismus

Es gibt auch andere Ursachen für Indeterminismus in .net.

  • Wenn Sie über ein Dictionary<TKey,TValue>oder iterieren, werden HashSet<T>die Elemente in einer undefinierten Reihenfolge zurückgegeben.
  • object.GetHashCode() unterscheidet sich von Lauf zu Lauf.
  • Die Implementierung der eingebauten RandomKlasse ist nicht spezifiziert, verwenden Sie Ihre eigene.
  • Multithreading mit naivem Locking führt zu Neuordnungen und unterschiedlichen Ergebnissen. Achten Sie sehr darauf, dass Sie die Fäden richtig verwenden.
  • Wenn WeakReferences verlieren, ist ihr Ziel unbestimmt, da der GC jederzeit ausgeführt werden kann.
CodesInChaos
quelle
23

Die Antwort auf diese Frage stammt von dem Link, den Sie gepostet haben. Insbesondere solltest du das Zitat von Gas Powered Games lesen:

Ich arbeite bei Gas Powered Games und kann Ihnen aus erster Hand sagen, dass Gleitkomma-Mathematik deterministisch ist. Sie brauchen nur den gleichen Befehlssatz und Compiler, und der Prozessor des Benutzers hält sich natürlich an den IEEE754-Standard, der alle unsere PC- und 360-Kunden umfasst. Die Engine für DemiGod, Supreme Commander 1 und 2 basiert auf dem IEEE754-Standard. Ganz zu schweigen von allen anderen RTS-Peer-to-Peer-Spielen auf dem Markt.

Und darunter ist das:

Wenn Sie Wiederholungen als Controller-Eingaben speichern, können diese nicht auf Computern mit unterschiedlichen CPU-Architekturen, Compilern oder Optimierungseinstellungen wiedergegeben werden. In der MotoGP bedeutete dies, dass wir gespeicherte Wiederholungen nicht zwischen Xbox und PC teilen konnten.

Ein deterministisches Spiel ist nur dann deterministisch, wenn die identisch kompilierten Dateien verwendet und auf Systemen ausgeführt werden, die den IEEE-Standards entsprechen. Plattformübergreifend synchronisierte Netzwerksimulationen oder -wiederholungen sind nicht möglich.

AttackingHobo
quelle
2
Wie ich bereits erwähnte, interessiere ich mich hauptsächlich für C #. Da das JIT die eigentliche Kompilierung durchführt, kann ich nicht garantieren, dass es "mit denselben Optimierungseinstellungen kompiliert" wird, auch wenn dieselbe ausführbare Datei auf demselben Computer ausgeführt wird!
BlueRaja - Danny Pflughoeft
2
Manchmal ist der Rundungsmodus in der fpu anders eingestellt, auf einigen Architekturen hat die fpu ein überpräzises internes Register für Berechnungen ... während IEEE754 keinen Spielraum in Bezug auf die Funktionsweise von FP-Operationen gibt, tut es nicht. ' t spezifizieren, wie eine bestimmte mathematische Funktion implementiert werden soll, wodurch die architektonischen Unterschiede aufgedeckt werden können.
Stephen
4
@ 3nixios Mit dieser Art von Setup ist das Spiel nicht deterministisch. Nur Spiele mit einem festen Zeitschritt können deterministisch sein. Sie argumentieren, dass etwas nicht deterministisch ist, wenn Sie eine Simulation auf einem einzelnen Computer ausführen.
AttackingHobo
4
@ 3nixios, "Ich habe gesagt, dass selbst bei einem festen Zeitschritt nichts dafür sorgt, dass der Zeitschritt immer fest bleibt." Du liegst völlig falsch. Der Punkt eines festen Zeitschritts ist, immer die gleiche Deltazeit für jeden Tick beim Aktualisieren zu haben
AttackingHobo
3
@ 3nixios Durch die Verwendung eines festen Zeitschritts wird sichergestellt, dass der Zeitschritt behoben wird, da wir Entwickler dies nicht zulassen. Sie interpretieren falsch, wie die Verzögerung bei Verwendung eines festen Zeitschritts ausgeglichen werden soll. Jedes Spiel-Update muss dieselbe Update-Zeit verwenden. Wenn die Verbindung eines Peers verzögert ist, muss er dennoch jedes einzelne Update berechnen, das er verpasst hat.
Keeblebrox
3

Verwenden Sie Festkomma-Arithmetik. Oder wähle einen autorisierenden Server und lasse ihn von Zeit zu Zeit den Spielstatus synchronisieren - das ist, was MMORTS macht. (Zumindest funktioniert Elements of War so. Es ist auch in C # geschrieben.) Auf diese Weise haben Fehler keine Chance, sich anzusammeln.

Keine Ursache
quelle
Ja, ich könnte es zu einem Client-Server machen und mich mit den Problemen der clientseitigen Vorhersage und Extrapolation befassen. Bei dieser Frage geht es um Peer-to-Peer-Architekturen, die einfacher sein sollen ...
BlueRaja - Danny Pflughoeft
Nun, Sie müssen keine Vorhersage in einem Szenario "Alle Clients führen denselben Code aus" durchführen. Die Rolle des Servers soll nur die Autorität für die Synchronisation sein.
Nevermind
Server / Client ist nur eine Methode, um ein vernetztes Spiel zu erstellen. Eine andere beliebte Methode (vor allem für z. B. RTS - Spiele, wie C & C oder Starcraft) ist Peer-to-Peer, in denen es ist kein autoritativen Server. Damit dies möglich ist, müssen alle Berechnungen für alle Kunden vollständig deterministisch und konsistent sein - daher meine Frage.
BlueRaja - Danny Pflughoeft
Nun, es ist nicht so, dass Sie das Spiel unbedingt p2p ohne Server / gehobene Clients machen MÜSSEN. Wenn Sie es aber unbedingt müssen - dann verwenden Sie Fixpunkt.
Nevermind
3

Edit: Ein Link zu einer Festkommaklasse (Käufer aufgepasst! - Ich habe es nicht benutzt ...)

Sie könnten immer auf Festkomma- Arithmetik zurückgreifen . Jemand (macht ein RTS, nicht weniger) hat bereits die Arbeit am Stackoverflow gemacht .

Sie zahlen eine Leistungsstrafe, aber dies kann ein Problem sein oder auch nicht, da .net hier nicht besonders performant ist, da es keine simd-Anweisungen verwendet. Benchmark!

NB Anscheinend scheint jemand von Intel eine Lösung zu haben, mit der Sie die Intel Performance Primitives Library von c # verwenden können. Dies kann dazu beitragen, den Festpunktcode zu vektorisieren, um die langsamere Leistung zu kompensieren.

LukeN
quelle
decimalwürde auch dafür gut funktionieren; Aber dies hat immer noch die gleichen Probleme wie die Verwendung int- wie kann ich damit umgehen?
BlueRaja - Danny Pflughoeft
1
Am einfachsten wäre es, eine Nachschlagetabelle zu erstellen und zusammen mit der Anwendung zu senden. Sie können zwischen den Werten interpolieren, wenn die Genauigkeit ein Problem darstellt.
LukeN
Alternativ können Sie möglicherweise Trigger-Anrufe durch imaginäre Zahlen oder Quaternionen ersetzen (wenn 3D). Dies ist eine hervorragende Erklärung
LukeN
Dies kann auch helfen.
LukeN
In der Firma, für die ich gearbeitet habe, haben wir ein Ultraschallgerät mit Festkomma-Mathematik gebaut, damit es auf jeden Fall für Sie funktioniert.
LukeN
3

Ich habe an mehreren großen Titeln gearbeitet.

Kurze Antwort: Es ist möglich, wenn Sie wahnsinnig streng sind, aber wahrscheinlich nicht wert. Sofern Sie sich nicht auf einer festen Architektur (sprich: Konsole) befinden, ist sie heikel, spröde und mit einer Reihe von sekundären Problemen verbunden, wie z. B. einem späten Beitritt.

Wenn Sie einige der genannten Artikel lesen, werden Sie feststellen, dass es bizarre Fälle gibt, in denen Sie den CPU-Modus einstellen können, z. B. wenn ein Druckertreiber den CPU-Modus wechselt, weil er sich im selben Adressraum befindet. Ich hatte einen Fall, in dem eine Anwendung an ein externes Gerät gesperrt war, aber eine fehlerhafte Komponente verursachte, dass die CPU morgens und nachmittags aufgrund von Hitze und Bericht unterschiedlich gedrosselt wurde, was sie nach dem Mittagessen zu einem anderen Computer machte.

Diese Plattformunterschiede liegen im Silizium, nicht in der Software. Um Ihre Frage zu beantworten, ist auch C # betroffen. Anweisungen wie Fused Multiply-Add (FMA) vs ADD + MUL ändern das Ergebnis, da es intern nur einmal statt zweimal rundet. C gibt Ihnen mehr Kontrolle, um die CPU zu zwingen, das zu tun, was Sie wollen, indem Sie Operationen wie FMA ausschließen, um die Dinge "standard" zu machen - aber auf Kosten der Geschwindigkeit. Die Eigenheiten scheinen am anfälligsten zu sein, sich zu unterscheiden. Bei einem Projekt musste ich ein 150 Jahre altes Buch mit acos-Tabellen ausgraben, um Vergleichswerte zu erhalten und festzustellen, welche CPU "richtig" war. Viele CPUs verwenden Polynomapproximationen für Triggerfunktionen, jedoch nicht immer mit denselben Koeffizienten.

Meine Empfehlung:

Unabhängig davon, ob Sie eine Ganzzahlsperre oder eine Synchronisierung durchführen, müssen Sie die wichtigsten Spielmechanismen separat von der Präsentation behandeln. Bringen Sie das Spiel auf den Punkt, aber sorgen Sie sich nicht um die Genauigkeit der Präsentationsebene. Denken Sie auch daran, dass Sie nicht alle Daten der vernetzten Welt mit derselben Bildrate senden müssen. Sie können Ihre Nachrichten priorisieren. Wenn Ihre Simulation zu 99,999% übereinstimmt, müssen Sie nicht so oft senden, um gepaart zu bleiben. (Betrugsprävention beiseite.)

Es gibt einen schönen Artikel über die Source Engine, in dem eine Möglichkeit zur Synchronisierung erläutert wird: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Denken Sie daran, wenn Sie an einer späten Teilnahme interessiert sind, müssen Sie auf jeden Fall in die Kugel beißen und synchronisieren.

Lisa
quelle
1

Beachten Sie, dass ich hauptsächlich an C # interessiert bin, was meines Erachtens genau die gleichen Probleme wie C ++ in dieser Hinsicht hat.

Ja, C # hat dieselben Probleme wie C ++. Es hat aber auch viel mehr zu bieten.

Nehmen Sie zum Beispiel diese Aussage von Shawn Hawgraves:

Wenn Sie Wiederholungen als Controller-Eingaben speichern, können diese nicht auf Computern mit unterschiedlichen CPU-Architekturen, Compilern oder Optimierungseinstellungen wiedergegeben werden.

Es ist "einfach genug", um sicherzustellen, dass dies in C ++ geschieht. In C # wird es jedoch viel schwieriger, damit umzugehen. Dies ist JIT zu verdanken.

Was würde Ihrer Meinung nach passieren, wenn der Interpreter Ihren Code einmal interpretiert und dann das zweite Mal JIT macht? Oder interpretiert es es vielleicht zweimal auf dem Computer eines anderen, aber JIT ist es danach?

JIT ist nicht deterministisch, da Sie nur sehr wenig Kontrolle darüber haben. Dies ist eines der Dinge, die Sie aufgeben, um die CLR zu verwenden.

Und Gott helfe Ihnen, wenn eine Person .NET 4.0 verwendet, um Ihr Spiel auszuführen, während eine andere Person die Mono-CLR verwendet (natürlich unter Verwendung der .NET-Bibliotheken). Sogar .NET 4.0 und .NET 5.0 können unterschiedlich sein. Sie brauchen einfach mehr Kontrolle über die Details auf niedriger Ebene einer Plattform, um dies zu gewährleisten .

Sie sollten in der Lage sein, mit Festkomma-Mathematik davonzukommen. Aber das war es schon.

Nicol Bolas
quelle
Was ist anders als Mathe? Vermutlich werden "Eingabe" -Aktionen als logische Aktionen in einem RTS gesendet. ZB Einheit "a" auf Position "b" stellen. Ich sehe ein Problem mit der Zufallszahlengenerierung, aber das muss natürlich auch als Simulationseingabe gesendet werden.
LukeN
@LukeN: Das Problem ist, dass Shawns Position stark darauf hindeutet, dass Compilerunterschiede echte Auswirkungen auf die Gleitkomma-Mathematik haben können. Er würde mehr wissen als ich; Ich extrapoliere einfach seine Warnung in den Bereich der JIT- und C # -Kompilierung / -Interpretation.
Nicol Bolas
C # hat eine Überladung von Operatoren und einen eingebauten Typ für Festkomma-Mathematik. Dies hat jedoch die gleichen Probleme wie die Verwendung eines int- wie kann ich damit umgehen?
BlueRaja - Danny Pflughoeft
1
> Was würde Ihrer Meinung nach passieren, wenn der Interpreter Ihren Code einmal> interpretiert und dann das zweite Mal JIT-fähig macht? Oder interpretiert es es vielleicht zweimal auf der Maschine eines anderen, aber JIT ist es danach? 1. Der CLR-Code wird immer vor der Ausführung ausgegeben. 2. .net verwendet natürlich IEEE 754 für Floats. > JIT ist nicht deterministisch, da Sie sehr wenig Kontrolle darüber haben. Ihre Schlussfolgerung ist ziemlich schwache Ursache für falsche falsche Aussagen. > Und Gott helfe Ihnen, wenn eine Person .NET 4.0 verwendet, um Ihr Spiel auszuführen,> während eine andere Person die Mono-CLR verwendet (> natürlich unter Verwendung der .NET-Bibliotheken). Auch .NET
Romanenkov Andrey
@ Romanenkov: "Sie Schlussfolgerung ist ziemlich schwache Ursache für falsche falsche Aussagen." Sagen Sie mir bitte, welche Aussagen falsch und warum sind, damit sie korrigiert werden können.
Nicol Bolas
1

Nachdem ich diese Antwort geschrieben hatte, wurde mir klar, dass sie nicht wirklich die Frage beantwortet, bei der es speziell um Gleitkomma-Nichtdeterminismus ging. Aber vielleicht hilft ihm das trotzdem, wenn er auf diese Weise ein vernetztes Spiel machen will.

Neben der Freigabe von Eingaben, die Sie an alle Spieler senden, kann es sehr nützlich sein, eine Prüfsumme für wichtige Spielzustände wie Spielerpositionen, Gesundheit usw. zu erstellen und zu senden. Stellen Sie bei der Verarbeitung von Eingaben sicher, dass die Prüfsummen für den Spielzustand gültig sind Alle Remote-Player sind synchronisiert. Es ist garantiert, dass Sie nicht synchronisierte Fehler (OOS) haben, die behoben werden müssen, und dies wird es einfacher machen - Sie werden früher feststellen, dass etwas schief gelaufen ist (was Ihnen hilft, die Reproduktionsschritte herauszufinden), und Sie sollten in der Lage sein, weitere hinzuzufügen Protokollierung des Spielzustands im verdächtigen Code, damit Sie die Ursache des OOS ermitteln können.

Flip
quelle
0

Ich denke, die Idee aus dem Blog, die mit verknüpft ist, muss immer noch regelmäßig synchronisiert werden, damit sie umgesetzt werden kann. Ich habe genug Fehler in vernetzten RTS-Spielen gesehen, die diesen Ansatz nicht verfolgen.

Netzwerke sind verlustbehaftet, langsam, haben Latenz und können sogar Ihre Daten verschmutzen. "Fließkomma-Determinismus" (der so lebhaft klingt, dass ich skeptisch bin) ist in Wirklichkeit die geringste Sorge, die Sie haben ... vor allem, wenn Sie einen festen Zeitschritt verwenden. Bei variablen Zeitschritten müssen Sie zwischen festen Zeitschritten interpolieren, um auch Determinismusprobleme zu vermeiden. Ich denke, dies ist normalerweise das, was mit nicht-deterministischem "Gleitkomma" -Verhalten gemeint ist - nur dass variable Zeitschritte dazu führen, dass Integrationen auseinander gehen - und nichts mit mathematischen Bibliotheken oder Funktionen auf niedriger Ebene zu tun hat.

Die Synchronisation ist jedoch der Schlüssel.

jheriko
quelle
-2

Sie machen sie deterministisch. Ein gutes Beispiel finden Sie in der Dungeon Siege GDC-Präsentation , in der erläutert wird, wie die Standorte in der Welt vernetzbar gemacht wurden.

Denken Sie auch daran, dass Determinismus auch für zufällige Ereignisse gilt!

Doug-W
quelle
1
Das ist es, was das OP mit Gleitkomma wissen will.
Die kommunistische Ente