- La résolution des collisions de corps rigides en physique de jeu 2D consiste à calculer les changements de vitesse pour éviter que des objets déjà en contact ou qui se chevauchent ne se pénètrent à l’image suivante
- Comme la boucle de jeu met à jour les positions à chaque frame à partir de la vitesse et de Δt, si les géométries se chevauchent à la nouvelle position, les objets se traversent en l’absence de traitement spécifique
- Une collision ne se limite pas à un simple état de contact : il faut aussi vérifier si les objets en contact continuent à se déplacer l’un vers l’autre à leurs vitesses actuelles
- On peut déterminer si un objet s’éloigne d’une surface grâce au signe du produit scalaire entre la normale (normal) et la vitesse : positif s’il existe une composante dans la même direction, négatif s’il existe une composante en direction opposée
- Dans le cas de deux objets, la vitesse relative et la normale de collision comptent davantage que les vitesses individuelles ; en état de contact, on peut considérer qu’il y a collision lorsque la vitesse normale relative est négative
Corps rigides et périmètre de la résolution des collisions
- Le sujet est la physique des corps rigides (rigid body physics), qui traite des objets qui ne se déforment pas sous l’effet de forces
- Dans la réalité, tous les objets se déforment à l’échelle moléculaire ; un corps parfaitement rigide n’existe donc pas
- Dans la plupart des simulations physiques, calculer ces déformations détaillées est très difficile ou coûteux
- Si un objet paraît suffisamment réaliste, le simplifier comme un corps rigide est une approche pratique
- Le traitement des collisions dans un moteur de jeu se divise généralement en deux étapes
- Détection de collision (collision detection) : déterminer quels objets de la scène sont en collision
- Résolution de collision (collision resolution) : déterminer l’état suivant en fonction de la direction de déplacement, de la vitesse, du matériau, etc. des objets en collision
- Ici, l’accent n’est pas mis sur l’étape qui recherche les intersections géométriques, mais sur la résolution des collisions, qui détermine le mouvement après la collision
Comment les collisions apparaissent dans la boucle de jeu
- La plupart des jeux recalculent de façon répétée la position des objets de la scène au sein d’une grande boucle
- À chaque itération, la position d’un objet est mise à jour à partir de sa vitesse (velocity) actuelle
- La vitesse est une grandeur vectorielle qui possède à la fois une norme et une direction
- La longueur de la flèche représente la vitesse scalaire, et la direction indiquée par la flèche représente la direction du déplacement
- Le changement de position pendant un intervalle de temps Δt s’exprime comme un déplacement (displacement)
- Le déplacement est lui aussi une grandeur vectorielle avec une norme et une direction
- Si la boucle de jeu s’exécute 60 fois par seconde, Δt vaut 1/60 seconde
- La nouvelle position s’obtient en ajoutant à l’ancienne position le déplacement calculé à partir de la vitesse actuelle
- Si les nouvelles positions de deux objets font se chevaucher leurs géométries, en l’absence de traitement spécifique, les objets se pénètrent puis se traversent
La valeur recherchée par la résolution des collisions
- L’objectif de la résolution des collisions est de déterminer le changement de vitesse de chaque objet afin qu’ils ne se pénètrent plus à mesure que la simulation progresse
- Les vitesses avant et après collision s’expriment avec les notations suivantes
v_a,i,v_b,i: vitesses des objetsaetbavant la collisionv_a,f,v_b,f: vitesses des objetsaetbaprès la collisionΔv_a,Δv_b: changements de vitesse de chaque objet dus à la collision
- En fin de compte, la résolution des collisions consiste à trouver les valeurs Δv_a et Δv_b
- Pour produire une collision réaliste, les changements de vitesse choisis doivent respecter les lois physiques concernées
Le contact seul ne permet pas d’identifier une collision
- Ce n’est pas parce que deux objets se touchent qu’ils sont toujours en collision
- Une collision est une situation où les objets finiraient par se pénétrer s’ils continuaient à se déplacer à leurs vitesses actuelles
- Pour une même scène de contact, il peut y avoir collision ou non selon la direction des vitesses des deux objets
- Les conditions de collision exigent donc deux éléments à la fois
- Les géométries des objets doivent se toucher ou se chevaucher
- Les objets doivent encore se déplacer dans la direction de la collision
Normale de surface et direction d’éloignement
- Pour savoir si un objet s’éloigne d’une surface, on peut utiliser la direction normale (normal direction) à cette surface
- La direction normale est perpendiculaire à la surface et pointe dans la direction qui s’en éloigne directement
- Sur une surface plane, la direction normale est la même en tout point
- Sur une surface courbe, la direction normale varie selon le point
- Sur le périmètre d’un cercle, la direction qui va du centre vers le point correspondant du périmètre est la direction normale
- La direction normale est représentée par un vecteur normalisé de longueur 1
- Un vecteur de longueur 1 est aussi appelé vecteur unitaire (unit vector)
- Pour indiquer qu’un vecteur est normalisé, on peut placer le symbole
^au-dessus de la variable
- La direction normale en un point est perpendiculaire à la tangente (tangent) à la surface en ce point
Déterminer les composantes directionnelles avec le produit scalaire
- Pour calculer à quel point un vecteur pointe dans la même direction qu’un autre, on peut utiliser le produit scalaire (dot product)
- Pour des vecteurs 2D, le produit scalaire est la somme des produits de leurs composantes correspondantes ; le résultat n’est pas un vecteur, mais un scalaire
- Géométriquement, le produit scalaire peut être vu comme la longueur de la projection scalaire d’un vecteur sur la direction de l’autre, multipliée par la longueur du vecteur sur lequel on projette
- Le signe du produit scalaire indique la relation de direction entre deux vecteurs
- Si l’angle entre deux vecteurs est inférieur à 90°, le produit scalaire est positif et ils pointent globalement dans la même direction
- Si l’angle est supérieur à 90°, le produit scalaire est négatif et ils pointent globalement dans des directions opposées
- Si l’angle est exactement de 90°, le produit scalaire vaut 0
- Si le produit scalaire entre le vecteur vitesse d’un objet et la normale de surface est positif, l’objet s’éloigne de cette surface
Application aux collisions entre deux objets
- S’il y a deux objets, comme deux boîtes, il existe un vecteur vitesse pour chacun
- Dans ce cas, on utilise la vitesse relative (relative velocity) des deux objets plutôt que leurs vitesses individuelles
- La vitesse relative est la différence entre les vitesses des deux objets
- Géométriquement, c’est le vecteur qui va de l’extrémité de
v_bà l’extrémité dev_a - Par exemple, une collision frontale entre deux voitures roulant chacune à 50 km/h équivaut, toutes choses égales par ailleurs, à une voiture percutant à 100 km/h une voiture à l’arrêt
- La direction correspondant à la surface est représentée par la normale de collision (collision normal)
- La manière de calculer la normale de collision dépend de la forme ou de la géométrie des objets qui entrent en collision
- L’exemple utilisé ici est une collision sommet-arête (vertex-edge collision), où un point ou sommet d’un objet entre en collision avec une arête d’un autre objet
- Dans une collision sommet-arête, la normale de collision est perpendiculaire à cette arête
- Par convention, si les objets sont notés
aetb, la normale de collision pointe vers l’objeta- Peu importe quel objet est appelé
aoub, tant que la convention reste cohérente dans l’ensemble du calcul
- Peu importe quel objet est appelé
Définir la collision avec la vitesse normale relative
- En calculant le produit scalaire entre la vitesse relative
v_abet la normale de collisionn^, on peut déterminer si les deux objets se déplacent dans la direction de la collision - Cette valeur s’appelle la vitesse normale relative (relative normal velocity)
- C’est la composante de la vitesse relative dans la direction de la normale de collision
- Ici, son signe est important, mais elle joue aussi un rôle clé plus tard pour calculer les forces qui agissent pendant la collision
- Le signe de la vitesse normale relative distingue les états de collision
- Si la valeur est positive, les deux objets s’éloignent déjà l’un de l’autre
- Si la valeur est négative, les deux objets continuent encore à se percuter
- En définitive, une collision se produit lorsqu’un point d’un objet est en contact avec un autre objet et que la vitesse normale relative est négative
1 commentaires
Commentaires sur Hacker News
Cet article visait des personnes qui, comme moi, ne sont pas développeurs de jeux et n’ont pas un solide bagage en maths. J’ai donc pris pas mal de temps pour expliquer des concepts qui peuvent sembler presque évidents aux personnes expérimentées dans ce domaine. Je répondrai volontiers aux questions
Les débutants en développement de jeux pensent souvent à tort que pour gérer les collisions, il faut des calculs de collision de corps rigides ou un moteur physique 2D comme Box2D. C’est vrai si vous voulez faire un jeu de billard ou un jeu où des caisses s’effondrent comme Angry Birds, mais pour un platformer 2D, il suffit de détecter les collisions en comparant des rectangles alignés sur les axes, puis de corriger le chevauchement en modifiant les coordonnées X/Y du personnage ou en réglant sa vitesse Y après un saut ou un atterrissage. Cela facilite aussi un réglage plus fin de la maniabilité du personnage, et même s’il y a une forme d’inertie, ce n’est généralement pas une inertie physiquement réaliste. Quand un débutant essaie d’utiliser une physique réaliste, le mouvement devient souvent flottant et peu satisfaisant.
Exemple de tutoriel pour démarrer avec cette approche simple sans moteur physique : https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
J’empilais de manière itérative des éléments comme des points et des lignes, et comme j’avais ajouté beaucoup de petits pas et de lignes de débogage visuelles, le résultat était très bancal et lent, mais ça fonctionnait quand même à peu près
Prévoyez-vous aussi de lire et d’expliquer XPBD (Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) à l’avenir ? J’ai l’impression que ce concept attire de plus en plus l’attention, et je l’ai utilisé avec pas mal de succès dans Bevy via https://github.com/Jondolf/bevy_xpbd. Cela semble plus stable qu’une approche classique
Ce serait vraiment bien d’ajouter un flux RSS pour qu’on puisse continuer à suivre
Par curiosité, quels outils avez-vous utilisés pour créer cette page ?
Honnêtement, au début, en voyant le nom de domaine et en réalisant que le domaine de premier niveau était « .ski », j’ai cru que c’était le site de la personne qui a écrit Mechanical Watch [1] et d’autres excellents articles. En fait, c’est quelqu’un de complètement différent, mais la qualité est similaire. Quelle est donc la sauce secrète de ce domaine de premier niveau ".ski" ? :)
L’auteur des articles de https://ciechanow.ski, qu’on apprécie ici, est aussi un programmeur polonais qui travaille chez Apple
Un élément important du jeu est que les débris spatiaux peuvent être déplacés dans l’arène, et utilisés de manière créative pour piéger l’adversaire ou l’empêcher d’atteindre un objectif. Dans le cadre du projet, nous voulions carrément nous passer de moteur de jeu. Je voulais apprendre un peu plus à mon fils sur l’architecture des applications, et même si nous utilisons ensuite un moteur de jeu existant, je voulais qu’il passe au moins une fois par le processus consistant à tout implémenter lui-même. Tout allait bien jusqu’au moment d’aborder la détection et la résolution des collisions. À partir de là, la situation s’est rapidement dégradée. Malgré un bagage en maths théoriques, j’ai vite été submergé par l’énorme quantité de cas limites, et j’ai fini par abandonner pour utiliser Box2D. Je ne suis pas développeur de jeux professionnel, mais j’ai plus de 20 ans d’expérience en développement et un bagage en maths, et malgré cela j’ai commis l’erreur de sous-estimer ce problème. En paroles, cela paraît simple, mais dès qu’on entre dans les détails, la complexité semble croître de façon exponentielle
Voici une méthode courante pour faire un shoot’em up avec une simple comparaison de rectangles : https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
En revanche, si les objets de débris spatiaux doivent entrer en collision et s’agglomérer de manière réaliste, et si vous voulez que le vaisseau du joueur ait du mal à repousser un groupe d’objets lourds, alors utiliser une bibliothèque physique est tout à fait raisonnable
[1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...
[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...
C’était à l’époque où Flash était partout
Code : https://github.com/vandrieu/canvas-bouncing-ball
La logique de collision se trouve dans
src/collision.tsRésultat/démo : https://vandrieu.github.io/canvas-bouncing-ball/
Pourriez-vous ajouter une licence si possible ?
Mais dans les jeux, on utilise souvent une mise à jour physique qui descend jusqu’à 30 Hz avec une méthode Euler-Cromer assez arbitraire, donc il faut une approche assez différente
J’y ai passé des mois, mais au-delà des bases bien connues, je n’ai fait qu’effleurer la surface. Construire un moteur stable où les objets ne s’enfoncent pas les uns dans les autres et ne tremblent pas est un terrier sans fond, et même les articles très orientés maths que j’ai pu trouver l’abordaient à peine. J’ai compris les maths grâce à l’ancienne série d’articles de Chris Hecker
http://www.chrishecker.com/Rigid_Body_Dynamics
La partie difficile, ce sont les collisions de projectiles. Il aurait fallu prendre la position actuelle de la balle et sa position à l’étape de temps suivante, puis faire la même chose pour la hitbox de l’ennemi afin de vérifier s’il y a intersection, mais je n’ai vérifié que l’étape de temps actuelle. Résultat : les balles peuvent passer magiquement à travers les ennemis sans les toucher ! C’est idiot. Peut-être qu’un jour j’y reviendrai pour corriger ça.