Cet article est une ébauche, son contenu est susceptible d’évoluer.

Que serait le jeu vidéo aujourd’hui sans la possibilité de détruire l’environnement ? Battlefield serait moins grandiose, Rainbow Six Siege perdrait beaucoup de son aspect stratégique et Control serait moins grisant. De nos jours la destruction occupe une place de plus en plus importante dans de nombreux jeux. Cet article est un rapide tour d’horizon des différents types de destruction, de leur fonctionnement et des différentes manières de les synchroniser en réseau. Je me suis principalement concentré sur la 3D mais la très grande majorité de ce qui est décrit ici peut aussi s’appliquer à la 2D.

Simulation physique

Chaque jeu a des besoins et des capacités différentes pour mettre en place la destruction. Certains ont besoin de précision, d’autres ont besoin de réalisme et certains souhaitent une simple feature décorative peu couteuse en performance. Il existe des méthodes différentes pour tous ces besoins. Chacune a des avantages et des inconvénients et se retrouve utile dans des cas bien précis.

Destruction Statique

La destruction statique est la séparation d’un objet en plusieurs éléments de façon déterministe. Quoi qu’il arrive, la destruction s’effectuera toujours de la même façon. C’est un type de destruction pré-fragmenté. C’est-à-dire que l’artiste 3D sépare à l’avance le mesh (maillage de l’objet 3D) de l’objet en différentes parties. Lorsque l’objet reçoit un nombre de dégâts suffisant les parties se détachent et deviennent des débris. Le principal intérêt de cette destruction est son faible coût en performance permettant un usage sur les machines low end comme les téléphones et les consoles portables. C’est aussi plus rapide à développer, c’est la principale raison pour laquelle on en voit encore dans de nombreux jeux. Mais le gros défaut de cette technique est le faible réalisme et le peu de liberté que cela laisse au joueur.

La destruction statique est tout de même très utile dans des cas précis comme dans la série Battlefield où l’effondrement des bâtiments suit ce système. On pourrait alors se demander pourquoi un jeu avec un si gros budget n’utilise pas une destruction plus réaliste. Tout simplement car les développeurs ont besoin de connaître le résultat final de la destruction pour anticiper ce qu’ils appellent la levolution (l’évolution du niveau au fil d’une partie). Cela permet aussi aux artistes de créer une destruction plus spectaculaire.

La tour de la carte Siege of Shanghai s’effondre - Battlefield 4

La tour de la carte Siege of Shanghai s’effondre – Battlefield 4

Destruction Dynamique

La destruction dynamique est la destruction d’un mesh pré-fragmenté mais dont l’issue est calculée en temps réel. On ne sait pas à l’avance ce qui va casser et comment mais on sait la forme qu’auront les débris et leur granularité. C’est aujourd’hui la technique la plus utilisée dans les AAA car elle combine une bonne liberté pour le joueur avec un coût de calcul raisonnable. Son fonctionnement peut être très différent d’un moteur physique à l’autre. Dans cet article nous n’allons pas détailler le fonctionnement de chaque moteur mais plutôt nous concentrer sur les bases communes que l’on retrouve un peu partout (aussi bien dans NVidia Blast, RealBlast, Chaos, Havok, …).

Fragmenter le mesh efficacement

Lors de la création d’un mesh destructible, les développeurs doivent définir à l’avance les différentes parties détachables. Les artistes définissent manuellement les grandes parties de l’objet. Ensuite selon le moteur utilisé les sous-parties sont soit générées automatiquement (Chaos) soit manuellement. Dans le cas du moteur Chaos, les artistes ont à disposition des patterns nommés fracture qui vont sous diviser les parties. Ils peuvent ensuite les rediviser s’ils le souhaitent et ainsi créer des niveaux de regroupement (clustering level). L’intérêt est de casser l’objet principal en gros éléments qui deviennent des objets indépendants et peuvent alors à leur tour se briser et ainsi de suite de niveau en niveau.

Représentation des niveaux de regroupements dans le moteur Chaos

Représentation des niveaux de regroupement dans le moteur Chaos © Unreal Engine

Calcul des dégâts

Lorsque le mesh est prêt, on peut lui faire subir des dégâts. Il y a plusieurs types de dégâts, ceux d’impact, ceux de zone et enfin ceux de contrainte. Les premiers sont les plus simples, la zone touchée est la seule à subir une force et si cette force est suffisante alors la forme se détache. Les dégâts de zone quant à eux peuvent toucher de nombreuses parties simultanément. En plus d’appliquer une force, ils peuvent fragiliser ou briser les liens entre les parties. Cela a pour conséquence de ne pas détacher un unique gros bloc qui serait composé de plusieurs parties mais plutôt d’en détacher plusieurs, certains possiblement encore relié entre eux si leur lien n’est pas brisé. Enfin, les dégâts de contrainte ou de stress sont utiles dans le cas d’objet ayant des points « faibles » susceptibles de se briser si une force trop importante est exercée sur une partie de l’objet. Par exemple, une force importante exercée sur une table et susceptible de briser les attaches des pieds.

Application de la destruction

Lorsque le mesh prend des dégâts, il suit des règles qui dictent ce qui doit casser et comment. Les différentes parties de l’objet sont représentées par des nœuds dans des graphes. Elles sont liées entre elles par ce que l’on appelle un support graph ou connection graph. Dans ce graphe, si un nœud n’est plus attaché aux autres alors il devient un objet indépendant soumis à la gravité et aux autres lois de la physique, il devient un rigidbody. Ce graphe peut comporter des nœuds d’ancrages liés à des objets statiques. Lorsqu’une partie d’un graphe ne comporte plus aucun nœud d’ancrage alors ce sous graphe devient un rigibody et s’effondre.

Connection Graph avec le moteur Chaos © Unreal Engine

Connection Graph avec le moteur Chaos © Unreal Engine

Graphes utilisés par Nvidia Blast, la chunk hierarchy est équivalente aux clustering levels du moteur Chaos. © Nvidia PhysX

Graphes utilisés par Nvidia Blast, la chunk hierarchy est équivalente aux clustering levels du moteur Chaos. © Nvidia PhysX

Destruction Procédurale

La destruction procédurale est un changement dans l’état d’un objet généré en temps réel et dont le résultat est unique. Contrairement aux méthodes détaillées plus tôt, l’objet n’est pas fragmenté à l’avance. Cette technique requiert beaucoup de calculs à chaque destruction elle est donc encore peu présente même dans les AAA.

Dans Rainbow Six Siege la destruction des murs, trappes et du sol se doit d’être très précise et très performante. Elle joue un rôle très important dans les mécaniques du jeu. Un tir dans un mur doit créer un trou de la taille de la balle et non ouvrir une grande brèche. Les explosifs disponibles avec certains personnages doivent aussi faire des formes très précises dans les murs (Termite, Hibana) pour que les joueurs puissent prédire avec précision le résultat de l’explosion. Les dommages effectués aux surfaces possèdent donc une granularité très fine car la forme exacte et la zone des destructions sont imprédictibles à l’avance par les développeurs. Dans les modèles vus précédemment les parties des objets détruits restent de taille assez importante pour garder un coût de calcul raisonnable. Les développeurs de Rainbow Six Siege ont donc dû mettre en place une méthode pour avoir une destruction procédurale très précise avec un besoin de calcul limité, c’est la surface procedural destruction.

Mur détruit suite à une explosion – Rainbow Six Siege

Dans Rainbow Six Siege les éléments destructibles ayant une grande importance pour le gameplay sont tous des surfaces planes. Il est donc assez simple de projeter le modèle 3D sur un modèle 2D pour diminuer fortement le coût des calculs. Lorsque la surface subit des dégâts, un pattern de découpage est généré selon la position de l’impact, le type d’impact, les paramètres du matériel, etc …. Le pattern généré va ensuite être soustrait de la surface 2D. Avant de pouvoir projeter le visuel en 3D, il faut trianguler la nouvelle surface obtenue.

La triangulation est la découpe d’un polygone en triangles (appelés vertices). La triangulation est une étape de la convex decomposition qui consiste à s’assurer que tous les polygones de la surface sont convex et pas concaves. Les formes concaves complexifient énormément les calculs de collision et ne sont pas supportées par la majorité des moteurs physiques. Pour trianguler les surfaces, l’équipe de Rainbow Six a utilisé l’algorithme le plus connu, le Ear Clipping. C’est un algorithme assez simple qui itère sur tous les sommets d’un polygone. Il regarde si les deux sommets adjacents au sommet actuel peuvent être reliés entre eux pour former un triangle contenu dans le polygone principal. Si c’est le cas, les deux sommets sont reliés et un nouveau triangle est créé.

Beaucoup de jeux faisant usage de la destruction sont des jeux multijoueur en ligne.  Après avoir décrit le fonctionnement général de la destruction en local, il est temps de parler de sa propagation dans les jeux en réseau.

II Networking

La physique en réseau pose de nombreux problèmes. Elle doit donner des résultats identiques ou presque sur toutes les machines tout en économisant la bande passante pour pouvoir fonctionner sur toutes les connexions. La destruction reposant beaucoup sur la physique, elle souffre des mêmes problèmes. Il existe différentes manières de synchroniser l’état d’un objet sur le réseau, chacune ayant des contraintes et avantages différents (latence, précision, consommation de bande passante, …).

Deterministic Lockstep

Le deterministic lockstep est la méthode la plus simple et aussi la plus économe en bande passante. Mais elle possède des défauts importants. Elle est basée sur l’envoi d’inputs à tous les joueurs. Les inputs sont les actions qui vont influer sur l’environnement. Par exemple si un personnage pousse une caisse, il enverra un message disant qu’il pousse la caisse dans tel sens avec tel force. Les receveurs de leur côté appliqueront la force et le sens reçu sur la caisse. Le problème avec cette méthode c’est que le système doit être déterministe et les moteurs physiques ne sont généralement pas déterministes (notamment à cause de l’arrondi des nombres à virgules). Même si le résultat peut être visuellement proche, il y aura toujours un calcul de collision ou de vitesse qui fera légèrement différer le résultat final. De plus un système déterministe implique une exécution des inputs dans le bon ordre et au bon moment.

Fonctionnement

Comment s’assurer d’exécuter les inputs dans le bon ordre coté client et au bon moment ? Pour avoir le bon ordre il suffit de numéroter les paquets de données envoyés et le client (logiciel qui envoie des demandes à un serveur) suivra la numérotation pour l’exécution. Mais la moindre perte de paquet risque de casser le déterminisme du système car il manquera des informations au client. La solution la plus évidente à ce problème est d’utiliser le protocole TCP. Ce protocole demande au client d’envoyer une confirmation lorsqu’il reçoit des données. Ainsi, si l’envoyeur ne reçoit pas de réponse de la part du client au bout d’un certain temps il peut envoyer à nouveau les données. Par ce moyen on s’assure que tous les clients recevront toutes les infos. Cette solution n’est pas parfaite, une perte va ralentir le jeu. Une technique avec le protocole UDP résout ce problème. Ce protocole n’attend pas de confirmation de la part du client. L’envoyeur envoie une liste d’input qu’il pense que le receveur n’a pas effectué. Lorsque le receveur effectue une simulation il dit à l’envoyeur : « Ne m’envoie plus les inputs x, je m’en suis déjà servi » et cela évite de renvoyer inutilement un input déjà effectué.

Maintenant que les inputs s’exécutent dans le bon ordre il faut s’assurer qu’ils s’exécutent au bon moment. Pour cela il faut utiliser un Input Delay Buffer. Le client va accumuler les inputs reçus dans un buffer en mettant un temps ou un nombre d’images précis (delay) entre l’application de chaque input. Le client aura une latence fixe par rapport à l’envoyeur. S’il y a des pertes de paquets en chemin, cela entraine un retard chez le client le forçant à diminuer le délai entre l’application des inputs pour « rattraper » son retard.

Schéma d’envoi de données avec la deterministic lockstep – © Gaffer On Games

Dans notre cas, cela peut tout de même s’avérer utile pour la destruction statique car comme nous l’avons vu plutôt c’est un type de destruction déterministe. Les seules infos importantes sont le nombre de dégâts reçu et l’état de l’objet (détruit ou non).

Usage dans Rainbow Six Siege

C’est la méthode qui semble utilisée pour la destruction procédurale de Rainbow Six Siege. Pour s’assurer du déterminisme de leur système, les développeurs utilisent un système de génération de nombres aléatoires (RNG) basé sur des infos comme la position de l’impact, le type d’arme, etc…. Ce nombre va être envoyé en tant qu’input sur le réseau et toutes les machines traduiront ce nombre de la même façon et appliqueront la destruction localement. Dans R6 l’ordre d’application de la destruction est très important. Si un trou s’applique avant un autre cela peut complètement changer la forme des trous « composites ». Ce sont des brèches qui s’ouvrent dans les murs lorsque plusieurs dégâts sont physiquement proches.

En tant que jeu compétitif en haut niveau le résultat d’un tir dans un mur se doit d’être très rapide. Il est nécessaire d’avoir un feedback instantané pour le tireur. Le problème étant que si on applique immédiatement les dommages et la destruction, alors on casse le déterminisme du système. En effet, il y a peut-être des infos en transit sur le réseau que l’on va recevoir après avoir appliqué la destruction. La solution est d’appliquer l’effet de destruction instantanément (un simple trou pour une balle) et d’attendre le retour du serveur pour appliquer les vrais dégâts aux murs (ce qui peut conduire à la formation de trous composites). Cette solution n’est pas parfaite et il est possible que le joueur finisse avec un état très légèrement différent des autres joueurs mais c’est suffisamment minime pour être ignoré.

Solution pour avoir un feedback instantané sur Rainbow Six Siege © Julien L'Heureux

Solution pour avoir un feedback instantané sur Rainbow Six Siege © Julien L’Heureux

Snapshot Interpolation

Contrairement à la determinitic lockstep, la snapshot interpolation n’a pas besoin que chaque client fasse la simulation physique de son côté. À la place, c’est un système dans lequel l’hôte envoie régulièrement une mise à jour de la scène à tous les clients. Les clients ont alors simplement à attendre les paquets d’informations et à interpoler entre deux mises à jour de l’état d’un objet. L’interpolation est le fait d’approximer l’état actuel d’un objet entre deux états connus. Sans interpolation, les objets se téléporteraient à chaque réception d’informations.

Il existe plusieurs types d’interpolation. La plus simple est l’interpolation linéaire, on fait une progression droite entre deux états. Ce qui nous intéresse ici est l’interpolation d’Hermite qui, en plus de prendre un état de départ et un état d’arrivée, va prendre d’autres paramètres en compte pour être la plus proche possible du mouvement réel. Par exemple, si un joueur court dans un sens et que le client reçoit deux positions où le joueur à une vitesse différente, il va prendre en compte la vitesse et faire ralentir de façon crédible le joueur entre les deux positions. Avec l’interpolation linéaire il l’aurait fait avancer avec une vitesse constante.

Différents types d’interpolation

Le gros problème de cette technique est son coût en bande passante car plus il y a d’objets plus il faut envoyer d’informations. Heureusement il existe des techniques d’optimisation et de compression de données qui permettent d’atteindre un coût abordable. Elles ne seront pas détaillées dans cet article mais si le sujet vous intéresse vous trouverez plein d’infos sur le site de www.gafferongames.com.

La snapshot interpolation est aujourd’hui la technique la plus utilisée dans l’industrie pour la physique en général. Elle est notamment la méthode par défaut du moteur Source (Titanfall, Left 4 Dead, Portal, …) développé par Valve. Mais pour ce qui est de la destruction pure c’est assez peu utile car on ne peut pas interpoler sur la destruction d’un objet. Une partie ne disparait pas progressivement, le plus souvent elle est soit présente soit détruite (où en mouvement dans le cas de débris). Cela a donc un intérêt uniquement pour la gestion des débris.

State synchronization

La state synchronization repose comme son nom l’indique sur la synchronisation d’états. Un état comprend tout ce qui est visuel pour un objet (position, rotation, …) mais aussi ce qui ne l’est pas (vitesse linéaire, vitesse angulaire, …). La simulation physique est effectuée sur chaque client mais un des clients ou le serveur lui-même est désigné comme « possesseur » de l’objet. Il fait figure d’autorité sur le comportement de l’objet. Lorsqu’un des clients effectue une simulation sur un objet qu’il ne « possède » pas, alors il envoie l’état qu’il a obtenu et attend une réponse du serveur pour savoir s’il doit corriger l’état de l’objet. La correction de l’état se fait immédiatement, sans interpolation. Une personne ne « possédant » pas un objet extrapole l’état de l’objet entre 2 états « officiels » reçus. Il extrapole l’évolution de l’objet en se servant du dernier état reçu.

Fonctionnement

La state synchronization est une technique où l’on ne synchronise pas l’état de tous les objets à la fois. Il faut déterminer des priorités. L’avatar du joueur par exemple sera mis à jour très régulièrement alors qu’un objet peu susceptible de bouger sera rarement mis à jour. Pour définir efficacement l’importance de mettre à jour l’état d’un objet, on peut utiliser un système d’accumulation de priorités. Les objets gagnent en priorité (plus ou moins vite selon leur importance) au cours du temps. Lorsqu’ils sont mis à jour, leur priorité retombe à 0. Ainsi, on s’assure de finir par mettre à jour tous les objets même les moins importants. Un des avantages de la state synchronization est sa consommation de bande passante prévisible. On peut facilement déterminer à l’avance un nombre fixe d’états et d’inputs à envoyer sur une seconde.

Même si l’envoyeur envoie les états de façon régulière, le client ne les recevra pas toujours à la même fréquence. Si le client appliquait les états dès leur réception et qu’il recevait par exemple 4 paquets d’un coup, il risquerait de voir les objets faire des mouvements insensés. Pour éviter cela il possède un jitter buffer qui va stocker tous les états à appliquer. Le client va attendre un moment précis spécifié dans le paquet reçu avant d’appliquer la correction d’état. Les mises à jour d’état s’effectuent alors de façon régulières et prévisibles. Ce n’est pas grave de rater un paquet car un nouvel état viendra rapidement le remplacer pour cette raison il est préférable d’utiliser le protocole UDP.

Schéma d’envoi de données avec la state synchronization – © Gaffer On Games

La state synchronization est une technique utilisée dans de nombreux jeux. Pour la destruction, elle peut être utilisée dans le cas de la destruction dynamique où le plus important est de s’assurer que tous les joueurs aient un objet dans le même état.

La physique en réseau est complexe et est toujours un champ de recherche important. Il n’existe pas que les 3 techniques cités dans cet article, il y en a beaucoup d’autres. Elles reprennent le plus souvent des bases communes. Par exemple le lockstep protocol est proche de la state synchronisation mais ici tout le monde fait figure d’autorité. Les clients doivent se mettre d’accord sur l’état des objets pour pouvoir faire avancer le jeu. Il n’est pas rare que des jeux utilisent plusieurs techniques en fonction des besoins de chaque objet ou de chaque mode de jeu. Ainsi, le mode campagne co-op de Halo 3 est basé sur de l’asynchronous lockstep protocol (variante asynchrone du lockstep protocol) alors que son mode multijoueur compétitif se base sur la state synchronization.

Conclusion

Ce tour d’horizon de la destruction dans le jeu vidéo s’achève. J’espère que vous avez pu apprendre autant de chose que moi en préparant cet article. J’effleure ici uniquement les bases d’un sujet très vaste et fortement lié aux systèmes physiques des jeux sur lesquels il y aurait aussi énormément de chose à dire. Si le sujet vous intéresse n’hésitez pas à aller jeter un œil aux sources de cet article.

Des questions ? Des corrections ? Des suggestions ? Laissez un commentaire.

Cet article fait partie de la série d'articles Tech Temps Réel  dédiée à la vulgarisation des méthodes de rendues et de simulation temps réel utilisées dans les jeux vidéo. Pour ne pas rater les prochains articles :  Twitter / Mastodon / Bluesky.

Sources :

Aperçu du fonctionnement de Nvidia Blast. Lien
GDC Talk – The Art of Destruction in Rainbow Six: Siege. Lien
GDC Talk – Battlefield 4: Creating a More Dynamic Battlefield. Lien
GDC Talk – Causing Chaos: The Future of Physics and Destruction in Unreal Engine. Lien
GDC Talk – Physics for Game Programmers: Destruction in Smash Hit. Lien
Gaffer On Games – Networking Physics. Lien
David Eberly – Triangulation by Ear Clipping. Lien
A Guide to Networking, Matchmaking, and Host in Halo. Lien
Source Engine Multiplayer Networking. Lien