Formes simples

Définitions

Tout d’abord définissons AABB : « Axis Aligned Bounding Box ». Il s’agit d’un rectangle aligné avec les axes, c’est à dire que ses coté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 OBB : « Oriented Bounding Box », qui est un rectangle qui peut être orienté : ses cotés ne sont pas obligatoirement parallèles aux axes de votre repère.

Une AABB peut être définie par 4 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 (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.

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 la première image, 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.

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 tuto 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 box.

• 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 box. 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 box.

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 !

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

Applications

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

Nous voyons en haut 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 2 Bounding box.

Pareil, en bas, Gradius est un shoot’em up à l’ancienne. Chaque vaisseau, chaque missile, a sa bounding box. 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.

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 coté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 en haut de la ligne bleue ;
• il est complètement en bas de la ligne rouge.

Voyons avec le dessin ci-dessus des exemples.

• Le rectangle bleu est non seulement complètement à gauche de la ligne jaune, mais aussi complètement en bas 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.

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 :

$box2.x > box1.x + box1.w − 1$

Ce qui équivaut à :

$box2.x >= box1.x + box1.w$

Pour les 4 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 calcul, 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 ou les objets ne se touchent clairement pas.

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.

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;
};

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 sur que Puzzle Bubble utilise rigoureusement cette collision), alors cette collision vous sera fort utile.

Calcul de collision

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. La distance Euclidienne dans un plan se calcule simplement.

$d = \sqrt{(x − C_x)^2 + (y − C_y)^2}$

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 $d > C_r \iff d^2 > C_r^2$.

Du coup, la racine carré disparaît.

$d^2 = (x − C_x)^2 + (y − C_y)^2$

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 : une idée pour optimiser davantage est de stocker directement le rayon au carré dans la structure du cercle. Si le rayon reste contant, on gagnera en optimisation en évitant à chaque fois de recalculer C.rayon * C.rayon.

Collision de 2 cercles

Nous souhaitons maintenant savoir si 2 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.

$d = \sqrt{(C1_x − C2_x)^2 + (C1_y − C2_y)^2}$

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;
}

Note : si le rayon des cercles est constant, alors (C1.rayon + C2.rayon) * (C1.rayon + C2.rayon) est contant 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.