When Worlds Collide Simulation de collisions cercle-cercle

La plupart des détections de collisions dans les jeux informatiques sont effectuées à l'aide de la technique AABB: très simplement, si deux rectangles se croisent, une collision s'est produite. C'est rapide, efficace et incroyablement efficace - pour les objets rectangulaires. Mais si nous voulions briser les cercles ensemble? Comment calcule-t-on le point de collision et où vont les objets? Ce n'est pas aussi difficile que vous pourriez le penser…

Remarque: Bien que ce tutoriel ait été écrit avec AS3 et Flash, vous devriez pouvoir utiliser les mêmes techniques et concepts dans presque tous les environnements de développement de jeux..

Prévisualisation de l'image tirée de ce classique Psdtuts + tutoriel.


Étape 1: Créer des boules

Je vais passer sous silence cette étape, car si vous ne pouvez pas créer de sprites de base, le reste du didacticiel sera un peu plus difficile que vous..

Autant dire que nous avons un point de départ. Vous trouverez ci-dessous une simulation très rudimentaire de balles rebondissant autour d’un écran. S'ils touchent le bord de l'écran, ils rebondissent.

Cependant, il y a une chose importante à noter: souvent, lorsque vous créez des sprites, la partie supérieure gauche est définie sur l'origine. (0, 0) et en bas à droite est (largeur hauteur). Ici, les cercles que nous avons créés sont centrés sur le sprite.

Cela simplifie considérablement les choses, car si les cercles ne sont pas centrés, il faut compenser le rayon par plus ou moins de tous les calculs, effectuer le calcul, puis le réinitialiser..

Vous pouvez trouver le code jusqu'à ce point dans la v1 dossier du téléchargement source.


Étape 2: Vérifiez les chevauchements

La première chose à faire est de vérifier si nos balles sont proches les unes des autres. Il y a plusieurs façons de le faire, mais comme nous voulons être de bons programmeurs, nous allons commencer par un contrôle AABB..

AABB représente un cadre de sélection aligné par axe et désigne un rectangle dessiné pour s'ajuster étroitement autour d'un objet, aligné de telle sorte que ses côtés soient parallèles aux axes..

Une vérification de collision AABB ne ne pas vérifier si les cercles se chevauchent, mais cela nous permet de savoir s’ils le sont près L'un et l'autre. Comme notre jeu n'utilise que quatre objets, ce n'est pas nécessaire, mais si nous utilisions une simulation avec 10 000 objets, cette petite optimisation nous permettrait d'économiser de nombreux cycles de traitement..

Alors on y va:

 if (firstBall.x + firstBall.radius + secondBall.radius> secondBall.x && firstBall.x < secondBall.x + firstBall.radius + secondBall.radius && firstBall.y + firstBall.radius + secondBall.radius > secondBall.y && firstBall.y < seconBall.y + firstBall.radius + secondBall.radius)  //AABBs are overlapping 

Cela devrait être assez simple: nous établissons des boîtes englobantes de la taille du diamètre de chaque balle au carré.

Ici, une "collision" s'est produite - ou plutôt, les deux AABB se chevauchent, ce qui signifie que les cercles sont proches et peuvent potentiellement entrer en collision..

Une fois que nous savons que les balles sont à proximité, nous pouvons être un peu plus complexes. En utilisant la trigonométrie, nous pouvons déterminer la distance entre les deux points:

 distance = Math.sqrt ((((firstBall.x - secondBall.x) * (firstBall.x - secondBall.x))) + ((firstBall.y - secondBall.y) * (firstBall.y - secondBall.y))) ; si (distance < firstBall.radius + secondBall.radius)  //balls have collided 

Ici, nous utilisons le théorème de Pythagore, a ^ 2 + b ^ 2 = c ^ 2, pour déterminer la distance entre les centres des deux cercles.

Nous ne connaissons pas immédiatement les longueurs de une et b, mais nous connaissons les coordonnées de chaque balle, il est donc facile de trouver une solution:

 a = firstBall.x - secondBall.x; b = premierBall.y - secondBall.y;

Nous résolvons alors pour c avec un peu de réarrangement algébrique: c = Math.sqrt (a ^ 2 + b ^ 2) - d'où cette partie du code:

 distance = Math.sqrt ((((firstBall.x - secondBall.x) * (firstBall.x - secondBall.x))) + ((firstBall.y - secondBall.y) * (firstBall.y - secondBall.y))) ;

Nous comparons ensuite cette valeur à la somme des rayons des deux cercles:

 si (distance < firstBall.radius + secondBall.radius)  //balls have collided 

Pourquoi vérifions-nous les rayons combinés des cercles? Eh bien, si nous regardons la photo ci-dessous, nous pouvons voir que, quel que soit l'angle auquel les cercles se touchent, s'ils touchent la ligne, c est égal à r1 + r2.

Donc si c est égal ou inférieur à r1 + r2, alors les cercles doivent se toucher. Simple!

Notez également que, pour calculer correctement les collisions, vous souhaiterez probablement d'abord déplacer tous vos objets, puis leur détecter les collisions. Sinon, vous pourriez avoir une situation où Ball1 mises à jour, vérifie les collisions, les collisions, puis Ball2 mises à jour, n'est plus dans la même zone que Ball1, et ne signale aucune collision. Ou, en termes de code:

 pour (n = 0; n 

est beaucoup mieux que

 pour (n = 0; n   

Vous pouvez trouver le code jusqu'à ce point dans la v2 dossier du téléchargement source.


Étape 3: Calculer les points de collision

Cette partie n'est pas vraiment nécessaire pour les collisions de balles, mais c'est assez cool, alors je la lance. Si vous voulez juste que tout rebondisse, n'hésitez pas à passer à l'étape suivante..

Il peut parfois être utile de déterminer le point où deux balles sont entrées en collision. Si vous souhaitez, par exemple, ajouter un effet de particule (peut-être une petite explosion) ou créer une sorte de guide pour un jeu de billard, il peut être utile de connaître le point de collision..

Il y a deux façons de résoudre ce problème: la bonne et la mauvaise..

La mauvaise façon, utilisée par de nombreux tutoriels, est de faire la moyenne des deux points:

 collisionPointX = (firstBall.x + secondBall.x) / 2 collisionPointY = (firstBall.y + secondBall.y) / 2

Cela fonctionne, mais seulement si les balles ont la même taille.

La formule que nous voulons utiliser est légèrement plus compliquée, mais fonctionne pour les balles de toutes tailles:

 collisionPointX = ((firstBall.x * secondBall.radius) + (secondBall.x * firstBall.radius)) / (firstBall.radius + secondBall.radius); collisionPointY = ((firstBall.y * secondBall.radius) + (secondBall.y * firstBall.radius)) / (firstBall.radius + secondBall.radius);

Ceci utilise les rayons des boules pour nous donner les vraies coordonnées x et y du point de collision, représentées par le point bleu dans la démo ci-dessous..

Vous pouvez trouver le code jusqu'à ce point dans la v3 dossier du téléchargement source.


Étape 4: rebondir

Nous savons maintenant quand nos objets se rencontrent, et nous connaissons leur vitesse et leurs emplacements x et y. Comment travaillons-nous pour leur prochaine destination??

Nous pouvons faire quelque chose appelé choc élastique.

Essayer d'expliquer avec des mots le fonctionnement d'une collision élastique peut être compliqué - l'image animée suivante devrait rendre les choses plus claires.


Image de http://fr.wikipedia.org/wiki/Collision_Elastique

Simplement, nous utilisons plus de triangles.

Maintenant, nous pouvons déterminer la direction que prend chaque balle, mais d’autres facteurs peuvent jouer. Le spin, la friction, le matériau dont sont faites les billes, la masse et d’autres facteurs peuvent être pris en compte pour essayer de créer la collision «parfaite». Nous ne nous préoccuperons que de l'un d'entre eux: la masse.

Dans notre exemple, nous allons supposer que le rayon des billes que nous utilisons est aussi leur masse. Si nous recherchions le réalisme, cela serait alors inexact, car - en supposant que les balles soient toutes fabriquées dans le même matériau - la masse des balles serait proportionnelle à leur surface ou à leur volume, selon que vous souhaitiez ou non les considérer. disques ou sphères. Cependant, comme il s’agit d’un jeu simple, il suffit d’utiliser leurs rayons.

Nous pouvons utiliser la formule suivante pour calculer la variation de la vitesse x de la première balle:

 newVelX = (firstBall.speed.x * (firstBall.mass - secondBall.mass) + (2 * secondBall.mass * secondBall.speed.x)) / (firstBall.mass + secondBall.mass);

Alors, passons simplement en revue ceci:

  • Supposons que les deux balles ont la même masse (nous dirons 10).
  • La première balle se déplace à 5 unités / mise à jour (à droite). La deuxième balle se déplace -1 unités / mise à jour (à gauche).
 NewVelX = (5 * (10-10) + (2 * 10 * -1)) / (10 + 10) = (5 * 0) + (-20) / 20 = -20/20 = -1

Dans ce cas, en supposant une collision frontale, la première balle commencera à se déplacer à -1 unité / mise à jour. (À gauche). Parce que les masses des balles sont égales, la collision est directe et aucune énergie n'a été perdue, les balles auront des vitesses "échangées". Changer l’un de ces facteurs changera évidemment le résultat.

(Si vous utilisez le même calcul pour déterminer la nouvelle vitesse de la seconde balle, vous constaterez que celle-ci se déplace à 5 unités / mise à jour, à droite).

Nous pouvons utiliser cette même formule pour calculer les vitesses x / y des deux billes après la collision:

 newVelX1 = (firstBall.speed.x * (firstBall.mass - secondBall.mass) + (2 * secondBall.mass * secondBall.speed.x)) / (firstBall.mass + secondBall.mass); newVelY1 = (firstBall.speed.y * (firstBall.mass - secondBall.mass) + (2 * secondBall.mass * secondBall.speed.y)) / (firstBall.mass + secondBall.mass); newVelX2 = (secondBall.speed.x * (secondBall.mass - firstBall.mass) + (2 * firstBall.mass * firstBall.speed.x)) / (firstBall.mass + secondBall.mass); newVelY2 = (secondBall.speed.y * (secondBall.mass - firstBall.mass) + (2 * firstBall.mass * firstBall.speed.y)) / (firstBall.mass + secondBall.mass);

Espérons qu'il est évident que chaque calcul est identique, remplaçant simplement les valeurs en conséquence.

Une fois que cela est fait, nous avons les nouvelles vitesses de chaque balle. Alors est-ce qu'on a fini? Pas assez.

Plus tôt, nous nous sommes assurés de faire toutes nos mises à jour de position à la fois, et puis vérifier les collisions. Cela signifie que lorsque nous vérifions la présence de balles en collision, il est très probable qu'une balle soit «dans» une autre. Ainsi, lorsque la détection de collision est appelée, la première balle et la seconde balle enregistrent cette collision, ce qui signifie que nos objets peuvent recevoir collé ensemble.

(Si les balles vont ensemble, la première collision inversera leurs directions - de sorte qu'elles se séparent - et la seconde collision inversera à nouveau leur direction, les obligeant à se déplacer ensemble).

Il y a plusieurs façons de gérer cela, par exemple, l'implémentation d'un booléen qui vérifie si les billes ont déjà heurté ce cadre, mais le moyen le plus simple consiste simplement à déplacer chaque balle à la nouvelle vitesse. Cela signifie, en principe, que les balles doivent se séparer avec la même vitesse de déplacement, ce qui les place à une distance égale à celle du cadre avant la collision..

 firstBall.x = firstBall.x + newVelX1; firstBall.y = firstBall.y + newVelY1; secondBall.x = secondBall.x + newVelX2; secondBall.y = secondBall.y + newVelY2;

Et c'est tout!

Vous pouvez voir le produit final ici:

Et le code source de cette partie est disponible dans le v4 dossier du téléchargement source.

Merci d'avoir lu! Si vous souhaitez en savoir plus sur les méthodes de détection de collision, consultez cette session. Vous pouvez également être intéressé par ce tutoriel sur les arbres à quatre branches et sur le test de séparation des axes.