Théorie des collisions : Formes 2D simples

Fvirtman

Nous allons commencer ici par les algorithmes de collision les plus élémentaires.

Commentez

- Titre : Théorie des collisions : Formes 2D simples

- Auteur : Fvirtman

- Parution : 21 novembre 2013

- Public visé :

- Licence : Le contenu de cet article est rédigé par Fvirtman et est mis à disposition selon les termes de la Licence Creative Commons Attribution 3.0 non transposé. Les logos Developpez.com, en-tête, pied de page, css, et look & feel de l'article sont Copyright ® 2013 Developpez.com.

Sommaire

- Navigation

- II. Introduction

- III. Point dans Axis Aligned Bounding Box

- III-A. Définitions

- III-B. Applications

- III-C. Calcul de collision

- IV. Collision entre deux Axis Aligned Bounding Box

- IV-A. Applications

- IV-B. Calcul de collision

- V. Cercles

- V-A. Définitions

- V-B. Applications

- V-C. Calcul de collision

- V-C-1. Point dans un cercle

- V-C-2. Collision de deux cercles

- Navigation

Navigation

Sommaire

Tutoriel suivant : formes complexes

II - Introduction

Nous allons commencer ici par les algorithmes de collision les plus élémentaires.

III - Point dans Axis Aligned Bounding Box

III-A - Définitions

Tout d'abord, définissons une Axis Aligned Bounding Box (AABB). Il s'agit d'un rectangle aligné avec les axes, c'est-à-dire que ses côtés sont parallèles aux axes des x et des y de votre repère (de votre écran pour les cas standard).

À la différence d'une Oriented Bounding Box (OBB), qui est un rectangle qui peut être orienté : ses côtés ne sont pas obligatoirement parallèles aux axes de votre repère.

Une AABB peut être définie par quatre paramètres : la position x,y de son coin supérieur gauche (en 2D, l'axe Y va vers le bas). Ainsi que de sa largeur w (comme width) et sa hauteur h (comme height).

Cela donne, en C, la structure suivante :

struct AABB
{
int x;
int y;
int w;
int h;
};

Notez, pour les utilisateurs de SDL, que cette structure est exactement SDL_Rect (à un type près), et que donc SDL_Rect est parfaite pour décrire une AABB.

III-B - Applications

Ce type de collision cherche donc à savoir si un point (de coordonnées x,y) est dans une AABB ou non.
Dans quel cas avons-nous besoin de ce type de collision ?
Par exemple pour un jeu de tir comme Opération Wolf, ou la sélection d'un menu de ce bon vieux Warcraft premier du nom :

Dans l'image à gauche, j'ai encadré les cibles en vert. Ce sont les AABB qui les portent. Bien que cette collision ne soit pas parfaite (vous pouvez descendre l'ennemi en tirant juste au-dessus de son épaule), elle est très utilisée et rapide.
(Certains vont me dire qu'Opération Wolf affine ses collisions… ça se peut, mais considérons que non.)
L'idée de ce jeu est simple : on déplace le curseur à la souris (pointeur rouge) et quand on clique, on regarde s'il est dans une AABB ou non, tout simplement.

Pour la deuxième image, chaque option du menu est un rectangle, une AABB. On va aller cliquer sur une option ou une autre avec la souris. C'est la même collision.

III-C - Calcul de collision

La fonction de collision aura cette signature :

bool Collision(int curseur_x,int curseur_y,AABB box)

Notes :

- Je renvoie un bool même si celui-ci n'est pas défini en C, vous adapterez si besoin. Ce choix a été fait pour donner davantage de sémantique au code. Vous pouvez définir en C le type et les deux constantes suivantes :

typedef int bool;
#define true 1
#define false 0

- Idéalement, en C, il est préférable de passer un pointeur vers une structure plutôt que la structure entière, cependant, ce tutoriel voulant rester théorique, je n'alourdirai pas le code par des pointeurs.

Le calcul est très simple : il y a collision si et seulement si le point est à l'intérieur de la boite.
Le point supérieur gauche est : (box.x;box.y)
Le point inférieur droit est : (box.x+box.w-1;box.y+box.h-1)

Pourquoi -1 ? Parce que nous commençons à 0. Si nous ajoutons juste box.w à box.x, nous tombons sur le premier point hors de la boite. Cependant, on peut se passer du -1 si on considère que le point testé sera strictement inférieur à ce premier point après la boite.

Du coup, la fonction de collision est triviale :

bool Collision(int curseur_x,int curseur_y,AABB box)
{
if (curseur_x >= box.x
&& curseur_x < box.x + box.w
&& curseur_y >= box.y
&& curseur_y < box.y + box.h)
return true;
else
return false;
}

Note : il m'a été reproché de faire un if avec return true ou false, au lieu de mettre directement la condition dans le return, comme le permet le langage C. Ce choix a été fait pour des raisons de clarté, de sémantique, et de compréhension, car tous les langages ne permettent pas de factoriser de la sorte. Si vous trouvez ça horrible, vous pouvez bien sûr adapter.

Je pense que la fonction parle d'elle-même. Voici donc notre première fonction de collision !

Les bibliothèques graphiques 2D utilisent souvent des nombres entiers (int, short…) pour les coordonnées. On parle de coordonnées discrètes. On dit qu'on est dans le plan N^2. Si vous faites de la 2D avec OpenGL, avec glOrtho, vous utilisez des float pour les coordonnées. On parle de coordonnées réelles, on est dans le plan R^2. Cet algorithme marche aussi bien dans N^2 que dans R^2 (il suffit d'adapter les coordonnées en float).

IV - Collision entre deux Axis Aligned Bounding Box

Voici un autre test de collision.
Cette fois-ci, nous allons voir comment tester la collision entre deux AABB.

IV-A - Applications

Cette fonction est extrêmement utilisée dans énormément de jeux.

Nous voyons à gauche ce cher Mario. Il a sa boite englobante (en vert), et la tortue aussi. Comment voir s'il la touche ? Eh bien en testant une collision entre deux boites englobantes.
Pareil, à droite, Gradius est un shoot'em up à l'ancienne. Chaque vaisseau, chaque missile ont leur boite englobante. Il faut tester les collisions entre notre vaisseau et tous les vaisseaux et missiles ennemis (ce qui nous fait perdre), et également la collision entre nos missiles et les vaisseaux ennemis (pour les détruire).

Il y a beaucoup de collisions à tester, cela doit donc être rapide de préférence.

IV-B - Calcul de collision

La signature de notre fonction sera la suivante :

bool Collision(AABB box1,AABB box2)

L'idée est la suivante. Regardons le petit schéma ci-dessous :

Le rectangle rouge est box1. J'ai dessiné des traits, rouge, bleu, jaune et vert, en prolongeant les côtés à l'infini. Pour savoir si un autre rectangle touche le rectangle rouge, raisonnons à l'envers : essayons de savoir quand il ne touche pas.
Un rectangle box2 ne touche pas si :

- il est complètement à gauche de la ligne jaune ;

- il est complètement à droite de la ligne verte ;

- il est complètement au-dessus de la ligne bleue ;

- il est complètement au-dessous de la ligne rouge.

Voyons avec le dessin ci-dessous les exemples :

- le rectangle bleu est non seulement complètement à gauche de la ligne jaune, mais aussi complètement au-dessous de la ligne rouge : il ne touche pas ;

- le rectangle vert est complètement au-dessus de la ligne bleue : il ne touche pas ;

- Le rectangle jaune n'est ni complètement en haut, ni à gauche, ni à droite, ni en bas : il touche.

Voici la règle énoncée :

Si la box2 est complètement à gauche, ou complètement en haut, ou complètement à droite, ou complètement en bas, alors elle ne touche pas. Sinon, elle touche.

Pour savoir si la box2 est à droite du trait vert (donc trop à droite), on regarde simplement si sa coordonnée x (son minimum en x) est plus grande que le maximum en x de box1 (le maximum en x étant box1.x + box1.w -1).
Donc on obtient le test suivant :

Ce qui équivaut à :

Pour les quatre autres directions, le calcul est similaire.

La fonction suivante en découle :

bool Collision(AABB box1,AABB box2)
{
if((box2.x >= box1.x + box1.w)      // trop à droite
|| (box2.x + box2.w <= box1.x) // trop à gauche
|| (box2.y >= box1.y + box1.h) // trop en bas
|| (box2.y + box2.h <= box1.y))  // trop en haut
return false;
else
return true;
}

La rapidité de cette collision est assurée. En très peu de calculs, on a notre résultat, ce qui permet de pouvoir faire beaucoup de tests dans le jeu sans ralentissements.
Cette collision peut paraître grossière, mais elle est souvent largement suffisante pour beaucoup de cas. D'autres collisions plus fines, mais aussi plus coûteuses en temps de calcul, utiliseront cette collision auparavant, afin d'éliminer facilement les cas où les objets ne se touchent clairement pas.

- Notez qu'on se moque de savoir quelle est la box1 et quelle est la box2. Si la box1 touche la box2, alors la box2 touche aussi la box1.

- Ça fonctionne avec des boîtes de tailles différentes, aucune restriction sur ce point.

- Cet algorithme marche aussi bien dans N^2 que dans R^2.

V - Cercles

Les cercles sont également fort intéressants pour les collisions. On peut très rapidement tester si un point est dans un cercle, ou si deux cercles se touchent, ce qui peut être fort utile.

V-A - Définitions

Un cercle, c'est un centre x,y et un rayon.

Nous pouvons immédiatement définir une structure de cercle :

struct Cercle
{
int x,y;
int rayon;
};

V-B - Applications

Imaginons que vous vouliez cliquer dans une zone de cercle (crever des ballons par exemple), ou alors que vous fassiez un jeu de billard ou un jeu du genre Puzzle Bubble (même si je ne suis pas sûr que Puzzle Bubble utilise rigoureusement cette collision), alors cette collision vous sera fort utile.

V-C - Calcul de collision

V-C-1 - Point dans un cercle

Tout d'abord, voyons le cas d'un point dans un cercle.
La signature de notre fonction sera la suivante :

bool Collision(int x,int y,Cercle C)

Vous souhaitez savoir si le point x,y est dans le cercle ou non.
C'est très simple, il suffit de calculer la distance du point x,y au centre du cercle. Si cette distance est supérieure au rayon, alors vous êtes dehors, sinon, vous êtes dedans.

Pour le calcul de distance, pensez à Pythagore. Le calcul de la distance euclidienne dans un plan se calcule simplement :

Le seul inconvénient de cette méthode, c'est qu'il y a une racine carrée. C'est une opération assez coûteuse, même si maintenant, les machines sont suffisamment puissantes pour ne pas trop s'en rendre compte. Si on peut l'éviter, alors on l'évite.

Et dans notre cas, on peut. En effet, on souhaite savoir si d>C.r ou pas. Or, d et C.r étant positifs, on peut dire que :

Du coup, la racine carrée disparaît :

La fonction de collision est donc très simple :

bool Collision(int x,int y,Cercle C)
{
int d2 = (x-C.x)*(x-C.x) + (y-C.y)*(y-C.y);
if (d2>C.rayon*C.rayon)
return false;
else
return true;
}

Note : en C, la « puissance 2 » n'existe pas. Je multiplie donc (x-C.x)*(x-C.x), ce qui en soi est un vilain copier/coller, et un calcul fait deux fois. On pourrait éviter ça avec des variables intermédiaires, mais y gagnerait-on en vitesse ? Pas sûr. Une chose par contre est sûre, n'utilisez pas la fonction pow() en C pour faire des carrés, jamais. C'est sortir l'artillerie lourde, et perdre du temps, pour une simple mise au carré.

Note : une idée pour optimiser davantage est de stocker directement le rayon au carré dans la structure du cercle. Si le rayon reste constant, on gagnera en optimisation en évitant à chaque fois de recalculer C.rayon * C.rayon.

V-C-2 - Collision de deux cercles

Nous souhaitons maintenant savoir si deux cercles se touchent. Pour un jeu de billard par exemple, c'est fort utile.

La signature de notre fonction sera celle-ci :

bool Collision(Cercle C1,Cercle C2)

Comment savoir si deux cercles se touchent ? En réalité, c'est très simple : nous mesurons la distance entre leurs deux centres, et il suffit de voir si cette distance est supérieure ou inférieure à la somme des rayons.

La distance entre les rayons sera bien sûr un calcul similaire à ce qu'on a vu au-dessus :

L'astuce pour éliminer les carrés est la même. Nous obtenons donc la fonction suivante :

bool Collision(Cercle C1,Cercle C2)
{
int d2 = (C1.x-C2.x)*(C1.x-C2.x) + (C1.y-C2.y)*(C1.y-C2.y);
if (d2 > (C1.rayon + C2.rayon)*(C1.rayon + C2.rayon))
return false;
else
return true;
}

- Cela fonctionne même avec des cercles de rayons différents. Une bille et une boule de pétanque par exemple.

- Cet algorithme marche aussi bien dans N^2 que dans R^2.

Note : si le rayon des cercles est constant, alors (C1.rayon + C2.rayon) * (C1.rayon + C2.rayon) est constant aussi. On pourrait donc, si besoin, stocker cette valeur quelque part pour optimiser le calcul au lieu de le refaire à chaque fois. Merci à Sylvior pour cette remarque.

Tous ces algorithmes sont très rapides et utiles pour beaucoup de problèmes.

Navigation

Sommaire

Tutoriel suivant : formes complexes