Théorie des collisions : Décor

Le sol plat n'a qu'un seul paramètre : son altitude a. Nous souhaitons savoir si la boite englobante de notre personnage passe à travers ou pas.

La signature de notre fonction sera la suivante :

bool Collision(AABB box,int a)

Pour savoir si on passe à travers, c'est très simple : si l'ordonnée du point du bas de la boite englobante est supérieure à 'a', alors on passe à travers, sinon, non.

La fonction est donc triviale :

bool Collision(AABB box,int a) 
{ 
   if (box.y + box.h >=a) 
      return true; 
   else 
      return false; 
}

Souvenez-vous de vos cours de maths. Une fonction cartésienne f(x) = y a cette forme :

Voici une belle fonction sinus (à gauche). Pensez-vous qu'on puisse marcher dessus ? En réalité, c'est très facile…

Notre fonction aura cette signature :

bool Collision(AABB box,fonction f)

f est un pointeur de fonction (c'est pour illustrer le principe, vous pouvez faire sans).

Pour savoir si le perso touche ou pas la fonction, nous n'allons considérer qu'un seul point x,y : celui en bas au milieu de la AABB (point mauve sur l'image de droite ci-dessus).
Comment savoir si le joueur est au-dessus ou en dessous de la courbe ? Il suffit de voir si f(x) > y ou non.

Cela donne la chose suivante :

bool Collision(AABB box,fonction f) 
{ 
   int x = box.x + box.w/2;  // point milieu bas. 
   int y = box.y + box.h; 
   if (f(x)>y) 
      return true; 
   else 
      return false; 
}

Toute la difficulté revient à avoir l'équation du sol. Il faut pouvoir dire, pour un x donné, où est la coordonnée y du sol, un f(x) = y. Souvent, on voudra une courbe qui passe par des points qu'on aura choisis. Les splines cubiques sont de bonnes candidates. Mais cela sort du cadre de ce tutoriel.

Ce chapitre vous montre déjà comment marcher sur une fonction mathématique... Vous penserez à un petit bonhomme qui se déplace sur la fonction que votre prof de maths dessinera au tableau ! :p

J'ai même une astuce supplémentaire pour vous faire utiliser les dérivées.
Dans certains jeux où il y a des pentes, le personnage peut gravir la pente si elle est douce, et glisse si elle est « trop raide ». Comment savoir cela ? Il suffit de calculer la dérivée f'(x), et de voir sa valeur absolue. Si elle est plus grande qu'un seuil que vous fixerez, vous pourrez dire que c'est trop pentu et jouer en conséquence…

Le calcul de dérivée, vous n'avez pas à le programmer, vous le précalculez sur une feuille. Par exemple, si vous marchez sur la fonction sin(x), vous savez que sa dérivée est cos(x).
Pour les splines cubiques, ce sont des polynômes. Un polynôme se dérive facilement…

Cette technique de collision n'est pas très utilisée dans les jeux 2D (à ma connaissance), les jeux de plateforme avec pentes préfèreront un concept de tuiles améliorées, dont nous parlerons plus bas. Cependant, beaucoup de jeux 3D utilisent ce concept, dans ce qu'on appellera le Heightmap. Nous verrons ça par la suite.

Comment savoir si un point donné touche un mur ou non ? Cela est extrêmement simple.

Vous avez un point x,y à tester. Il suffit de savoir au-dessus de quelle case de la grille il est. On regardera ensuite si la tuile correspondante à cette case est un mur ou non…
Nous partons du principe que la grille commence aux coordonnées 0,0.

Il suffira, pour avoir les coordonnées i,j de la tuile concernée, d'une simple division…
i = x/LARGEURTILE
j = y/HAUTEURTILE

Nous prendrons la partie entière de i et j.
Autrement dit, si la division donne 5.1 ou 5.9, nous prendrons 5.
En C, le fait de diviser deux entiers donne une division entière, ce qui donne notre résultat.

Cela nous donne immédiatement le code suivant :

bool CollisionTile(int x,int y) 
{ 
   int i = x/LARGEUR_TILE;   
   int j = y/HAUTEUR_TILE; 
   return TileIsMur(i,j); 
}

Variante :
Si votre grille ne démarre pas aux coordonnées 0,0 mais aux coordonnées a,b, la variante est extrêmement simple :

int i = (x-a)/LARGEUR_TILE;
int j = (y-b)/HAUTEUR_TILE;

Votre Mario n'est pas un point, mais une AABB, et vous souhaitez savoir s'il touche un mur.
Regardons le dessin ci-dessous :

Nous voyons la grille, et quelques AABB à tester (en couleurs claires).
Pour savoir si le personnage touche le mur, il suffit de tester toutes les tuiles que coupe la AABB.

Eh bien non, puisque comme la grille est droite, et que la AABB aussi, alors il suffira de considérer i1,j1 comme le point supérieur gauche de la AABB, et i2,j2 comme le coin inférieur droit. Les tuiles concernées seront toutes celles dans le rectangle i1,j1 et i2,j2.
Sur le dessin, cela nous donne les tuiles remplies de couleur foncée.

Voici le code :

bool CollisionTiles(AABB box) 
{ 
   i1 = box.x/LARGEUR_TILE;; 
   j1 = box.y/HAUTEUR_TILE; 
   i2 = (box.x + box.w -1)/LARGEUR_TILE;  
   j2 = (box.y + box.h -1)/HAUTEUR_TILE; 
   int i,j; 
   for(i=i1;i<=i2;i++) 
   { 
     for(j=j1;j<=j2;j++) 
     { 
         if (TileIsMur(i,j)) 
             return true; 
     } 
   } 
   return false;  // si on n'est pas sorti avant, c'est qu'on ne touche aucune tuile. 
}

Imaginons que vous ayez un point x,y (sur l'écran), et vous avez envie de savoir sur quelle tuile isométrique il est. (Par exemple, vous voulez cliquer dessus.)
Revoyons notre image :

Ma grille isométrique commence au point O de coordonnées Ox,Oy.
Je définis le repère du monde de tuiles par deux vecteurs X et Y, sont les vecteurs kitxmlcodeinlinelatexdvp\vec{X} = \vec{OB}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\vec{Y} = \vec{OA}finkitxmlcodeinlinelatexdvp.

Si on considère O comme le point d'ancrage de la tuile de coordonnées (0,0), pour avoir le point d'ancrage P de la tuile de coordonnées (i,j), il suffit de faire :

Si on pose Q de coordonnées (i,j), on a alors, de façon matricielle :

Avec M la matrice du repère O,X,Y :

Ce qui nous donne :

Ceci est l'écriture matricielle de : kitxmlcodeinlinelatexdvpP = M*Qfinkitxmlcodeinlinelatexdvp.

Grâce à cela, pour un couple i,j donné, nous pouvons calculer le point correspondant dans le repère de l'écran.

SikitxmlcodeinlinelatexdvpP = M*Qfinkitxmlcodeinlinelatexdvp alors Si kitxmlcodeinlinelatexdvpQ = M^{-1}*Pfinkitxmlcodeinlinelatexdvp

kitxmlcodeinlinelatexdvpM^{-1}finkitxmlcodeinlinelatexdvp est l'inverse de la matrice M.

Si vous ne connaissez pas les matrices en maths, sachez juste que c'est un outil puissant pour changer de repère. Votre écran est un repère, la grille en est un autre. Vous avez un point dans un repère, vous voulez savoir quelles sont ses coordonnées dans l'autre ? Utilisez des matrices.

Voici donc les étapes que nous devons effectuer :

• nous avons A,B,C, et x,y dans l'écran ;
• nous devons calculer kitxmlcodeinlinelatexdvp\vec{X}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\vec{Y}finkitxmlcodeinlinelatexdvp ;
• nous devons calculer P ;
• nous devons construire M ;
• nous devons calculer kitxmlcodeinlinelatexdvpM^{-1}finkitxmlcodeinlinelatexdvp ;
• nous devons multiplier cette dernière par P.
• Nous récupérons Q, nous faisons une division entière comme pour les tuiles droites ci-dessus, et nous pourrons dire que le clic x,y touche la tuile i,j

Calculer kitxmlcodeinlinelatexdvp\vec{X}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\vec{Y}finkitxmlcodeinlinelatexdvp :

Si on regarde le dessin ci-dessus, c'est simple !

Ce sont des vecteurs, on pose 0 comme dernières coordonnées.

O est le point origine de la grille. On peut l'écrire ainsi :

O est un point, on pose 1 comme dernière coordonnée.

Calculer P :

P, c'est le point que j'ai en entrée.

P est un point, on pose 1 comme dernière coordonnée.

Nous cherchons :

Q est un point, on pose 1 comme dernière coordonnée.

calculer M

La matrice d'un repère en 2D est une matrice 3 lignes et 3 colonnes. La construire est simple, ayant le repère O,kitxmlcodeinlinelatexdvp\vec{X}finkitxmlcodeinlinelatexdvp,kitxmlcodeinlinelatexdvp\vec{Y}finkitxmlcodeinlinelatexdvp, la matrice est simplement (kitxmlcodeinlinelatexdvp\vec{X}finkitxmlcodeinlinelatexdvp,kitxmlcodeinlinelatexdvp\vec{Y}finkitxmlcodeinlinelatexdvp,O)

Si on prend l'expression des points et vecteurs ci-dessus, on trouve bien :

calculer kitxmlcodeinlinelatexdvpM^{-1}finkitxmlcodeinlinelatexdvp

kitxmlcodeinlinelatexdvpM^{-1}finkitxmlcodeinlinelatexdvp est l'inverse de la matrice M. Je vous renvoie à vos cours de maths. Nous trouvons :

kitxmlcodeinlinelatexdvpM^{-1}finkitxmlcodeinlinelatexdvp =

Multiplication par P

Enfin, pour avoir Q, et donc i et j, il faut multiplier kitxmlcodeinlinelatexdvpM^{-1}finkitxmlcodeinlinelatexdvp par P, ce qui nous donne :

Au niveau du code, cela nous donne :

bool CollisionIso(Point O,Point A,Point B,float x,float y) 
{ 
  Vecteur X,Y; 
  X.x = B.x - O.x; 
  X.y = B.y - O.y; 
  Y.x = A.x - O.x; 
  Y.y = A.y - O.y; 
  float denom = X.x*Y.y-X.y*Y.x;  
// coordonnées réelles de x,y dans repère de la grille. 
  float fi = (Y.y*x - Y.x*y + Y.x*O.y-O.x*Y.y)/denom;  // i et j non tronqués. 
  float fj = -(X.y*x - X.x*y + X*x*O.y-O.x*X.y)/denom; 
// prendre la partie entière pour savoir sur quelle tuile on est. 
  int i = (int)fi; 
  int j = (int)fj;  // vous pouvez modifier la fonction pour renvoyer i et j. 
// est-ce que cette tuile est un mur ? 
  return TileIsMur(i,j); 
}

Je suis sûr que vous me voyez déjà venir avec de gros calculs, mais il n'en est rien ici.

L'astuce, quand on fait un jeu isométrique, c'est de garder en mémoire les mêmes données que si c'était droit. En effet, si on regarde un jeu isométrique, on peut l'imaginer comme un jeu « droit ».
Tout calcul de collision entre objets marchera de la même manière.

Et c'est seulement au moment de l'affichage que vous dessinerez vos tuiles en biais.
Et c'est également seulement quand vous cliquez sur une tuile que vous calculerez le point dans le repère de la grille comme vu au chapitre précédent.
Mais en mémoire, tout se passe dans le repère de la grille.

Donc toute collision entre objets, tout objet avec les murs, se passe comme dans un monde de tuiles droites.

D'autres types de collisions viendront enrichir prochainement ce paragraphe.