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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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!