Tile Mapping : insertion dans un monde de tuiles

Fvirtman

Nous avons vu dans la première partie comment créer un monde fait de tuiles.

Nous avons vu au début de la seconde partie comment gérer un personnage simpliste et ses collisions avec un mur simple.

Voyons maintenant comment relier le tout !

Commentez

- Titre : Tile Mapping : insertion dans un monde de tuiles

- Auteur : Fvirtman

- Parution : 21 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. La nouvelle fonction CollisionDecor

- III-A. La solution violente

- III-B. Localiser les tuiles qui pourraient intervenir

- III-C. Localiser les tuiles concernées

- III-D. Boucle de tests à faire

- III-E. Tester une tuile (version lente)

- III-F. Tester une tuile (version optimale)

- III-G. La fonction complète

- IV. Les déplacements rapides

- V. Code exemple

- V-A. La fonction AfficherSprite

- Navigation

Navigation

Tutoriel précédent : simple personnage

Sommaire

Tutoriel suivant : défilement automatique

II - Introduction

Nous avons vu dans la première partie comment créer un monde fait de tuiles.

Nous avons vu au début de la seconde partie comment gérer un personnage simpliste et ses collisions avec un mur simple.

Voyons maintenant comment relier le tout !

III - La nouvelle fonction CollisionDecor

Comme je vous le disais en conclusion de la sous-partie précédente, le concept de déplacement va rester le même : la fonction DeplaceSprite et ses sous-fonctions vont ressembler à celles d'avant, le changement majeur va être le changement de la fonction CollisionDecor, celle qui dit « tu es dans un mur ou pas ».

Nous allons donc voir comment cette fonction peut marcher pour un monde fait de tuiles.

Rappelons que nous raisonnons dans le « grand monde », qui, même s'il n'est pas affiché, est calculable.

C'est-à-dire que si je suis dans un grand monde, mon personnage peut très bien être à la position x = 10000, y = 8625 par exemple…

Dans le chapitre d'avant, cette fonction se ramenait à simplement tester une collision entre deux rectangles : le personnage et le mur.

Voyons pour tester les collisions dans un monde de tuiles.

III-A - La solution violente

La première idée est de se dire que dans l'exemple d'avant, j'avais un mur, je testais avec un algorithme de collision boîte/boîte.

Ici, dans mon monde, j'ai davantage de murs, je teste avec chacun, et si on en touche un, on renvoie 1.

Le gros problème qu'on voit tout de suite est que, dans un monde de Mario, on est au début du stage, et on va tester tous les murs du stage, y compris les blocs de l'arrivée, qui sont loin ! Loin et nombreux !

C'est très calculatoire, beaucoup trop violent à infliger à sa machine, et à oublier rapidement.

III-B - Localiser les tuiles qui pourraient intervenir

L'idée première va être de localiser les tuiles concernées. C'est-à-dire que si notre Mario est au début du stage, inutile de tester les tuiles de la fin du stage : on ne va tester que celles qu'il touche.

Ci-dessus un petit dessin, nous voyons le monde complet, découpé en tuiles (en gris), et plusieurs personnages schématisés par leur boîte englobante (notre fameuse boîte verte).

En clair derrière eux, les tuiles que le perso touche.

Tester ces tuiles-là, et uniquement ceux-la, est suffisant.

L'algorithme va être le suivant :

- localiser les tuiles concernées (les tuiles colorées) en fonction du personnage ;

- tester chacune de ces tuiles : si l'un d'entre eux est un mur, on renvoie 1 (collision).

Sinon, on renvoie 0 (pas de collision).

III-C - Localiser les tuiles concernées

L'ensemble des tuiles concernées formera un rectangle. Ce rectangle aura comme première tuile celle d'en haut à gauche, la tuile aux coordonnées (xmin,ymin), et comme dernière tuile celle d'en bas à droite, la tuile de coordonnées (xmax,ymax).

Déterminer ces quatre données sera très rapide : pour (xmin,ymin), il va falloir déterminer dans quelle tuile est le point en haut à gauche de notre rectangle de personnage. Pour déterminer (xmax,ymax), il va falloir déterminer dans quelle tuile est le point en bas à droite de notre rectangle de personnage.

Regardez de nouveau le dessin, la règle est respectée.

Déterminer dans quelle tuile est un point est extrêmement rapide : notre monde est régulier, et la première tuile commence à la coordonnée (0,0).

Pour un personnage ayant comme boîte x,y (point en haut à gauche personnage), et largeur w et hauteur h, on peut écrire :

xmin=x/LARGEURTILE
ymin=y/HAUTEURTILE

Le point en bas à droite du personnage est calculé à partir de ses coordonnées (x,y) auxquelles on ajoute respectivement w-1 et h-1.

De ce fait, nous avons :

xmax=xbasdroite/LARGEURTILE
ymax=ybasdroite/HAUTEURTILE

Le calcul de ces valeurs ne dépend absolument pas de la taille du monde : de ce fait, même si le monde est immense, le calcul ne sera pas plus long.

III-D - Boucle de tests à faire

Une fois qu'on a déterminé le rectangle de tuiles à tester, il faut toutes les tester. Nous n'échapperons pas à un double for :

int i,j;
for(i=xmin;i<=xmax;i++)
{
for(j=ymin;j<=ymax;j++)
{
// tester une tuile, si on touche un mur, inutile d'aller plus loin : on retourne 1
}
}

La vitesse de cet algorithme dépend directement de la taille de votre personnage. Si votre personnage est petit, on testera deux, quatre, voire six tuiles (tout dépend du chevauchement de tuiles de votre personnage). Ce n'est pas fixe, regardez le dessin ci-dessus, les rectangles violet et rouge font à peu près la même taille, mais leur position n'est pas la même, et le rouge est à cheval sur davantage de tuiles.

Le carré vert est un plus gros personnage (un gros monstre par exemple), on testera donc davantage de tuiles pour lui.

Notre algorithme de collision fonctionnera sur tout type de personnage, de taille quelconque.

Même si ce double for dépend de la taille du personnage, il sera rapide car, à moins de faire des super-monstres-énormes, il y aura toujours peu de tuiles à tester !

Pour les furieux de l'optimisation, on peut toujours aller plus loin :

Au lieu de tester toutes les tuiles entre xmin,ymin / xmax,ymax, on peut ne tester que ceux du bord du rectangle, et pas les tuiles intérieures. En effet, on peut partir du principe qu'un gros personnage est hors de tout mur, et qu'il ne pourra jamais avoir de mur à l'intérieur de lui, car les tests de collision avec les bords auront empêché ça. De ce fait, seules les tuiles du bord du rectangle de tuiles concernées peuvent être testées. Sur le dessin ci-dessus, on pourrait ne pas tester les trois tuiles au milieu du rectangle de tuiles vert.

Cette optimisation n'a de raison d'être que pour les très gros personnages, pas pour un Mario…

Souvent dans les jeux, les gros monstres sont d'ailleurs dans des zones ouvertes, et on ne teste pas leur collision avec le décor.

III-E - Tester une tuile (version lente)

Dans la boucle qu'on aura faite, il faut donc tester une tuile. La version lente consiste à récupérer la tuile à tester, puis sa boîte englobante, et lancer un algorithme de collision boîte/boîte (vu au chapitre précédent) pour voir si on touche.

Même si c'est rapide, c'est un peu bête car le travail est pré-mâché pour aller bien plus vite.

III-F - Tester une tuile (version optimale)

Nous testons une tuile à la position i,j. Si nous la testons, c'est que le perso la chevauche. Il suffit juste de voir si cette tuile est identifiée comme un « mur » ou pas. C'est tout !

III-G - La fonction complète

Voici donc la fonction complète qui résume tout ce que nous avons vu :

int CollisionDecor(Sprite* perso)
{
int xmin,xmax,ymin,ymax,i,j,indicetile;
Map* m = perso->m;
if (perso->x<0 || (perso->x + perso->w -1)>=m->nbtiles_largeur_monde*m->LARGEUR_TILE
|| perso->y<0 || (perso->y + perso->h -1)>=m->nbtiles_hauteur_monde*m->HAUTEUR_TILE)
return 1;
xmin = perso->x / m->LARGEUR_TILE;
ymin = perso->y / m->HAUTEUR_TILE;
xmax = (perso->x + perso->w -1) / m->LARGEUR_TILE;
ymax = (perso->y + perso->h -1) / m->HAUTEUR_TILE;
for(i=xmin;i<=xmax;i++)
{
for(j=ymin;j<=ymax;j++)
{
indicetile = m->schema[i][j];
if (m->props[indicetile].plein)
return 1;
}
}
return 0;
}

On retrouve xmin,xmax,ymin,ymax calculés comme nous avons vu.

Il y a en dessous un petit test, qui regarde si le perso sort du monde. Nous partons du principe que le perso ne doit pas sortir du monde. Donc si une de nos quatre valeurs est hors du monde, en renvoie 1 → on touche. Concrètement, tout se passe comme si le monde était entouré par un mur. Vous verrez dans l'exemple ci-dessous qu'on ne peut pas sortir.

On pourrait changer ça, et dire que le bord du monde ne contient pas de mur. Dans ce cas, il suffirait de ramener les coordonnées xmin,ymin / xmax,ymax dans le monde. On ne testerait ainsi que les rectangles du monde.

Quoi que vous choisissiez comme principe quand le perso sort du monde, il faut faire attention à ce que xmin,ymin / xmax,ymax soient des valeurs dans le monde. En effet, ces valeurs vont être utilisées pour tester le tableau carte->schema[][] de la structure Map. Il ne faut pas déborder, sous peine de plantage...

On retrouve ensuite le double for. Dedans, pour chaque i,j concerné, on regarde l'indice de la tuile concernée, et on va voir dans le tableau props si cette tuile a la propriété mur activée. Si c'est le cas, on renvoie qu'on touche, sans même avoir besoin de finir le for.

Si on sort du for, c'est qu'aucune tuile mur n'a été touchée, alors on renvoie 0 → on ne touche pas.

Cette fonction est peu calculatoire, très rapide, et fiable. Tant mieux car c'est une fonction appelée souvent, il faut qu'elle soit rapide. C'est le cas !

IV - Les déplacements rapides

Avant de voir le code, et un beau petit exemple de collision dans notre petit monde, soulevons un petit problème.

Nous avons vu comment nous faisions nos déplacements : on applique un vecteur de translation, si la position finale est valide, on bouge, sinon, on affine ou on ne bouge pas.

Cela marche très bien, mais à une seule condition : qu'on ne bouge pas trop vite.

Imaginons un Sonic qui fonce. Son vecteur de déplacement devient grand, il tabule, c'est-à-dire qu'à une image on le dessine à une position, à une autre, on le dessine beaucoup plus loin (en réalité, avec le scrolling, c'est la carte qui tabule, mais ça revient au même).

Voici le problème que ça peut poser :

À gauche, on voit notre boîte verte. On veut la déplacer selon le vecteur rouge. Or, il y a un mur. Mais le vecteur rouge est grand, donc l'algorithme qu'on a vu plus haut va tenter de le déplacer, va réussir, car la position test est hors mur. Et Sonic aura traversé le mur… C'est moche, non ?

Il y a danger que cela arrive si, pour un vecteur vx,vy, vx >= LARGEUR_TILE ou vy >= HAUTEUR_TILE.

Par contre, si cette condition n'est pas remplie, aucune chance d'avoir ce problème.

Il faut donc éviter ce cas :

- soit en empêchant de se déplacer trop vite ;

- soit en coupant le déplacement en plusieurs morceaux acceptables.

Nous n'allons bien sûr pas vous empêcher d'aller vite. Nous allons voir comment faire pour couper le déplacement en deux.

Si vous regardez la partie droite du dessin, vous voyez qu'au lieu de translater d'un grand vecteur rouge, je translate deux fois d'un plus petit vecteur rouge. Et ce vecteur nous permettra de bien se payer le mur.

On va lancer deux fois la fonction Deplace, avec un vecteur réduit de moitié à chaque fois.

La première fois, on va aller cogner le mur, et l'affinage va nous plaquer contre.

La deuxième fois, à partir de la position collée contre le mur, on n'avancera pas.

Le problème disparaît.

L'algorithme qu'on va mettre en place dans la fonction Deplace est simple et récursif :

int DeplaceSprite(Sprite* perso,int vx,int vy)
{
if (vx>=perso->m->LARGEUR_TILE || vy>=perso->m->HAUTEUR_TILE)
{
DeplaceSprite(perso,vx/2,vy/2);
DeplaceSprite(perso,vx-vx/2,vy-vy/2);
return 3;
}
if (EssaiDeplacement(perso,vx,vy)==1)
return 1;
Affine(perso,vx,vy);
return 2;
}

Nous voyons que si vx ou vy sont trop grands, on relance deux fois la fonction avec un vecteur deux fois plus petit dans un premier temps, suivi du « reste », donc également un vecteur deux fois plus petit.

L'avantage de la récursivité, c'est que si les nouveaux vecteurs sont toujours trop grands, on redécoupe, quitte à relancer l'algorithme quatre fois, huit fois… Jusqu'à ce que le vecteur soit acceptable !

Si ce chapitre vous échappe (car vous n'aimez pas la récursivité ou ne comprenez pas tout) ignorez, mais faites attention à vos vitesses… Ou alors acceptez la fonction telle qu'elle est.

Notez qu'avec des nombres entiers, vx-vx/2 n'est pas forcément égal à vx/2.

V - Code exemple

Nous finirons ce chapitre par du code qui reprend ce que nous avons vu plus haut.

Prenez le programme « prog5 ».

Compilez-le et lancez-le. Utilisez les flèches pour déplacer le rectangle vert, et les touches « fgth » pour contrôler le scrolling.

Vous pouvez remarquer que vous ne pouvez pas rentrer dans les décors.

Sauf les barrières et fleurs, car elles sont renseignées comme « vide ».

Vous ne pouvez pas sortir non plus du monde, car la fonction CollisionDecor renvoie qu'il y a collision si on sort.

Voyons un petit peu de code.

Beaucoup de choses réutilisées des anciens codes.

Ici, j'ai changé la structure Sprite dans fsprite.h :

typedef struct
{
Map* m;
int x,y,w,h;
} Sprite;

Les sprites embarquent maintenant un pointeur vers la carte. Et les x,y,w,h ne sont plus dans SDL_Rect, parce que les x,y pourront devenir très grands. En effet, les coordonnées du sprite seront celles du repère global.

Cela pourra permettre au sprite de pouvoir sortir de la zone de scrolling, en continuant d'être actif.

L'intérêt de stocker les coordonnées globales, c'est que le scrolling le déplacera automatiquement, il n'y aura pas de mouvement à compenser par le scrolling.

V-A - La fonction AfficherSprite

void AfficherSprite(Sprite* perso,SDL_Surface* screen)
{
SDL_Rect R;
R.x = perso->x - perso->m->xscroll;
R.y = perso->y - perso->m->yscroll;
R.w = perso->w;
R.h = perso->h;
SDL_FillRect(screen,&R,0x00FF00);  // affiche le perso
}

Elle tient compte des paramètres de fenêtrage qu'elle va chercher via le lien qu'embarque chaque sprite.

Notez bien que s'il y a plusieurs sprites, ils auront tous un lien vers la même carte. Il n'y a pas une carte par sprite.

Tout le reste est de la réutilisation des chapitres précédents.

Nous avons enfin intégré notre personnage (même réduit à un simple rectangle) dans le monde des tuiles.

Il ne passe plus à travers les murs.

Pour l'instant, il est vert et carré, et il vole.

Notez que les jeux vus de dessus (comme Zelda Link to the past, ou la philosophie RPG Maker), utilisent ce concept. Dans ces jeux, pas besoin de gravité.

Vous pouvez vous appuyer sur l'exemple en l'état pour faire un jeu vu de dessus, même s'il est préférable de continuer à lire pour voir les diverses techniques que je vais vous proposer !

Navigation

Tutoriel précédent : simple personnage

Sommaire

Tutoriel suivant : défilement automatique