Le réseau dans les jeux vidéo

Bonjour, et bienvenue dans la traduction française du sixième article de la série d'articles « le réseau dans les jeux vidéo » écrits par Glenn Fiedler.

Dernièrement j'ai fait des recherches pour simuler la physique d'un jeu via des méthodes déterministes de synchronisation par pas.

L'idée de base est qu'au lieu de synchroniser l'état des objets physiques directement en envoyant sur le réseau les positions, orientations, vitesses, etc., on pourrait synchroniser implicitement la simulation en envoyant uniquement les actions du joueur (touches du clavier appuyées, position de la souris).

C'est une technique de synchronisation très intéressante parce que la quantité de données qui transitent dépend de la taille des entrées du joueur et non du nombre d'états physiques dans le jeu. En fait, cette technique est utilisée depuis des années dans les STR (stratégie temps réel - RTS, real time strategy) pour cette raison ; avec des milliers d'unités sur la carte, il y aurait beaucoup trop d'états à envoyer.

Vous avez peut-être une simulation physique complexe avec de nombreux états de corps rigide, ou des mouvements de vêtement ou de corps qui doivent rester parfaitement synchronisés parce qu'ils affectent le gameplay, mais vous ne pouvez pas vous permettre d'envoyer tous ces états. Il est clair que dans cette situation la seule solution est d'essayer la technique de synchronisation déterministe.

Mais un problème apparait. Les simulations physiques utilisent des nombres flottants pour leurs calculs, et pour plusieurs raisons, il est considéré très difficile d'obtenir le même résultat pour un même calcul sur deux machines différentes. Certains rapportent même des résultats différents entre deux exécutions sur une même machine, ou entre des versions debug et release. D'autres disent que les machines utilisant des processeurs AMD donnent un résultat différent de celles utilisant des processeurs Intel, et que les résultats d'un SSE sont différents de ceux d'un x87. Que se passe-t-il exactement ? Les calculs de nombres flottants sont-ils déterministes ou non ?

Malheureusement, la réponse n'est pas un simple « oui » ou « non », mais un timide « peut-être ».

Voici ce que j'ai découvert jusqu'à présent :

1. Si votre simulation est elle-même déterministe, avec un peu de labeur vous devriez pouvoir rejouer une série d'entrées enregistrées sur la même machine et obtenir le même résultat ;
2. Il est possible d'obtenir un résultat déterministe sur les calculs flottants sur plusieurs ordinateurs si vous utilisez un exécutable compilé avec le même compilateur, sur des machines avec la même architecture, en utilisant quelques astuces spécifiques à la plateforme ;
3. C'est incroyablement naïf d'espérer écrire du code utilisant des flottants en C ou C++ et s'attendre à avoir le même résultat sur différents compilateurs ou architectures ;
4. Mais avec suffisamment d'efforts, vous devriez pouvoir provoquer exactement les mêmes résultats flottants sur différents compilateurs ou architectures en utilisant le mode de compatibilité « strict » IEEE 754 et en restreignant les opérations utilisées. Ceci mène généralement à une diminution significative des performances lors des calculs sur nombres flottants.

Si vous voulez débattre sur ces points ou ajouter un élément, n'hésitez pas à écrire un commentaire ! Je considère ce sujet totalement ouvert et je suis très intéressé par toute expérience sur le déterminisme des simulations utilisant des calculs flottants. Particulièrement, merci de me contacter si vous avez réussi à obtenir des résultats binaires exacts sur différents compilateurs et architectures dans des situations réelles.

Voici ce que j'ai découvert via mes recherches jusque là…

Jon Watte, GameDev.net forums (http://www.gamedev.net/community/forums/topic.asp?topic_id=499435) 

La technologie que nous vendons à de nombreux clients est basée sur le déterminisme des flottants (y compris en 64 bits) et fonctionne ainsi depuis 2000.
Tant que vous vous en tenez à un seul compilateur, et un jeu d'instructions CPU unique, il est possible d'avoir des flottants totalement déterministes. Les spécificités vont avec la plateforme (c'est-à-dire, différences entre x86, x64 et PPC).
Vous devez vous assurer que la précision interne est définie à 64 bits (et non 80, parce que seul Intel l'implémente), et que le mode d'arrondi est cohérent. En plus, vous devez le vérifier après chaque appel à une DLL externe, parce que de nombreuses DLL (Direct3D, pilotes d'imprimante, bibliothèque audio, etc.) changent la précision ou le mode d'arrondi sans le remettre à son état d'origine.
L'ISA est compatible IEEE. Si votre implémentation x87 n'est pas IEEE, ce n'est pas x87.
De même, vous ne pouvez pas utiliser SSE ou SSE2 pour les flottants, c'est trop sous-spécifié pour être déterministe.

Elijah, Gas Powered Games (http://www.box2d.org/forum/viewtopic.php?f=3&t=1800) 

Je travaille chez Gas Powered Games et je peux vous dire dans un premier temps que les opérations sur flottants sont déterministes. Vous devez juste utiliser le même jeu d'instructions et le même compilateur et bien sûr le processeur de l'utilisateur doit suivre le standard IEEE 754, ce qui couvre tous nos clients sur PC et XBox 360. Le moteur sur lequel tourne DemiGod, Supreme Commander 1 et 2 repose sur le standard IEEE 754. Et probablement tous les RTS en peer to peer sur le marché. Dès que vous avez un jeu en réseau en peer to peer où chaque client broadcast les commandes à chaque « tick » pour que l'ordinateur distant rejoue la simulation physique, vous comptez sur le déterminisme des flottants.
Au démarrage de l'application, nous appelons :

_controlfp(_PC_24, _MCW_PC)
_controlfp(_RC_NEAR, _MCW_RC)

Puis, à chaque frame, nous utilisons des assertions pour vérifier que la configuration fpu (floating point unit) est toujours en place :

gpAssert( (_controlfp(0, 0) & _MCW_PC) == _PC_24 );
gpAssert( (_controlfp(0, 0) & _MCW_RC) == _RC_NEAR );

Il y a quelques fonctions dans l'API Microsoft qui peuvent changer le modèle fpu sans prévenir, vous devez donc forcer manuellement le mode après ces appels pour vous assurer qu'il n'y ait pas de différence entre les machines. L'assertion s'assure que personne n'a introduit de bogue avec le fpu.
Pour information, nous mettons le modèle flottant du compilateur sur Fast /fp:fast (mais ce n'est pas un prérequis).
Nous n'avons jamais eu de problème avec le standard IEEE sur un quelconque PC avec un CPU AMD ou Intel avec cette approche. Aucun de nos utilisateurs de SupCom ou Demigod n'a eu de problème avec sa machine non plus, et nous parlons de plus d'un million d'utilisateurs (supcom 1 + extension). Nous en aurions entendu parler, s'il y avait un problème avec les flottants puisque les replays ou le mode multijoueur ne marcheraient pas du tout.
Nous avons par contre eu quelques problèmes en utilisant certaines API physiques parce que leur code n'était pas conçu pour être déterministe ou reproductible. Par exemple certaines API ont des solveurs qui nécessitent X itérations où X peut être plus bas avec des CPU plus rapides.

Shawn Hargreaves, MSDN Blog (http://blogs.msdn.com/shawnhar/archive/2009/03/25/is-floating-point-math-deterministic.aspx) 

Si vous stockez un enregistrement comme des entrées de l'utilisateur, ils ne peuvent pas être joués sur des machines avec des architectures CPU, compilateurs, ou options d'optimisations différents. Dans MotoGP, ça signifiait qu'on ne pourrait pas partager les sauvegardes entre un PC et une Xbox. Ça voulait aussi dire que si nous avions sauvegardé un replay avec une version debug du jeu, il ne fonctionnerait pas avec une version release, et inversement. Ce n'est pas toujours un problème (nous n'avons jamais mis en boîte une version debug, après tout), mais si nous souhaitions sortir un patch, nous devons le créer en utilisant exactement le même compilateur que pour le jeu original. Si le compilateur a été mis à jour depuis, et que nous faisons un patch avec la nouvelle version, ça pourrait introduire des changements qui rendraient les replays sauvegardés auparavant impossible à rejouer correctement.
C'est fou ! Pourquoi ne faisons-nous pas en sorte que tous les matériels fonctionnent de la même manière ? Et bien, nous le pourrions, si l'on se moquait des performances. Nous pourrions dire « hey M. Hardware Guy, oubliez vos instructions folles de multiplication-addition croisées et donnez-nous juste une implémentation basique du standard IEEE », et « hey Compilo, s'il te plait n'essaye pas d'optimiser notre code ». De cette manière nos programmes tourneraient de manière homogène, lente, sur toutes les machines .

Ken Miller, Pandemic Studios (http://www.box2d.org/forum/viewtopic.php?f=4&t=175)

« Battlezone 2 utilise un modèle réseau de synchronisation par pas qui nécessite des résultats absolument identiques sur chaque client, jusqu'au plus petit bit de la mantisse, ou la simulation commencerait à diverger. Bien que ce fut difficile à obtenir, ça signifiait que nous avions besoin d'envoyer uniquement les entrées de l'utilisateur à travers le réseau ; tous les autres états du jeu pouvaient être calculés localement. Pendant le développement, nous avons découvert que les processeurs AMD et Intel produisaient des résultats un tantinet différents pour des fonctions transcendantes (cos, sin, tan et leurs inverses), nous avons donc dû les encapsuler dans des appels de fonctions non optimisées pour forcer le compilateur à les laisser à une précision unique. Ce fut suffisant pour rendre les processeurs AMD et Intel homogènes, mais c'était vraiment une expérience enrichissante.

Branimir Karadžić, Pandemic Studios (http://www.google.com/buzz/100111796601236342885/8hDZ655S6x3/Floating-Point-Determinism-Gaffer-on-Games) 

… Dans FSW1 quand une désynchronisation est détectée le joueur est instantanément tué par un « sniper magique » . Tout ceci a été corrigé dans FSW2. Nous utilisons juste des nombres flottants précis et les bibliothèques Havok FPU au lieu de SIMD sur PC. Le modulo entier est aussi un problème parce que la norme C++ indique que c'est « défini par l'implémentation » (dans le cas où plusieurs compilateurs/plateformes sont utilisés). En général j'apprécie les outils que nous avons développés pour la synchronisation par pas, qui ont rendu les désynchronisations triviales à trouver dans le code.

Yossi Kreinin, Consistency: how to defeat the purpose of IEEE floating point (http://www.yosefk.com/blog/consistency-how-to-defeat-the-purpose-of-ieee-floating-point.html) 

Je connais trois sources d'erreur principale :

• les optimisations algébriques du compilateur ;
• les instructions « complexes » comme le mélange d'additions et multiplications ou le sinus ;
• les spécificités x86 non disponibles sur toutes les plateformes ; non que ~100 % des appareils non embarqués soient une petite part de marché qui mérite de s'y attarder.

La bonne nouvelle c'est que la plupart des problèmes viennent du troisième point qui peut plus ou moins se résoudre automatiquement. Pour prendre cette décision (« devrions-nous investir dans la consistance des nombres flottants ou est-ce inutile ? »), je dirais que ce n'est pas inutile et si vous pouvez citer des avantages à tirer de cette consistance, alors ça vaut le coup.
Résumé : utilisez SSE2 ou SSE, et si vous ne pouvez pas, configurez le CSR (Control/Status Register - Registre de contrôle/statut) des nombres flottants pour utiliser les intermédiaires 64 bits et évitez les flottants 32 bits. Même cette dernière solution marche plutôt bien en pratique, tant que tout le monde en est conscient.

Todd Gamblin, Stack Overflow (http://stackoverflow.com/questions/968435/what-could-cause-a-deterministic-process-to-generate-floating-point-errors) 

La réponse courte est que les calculs à virgule flottante sont déterministes, d'après le standard IEEE, mais ça ne signifie pas qu'ils sont reproductibles sur différentes machines, différents compilateurs, OS, etc.
La réponse longue à ces questions et bien plus peut se trouver dans ce qui est probablement la meilleure référence sur les flottants, What Every Computer Scientist Should Know About Floating Point Arithmetic de David Goldberg. Lisez directement la section standard IEEE pour les détails importants.
Finalement, si vous faites la même séquence de calculs à virgule flottante avec les mêmes conditions initiales, alors tout devrait se dérouler exactement à l'identique. La séquence exacte peut changer selon votre compilateur/OS/bibliothèque standard, vous pourriez donc avoir quelques erreurs à ce niveau.
Les problèmes de flottants démarrent généralement avec une fonction numérique instable et l'utilisation de flottants en entrée qui sont approximativement les mêmes, mais pas exactement. Si votre fonction est stable, vous devriez pouvoir garantir la reproductibilité avec une certaine tolérance. Si vous voulez plus de détails que ça, regardez l'article de Goldberg ou un texte d'analyse numérique.

Günter Obiltschnig, Cross-Platform Issues with Floating-Point arithmetics in C++ (http://www.appinf.com/download/FPIssues.pdf) 

Le standard C++ ne spécifie aucune représentation binaire pour les types de nombres à virgule flottante float, double et long double. Bien que non requis par le standard, l'implémentation des calculs flottants utilisée par la majorité des compilateurs C++ se conforme à un standard, l'IEEE 754-1985, au moins pour les float et double. Ceci est directement lié au fait que les unités à virgule des CPU modernes supportent aussi ce standard. Le standard IEEE 754 spécifie le format binaire pour les nombres à virgule, ainsi que la sémantique des opérations. Cependant, le niveau de conformité des compilateurs à implémenter toutes les caractéristiques de IEEE 754 varie. Ceci crée différents pièges pour quiconque écrit du code portable utilisant des flottants en C++.

STREFLOP Library (http://nicolas.brodu.numerimoire.net/en/programmation/streflop/index.html) 

Les calculs à virgule flottante sont très dépendants de l'implémentation du FPU par le matériel, le compilateur et ses optimisations, et la bibliothèque mathématique du système (libm). Les expériences sont généralement reproductibles uniquement sur la même machine avec la même bibliothèque système et le même compilateur avec les mêmes options.

Intel C++ Compiler: Floating Point Consistency (http://www.nccs.nasa.gov/images/FloatingPoint_consistency.pdf) 

Objectifs de la programmation avec les nombres flottants (FP) :

• précision - produire des résultats « proches » de la valeur correcte ;
• reproductibilité - produire des résultats cohérents d'une exécution à l'autre. D'une configuration de compilation à l'autre. D'un compilateur à l'autre. D'une plateforme à l'autre ;
• performance - produire le code le plus efficace possible.

Ces points sont généralement conflictuels ! Une utilisation judicieuse des options du compilateur vous permet de trouver un compromis.

Intel C++ Compiler Manual (http://cache-www.intel.com/cd/00/00/34/76/347605_347605.pdf) 

Si la reproductibilité stricte et la cohérence sont importantes, ne modifiez pas l'environnement des nombres à virgule sans aussi utiliser l'option de modèle strict (fp-model strict - Linux ou Mac OS) ou /fp:strict (Windows) ou pragma fenv_access.

Microsoft Visual C++ Floating-Point Optimization (http://msdn.microsoft.com/en-us/library/aa289157(VS.71).aspx#floapoint_topic4) 

En mode fp:strict, le compilateur ne fait aucune optimisation qui pourrait perturber la précision des calculs à virgule flottante. Le compilateur arrondira toujours correctement les assignations, les conversions de type et appels de fonction, et les arrondis intermédiaires seront cohérents avec la précision des registres du FPU. Les sémantiques d'exception des nombres à virgule et la précision de l'environnement du FPU sont activées par défaut. Certaines optimisations, comme la contraction, sont désactivées parce que le compilateur ne peut pas garantir l'exactitude dans tous les cas.

Apple Developer Support (http://developer.apple.com/hardwaredrivers/ve/sse.html) 

Veuillez noter que les résultats des calculs à virgule flottante ne seront probablement pas identiques entre PowerPC et Intel, parce que les unités scalaires et vectorielles du FPU du PowerPC sont conçues autour d'une fusion de multiples opérations d'addition. Les puces Intel ont des additionneurs et multiplicateurs séparés, ce qui signifie que ces opérations doivent être faites séparément. Ainsi pour certaines étapes de calcul, le CPU Intel peut réaliser un arrondi supplémentaire, qui peut introduire une ou deux erreur(s) ULP pendant la phase de multiplication.

Intel Software Network Support (http://software.intel.com/en-us/forums/showthread.php?t=48339) 

Toutes les instructions qui sont des opérations IEEE (*, +, -, /, sqrt, comparaisons, qu'elles soient SSE ou X87) produiront le même résultat sur toutes les plateformes avec les mêmes options (mêmes précision et modes d'arrondi, remise à 0, etc.) et les mêmes entrées. Ceci est vrai pour les processeurs 32 bits et 64 bits… Pour les x87, les instructions transcendantes comme fsin, fcos, etc. pourraient produire des résultats légèrement différents selon la plateforme. Elles sont spécifiées avec une erreur garantie, mais non précises au bit près.

D. Monniaux on IEEE 754 mailing list (http://grouper.ieee.org/groups/754/email/msg03864.html) 

Je suis gêné par les possibles différences d'implémentation de IEEE 754 selon le matériel. Je suis déjà conscient des subtiles différences que peuvent introduire les langages de programmation entre le code source écrit et ce qui est exécuté au niveau assembleur. Maintenant, je m'intéresse aux différences entre, disons, Intel/SSE et PowerPC au niveau des instructions individuelles.

David Hough on 754 IEEE mailing list (http://grouper.ieee.org/groups/754/email/msg03867.html) 

On devrait… éviter les instructions non 754 qui deviennent plus fréquentes pour l'inverse et la racine carrée inverse qui ne sont pas arrondis correctement ni même avec cohérence d'une implémentation à une autre, tout comme les opérations transcendantales du x87 qui sont nécessairement implémentées différemment par AMD et Intel.

Nick Maclaren on 754 IEEE mailing list (http://grouper.ieee.org/groups/754/email/msg03872.html) 

Oui, avoir des résultats reproductibles EST possible. Mais vous ne pouvez PAS y parvenir sans définir une méthodologie de programmation pour y parvenir. Et ça a BIEN PLUS de conséquences que ses partisans ne veulent admettre - en particulier, c'est incompatible avec la plupart des formes de parallélisme.

Nick Maclaren on 754 IEEE mailing list (http://grouper.ieee.org/groups/754/email/msg03862.html) 

Si on parle d'aspect pratique, les choses sont différentes, et espérer un résultat répétable dans un programme réel c'est demander la lune. Mais nous y avons déjà été, et nous n'y retournerons pas une nouvelle fois.

Wikipedia Page on IEEE 754-2008 standard (http://en.wikipedia.org/wiki/IEEE_754-2008#Reproducibility) 

L'IEEE 754-1985 autorisait des variations dans l'implémentation (comme l'encodage de certaines valeurs et la détection de certaines exceptions). L'IEEE 754-2008 a renforcé la plupart d'entre elles, mais certaines variations subsistent (en particulier sur les formats binaires). La clause de reproductibilité recommande que les standards des langages doivent fournir un moyen d'écrire des programmes reproductibles (c'est-à-dire des programmes qui produiront le même résultat dans toutes les implémentations du langage), et décrire ce qui doit être fait pour obtenir des résultats reproductibles.

David Monniaux, The pitfalls of verifying floating-point computations (http://hal.archives-ouvertes.fr/docs/00/28/14/29/PDF/floating-point-article.pdf) 

Si l'on veut des sémantiques presque exactement fidèles aux calculs IEEE 754 à simple ou double précision dans le mode arrondi au plus proche, incluant le respect des conditions de dépassement de part et d'autre, on peut utiliser, en même temps, la limitation de la précision et des options et un style de programmation qui force les opérandes à être systématiquement écrits en mémoire entre chaque opération à virgule. Ceci mène à quelques pertes de performance ; de plus, il y aura toujours quelques écarts à cause du double arrondi sur le débordement par le bas.
Une solution plus simple pour les ordinateurs actuels est de simplement forcer le compilateur à utiliser l'unité SSE pour les calculs IEEE 754 ; cependant, la plupart des systèmes embarqués utilisant un microprocesseur IA32 ou un microcontrôleur n'ont pas de processeur équipé avec cette unité.

Peter Markstein, The New IEEE Standard for Floating Point Arithmetic (http://drops.dagstuhl.de/opus/volltexte/2008/1448/pdf/08021.MarksteinPeter.ExtAbstract.1448.pdf) 

6. Reproductibilité

Même dans la version de 1985 de IEEE 754, si deux implémentations du standard exécutaient une opération sur la même donnée, dans le même mode d'arrondi et avec la gestion des exceptions par défaut, le résultat de l'opération serait identique. Le nouveau standard essaye de décrire plus en détail quand un programme produira des résultats flottants identiques sur différentes implémentations. Les opérations décrites dans le standard sont toutes reproductibles.
Les opérations recommandées, comme des méthodes de bibliothèque ou des opérations de réduction, ne sont pas reproductibles, parce qu'elles ne sont pas requises dans toutes les implémentations. De même la dépendance sur le débordement bas et les marqueurs inexacts ne sont pas reproductibles parce que deux fonctions différentes de traitement du débordement sont autorisées pour conserver la conformité entre IEEE 754 (1985) et IEEE 754 (2008). Les modes d'arrondi sont des attributs reproductibles. Les attributs optionnels ne sont pas reproductibles.
L'utilisation d'optimisation de changement de valeur est à éviter pour viser la reproductibilité. Ceci inclut l'utilisation des lois d'association et de distribution, et la génération automatique de mélanges d'opérations de multiplications et additions quand le programmeur n'utilise pas explicitement cet opérateur.

Differences Among IEEE 754 Implementations (http://docs.sun.com/source/806-3568/ncg_goldberg.html#3098) 

Malheureusement, le standard IEEE ne garantit pas que le même programme fournira des résultats identiques sur tous les systèmes qui s'y conforment. La plupart des programmes produiront des résultats différents sur différents systèmes pour tout un tas de raisons. Une d'entre elles est que la plupart des programmes impliquent la conversion entre des formats binaires et décimaux, et le standard IEEE ne spécifie pas totalement la précision que doivent fournir de telles conversions. Une autre raison est que beaucoup de programmes utilisent des méthodes élémentaires fournies par une bibliothèque système, et le standard ne spécifie pas du tout ces méthodes. Bien sûr, la plupart des programmeurs connaissent ces caractéristiques trompeuses hors de portée du standard IEEE.
Beaucoup de programmeurs ne réalisent même pas qu'un programme qui utilise uniquement les formats numériques et opérations prescrites par le standard IEEE peut fournir des résultats différents sur différents systèmes. En fait, les auteurs du standard souhaitaient autoriser différentes implémentations pour obtenir différents résultats. Leurs intentions sont évidentes dans la définition de l'objectif du standard IEEE 754 : « Un objectif peut être à la fois explicitement désigné par l'utilisateur ou implicitement fourni par le système (par exemple, les résultats intermédiaires dans les sous-expressions ou paramètres de fonctions). Certains langages placent les résultats intermédiaires hors de contrôle de l'utilisateur. Toutefois, ce standard définit le résultat d'une opération en termes de format de destination et de valeurs d'opérandes. » (IEEE 754-1985, p. 7) En d'autres mots, le standard IEEE requiert que chaque résultat soit correctement arrondi à la précision finale, mais pas que la précision doive être déterminée par l'utilisateur du programme. Donc, différents systèmes peuvent fournir différents résultats avec des précisions différentes, ayant pour conséquence que le même programme produit différents résultats (parfois très différents), même si ces systèmes se conforment au standard.

Cet article est une traduction autorisée de l'article de Glenn Fiedler.

Merci aussi à Claude Leloup pour sa relecture orthographique.