Nov 04 2010
La détection de collision
A mes débuts de “flasher” j’avais était super impressionné par “N” : un vrai jeu avec un moteur de collisions + physique poussé. Ce jeu fonctionne vraiment bien et on ne tombe jamais sur aucun glitch de collision très courant à l’époque des jeux flashs : Passage au travers d’un mur, décalage plus qu’approximatif dans le calcul de la trajectoire etc. Je me suis replongé dans la détection de collision l’autre jour et j’ai tout de suite pensé à ce jeu comme base de réflexion.
Je sais qu’il existe des moteurs très puissant de physique tel que box 2D (largement exploité en minigame iphone, android flash…) mais malheureusement je trouve que trop de physique peut nuire grandement au gameplay et j’ai pas envie de m’embêter avec des poids, vélocité etc… pour un jeu de plateforme. Sur le plutôt bon Angrybirds la physique m’énerve un peu trop des fois.
Dans “new super mario bros wii” par exemple, il y a une super bonne détection de collisions qui est loin d’être réaliste (heureusement) et pourtant on s’en passe et le jeu arrache tout. Mario est soumis à la gravité, il peut marcher sur des plateformes rondes (qui tournent), en pentes, qui bougent, des rectangulaires qui tournent etc… C’est ce compromis que je recherche et aujourd’hui, à ma connaissance, il n’y a pas de moteur de collisions / faussement physique.
Exemple de belles plateformes rectangulaires qui tournent dans le niveau 9-1 :
En cherchant un peu je suis tombé sur les tutoriels de N : http://www.metanetsoftware.com/technique/tutorialA.html
Ils expliquent assez bien et sont très utiles pour comprendre les concepts de collisions entre différents objets. Et bien sûr la fameuse technique de l’axe séparateur qui semble faire l’unanimité chez les développeurs.
Récap :
- on peut dire que deux objets ne se touchent pas tant qu’on peut tirer un trait entre les deux.
- un de ces traits est forcément parallèle à un coté d’un des objets.
Partant de là, il est assez facile par “projection” de trouver (ou pas) les collisions. Encore faut il comprendre la projection, sur quoi projeter et pourquoi.
En informatique 2D on teste souvent la collision entre “hitbox” (une boîte rectangulaire qui entoure la totalité ou une partie seulement d’un sprite.) Ça facilite grandement les calculs, on gagne en performance mais des fois c’est pas suffisant. On verra néanmoins que ce calcul rapide est à effectué dans certains cas. Le principe est simple : si les distances respectives en x et y entre les centres des deux objets sont inférieures à la moitié de la somme de leurs longueurs et hauteurs, il y a collision.
La soustraction de ces distances et des sommes des longueurs et hauteurs donnent des valeurs de superpositions des objets : des vecteurs de pénétration.
Ça marche très bien, mais seulement pour les AABB : Axis Aligned Bounding Box. Comprendre “Boites rectangulaires sans rotation”
Ce principe de détection de collisions marche super bien dans beaucoup de cas (Shmup, jeux de plateforme etc…) mais il est limite quand on veut pousser l’expérience de l’utilisateur un peu plus loin. (voir exemple de mario ci dessus)
Si on commence à faire tourner les boites ca devient compliqué car la petite astuce précédente ne marche plus :
Pourtant, on voit bien que l’on peut tracer ce fameux trait entre les deux boites ! et on voit bien qu’il devrait être parallèle au côté de la boite rouge comme précédemment énoncé.
Avec la précédente technique ça ne marche pas car on ne vérifie que le recouvrement sur les axes x et y. Sauf qu’ici, ce n’est pas sur ces axes qu’il faut chercher mais bien sur tous les axes décrits par les arêtes des boites. Pour “voir” que les boîtes ne se touchent pas, il faut se positionner au niveau de la boite rouge et de regarder le long de son côté à droite sur le dessin.
en supprimant les doublons on trouve 4 axes…
Pour le cas des AABB il n’y avait que 2 axes, ici on en a 4 mais le principe reste le même. Il faut calculer les superpositions des deux boites sur les 4 axes. Je ne vais pas vous expliquer comment faire parce que pour le coup, les tutoriels de N expliquent très bien les vecteurs et tout le bordel mais le principe est pas forcément simple à comprendre.
En écartant les axes ca devient un peu plus lisible (c’est pas nécessaire pour le code, en général on teste les axes en 0,0).
Première projection, je trouve une collision.
Deuxième projection, pas de collision…
En faisant les mêmes calculs sur tous les axes séparateurs, on obtient donc les collisions ou pas. En prenant le vecteur de pénétration le plus court de toutes les collisions des projections on trouve la position “idéale” où l’objet devrait être.
Dans ce test, on ne parle pas de physique, de rebonds ou de gravité… C’est un autre sujet, cependant un petit test flash donne déjà des résultats surprenants :
Dans cet exemple, on peut déplacer les formes à la souris et le rectangle gris à l’aide des touches. Le moteur physique se résume à “vitY += 1; ” autrement dit seulement une gravité basique. C’est pour ça que les plateformes ne transmettent pas leur vitesse de rotation au sprite rectangulaire. Mais ce n’est pas ce que l’on teste ici.
