Théorie des collisions : Formes 2D simples

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.

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.

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 :
   

  Sélectionnez

  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 !

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.

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 :

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.

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

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-1. Point dans un cercle▲

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

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

V-C-2. Collision de deux cercles▲

bool Collision(Cercle C1,Cercle C2)

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