Comment puis-je effectuer une simulation de physique déterministe?

43

Je crée un jeu de physique impliquant des corps rigides dans lequel les joueurs déplacent des pièces et des pièces pour résoudre un puzzle / une carte. Un aspect extrêmement important du jeu est que, lorsque les joueurs démarrent une simulation, celle-ci est identique partout , quel que soit leur système d'exploitation, leur processeur, etc.

Il y a de la place pour beaucoup de complexité et les simulations peuvent durer longtemps. Il est donc important que le moteur physique soit complètement déterministe en ce qui concerne ses opérations en virgule flottante, sinon une solution peut sembler "résoudre" sur la machine d'un joueur et "échouer" sur un autre.

Comment puis-je atteindre ce déterminisme dans mon jeu? Je suis prêt à utiliser divers cadres et langages, notamment Javascript, C ++, Java, Python et C #.

Box2D (C ++) et ses équivalents dans d’autres langages me tentent, même si cela semble répondre à mes besoins, mais il manque un déterminisme en virgule flottante, en particulier pour les fonctions trigonométriques.

La meilleure option que j'ai vue jusqu'à présent est l'équivalent Java de Box2D (JBox2D). Il semble tenter de déterminer le déterminisme à virgule flottante en utilisant StrictMathplutôt que Mathpour de nombreuses opérations, mais on ignore si ce moteur garantira tout ce dont j'ai besoin, car je n'ai pas encore construit le jeu.

Est-il possible d'utiliser ou de modifier un moteur existant pour répondre à mes besoins? Ou devrais-je construire un moteur moi-même?

EDIT: Ignorez le reste de ce post si vous ne vous souciez pas de savoir pourquoi quelqu'un aurait besoin d'une telle précision. Les personnes dans les commentaires et les réponses semblent croire que je cherche quelque chose que je ne devrais pas, et à ce titre, je vais expliquer davantage comment le jeu est censé fonctionner.

Le joueur reçoit un casse-tête ou un niveau contenant des obstacles et un but. Au départ, une simulation n'est pas en cours d'exécution. Ils peuvent ensuite utiliser des pièces ou des outils mis à leur disposition pour construire une machine. Une fois qu'ils ont appuyé sur démarrer, la simulation commence et ils ne peuvent plus modifier leur machine. Si la machine résout la carte, le joueur a battu le niveau. Sinon, ils devront appuyer sur Stop, modifier leur machine et réessayer.

La raison pour laquelle tout doit être déterministe est que je prévois de produire un code qui mappera chaque machine (un ensemble de pièces et d’outils qui tentent de résoudre un niveau) vers un fichier xml ou json en enregistrant la position, la taille et la rotation de chaque pièce. Il sera alors possible aux joueurs de partager des solutions (qui sont représentées par ces fichiers) afin de pouvoir vérifier les solutions, apprendre les unes des autres, organiser des compétitions, collaborer, etc. Bien sûr, la plupart des solutions sont résolues, en particulier la résolution simple ou rapide. ceux-ci, ne seront pas affectés par un manque de déterminisme. Mais les conceptions lentes ou complexes qui résolvent des niveaux très difficiles peuvent, et ce sont celles qui seront probablement les plus intéressantes et les plus intéressantes à partager.

jvn91173
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter . Si vous pensez avoir une solution au problème, pensez à l'afficher en tant que réponse plutôt qu'en commentaire - cela facilite la modification, l'évaluation via un vote / marquage accepté, ou la possibilité de commenter directement la suggestion elle-même pour obtenir un retour plutôt que le tissage des réponses dans un fil de conversation plus long.
DMGregory

Réponses:

45

Sur le traitement des nombres à virgule flottante de manière déterministe

La virgule flottante est déterministe. Eh bien, ça devrait l'être. C'est compliqué.

Il y a beaucoup de littérature sur les nombres à virgule flottante:

Et comment ils sont problématiques:

Pour résumé. Au moins, sur un seul thread, les mêmes opérations, avec les mêmes données, se déroulant dans le même ordre, devraient être déterministes. Ainsi, nous pouvons commencer par nous préoccuper des entrées et de la réorganisation.


Le temps est l’une des choses qui posent problème.

Tout d’abord, vous devez toujours calculer le même pas de temps. Je ne dis pas de ne pas mesurer le temps, je dis que vous ne passerez pas de temps à la simulation physique, car les variations dans le temps sont une source de bruit dans la simulation.

Pourquoi mesurez-vous le temps si vous ne le passez pas à la simulation physique? Vous souhaitez mesurer le temps écoulé pour savoir quand une étape de simulation doit être appelée et, en supposant que vous utilisiez le sommeil, combien de temps pour dormir.

Ainsi:

  • Temps de mesure: oui
  • Utiliser le temps en simulation: Non

Maintenant, réorganiser les instructions.

Le compilateur peut décider que f * a + bc'est la même chose b + f * a, mais que le résultat peut être différent. Il pourrait également compiler pour fmadd , ou décider de prendre plusieurs lignes comme celles-ci et de les écrire avec SIMD , ou une autre optimisation à laquelle je ne peux pas penser pour le moment. Et rappelez-vous que nous voulons que les mêmes opérations se déroulent dans le même ordre. Il est donc logique de vouloir contrôler quelles opérations ont lieu.

Et non, l'utilisation de double ne vous sauvera pas.

Vous devez vous préoccuper du compilateur et de sa configuration, en particulier pour synchroniser les nombres à virgule flottante sur le réseau. Vous devez obtenir que les versions acceptent de faire la même chose.

On pourrait soutenir que l'écriture d'assemblage serait idéale. De cette façon, vous décidez quelle opération faire. Cependant, cela pourrait poser un problème pour prendre en charge plusieurs plates-formes.

Ainsi:


Le cas des nombres à virgule fixe

En raison de la manière dont les flottants sont représentés en mémoire, les grandes valeurs vont perdre de la précision. Il va de soi que le fait de garder vos valeurs faibles (clamp) atténue le problème. Ainsi, pas de vitesses énormes et pas de grandes salles. Ce qui signifie également que vous pouvez utiliser la physique discrète car vous avez moins de risque de tunneling.

D'autre part, de petites erreurs vont s'accumuler. Donc, tronquer. Je veux dire, redimensionnez et convertissez en un type entier. De cette façon, vous savez que rien ne se construit. Il y aura des opérations que vous pouvez faire en restant avec le type entier. Lorsque vous devez revenir en virgule flottante, vous lancez et annulez la mise à l'échelle.

Notez que je dis l'échelle. L'idée est que 1 unité sera réellement représentée par une puissance de deux (16384 par exemple). Quoi que ce soit, faites-en une constante et utilisez-la. Vous l'utilisez essentiellement comme un nombre à virgule fixe. En fait, si vous pouvez utiliser beaucoup mieux les nombres à virgule fixe appropriés d'une bibliothèque fiable.

Je dis tronqué. À propos du problème d'arrondi, cela signifie que vous ne pouvez pas faire confiance au dernier bit de la valeur que vous avez obtenue après la distribution. Donc, avant la distribution, obtenez un peu plus que nécessaire et tronquez-le par la suite.

Ainsi:

  • Gardez les valeurs petites: Oui
  • Arrondissement prudent: oui
  • Numéros de points fixes lorsque possible: Oui

Attends, pourquoi as-tu besoin de virgule flottante? Ne pourriez-vous pas travailler uniquement avec un type entier? Oh, c'est vrai. Trigonométrie et radication. Vous pouvez calculer des tables pour la trigonométrie et le rayonnement et les faire cuire dans votre source. Vous pouvez également implémenter les algorithmes utilisés pour les calculer avec un nombre à virgule flottante, à l'exception de l'utilisation de nombres à virgule fixe. Oui, vous devez équilibrer la mémoire, les performances et la précision. Pourtant, vous pouvez rester en dehors des nombres en virgule flottante et rester déterministe.

Saviez-vous qu'ils ont fait ce genre de choses pour la PlayStation d'origine? S'il vous plaît rencontrer mon chien, des correctifs .

En passant, je ne dis pas de ne pas utiliser de virgule flottante pour les graphiques. Juste pour la physique. Je veux dire, bien sûr, les positions dépendront de la physique. Cependant, comme vous le savez, un collisionneur ne doit pas nécessairement correspondre à un modèle. Nous ne voulons pas voir les résultats de la troncature des modèles.

Ainsi: UTILISEZ DES NUMÉROS DE POINTS FIXES.


Pour être clair, si vous pouvez utiliser un compilateur qui vous permet de spécifier le fonctionnement des points flottants et que cela vous suffit, vous pouvez le faire. Ce n'est pas toujours une option. De plus, nous le faisons pour le déterminisme. Les nombres à point fixe ne signifient pas qu’il n’ya pas d’erreurs, après tout, leur précision est limitée.

Je ne pense pas que "nombre de points fixe sont difficiles" est une bonne raison de ne pas les utiliser. Et si vous voulez une bonne raison de les utiliser, c'est le déterminisme, en particulier le déterminisme sur toutes les plateformes.


Voir également:


Addendum : Je suggère de garder la taille du monde petite. Cela dit, les deux OP et Jibb Smart soulignent le fait que s’éloigner des flotteurs d’origine ont moins de précision. Cela aura un effet sur la physique, un phénomène qui sera vu beaucoup plus tôt que les confins du monde. Les nombres de points fixes, ainsi, ont une précision fixe, ils seront également bons (ou mauvais, si vous préférez) partout. Ce qui est bon si nous voulons le déterminisme. Je tiens également à mentionner que la manière dont nous pratiquons habituellement la physique a la propriété d’amplifier de petites variations. Voir L'effet papillon - Physique déterministe dans The Incredible Machine and Maker .


Une autre façon de faire de la physique

Je pensais que la petite erreur de précision dans les nombres en virgule flottante s’expliquait parce que nous effectuons des itérations sur ces nombres. À chaque étape de la simulation, nous prenons les résultats de la dernière étape de la simulation et les remplaçons. Cumul d'erreurs après sommet d'erreurs. C'est ton effet papillon.

Je ne pense pas que nous verrons une seule construction utilisant un seul thread sur la même machine donner une sortie différente par la même entrée. Pourtant, sur une autre machine, cela pourrait ou une construction différente.

Il y a un argument pour tester là-bas. Si nous décidons exactement comment les choses devraient fonctionner et que nous pouvons tester sur du matériel cible, nous ne devrions pas proposer de versions ayant un comportement différent.


Cependant, il y a aussi un argument pour ne pas travailler ailleurs qui accumule tant d'erreurs. C'est peut-être une occasion de faire de la physique d'une manière différente.

Comme vous le savez peut-être, il existe une physique continue et discrète, les deux travaillent sur la progression de chaque objet sur le pas de temps. Cependant, la physique continue a le moyen de déterminer le moment de la collision au lieu de sonder différents instants possibles pour voir si une collision s'est produite.

Ainsi, je propose ce qui suit: utilisez les techniques de la physique continue pour déterminer quand la prochaine collision de chaque objet se produira, avec un pas de temps important, beaucoup plus important que celui d’une seule étape de simulation. Ensuite, prenez l’instant de collision le plus proche et déterminez où tout se trouvera à cet instant.

Oui, cela représente beaucoup de travail d’une seule étape de simulation. Cela signifie que la simulation ne démarrera pas instantanément ...

... Cependant, vous pouvez simuler les prochaines étapes de la simulation sans vérifier chaque fois la collision, car vous savez déjà quand la prochaine collision se produira (ou qu'aucune collision ne se produira dans le grand intervalle de temps). De plus, les erreurs accumulées dans cette simulation sont sans importance car une fois que la simulation a atteint le pas de temps important, nous ne faisons que placer les positions que nous avons calculées auparavant.

Nous pouvons maintenant utiliser le budget-temps que nous aurions utilisé pour vérifier les collisions à chaque étape de la simulation afin de calculer la collision suivante après celle trouvée. C’est-à-dire que nous pouvons simuler l’avance en utilisant le grand pas de temps. En supposant un monde de portée limitée (cela ne fonctionnera pas pour des jeux énormes), il devrait y avoir une file d’états futurs pour la simulation, puis chaque image que vous venez d’interpoler du dernier état à l’autre.


Je plaiderais pour une interpolation. Cependant, étant donné qu'il y a des accélérations, nous ne pouvons pas simplement tout interpoler de la même manière. Au lieu de cela, nous devons interpoler en prenant en compte l'accélération de chaque objet. D'ailleurs, nous pourrions simplement mettre à jour la position de la même manière que nous le faisons pour le grand pas de temps (ce qui signifie également qu'il est moins sujet aux erreurs parce que nous n'utiliserions pas deux implémentations différentes pour le même mouvement).


Remarque : Si nous faisons ces nombres à virgule flottante, cette approche ne résout pas le problème des objets se comportant différemment à mesure qu'ils s'éloignent de l'origine. Cependant, s'il est vrai que la précision est perdue au fur et à mesure que l'on s'éloigne de l'origine, cela reste déterministe. En fait, c’est la raison pour laquelle cela n’a même pas été abordé à l’origine.


Addenda

De OP en commentaire :

L'idée est que les joueurs pourront sauvegarder leurs machines dans un format quelconque (tel que xml ou json), de manière à enregistrer la position et la rotation de chaque morceau. Ce fichier xml ou json sera ensuite utilisé pour reproduire la machine sur l’ordinateur d’un autre joueur.

Donc, pas de format binaire, non? Cela signifie que nous devons également nous inquiéter de savoir si les nombres en virgule flottante récupérés correspondent à l'original. Voir: La précision du flotteur revisitée: portabilité du flotteur à neuf chiffres

Theraot
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Vaillancourt
2
Très bonne réponse! 2 points supplémentaires en faveur du point fixe: 1. la virgule flottante se comportera différemment de l'origine (si vous avez le même puzzle à un endroit différent), mais pas du point fixe; 2. le point fixe a en réalité plus de précision que le point flottant pour la majeure partie de sa portée - vous pouvez gagner en précision en utilisant bien le point fixe
Jibb Smart
Il est possible de coder des données binaires à la fois en XML et en JSON à l'aide d' base64éléments. Ce n'est pas un moyen efficace de représenter de grandes quantités de telles données, mais il est incorrect de laisser entendre qu'elles empêchent l'utilisation de représentations binaires.
Pikalek
1
@Pikalek, je suis au courant, OP m'a posé des questions à ce sujet, j'ai mentionné base64 comme une option parmi d'autres, y compris hex, réinterpréter la conversion en tant qu'int, et utiliser le format protobuf, car personne ne comprendra ces fichiers de toute façon, ils ne le sont pas (non formés). ) lisible par l'homme. Ensuite - je suppose - un mod a supprimé les commentaires (non, ce n'est pas dans le chat lié ci-dessus). Est-ce que cela se reproduira? Devrais-je enlever cela de la réponse? Devrais-je le faire plus longtemps?
Theraot
@Theraot Ah, je vois comment j'aurais pu interpréter cela différemment dans le contexte des commentaires supprimés depuis. (FWIW, j'ai lu toutes les discussions sur cette réponse et cette question). Et même s’il existait un moyen natif et efficace d’encoder les données, il restait à s’assurer que cela signifiait la même chose sur toutes les plateformes. Étant donné le taux de désabonnement, il vaut peut-être mieux le laisser tel quel. Merci de clarifier!
Pikalek
6

Je travaille pour une entreprise qui réalise un certain jeu de stratégie en temps réel et je peux vous affirmer que le déterminisme en virgule flottante est possible.

L'utilisation de différents compilateurs, ou du même compilateur avec des paramètres différents, ou même de versions différentes du même compilateur, peut briser le déterminisme.

Si vous avez besoin d'un jeu croisé entre les plates-formes ou les versions de jeu, alors vous devez aller en virgule fixe. Le seul jeu croisé possible dont je suis au courant avec virgule flottante se situe entre PC et XBox1, mais c'est assez fou.

Vous devrez soit trouver un moteur physique entièrement déterministe, soit utiliser un moteur open source et le rendre déterministe, ou lancer votre propre moteur. De prime abord, j'ai le sentiment qu'Unity a ajouté un moteur de physique déterministe, mais je ne suis pas sûr qu'il soit simplement déterministe sur la même machine ou sur toutes les machines.

Si vous voulez essayer de faire votre propre travail, voici quelques conseils utiles:

  • Les flotteurs IEE754 sont déterministes si vous ne faites rien de trop fruité (google "déterminisme IEE754" pour plus d’informations sur ce qui est couvert ou non)
  • Vous devez vous assurer que chaque client a son mode d'arrondi et sa précision définis de manière identique (utilisez controlfp pour le définir)
  • Le mode d'arrondi et la précision peuvent être modifiés par certaines bibliothèques mathématiques. Par conséquent, si vous utilisez des bibliothèques fermées, vous pouvez les vérifier après avoir passé des appels (utilisez à nouveau controlfp pour vérifier)
  • certaines instructions SIMD sont déterministes, beaucoup ne le sont pas, soyez prudent
  • comme mentionné ci-dessus, pour assurer le déterminisme, vous avez également besoin de la même plate-forme, de la même version exacte du même compilateur, en compilant la même configuration, avec les mêmes paramètres de compilateur
  • construisez des outils pour détecter les désynchronisations d'état et aidez-les à les diagnostiquer - par exemple, CRC indique chaque image à détecter lorsqu'une désynchronisation se produit, puis vous pouvez activer un mode de journalisation détaillée vous permettant d'activer les modifications apportées à l'état du jeu dans un fichier, puis prenez 2 fichiers issus de simulations désynchronisées, et comparez-les dans un outil de comparaison pour voir où tout va mal
  • initialise toutes vos variables dans l'état du jeu, source majeure de désynchronisation
  • la simulation de jeu entière doit se dérouler exactement dans le même ordre à chaque fois pour éviter les désynchronisations, il est très facile de se tromper, il est conseillé de structurer la simulation de jeu de manière à minimiser ce problème. Je ne suis vraiment pas un type de modèle de conception de logiciel, mais dans ce cas, c'est probablement une bonne idée - vous pouvez envisager un type de modèle dans lequel la simulation de jeu ressemble à une boîte sécurisée, et le seul moyen de transformer l'état du jeu consiste à l'insérer. "messages" ou "commandes", avec uniquement un accès const fourni pour tout ce qui est en dehors de l'état du jeu (rendu, mise en réseau, etc.). Ainsi, la mise en réseau de la simulation pour un jeu multijoueur consiste à envoyer ces commandes sur le réseau, ou à rejouer la même simulation, à enregistrer le flux de commandes dès le début,
Joe
la source
1
Unity travaille en effet vers un objectif de déterminisme inter-plateformes avec son nouveau système Unity Physics pour sa pile de technologies orientée données, mais si je comprends bien, il s’agit toujours d’un travail en cours et pas encore complet / prêt à l’emploi.
DMGregory
Quel est un exemple d'instruction SIMD non déterministe? Pensez-vous à des approximations comme rsqrtps?
Ruslan
@DMGregory doit être dans l'aperçu, car vous pouvez déjà l'utiliser - mais comme vous le dites, il se peut qu'il ne soit pas encore terminé.
Joe
@Ruslan oui rsqrtps / rcpps les résultats dépendent de la mise en œuvre
Joe
5

Je ne sais pas si c'est le type de réponse que vous recherchez, mais une autre solution pourrait consister à exécuter les calculs sur un serveur central. Demandez aux clients d’envoyer la configuration à votre serveur, laissez-le effectuer la simulation (ou en récupérer une mise en cache) et renvoyer les résultats, qui sont ensuite interprétés par le client et traités sous forme de graphiques.

Bien sûr, cela supprime tout projet éventuel d’exécution du client en mode hors connexion et, selon l’intensité des calculs, vous aurez peut-être besoin d’un serveur très puissant. Ou plusieurs, mais au moins vous avez la possibilité de vous assurer qu'ils ont la même configuration matérielle et logicielle. Une simulation en temps réel peut être difficile mais pas impossible (pensez aux flux vidéo en direct - ils fonctionnent, mais avec un léger retard).

Glorfindel
la source
1
Je suis complètement d'accord. C’est ainsi que vous garantissez une expérience partagée avec tous les utilisateurs. gamedev.stackexchange.com/questions/6645/… aborde un sujet similaire en comparant la différence entre la physique côté client et la physique côté serveur.
Tim Holt
1

Je vais faire une suggestion contre-intuitive selon laquelle, même si elle n'est pas fiable à 100%, devrait fonctionner correctement la plupart du temps et est très facile à mettre en œuvre.

Réduisez la précision.

Utilisez une taille de pas de temps constante prédéterminée, effectuez la physique sur chaque pas de temps dans un float double précision standard, puis quantifiez la résolution de toutes les variables pour simple précision (ou quelque chose de pire encore) après chaque pas. Ensuite, la plupart des écarts que la réorganisation en virgule flottante pourrait éventuellement introduire (par rapport à un cycle de référence du même programme) seront éliminés, car ces écarts se produisent sous forme de chiffres qui n'existent même pas avec une précision réduite. Ainsi, la déviation n’aura pas la chance d’une accumulation de Lyapunov (effet papillon) qui finirait par devenir notable.

Bien sûr, la simulation sera légèrement moins précise que ce qu’elle pourrait être (comparée à la physique réelle), mais ce n’est pas vraiment remarquable tant que toutes les exécutions de votre programme sont inexactes. de la même manière .

Maintenant, techniquement parlant, il est bien sûr possible qu'un réordonnancement provoque une déviation qui atteigne un chiffre de signification supérieure, mais si les déviations ne sont réellement causées que par un flottant et que vos valeurs représentent des quantités physiques continues, cela est extrêmement improbable. Notez qu'il existe un demi-milliard de doublevaleurs entre deux valeurs quelconques single, de sorte que l'on peut s'attendre à ce que la grande majorité des pas de temps dans la plupart des simulations soient exactement les mêmes d'une exécution à l'autre. Les rares cas où une déviation réussit à travers la quantification seront, espérons-le, dans des simulations qui ne durent pas aussi longtemps (du moins pas avec une dynamique chaotique).


Je vous recommanderais également d’envisager l’approche complètement opposée à ce que vous demandez: embrasser l’incertitude ! Si le comportement est légèrement non déterministe, il s'agit en fait d'une approche plus proche des expériences réelles en physique. Alors, pourquoi ne pas délibérément randomiser les paramètres de départ pour chaque exécution de simulation et en faire une obligation pour que la simulation réussisse de manière cohérente sur plusieurs essais? Cela en apprendra beaucoup plus sur la physique et sur la façon de concevoir des machines suffisamment robustes / linéaires, plutôt que sur des machines ultra-fragiles qui ne sont réalistes que dans une simulation.

à gauche autour de
la source
Arrondir ne servira à rien, car si le résultat de haute précision n'est pas déterministe, il finira par arrondir le résultat d'une manière sur un système et de l'autre sur un autre système. Par exemple, vous pouvez toujours arrondir au nombre entier le plus proche, mais un ordinateur système 1.0 et un autre calculent 0.999999999999999999999999999999999999 et ils s’arrondissent différemment.
Yoyo
Oui c'est possible, comme je l'ai déjà dit dans la réponse. Mais cela arrivera extrêmement rarement , comme le font les autres problèmes de la physique des jeux. Donc arrondi ne l' aide. (Je n’aurais pas arrondi si; arrondir au plus proche pour éviter la
partialité
0

Créez votre propre classe pour stocker des nombres!

Vous pouvez forcer un comportement déterministe si vous savez exactement comment les calculs seront effectués. Par exemple, si les seules opérations que vous traitez sont la multiplication, la division, l’addition et la soustraction, il suffirait alors de représenter tous les nombres comme un simple nombre rationnel. Pour ce faire, une simple classe Rational ferait l'affaire.

Mais si vous souhaitez gérer des calculs plus complexes (éventuellement des fonctions trigonométriques, par exemple), vous devrez alors écrire ces fonctions vous-même. Si vous voulez pouvoir prendre le sinus d'un nombre, vous devez pouvoir écrire une fonction qui se rapproche du sinus d'un nombre tout en n'utilisant que les opérations mentionnées ci-dessus. Tout cela est faisable et, à mon avis, contourne une grande partie des détails velus dans les autres réponses. Le compromis est que vous aurez plutôt à faire face à des calculs.

Hahahh Jaddy Amal
la source
3
L'arithmétique rationnelle est totalement impraticable pour toute sorte d'intégration numérique. Même si chaque pas de temps ne le fait que * / + -les dénominateurs deviendront de plus en plus grands avec le temps.
gauche du
Je m'attendrais à ce que même sans considérer l'intégration, ce ne serait pas une bonne solution car après seulement quelques multiplications ou divisions, les nombres représentant votre numérateur et votre dénominateur débordent d'un nombre entier de 64 bits.
jvn91173
0

Il y a une certaine confusion de terminologie ici. Un système physique peut être complètement déterministe, mais impossible à modéliser pour une période de temps utile car son comportement est extrêmement sensible aux conditions initiales, et une modification infiniment petite des conditions initiales produira des comportements complètement différents.

Voici une vidéo d'un appareil réel dont le comportement est intentionnellement imprévisible, sauf d'un point de vue statistique:

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

Il est facile de construire des systèmes mathématiques simples (utilisant seulement l'addition et la multiplication) où le résultat après N étapes dépend de la N'-ème décimale des conditions de départ. Écrire un logiciel pour modéliser un tel système de manière cohérente, quel que soit le matériel informatique et les logiciels que l'utilisateur peut avoir, est quasiment impossible - même avec un budget suffisamment grand pour le test l'application sur toutes les combinaisons possibles de matériel et de logiciel.

Le meilleur moyen de résoudre ce problème est d’attaquer le problème à sa source: assurez-vous que la physique de votre jeu est aussi déterministe que nécessaire pour obtenir des résultats reproductibles.

L’autre solution consiste à essayer de le rendre déterministe en modifiant le logiciel afin de modéliser quelque chose qui n’est pas conforme à la physique. Le problème est que vous avez introduit plusieurs couches de complexité supplémentaires dans le système, par rapport à une modification explicite de la physique.

Par exemple, supposons que votre jeu implique des collisions de corps rigides. Même si vous ignorez les frictions, la modélisation exacte des collisions entre des objets de formes arbitraires susceptibles de tourner à mesure qu'ils se déplacent est pratiquement impossible. Mais si vous modifiez la situation de sorte que les seuls objets soient des briques rectangulaires non rotatives, la vie devient beaucoup plus simple. Si les objets de votre jeu ne ressemblent pas à des briques, masquez-le avec des graphismes "non physiques" - par exemple, cachez littéralement l'instant de collision derrière de la fumée ou des flammes, ou une bulle de texte de dessin animé "Ouch" ou peu importe.

Le joueur doit découvrir la physique du jeu en jouant. Peu importe si ce n'est pas «totalement réaliste», à condition que ce soit cohérent avec soi-même et suffisamment similaire à l'expérience du sens commun pour être plausible.

Si vous faites que la physique elle-même se comporte de manière stable, un modèle informatique de celle-ci peut également produire des résultats stables, du moins en ce sens que les erreurs d'arrondi n'auront aucune pertinence.

Alephzero
la source
1
Je ne vois aucune confusion dans la terminologie. Le PO veut un comportement déterministe d’un système potentiellement chaotique. C'est tout à fait faisable.
Marc
L'utilisation de formes plus simples (telles que des cercles et des rectangles) ne change en rien le problème. Vous avez encore besoin de beaucoup de fonctions trigonométriques, de sqrt, etc ...
jvn91173
-1

Utilisez la précision double en virgule flottante au lieu de la précision en virgule flottante simple . Bien que pas parfait, il est suffisamment précis pour être considéré comme déterministe dans votre physique. Vous pouvez envoyer une fusée sur la Lune avec une précision double, mais pas avec une précision unique.

Si vous avez vraiment besoin d'un déterminisme parfait, utilisez les mathématiques à points fixes . Cela vous donnera moins de précision (si vous utilisez le même nombre de bits), mais des résultats déterministes. Je ne suis au courant d'aucun moteur physique qui utilise le calcul mathématique à point fixe. Vous devrez peut-être écrire le vôtre si vous souhaitez emprunter cette voie. (Quelque chose que je déconseille.)

Evorlor
la source
11
L'approche en double précision va à l'encontre de l'effet papillon . Dans un système dynamique (comme une simulation physique), même une infime déviation dans les conditions initiales peut s'amplifier par le retour, créant une boule de neige pouvant aller jusqu'à une erreur perceptible. Tous les chiffres supplémentaires ne font que retarder cela un peu plus longtemps - obligeant la boule de neige à rouler un peu plus loin avant qu'elle ne devienne assez grosse pour causer des problèmes.
DMGregory
2
Deux erreurs à la fois: 1) Les points flottants doubles rencontrent les mêmes problèmes et ne font généralement que reporter le problème à un avenir de plus en plus difficile à résoudre. 2) Il n’existe aucune règle stipulant que le point fixe doit être moins précis que le nombre à virgule flottante. Selon l’échelle et le problème à résoudre, ou selon la mémoire que vous êtes prêt à utiliser par nombre de points fixes, elles peuvent être moins précises, plus ou moins précises. Cela n'a pas de sens de dire "ils sont moins précis".
phresnel
@phresnel, à titre d'exemple de précision en virgule fixe, la série IBM 1400 utilisait des calculs décimaux à précision fixe en virgule fixe. Dédiez 624 chiffres à chaque numéro et vous aurez dépassé la plage et la précision de la virgule flottante double précision.
Marc
@phresnel (2) Bon point. J'ai mis à jour ma réponse pour supposer le même nombre de bits.
Evorlor
-2

Utilisez le modèle de mémento .

Lors de votre exécution initiale, sauvegardez les données de position de chaque image ou de tout autre point de repère nécessaire. Si c'est trop peu performant, ne le faites que toutes les n images.

Ensuite, lorsque vous reproduisez la simulation, suivez la physique arbitraire, mais mettez à jour les données de position toutes les n images.

Pseudo-code trop simplifié:

function Update():
    if(firstRun) then (SaveData(frame, position));
    else if(reproducedRun) then (this.position = GetData(frame));
Evorlor
la source
9
Je ne pense pas que cela fonctionne pour OP. Disons que vous et moi jouons tous les deux le jeu sur des systèmes différents. Chacun de nous place les pièces du puzzle de la même manière - une solution qui n’avait pas été prédite à l’avance par le développeur. Lorsque vous cliquez sur "Démarrer", votre PC simule la physique de manière à ce que la solution aboutisse. Lorsque je fais la même chose, une petite différence dans la simulation fait que ma solution (identique) n’est pas jugée aussi performante. Ici, je n’ai pas l’occasion de consulter le souvenir de votre parcours réussi, car c’est arrivé sur votre machine, pas au moment du développement.
DMGregory
@DMGregory C'est correct. Merci.
jvn91173