Comment les jeux déterministes sont-ils possibles face au non-déterminisme à virgule flottante?

52

Pour créer un jeu comme un RTS en réseau, j'ai vu un certain nombre de réponses suggérer de rendre le jeu complètement déterministe; Ensuite, il vous suffit de transférer les actions des utilisateurs les uns aux autres et de décaler ce qui est affiché afin de "verrouiller" l'entrée de tout le monde avant le rendu de la prochaine image. Ensuite, des éléments tels que les positions de l'unité, la santé, etc., n'ont pas besoin d'être constamment mis à jour sur le réseau, car la simulation de chaque joueur sera exactement la même. J'ai également entendu la même chose suggérée pour faire des replays.

Cependant, puisque les calculs en virgule flottante ne sont pas déterministes entre les machines, ou même entre différentes compilations du même programme sur la même machine, est-ce vraiment possible? Comment pouvons-nous empêcher ce fait de causer de petites différences entre les joueurs (ou les replays) qui se répercutent tout au long du jeu ?

J'ai entendu dire que certaines personnes suggèrent d'éviter complètement les nombres à virgule flottante et d'utiliser intpour représenter le quotient d'une fraction, mais cela ne me semble pas pratique - que faire si j'ai besoin, par exemple, de prendre le cosinus d'un angle? Dois-je sérieusement réécrire toute une bibliothèque de mathématiques?

Notez que je suis principalement intéressé par C # qui, autant que je sache, a exactement les mêmes problèmes que C ++ à cet égard.

BlueRaja - Danny Pflughoeft
la source
5
Ce n'est pas une réponse à votre question, mais pour résoudre le problème de réseau RTS, je vous recommanderais de temps en temps de synchroniser les positions et la santé de l'unité afin de corriger toute dérive. Le type d’information à synchroniser dépend du jeu; vous pouvez optimiser l'utilisation de la bande passante en évitant de synchroniser des éléments tels que les effets de statut.
Jhocking
@jhocking Pourtant, c'est probablement la meilleure réponse.
Jonathan Connell
starcraft II infacti ne synchronise exactement que de temps en temps, j’ai regardé le gameplay avec mes amis côte à côte et là où il y avait des différences (aussi significatives), en particulier avec un retard important (1 sec). J'avais des unités qui avaient 6 carrés de carte sur leur écran respectant le sien
GameDeveloper

Réponses:

15

Les points flottants sont-ils déterministes?

Il y a quelques années, j’ai beaucoup lu sur cette question lorsque je voulais écrire un RTS en utilisant la même architecture lockstep que celle que vous utilisez.

Mes conclusions sur les points flottants du matériel sont les suivantes:

  • Le même code d'assemblage natif est probablement déterministe à condition que vous soyez prudent avec les indicateurs de virgule flottante et les paramètres du compilateur.
  • Un projet open source RTS a affirmé avoir obtenu des compilations déterministes C / C ++ sur différents compilateurs à l'aide d'une bibliothèque wrapper. Je n'ai pas vérifié cette affirmation. (Si je me souviens bien, c'était à propos de la STREFLOPbibliothèque)
  • Le JET .net a un peu de marge de manoeuvre. En particulier, il est permis d'utiliser une précision supérieure à celle requise. En outre, il utilise différents jeux d'instructions sur x86 et AMD64 (je pense que sur x86, il utilise le x87, AMD64 utilise certaines instructions SSE dont le comportement diffère pour les dénormations).
  • Les instructions complexes (y compris la fonction trigonométrique, les exponentielles, les logarithmes) sont particulièrement problématiques.

J'ai conclu qu'il était impossible d'utiliser les types à virgule flottante intégrés dans .net de manière déterministe.

Solutions de contournement possibles

Ainsi j'avais besoin de solutions de contournement. J'ai considéré:

  1. Implémenter FixedPoint32en C #. Bien que ce ne soit pas trop difficile (ma mise en œuvre est presque terminée), la très petite plage de valeurs rend son utilisation gênante. Vous devez faire attention à tout moment pour ne pas déborder, ni perdre trop de précision. En fin de compte, j'ai trouvé que ce n'était pas plus facile que d'utiliser des entiers directement.
  2. Implémenter FixedPoint64en C #. J'ai trouvé cela plutôt difficile à faire. Pour certaines opérations, des entiers intermédiaires de 128 bits seraient utiles. Mais .net ne propose pas un tel type.
  3. Utilisez du code natif pour les opérations mathématiques qui est déterministe sur une plate-forme. Engendre la surcharge d'un appel de délégué pour chaque opération mathématique. Perd la capacité de courir sur plusieurs plates-formes.
  4. Utilisez Decimal. Mais c'est lent, prend beaucoup de mémoire et jette facilement des exceptions (division par 0, débordements). C'est très bien pour une utilisation financière, mais pas bon pour les jeux.
  5. Implémentez une virgule flottante 32 bits personnalisée. Cela semblait plutôt difficile au début. L'absence d'un élément intrinsèque BitScanReverse provoque quelques inconvénients lors de la mise en œuvre.

Mon softfloat

Inspiré par votre message sur StackOverflow , je viens de commencer à implémenter un logiciel de type virgule flottante 32 bits et les résultats sont prometteurs.

  • La représentation en mémoire est compatible binaire avec les flottants IEEE. Je peux donc réinterpréter les conversions lors de leur sortie en code graphique.
  • Il supporte les sous-formes, les infinis et les NaN.
  • Les résultats exacts ne sont pas identiques aux résultats IEEE, mais cela n'a généralement pas d'importance pour les jeux. Dans ce type de code, il importe seulement que le résultat soit le même pour tous les utilisateurs, non pas qu'il soit précis au dernier chiffre.
  • La performance est décente. Un test trivial a montré qu'il peut faire environ 75MFLOPS comparé à 220-260MFLOPS avec floatune addition / multiplication (Single thread sur un i66 à 2.66 GHz). Si quelqu'un a de bons points de repère en virgule flottante pour .net, envoyez-les-moi, car mon test actuel est très rudimentaire.
  • L'arrondi peut être amélioré. Actuellement, il est tronqué, ce qui correspond approximativement à l’arrondi vers zéro.
  • C'est encore très incomplet. Actuellement, la division, les conversions et les opérations mathématiques complexes manquent.

Si quelqu'un souhaite contribuer aux tests ou améliorer le code, contactez-moi ou envoyez une demande de tirage sur github. https://github.com/CodesInChaos/SoftFloat

Autres sources d'indéterminisme

Il existe également d’autres sources d’indéterminisme dans .net.

  • itérer sur un Dictionary<TKey,TValue>ou HashSet<T>retourne les éléments dans un ordre indéfini.
  • object.GetHashCode() diffère d'une course à l'autre.
  • L'implémentation de la Randomclasse intégrée n'est pas spécifiée, utilisez la vôtre.
  • Le multithreading avec verrouillage naïf conduit à une réorganisation et à des résultats différents. Faites très attention à utiliser les fils correctement.
  • Quand WeakReferences perdent leur cible, c'est indéterministe car le GC peut être exécuté à tout moment.
CodesInChaos
la source
23

La réponse à cette question provient du lien que vous avez posté. Plus précisément, vous devriez lire la citation de Gas Powered Games:

Je travaille à Gas Powered Games et je peux vous affirmer que les mathématiques en virgule flottante sont déterministes. Vous avez juste besoin du même jeu d'instructions et du même compilateur et, bien entendu, le processeur de l'utilisateur adhère à la norme IEEE754, qui inclut tous nos clients PC et 360. Le moteur qui fait fonctionner DemiGod, Supreme Commander 1 et 2 repose sur la norme IEEE754. Sans parler de tous les autres jeux peer to peer RTS du marché.

Et puis en dessous de celui-ci se trouve ceci:

Si vous stockez des relectures en tant qu'entrées de contrôleur, elles ne peuvent pas être lues sur des ordinateurs dotés d'architectures de processeur, de compilateurs ou de paramètres d'optimisation différents. En MotoGP, cela signifiait que nous ne pouvions pas partager les rediffusions enregistrées entre Xbox et PC.

Un jeu déterministe ne sera déterministe que lorsque vous utiliserez des fichiers compilés de manière identique et que celui-ci sera exécuté sur des systèmes conformes aux normes IEEE. Les simulations de réseau multiplates-formes ou les relances ne seront pas possibles.

Attaquer
la source
2
Comme je l'ai mentionné, je m'intéresse principalement à C #; étant donné que JIT effectue la compilation proprement dite, je ne peux pas garantir qu'il soit "compilé avec les mêmes paramètres d'optimisation", même si le même exécutable est exécuté sur le même ordinateur!
BlueRaja - Danny Pflughoeft le
2
Parfois, le mode d'arrondi est défini différemment dans le fpu. Sur certaines architectures, le fpu a un registre interne plus grand que la précision pour les calculs ... alors que IEEE754 ne laisse aucune marge quant à la façon dont les opérations de PF doivent fonctionner, elles ne le sont pas. t spécifier comment une fonction mathématique particulière doit être mise en œuvre, ce qui peut révéler les différences architecturales.
Stephen le
4
@ 3nixios Avec ce type d'installation, le jeu n'est pas déterministe. Seuls les jeux avec un pas de temps fixe peuvent être déterministes. Vous dites que quelque chose n'est pas déjà déterministe lorsque vous exécutez une simulation sur une seule machine.
Attaquer contre
4
@ 3nixios, "je disais que même avec un pas de temps fixe, rien ne garantit que le pas de temps restera toujours fixe." Vous avez entièrement tort. Le point d'un pas de temps fixe est d'avoir toujours le même temps delta pour chaque tick dans la mise à jour
AttackingHobo
3
@ 3nixios L'utilisation d'un horodatage fixe garantit que celui-ci sera corrigé, car les développeurs ne le permettent pas autrement. Vous interprétez mal la manière dont le décalage devrait être compensé lors de l'utilisation d'un pas de temps fixe. Chaque mise à jour de jeu doit utiliser la même heure de mise à jour; par conséquent, lorsque la connexion d'un pair est à la traîne, il doit toujours calculer chaque mise à jour individuelle manquée.
Keeblebrox
3

Utilisez des arithmétiques à point fixe. Ou choisissez un serveur faisant autorité et synchronisez l'état du jeu de temps en temps - c'est ce que font les MMORTS. (Du moins, Elements of War fonctionne comme ceci. Il est également écrit en C #.) De cette façon, les erreurs ne risquent pas de s’accumuler.

Ça ne fait rien
la source
Oui, je pourrais en faire un client-serveur et gérer les problèmes de prédiction et d'extrapolation côté client. Cette question concerne les architectures entre homologues, qui sont supposées être plus faciles ...
BlueRaja - Danny Pflughoeft
Eh bien, vous n'avez pas besoin d'effectuer de prédiction dans un scénario "Tous les clients exécutent le même code". Le rôle du serveur doit être l'autorité sur la synchronisation uniquement.
Nevermind
Serveur / client n'est qu'un moyen de créer un jeu en réseau. Une autre méthode populaire (surtout pour les ex. Jeux RTS, comme C & C ou Starcraft) est peer-to-peer, dans lequel il est aucun serveur faisant autorité. Pour que cela soit possible, tous les calculs doivent être complètement déterministes et cohérents pour tous les clients - d'où ma question.
BlueRaja - Danny Pflughoeft le
Eh bien, ce n’est pas comme si vous DEVEZ absolument rendre le jeu strictement P2P sans serveurs / clients élevés. Si vous devez absolument, utilisez alors un point fixe.
Nevermind
3

Edit: un lien vers une classe à point fixe (attention acheteur - je ne l'ai pas utilisé ...)

Vous pouvez toujours avoir recours à l' arithmétique en virgule fixe. Quelqu'un (qui fabrique des droits, pas moins) a déjà effectué le travail sur le stackoverflow .

Vous devrez payer une pénalité de performance, mais cela peut ne pas être un problème, car .net ne sera pas particulièrement performant ici car il n’utilisera pas les instructions simd. Référence!

NB Apparemment, quelqu'un chez intel semble avoir une solution pour vous permettre d’utiliser la bibliothèque de primitives de performances intel de c #. Cela peut aider à vectoriser le code en virgule fixe pour compenser les performances plus lentes.

LukeN
la source
decimalfonctionnerait bien pour cela aussi; mais, cela a toujours les mêmes problèmes que d’utiliser int- comment puis-je déclencher avec elle?
BlueRaja - Danny Pflughoeft
1
Le moyen le plus simple serait de créer une table de recherche et de l'envoyer à côté de l'application. Vous pouvez interpoler entre les valeurs si la précision pose problème.
LukeN
Vous pouvez également remplacer les appels de trig par des nombres imaginaires ou des quaternions (si 3D). C'est une excellente explication
LukeN
Cela peut aussi aider.
LukeN
Dans l'entreprise pour laquelle je travaillais, nous avons construit une machine à ultrasons à l'aide de calculs mathématiques en virgule fixe. Elle fonctionnera donc parfaitement pour vous.
LukeN
3

J'ai travaillé sur un certain nombre de gros titres.

Réponse courte: C'est possible si vous êtes incroyablement rigoureux, mais n'en valez probablement pas la peine. À moins que vous n'ayez une architecture fixe (lire: console), elle est complexe, fragile et présente une foule de problèmes secondaires, tels qu'une jointure tardive.

Si vous lisez certains des articles mentionnés, vous remarquerez que, si vous pouvez définir le mode de fonctionnement du processeur, vous rencontrerez des cas bizarres, par exemple lorsqu'un pilote d'imprimante bascule le mode de traitement parce qu'il se trouvait dans le même espace d'adressage. Dans certains cas, une application avait été verrouillée par une application sur un périphérique externe, mais un composant défectueux provoquait un étranglement du processeur en raison de la chaleur et des rapports différents le matin et l'après-midi, ce qui en faisait un ordinateur différent après le déjeuner.

Ces différences de plate-forme se trouvent dans le silicium, pas dans le logiciel. Par conséquent, pour répondre à votre question, C # est également concerné. Des instructions telles que multiplier-ajouter fusionné (FMA) vs ADD + MUL changent le résultat car il arrondit en interne une seule fois au lieu de deux. C vous donne plus de contrôle pour forcer le processeur à faire ce que vous voulez en excluant des opérations comme FMA pour rendre les choses «standard», mais au détriment de la vitesse. Les éléments intrinsèques semblent être les plus susceptibles de différer. Sur un projet, j'ai dû extraire un livre de tableaux acos vieux de 150 ans pour obtenir des valeurs à comparer afin de déterminer quel processeur était "correct". De nombreux processeurs utilisent des approximations polynomiales pour les fonctions trig, mais pas toujours avec les mêmes coefficients.

Ma recommandation:

Que vous optiez pour une synchronisation ou un pas à pas entier, gérez les mécanismes de jeu séparément de la présentation. Assurez la précision du jeu, mais ne vous inquiétez pas de la précision de la couche de présentation. N'oubliez pas non plus que vous n'avez pas besoin d'envoyer toutes les données mondiales en réseau au même débit. Vous pouvez hiérarchiser vos messages. Si votre simulation correspond à 99,999%, vous n'aurez pas besoin de transmettre aussi souvent pour rester apparié. (Prévention de la triche à part.)

Il y a un bel article sur le moteur source qui explique une façon de synchroniser: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Rappelez-vous que si vous êtes intéressé par une participation tardive, vous devrez quand même vous en prendre à la synchronisation.

Lisa
la source
1

Notez que je suis principalement intéressé par C # qui, autant que je sache, a exactement les mêmes problèmes que C ++ à cet égard.

Oui, C # a les mêmes problèmes que C ++. Mais il a aussi beaucoup plus.

Par exemple, prenons cette déclaration de Shawn Hawgraves:

Si vous stockez des relectures en tant qu'entrées de contrôleur, elles ne peuvent pas être lues sur des ordinateurs dotés d'architectures de processeur, de compilateurs ou de paramètres d'optimisation différents.

Il est "assez facile" de faire en sorte que cela se produise en C ++. En C # , cependant, ce sera beaucoup plus difficile à gérer. C'est grâce à JIT.

Que pensez-vous qu'il se passerait si l'interprète exécutait votre code une fois interprété, puis que JIT le répète une seconde fois? Ou peut-être qu'il l'interprète deux fois sur la machine de quelqu'un d'autre, mais JIT l'a-t-il après?

JIT n'est pas déterministe, car vous avez très peu de contrôle sur elle. C’est l’une des choses que vous abandonnez pour utiliser le CLR.

Et que Dieu vous aide si une personne utilise .NET 4.0 pour exécuter votre jeu, tandis que quelqu'un d'autre utilise Mono CLR (en utilisant les bibliothèques .NET bien sûr). Même .NET 4.0 contre .NET 5.0 pourrait être différent. Vous avez simplement besoin de davantage de contrôle sur les détails de bas niveau d'une plate-forme pour garantir ce genre de chose.

Vous devriez être capable de vous en sortir avec des maths à points fixes. Mais c'est à peu près tout.

Nicol Bolas
la source
Mis à part le calcul, quoi d'autre est susceptible d'être différent? Vraisemblablement, les actions "input" sont envoyées en tant qu'actions logiques dans un réseau. Par exemple, déplacez l'unité "a" vers la position "b". Je peux voir un problème avec la génération de nombres aléatoires, mais cela doit évidemment aussi être envoyé comme entrée de simulation.
LukeN
@LukeN: Le problème est que la position de Shawn suggère fortement que les différences de compilateur peuvent avoir des effets réels sur les calculs en virgule flottante. Il en saurait plus que moi; J'extrapole simplement son avertissement dans le domaine de la compilation / interprétation JIT et C #.
Nicol Bolas
C # a surchargé les opérateurs et possède également un type intégré pour les mathématiques en virgule fixe. Cependant, cela pose les mêmes problèmes que d’utiliser un int- comment puis-je faire du trig avec?
BlueRaja - Danny Pflughoeft
1
> Qu'est-ce que vous supposez qu'il se passerait si l'interprète exécutait votre code> interprété une fois, puis que JIT le répète une seconde fois? Ou peut-être> l'interprète-t-il deux fois sur la machine de quelqu'un d'autre, mais JIT est-il après> ça? 1. Le code CLR est toujours jit avant l'exécution. 2. .net utilise IEEE 754 pour les flotteurs bien sûr. > JIT n'est pas déterministe, car vous avez très peu de contrôle sur elle. Votre conclusion est une cause assez faible de fausses déclarations fausses. > Et que Dieu vous aide si une personne utilise .NET 4.0 pour exécuter votre jeu,> pendant qu'une autre personne utilise le Mono CLR (en utilisant les bibliothèques .NET de> course). Même .NET
Romanenkov Andrey
@Romanenkov: "Votre conclusion est une cause assez faible de fausses déclarations fausses." Dites-moi quelles déclarations sont fausses et pourquoi, afin qu’elles puissent être corrigées.
Nicol Bolas
1

Après avoir écrit cette réponse, je me suis rendu compte qu'elle ne répondait pas vraiment à la question, qui portait spécifiquement sur le non-déterminisme à virgule flottante. Mais peut-être que cela l’aidera quand même s’il va créer un jeu en réseau de cette manière.

En plus du partage d’entrée que vous diffusez à tous les joueurs, il peut être très utile de créer et de diffuser une somme de contrôle sur l’état important du jeu, telle que la position du joueur, la santé, etc. Lors du traitement de l’entrée, affirmez que tous les lecteurs distants sont synchronisés. Vous aurez la garantie de pouvoir corriger les bogues non synchronisés (OOS), ce qui facilitera la tâche - vous recevrez un avis préalable indiquant que quelque chose ne va pas (ce qui vous aidera à comprendre les étapes de la reproduction), et vous devriez pouvoir en ajouter davantage. consignation de l’état du jeu dans un code suspect pour vous permettre de mettre entre parenthèses la cause du problème.

Flip
la source
0

Je pense que l'idée du blog liée à la nécessité d'une synchronisation périodique est toujours viable - j'ai vu suffisamment de bugs dans les jeux RTS en réseau qui n'acceptent pas cette approche.

Les réseaux sont à perte, lents, ont du temps de latence et peuvent même polluer vos données. Le "déterminisme à virgule flottante" (ce qui semble assez prétentieux pour me rendre sceptique) est le moindre de vos soucis dans la réalité ... surtout si vous utilisez un pas de temps fixe. avec des pas de temps variables, vous devrez aussi interpoler entre des pas de temps fixes pour éviter les problèmes de déterminisme. Je pense que c'est généralement ce que l'on entend par comportement "déterministe" non déterministe - ce n'est que le fait que les pas de temps variables entraînent une divergence des intégrations - rien à voir avec les bibliothèques mathématiques ou les fonctions de bas niveau.

La synchronisation est la clé cependant.

Jheriko
la source
-2

Vous les rendez déterministes. Pour un bon exemple, consultez la présentation de Dungeon Siege GDC sur la manière dont les sites du monde peuvent être mis en réseau.

Rappelez-vous également que le déterminisme s'applique également aux événements «aléatoires»!

Doug-W
la source
1
C’est ce que le PO veut savoir faire, en virgule flottante.
Le canard communiste