Théorie des collisions : Décor

Fvirtman

Jusqu'à présent, nous avons vu les collisions entre objets potentiellement mobiles.
Nous allons ici voir les différentes collisions avec des décors fixes.

Commentez

- Titre : Théorie des collisions : Décor

- Auteur : Fvirtman

- Parution : 26 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. Sol

- III-A. Applications

- III-B. Calcul de collision

- III-B-1. Sol plat

- III-B-2. Sol courbe

- IV. Tuiles droites

- IV-A. Définition

- IV-B. Applications

- IV-C. Calcul de collision

- IV-C-1. Juste un point dans le mur

- IV-C-2. Une AABB dans le mur

- V. Tuiles isométriques

- V-A. Définition

- V-B. Applications

- V-C. Calcul de collision

- V-C-1. Point dans une tuile isométrique

- V-C-2. Rectangle dans tuile isométrique

- Navigation

Navigation

Tutoriel précédent : formes complexes

Sommaire

Tutoriel suivant : partitionnement de l'espace

II - Introduction

Jusqu'à présent, nous avons vu les collisions entre objets potentiellement mobiles.
Nous allons ici voir les différentes collisions avec des décors fixes.

III - Sol

Nous allons voir maintenant comment tester la collision avec le sol.
Tout d'abord avec un sol plat, puis un sol bien courbe.

III-A - Applications

Nous voyons à gauche Street Fighter 2 où le sol est plat. Si le personnage saute et retombe sur le sol, il faut qu'il s'arrête. À droite, Rayman évolue dans un monde où le sol est en pente. En réalité, je pense que Rayman utilise un système de tuiles amélioré, mais imaginons que non.

III-B - Calcul de collision

III-B-1 - Sol plat

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

III-B-2 - Sol courbe

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.

IV - Tuiles droites

Dans beaucoup de jeux 2D, les décors sont définis par des tuiles.

IV-A - Définition

Les jeux exploitant le tilemapping sont reconnaissables par leurs carreaux répétitifs régulièrement placés. Si on regarde l'image ci-dessous :

Nous pouvons constater que les blocs se répètent et s'inscrivent exactement dans une grille de taille régulière.
Stocker le TileMapping en mémoire revient juste à stocker les dessins de quelques blocs, et un tableau de nombres (appelés indices), qui permettent de construire l'image, comme le montre ce schéma :

À gauche, j'ai huit petits dessins (numérotés de 0 à 7). Au milieu, j'ai un tableau de nombres. À partir de là, je peux reconstruire l'image de droite. Pour afficher l'image, il suffira d'appliquer l'algorithme formel suivant :

// soit T le tableau de nombres, de dimension X,Y
for(i=0;i<X;i++)
{
for(j=0;j<X;j++)
{
typetile = T[i][j];
px = i*LARGEUR_TILE;
py = i*HAUTEUR_TILE;
BlitTile(typetile,px,py);   // blit le tile typetile a la position px,py
}
}

La grille étant régulière, LARGEUR_TILE et HAUTEUR_TILE sont constants. Sur le dessin ci-dessus, c'est l'écart qu'il y a entre deux lignes verticales (pour la largeur), et deux lignes horizontales (pour la hauteur).

Même si parfois, en mémoire, c'est légèrement plus complexe, il y a toujours cette notion de tableau à deux dimensions qui réfèrent un type de tuile. Certaines tuiles seront des murs, d'autres non.

Pour ce tutoriel, je définirai la fonction suivante :

bool TileIsMur(int i,int j);

qui me dira si la tuile à la position i,j est un mur ou non.

IV-B - Applications

Les jeux utilisant le tilemapping sont légion.

Zelda, Mario, les jeux de plateforme des consoles 8 bits et 16 bits utilisent du tilemapping.
Même si, dans le 3e exemple (secret of mana), ce n'est pas flagrant, ce sont des tuiles.

IV-C - Calcul de collision

IV-C-1 - Juste un point dans le mur

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.

Il ne s'agit pas d'arrondir, mais bien de prendre la partie entière. Si on arrondit 5.9, on trouve 6, si on prend sa partie entière, on a 5. Et on attend 5.

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;

IV-C-2 - Une AABB dans le mur

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.

Alors il faut déjà calculer l'intersection entre toutes les tuiles possibles et notre AABB, ce sera long !

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.

Si une seule de ces tuiles à tester est un mur, alors notre perso est dans un mur. Si aucun n'est un mur, alors on n'est pas dans un mur.

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

V - Tuiles isométriques

V-A - Définition

On parle de tuile isométrique quand, au lieu d'être un rectangle, la tuile est inclinée comme ci-dessous :

Cela permet de simuler un effet 3D, et est très utilisé dans les jeux 2D qui veulent donner une sorte de profondeur.

V-B - Applications

Les jeux suivants utilisent des tuiles isométriques.

On voit bien le sol « penché », qui nous donne un effet de profondeur.
De plus, pour donner une sorte d'altitude, des objets sont blittés par-dessus, comme les barrières dans Diablo (image de gauche) ce qui nous donne une réelle impression de 3D, alors que ce n'est que de la 2D.

V-C - Calcul de collision

V-C-1 - Point dans une tuile isométrique

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 et .

Il vous suffit de trois points : O,A,B pour définir votre grille. Nous définissons ainsi le repère de la grille isométrique.

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 : .

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

Oui, mais nous voulons l'inverse : nous avons le point dans le repère de l'écran, et nous voulons savoir sur quelle tuile il est, autrement dit quelles sont ses coordonnées dans le repère de la grille… Autrement dit, nous avons P, nous voulons connaître Q.

Si alors Si

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

- nous devons calculer P ;

- nous devons construire M ;

- nous devons calculer  ;

- 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 et  :

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,,, la matrice est simplement (,,O)

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

calculer

est l'inverse de la matrice M. Je vous renvoie à vos cours de maths. Nous trouvons :

=

Multiplication par P

Enfin, pour avoir Q, et donc i et j, il faut multiplier 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);
}

Ce calcul marchera dans les cas quelconques. Dans le dessin ci-dessus, l'axe X est bien horizontal, ce qui nous permettrait de simplifier quelques calculs. Mais qui peut le plus peut le moins, dit-on !

V-C-2 - Rectangle dans tuile isométrique

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.

Navigation

Tutoriel précédent : formes complexes

Sommaire

Tutoriel suivant : partitionnement de l'espace