Article rédigé par Xfennec – Raydium – CQFD Corp OpenGL 3D engine –
J’écris depuis quelques temps un moteur de jeux 3D, libre, gratuit, amateur, comme vous voulez et ce projet est l’occasion pour moi de rentrer dans le détail de l’implémentation des moteurs 3D, du netcode, de la physique et de tout le reste.
Afin de vous faire partager mon intérêt, voici un petit article qui devrait vous aider à mieux comprendre comment fonctionnent les moteurs physiques.[–SUITE–]Les principes de base
En ce qui me concerne, j’utilise Open Dynamics Engine, (ODE), le seul moteur physique libre disponible. Même s’il est moins connu que Havok ou Novodex, il reste un moteur très capable. Par exemple, des jeux comme STALKER ou Xpand Rally l’utilisent en partie. On voit aussi passer sur la mailing-list des gens d’Epic, de Serious Sam 2, etc. ODE utilise une license Open Source et son usage est gratuit.
Les principes internes d’ODE restent les mêmes que ceux des autres moteurs du genre, il décompose les objets du jeu en 2 grandes catégories : les corps (body) et les géométries (geom).
Les Geoms
Exemple de geom disponibles dans ODE
Avant de positionner une simple caisse dans un jeu, il faut passer par deux étapes. Avant tout, il faut donner une forme à l’objet pour pouvoir déterminer comment les autres objets entreront en contact avec lui. C’est la partie « détection de collision » qui s’occupe de ça, en utilisant donc des geoms. En général, les moteurs physiques offrent des (formes) primitives : sphère, boite, cylindre à bords plats, cylindre à bords arrondis, rayon. Pour en revenir à notre caisse, nous utiliserons évidemment le gemo de la boîte.
Approximations de geom complexes
Avec ces différentes formes et en en mélangeant plusieurs s’il le faut, on arrive à approximer à peu près n’importe quelle forme. Ces approximations engendrent les légères erreurs qu’on retrouve dans certains jeux au niveau des collisions.
Pour les cas plus complexes, les moteurs fournissent généralement une autre primitive : le trimesh. Il s’agit tout simplement d’un modèle 3D (souvent une version simplifiée de l’objet 3D que l’on affiche) qui est utilisé pour déterminer les contours de l’objet en question. Cette méthode est rarement utilisée dans les jeux à cause de la complexité des calculs qu’elle engendre.
Les Bodies
Une fois notre caisse dotée d’une forme (geom), il faut lui associer plusieurs paramêtres purement physiques : masse, centre de gravité, tenseur d’inertie, etc. C’est cet aspect qui est géré par le « body » de la caisse.
Les bodies réagissent donc de manière réaliste aux solicitations extérieurs (contacts, forces, gravité) déduites entre autres par son geom. Les éléments de décors sont parfois traités de manière particulière s’ils sont statiques comme le sol par exemple : il n’ont qu’une geom et pas de body. Ainsi, ils ne « subissent » pas la physique, mais sont capables d’agir avec des objets physiques.
Les contacts
Lorsque qu’on objet, un ballon par exemple, s’approche de notre caisse, le moteur physique détecte une collision potentielle entre les deux objets. En général, cette détection est réalisée au moyen des AABB.
Pour faire simple, les AABB sont des boites qui englobent chaque objet ou groupe d’objets de la scène. Sur l’image ci-contre, les geoms sont dessinées en rouge et les AABB en bleu. Vous noterez que les AABB sont alignées entre elles et sur les axes du monde, quelle que soit la rotation de l’objet qu’elles entourent.
Du fait de leur simplicité, il est très rapide de déterminer sir deux AABB se recouvrent. Si c’est le cas, alors les geoms à l’intérieur de ces boites sont probablement en collision. Ce n’est qu’à ce moment que le moteur physique va demander un test plus précis entre les deux objets au moyen de leur véritable géométrie. Au passage, cela signifie donc qu’un moteur physique de ce type ne détecte une collision que si les deux objets concernés s’interpénètrent.
Si la collision est validée, le moteur génère des points de contact. Le nombre de points varit selon les géométries concernées : par exemple, une sphère ne génère qu’un seul point de contact par plan (une sphère parfaite qui roule sur un sol parfait n’a qu’un seul point d’appuis) alors qu’une boite va en générer au moins trois. Ces points de contact possèdent des coordonnées permettant de déterminer à quel endroit précis de la caisse le ballon est rentré. Ils possèdent aussi une force qui indique la puissance de l’impact et une normale qui donne la direction dans laquelle la force doit être appliquée.
Le but de ces points de contact est de revenir à une situation normale. En effet, pour un moteur de simulation physique des corps rigides, deux objets ne peuvent pas s’interpénétrer (situation anormale) et les points de contact sont donc là pour que les objets se repoussent entre eux lorsqu’ils se rentrent dedans.
Si la caisse de notre exemple tombe à cause du « choc », ou plutôt devrions-nous dire à cause de la pénétration de la balle et que cette balle est elle même repoussée, c’est bien parce que deux contacts ont été générés (un sur le body de la caisse, l’autre sur celui de la balle) et ont « poussé » les deux objets. C’est aussi pour cette raison que la caisse ne traverse pas le sol : il y a un contact sol-caisse.
Les autres contraintes
Les contacts font partie d’une famille qui se nomme « contraintes » et dont le rôle est de « gêner » les déplacement des objets en appliquant des forces virtuelles sur ces derniers. On y retrouve les articulations habituelles : charnières, suspensions, pivots, rotules, etc.
Ces contraintes sont évidemment appliquées à deux bodies au minimum et elle peuvent être motorisées.
Il est possible de produire à peu près n’importe quel assemblage en combinant ces contraintes. On utilise de nombreuses contraintes pour simuler les articulations du corps humain et produire des effets de pantin crédibles (ragdoll).
Le temps
La gestion du temps est un aspect beaucoup plus complexe qu’il n’y parait. C’est en effet à la charge du programmeur de gérer le « World Stepping » : l’avancée du temps dans le monde. Il faut, à chaque image, expliquer au moteur physique de combien d’unités de temps il doit avancer les objets. Et là, ça se complique…
La première idée qui vient, c’est de mesurer le temps de rendu de la dernière frame et d’avancer le temps d’autant. Par exemple, si on a un rendu à 100FPS, la dernière frame durera 10ms et il faudra faire avancer le temps de 0.01s. Si on a un rendu de 10FPS (une frame toutes les 100ms), on avancera de 0.1 seconde. Malheureusement, cette méthode ne fonctionne pas :
Avancer le temps de une unité de 0.1s n’est pas du tout la même chose que d’avancer le temps de dix unités de 0.01s chacune. En effet, la détection de collision n’est effectuée qu’une fois pour l’ensemble d’une incrémenation du temps, quelle soit de 10ms ou de 100ms. Les collisions seraient donc dix fois moins précises lorsque le jeu tourne à 10 FPS qu’à 100 FPS. En fonction de votre nombre de FPS, les balles vont traverser les murs ou non : si la détection de collision est précise, la collision balle-mur va être détectée alors que si le jeu rame, elle ne le sera pas. Les balles sont très sensibles à ce genre de problèmes car ce sont des objets TRES véloces et aussi très petits. Bref, ça ne peut pas fonctionner.
L’astuce consiste à choisir un « timestep » fixe et à répeter l’avancée du temps autant de fois qu’il le faut entre chaque frame. Fixons par exemple le timestep 0,01s. Si le jeu tourne à 100 FPS, il affiche une image toutes les 0,01s donc entre chaque image il suffit de faire avancer le temps d’une unité (un step). Si le jeu ralenti à 10 FPS et qu’il ne calcule plus qu’une image toutes les 0.1s, il faudra par contre faire avancer le temps de 10 steps entre deux images.
On arrive alors à un système logique : l’avancée du temps est synchronisée sur le temps réel. Dans notre exemple, on simulera les physiques à un fréquence de 100 Hz quelque soit le framerate du jeu. Il est bien sur possible de changer cette fréquence pour créer des effets de ralentis ou geler le jeu pendant un moment.
Malheureusement, effectuer une telle synchronisation en réseau, au travers du net, avec des dizaines de joueurs est un véritable cauchemar pour le programmeur devant écrire un netcode capable de gérer la physique. C’est pour cette raison qu’actuellement la plupart des effets calculés par les moteurs physiques n’ont qu’une utilisation purement esthétique en multiplayer : nul doute que les animations de ragdoll sont différentes chez les autres joueurs que chez vous mais tant que ça n’influe pas sur le gamplay, ça n’a pas d’importance.
L’explosion
Vous avez peut-être déjà observé que certains objets, notamment les cadavres, sont soudaint pris de soubresauts au moment de toucher le sol. C’est là le signe annonciateur d’un phénomène très redouté des programmeur de moteurs physiques : l’explosion. Je ne saurais trop vous expliquer les véritables raisons de ce problème : un truc relatif aux intégrateurs de premier ordre ou quelque chose dans le genre. Ce phénomène vient aussi du relatif manque de précision de nos processeurs qui arrondissent certains calculs.
Quoi qu’il en soit, quelque foit une erreur se trouve intégrée dans le monde et elle a de très fortes chances d’être amplifiée à chaque itération… Et les itérations, comme nous avons pu le voir, peuvent s’enchaîner très très vite : plus de 100 par seconde dans notre précédent exemple. Bref, ça tourne vite à l’explosion, les objets sont dégagés en hyper-espace, on retrouve du NaN (not a number) et du inf (infini) partout et en général ça se termine par un plantage de l’application.
L’erreur initiale est souvent minime, elle peut être introduite par le FPU de la machine qui fait un arrondi trop fort et/ou une génération de points de contacts hasardeuse. Par exemple, <a href='les ragdolls sont souvent modélisées par un ensemble de boites reliées entre elles par des articulations type rotule ou charnière (ball ou hinge). Or, si on met de coté les trimesh, les boites sont les formes ou la génération de contact est la plus compliquée.
Pour illustrer ça, imaginez le problème suivant : comment faire tenir une boite en l’air en la posant sur trois têtes d’épingle (trois points de contacts) ? Difficile, surtout quand il faut trouver un algorithme capable de déterminer le point de contact des trois têtes d’épingles plusieurs dizaines de milliers de fois par secondes, quelle que soit l’orientation de la boite.
En fait, la génération de contacts n’est pas toujours très propre entre deux boites ou entre une boite et un trimesh (le sol), mais dans 99,999% des cas c’est sans aucune conséquence. Le pourcentage restant, c’est lorsque la génération « échoue » (solution dégénérée). Si elle échoue, il n’y a pas de point de contact générés et sans points de contact, un body retrouve son comportement naturel : il tombe. Résultat, à l’itération suivante, le moteur de détection se retrouve avec un objet enfoncé dans un autre, il en déduit que l’objet en question devait arriver vachement vite pour être enfoncé si profondément et le repousse donc violemment dans le sens inverse (hop ! un soubresaut). Si tout ca ne tourne pas à l’explosion, c’est parce que cette situation est bien connue et que les jeux utilisent des solvers itératifs* bien moins sujet aux explosions que les solvers-à-grosses-matrices ™.
En résumé, les développeurs préfèrent une génération de contact très rapide mais pas toujours fiable (bien que ce ne soit pas si loin de la perfection) et avoir un mécanisme derrière qui soit capable de corriger les problèmes en douceur. Ce mécanisme est en général complété par une méthode de détection des objets stables qui sont désactivés s’ils restent dans une position et une orientation quasi-identiques pendant un temps donné. Ils sont réactivés dès qu’une force est appliquée ou dès qu’une nouvelle collision est détectée.
Si vous avez un jour été catapulté à des hauteurs monstrueuses dans un jeu, alors vous avez déjà été victime d’un moteur physique qui a explosé.
* solver itératif :
Pour résoudre les forces et les contraintes appliquées à un body, les moteurs physiques utilisent des solvers : ils déterminent la nouvelle position des bodies après application des contraintes et des forces en fonction de leurs propriétés (masse, tenseur, etc). Cette opération est très couteuse et il existe deux grandes solutions :
1) Construire une immense matrice et la résoudre. C’est lent ( O(n^3), avec n le nombre de contraintes du monde ) mais extrémement précis.
2) Ne pas résoudre toutes les contraintes mais seulement certaines et de manière linéaire, sélectionnées à chaque itération au hasard. C’est beaucoup plus rapide (linéaire), surtout lorsqu’il y a beaucoup d’éléments dans le monde et donc beaucoup de contraintes. Par contre, c’est bien moins précis. Pour information, c’est justement ce que la dev-team de Serious Sam 2 (Alen Ladavac en particulier) a donné à ODE il y’a quelques mois.
En général les jeux utilisent la deuxième méthode dite itérative tandis que les applications scientifiques utilisent la première.
Et le hitscan, comment ça marche ?
J’ai connu quelqu’un qui s’étonnait de constater que dans mon exemple de la fréquence de détection des collisions de la balle, les moteurs de jeux doivent faire autant de calculs. Mais l’exemple que j’utilisais avec les balles n’est pas la seule méthode utilisée, en particulier pour les objets les plus véloces.
Pour gérer les collisions des balles, la méthode la plus connue est celle que les joueurs appellent « hitscan ». Elle consiste à ne pas utilser un projectile physique basé sur une boite ou une capsule mais un rayon (voir la liste des primitives en haut de l’article). Les rayons sont infinis et entrent en collision avec le monde dès l’itération suivante. Il reste à prendre la collision la plus proche de la source du tir (ou 2 ou 3 après, pourquoi pas) pour savoir tout de suite qui/quoi à été touché.
Il est aussi possible de mélanger les deux méthodes pour créer un rayon « segment » qui avance d’une distance inférieure à sa propre longueur à chaque itération. Certains moteurs physiques utilisent en interne des méthodes de ce style pour éviter tous les effets tunnel.
Les cas Doom 3 et Quake 3
id Software avait annoncé pendant le développement de Doom 3 que le framerate du jeu serait bridé à 60 Hz. La raison de cette décision est due au fait que le moteur physique lui même n’est appelé que 60 fois par secondes. Dès lors et puisque le temps ne change pas entre deux appels au moteur physique, pourquoi recalculer 2 fois la même image ? Le truc très fort dans l’histoire c’est que le moteur physique d’id reste stable à une fréquence aussi faible (pour information, je suis à 400 Hz dans mon moteur perso).
Quand aux framerates magiques de Quake 3, là encore sans le code source il est très délicat de comprendre ce qui se passe réellement, mais on imagine assez facilement qu’a certaines fréquences la synchro entre les timesteps du moteur physique et l’affichage des frames fait que le moteur physique est appelé une fois de trop entre deux frames : par exemple, s’il faut avancer le temps 9,6 fois depuis la dernière frame, on le fait 10 fois et on en parle plus – le nombre d’appels est forcément un entier. Du coup, le temps du moteur physique est en avance sur le temps réel et du coup, le joueur aussi se retrouve en avance sur les autres.
Pour conclure
J’éspère avoir éclairé certaines lanternes et je remercie les participants du thread à l’origine de cet article pour leurs questions : Dr.Loser, Snowman, barbariedoll, divide, Nutz, Deadrom, Bernard_Julius, Arkan et tous les autres pour leurs encouragements.
