Théorie des collisions : Collisions spécifiques

On ne présente plus Pong : deux raquettes et une balle. La balle rebondit sur les murs, et si on ne la rattrape pas, on perd le point.

L'algorithme de collisions testera donc la collision avec chacune des raquettes. La balle est carrée, les raquettes sont rectangles, comme dans le Pong original.
Notez que si la balle est ronde, on peut considérer sa zone de collision comme un carré.

Notre première approche sera donc de détecter les collisions AABB, vues au début de ce chapitre, entre la balle et chacune des raquettes.

Cela serait rapide avec nos machines actuelles. À chaque itération de notre boucle principale, deux tests de collision à faire. Le if qu'il y a dans la fonction de collision effectue cependant plusieurs tests, même s'ils sont rapides.

Nous pouvons aller encore plus vite, et faire moins de calcul, ce qui n'était pas du luxe pour les premières machines qui ont fait tourner Pong.

Regardons l'image ci-dessus. J'ai rajouté deux traits verticaux rouges.
L'idée est simple, si la balle traverse un de ces traits rouges, alors on doit tester si on touche la raquette concernée ou non. Soit la balle rebondit, soit on perd un point.

Dans Pong, les raquettes se déplacent verticalement, mais pas latéralement. De ce fait, la position de ces hypothétiques traits rouges sera constante.

Si on regarde à gauche, le trait rouge touche la raquette, si on regarde à droite, ce n'est pas le cas, pourquoi ? Eh bien parce que la position de la balle est définie par son coin supérieur gauche. De ce fait, si le coin supérieur gauche touche le trait rouge de droite, alors la balle touche la raquette, l'espace entre le trait et la raquette étant la largeur de la balle. Cela nous évitera de calculer sans cesse le point de droite de la balle.

De ce fait, dans notre boucle principale, au lieu d'appeler deux fois une fonction de collision à plusieurs tests, nous allons faire uniquement deux tests :

if (balle.x<X_TRAIT_ROUGE_GAUCHE) 
{ 
  TestCollisionY(balle,raquette1); 
  ... 
} 
if (balle.x>X_TRAIT_ROUGE_DROITE) 
{ 
  TestCollisionY(balle,raquette2); 
  ... 
}

Dans la majorité des cas, quand la balle transite au milieu, on ne rentrera pas dans ces if.
Que faire maintenant si on rentre dans le if ?

Il suffira de tester la position y de la balle, par rapport à celle de la raquette.

La balle touchera la raquette si :

• balle.y + balle.h > raquette.y
• balle.y < raquette.y + raquette.w

Sinon, elle ne touche pas, et on perd le point.

Cela peut s'écrire aussi :

• balle.y > raquette.y - balle.h
• balle.y < raquette.y + raquette.w

Si on regarde de nouveau le dessin ci-dessus, on voit le trait jaune qui correspond à la position « raquette.y - balle.h ».

Cet algorithme sera un petit peu plus rapide que les collisions AABB, et il est plus intuitif, même si sur nos machines actuelles, cela n'a plus aucune importance pour un Pong. :)

Vous avez dessiné une piste comme ci-dessous :

Votre route est la zone marron. Vous êtes le véhicule bleu, et vous souhaitez tester les collisions avec le décor (le vert). L'idée étant de ne pas sortir. Vous déplacez votre véhicule et vous voulez tester la collision avec le décor.

IV-A-1. Pourquoi un cercle▲

Dans ce genre de jeux, la voiture peut tourner à 360 °. Nous pouvons donc considérer une OBB qui s'adaptera à l'angle de rotation de la voiture, ou bien considérer que la voiture n'est pas trop longue, et donc s'inscrira dans un cercle qui lui ne dépendra donc pas de l'angle de rotation, ce sera plus simple, et tout aussi efficace.

Voici une image du jeu « Micro Machines » qui gère probablement ses collisions avec des cercles. J'ai rajouté les cercles moi-même sur l'image, en mauve :

Si on considère le problème de cette manière, la première idée est de tester la collision d'un cercle avec des pixels verts. En effet, si un seul pixel bleu touche le vert, alors il y a collision. Nous pensons donc à ce lourd algorithme qu'est le pixel perfect, décrit plus haut dans ce tutoriel.

L'idée sera donc de tester chaque point du cercle, et voir s'il touche le bord. C'est assez long et lourd.

Nous avons donc dit que nous allions nous servir du cercle pour les collisions. Mais au lieu de tester chaque point du cercle, nous allons nous appuyer sur une propriété du cercle :

Citation : Prof de maths

Tous les points du cercle sont à égale distance du centre, cette distance s'appelle rayon

Donc l'idée est simple, au lieu de considérer tout le cercle et chacun de ses points, on ne considère que le centre du cercle, et on regarde si sa distance au bord de la route est inférieure ou supérieure au rayon. Pour cela, nous allons dessiner sur la carte les zones ou la distance au bord est plus petite que le rayon. Cela, on peut le définir graphiquement, regardez :

Ici, j'ai redessiné la même route, mais, j'ai dessiné au bord une bande rouge qui a pour largeur le rayon du cercle.
J'ai redessiné le cercle bleu. Le cercle touche la bordure verte. On constate que son centre, lui, touche la bordure rouge.
On peut donc dire :

L'idée sera donc de dessiner cette bande rouge sur le schéma de vos circuits. Évidemment, vous ne serez pas obligés de l'afficher. Nous utiliserons donc le concept plus rapide des masques décrit dans le chapitre précédent, vous pourrez avoir deux images : une pour le circuit, une pour le masque.

IV-C-1. Collision▲

IV-C-2. Dessiner la bande rouge▲

Pour la plupart d'entre vous, cette partie ne servira pas. Un coup de pinceau de bonne largeur dans Paint suffit à donner un bon résultat.

Cette partie sert juste à définir mathématiquement le concept évoqué.

Si on considère que le bord de la route est une courbe C, alors le bord de la zone rouge est la courbe offset O de la courbe C, à distance d.
Une courbe d'offset, c'est une courbe dont chaque point est à une distance d fixée de la courbe originale. Ci-dessus, si on regarde la courbe bleu ciel, elle est en tout point à égale distance de la courbe marron. Chaque segment bleu fait la même longueur.

La courbe offset O(u), à distance d, de la courbe C(u) se définit par la formule suivante :

N(u) est la normale à la courbe au point de paramètre u.

kitxmlcodeinlinelatexdvpN(u) = \frac{C'(u)\wedge{A}}{||C'(u)\wedge{A}||}finkitxmlcodeinlinelatexdvp avec A vecteur normal au plan kitxmlcodeinlinelatexdvpA = {0,0,1}finkitxmlcodeinlinelatexdvp.

Nous allons parler des labyrinthes basés sur une grille, comme ci-dessous :

Il existe plusieurs types de codage pour les labyrinthes.

En voici deux formes :

La première forme, nous l'avons déjà rencontrée quand nous parlions du tile mapping dans ce tutoriel. La collision est donc du même type, à savoir déterminer au-dessus de quelle(s) case(s) est notre personnage, puis dire qu'il y a collision si une de ces cases est un mur.

Nous allons nous intéresser au deuxième cas, où cette fois les murs sont fins, et sont les bords de chaque carré de la grille.

V-A-1. Codage▲

Avant de parler collision, il faut voir comment ceci est codé en mémoire. Ici, nous considèrerons un codage basé sur une grille comme le tile mapping.

Nous aurons donc le labyrinthe stocké en tant que tableau en deux dimensions de « Case ». Chaque case aura chacun de ses bords qui sera un mur ou non. La première idée est donc de se dire « chaque case a donc quatre murs potentiels », un en haut, un en bas, un à gauche, un à droite. Mais si vous regardez mieux, vous verrez qu'on peut même considérer chaque case comme ayant potentiellement deux murs : un en haut, un à gauche.

Regardez cette image :

Voici les quatre types de cases nécessaires et suffisants pour reconstruire le labyrinthe ci-dessus. Regardez l'image ci-dessus et constatez que l'on peut construire ce résultat avec seulement ces quatre cases-là.

C'est économique, et il n'y a pas de redondances, contrairement à un codage avec quatre murs par case.

Le seul inconvénient, qui n'en est pas vraiment un, est qu'on n'ira jamais sur les cases tout à droite et tout en bas du labyrinthe : l'image ci-dessus le montre, on a l'impression que la ligne du bas, et la colonne de droite sont de trop, alors qu'elles permettent simplement de ne pas faire d'exceptions pour notre codage.

Bref, un labyrinthe est donc un tableau en 2D de cases qui contiennent chacune uniquement deux bits : une pour le mur d'en haut (présent ou non), un pour le mur de gauche.

Si on illustre cela par du pseudocode, on obtient :

 

Sélectionnez

struct Case 
{ 
  unsigned int murgauche:1;  // variable d'un bit 
  unsigned int murhaut:1;  // variable d'un bit 
}; 

struct Laby 
{ 
   struct Case** Tableau;   // tableau 2D. Certains préfèreront la syntaxe : Case[X][Y]; 
   int X,Y;  // taille labyrinthe 
   int LARGEURCASE,HAUTEURCASE; // nom explicite 
   int Orx,Ory;  // Origine du labyrinthe en x et y : si la première case ne commence pas à (0,0) 
};

À partir de là, voici comment on va faire pour savoir si on touche un mur. Observons ci-dessous une image qui nous servira d'exemple :

Les carrés de couleur creux représentent les AABB de notre personnage, et les zones de couleurs derrière représentent les cases de la grille impliquées.

Le calcul de zones de couleur derrière se fait de la même manière que dans le cas des tuiles vu. Rappelez-vous, la zone sera rectangulaire, les coordonnées minimales seront les coordonnées de la zone que touche le point en haut à gauche, et les coordonnées maximales seront les coordonnées de la zone que touche le point en bas à droite.

Tout s'appuie donc sur une fonction GetPointPosition, qui va, pour un pixel x,y donné, dire dans quelle case (xc,yc) il est :

void GetPointPosition(Laby L,int x,int y,int* xc,int* yc) 
{ 
   *xc = (x-L.Orx)/L.LARGEURCASE; 
   *yc = (x-L.Ory)/L.HAUTEURCASE; 
}

Notez que si votre grille commence à la coordonnée (0,0), alors on retombe sur une simple division.

Le début de la fonction collision consiste donc à calculer xmin,ymin,xmax,ymax, coordonnées minimales et maximales des cases à analyser en fonction de la AABB de notre personnage à tester.

int Collision(Laby L,AABB box) 
{ 
   int xmin,xmax,ymin,ymax; 
   GetPointPosition(L,box.x,box.y,&xmin,&ymin); 
   GetPointPosition(L,box.x+box.w-1,box.y+box.h-1,&xmin,&ymin); 
   ... 
}

Une fois que nous avons xmin,xmax,ymin,ymax, il ne reste plus qu'à tester s'il y a un mur au milieu de la zone.

Si on regarde la zone rouge ci-dessus : le personnage est inclus dans une seule case. On a xmin = xmax et ymin = ymax : pas de collision avec le mur possible.

Si on regarde la zone bleue : il y aura collision uniquement si la case de droite a son mur gauche actif (concrètement, le mur vertical entre les deux).

Si on regarde la zone violette, il faudra vérifier tous les murs (traits noirs) au milieu, et pareil pour la zone jaune, où l'on considère un gros personnage !

Si un seul de ces murs est présent, alors notre personnage touche un mur, et il y a collision.

Le code suivant illustre simplement cela :

int Collision(Laby L,AABB box) 
{ 
   int xmin,xmax,ymin,ymax; 
   GetPointPosition(L,box.x,box.y,&xmin,&ymin); 
   GetPointPosition(L,box.x+box.w-1,box.y+box.h-1,&xmin,&ymin); 
   for(i=xmin;i<=xmax;i++) 
   { 
     for(j=ymin;j<=ymax;j++) 
     { 
       if (i!=xmin && L.Tableau[i][j].murgauche==1) 
          return 1; 
       if (j!=ymin && L.Tableau[i][j].murhaut==1) 
          return 1; 
     } 
   } 
   return 0; // pas de collision. 
}

Cette partie pourra s'étoffer avec le temps. Je pioche bien souvent mes idées dans les différents sujets que je peux lire sur ce site.

D'autres algorithmes existent et seront abordés plus tard, selon l'avancement de ce tutoriel.