• Difficile

Mis à jour le 06/12/2013

Insertion dans un monde de Tiles

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Nous avons vu dans la partie 1 comment créer un monde fait de tiles.
Nous avons vu au début de la partie 2 comment gérer un personnage simpliste et ses collisions avec un mur simple.
Voyons maintenant comment relier le tout !

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 majeur changement 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 tiles.

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

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 boite/boite.
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.

Localiser les tiles qui pourraient intervenir

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

Image utilisateur

Ci-dessus un petit dessin, nous voyons le monde complet, découpé en tiles (en gris), et plusieurs personnages schématisés par leur boîte englobante (notre fameuse boîte verte).
En clair derrière eux, les tiles que le perso touche.

L'algorithme va être le suivant :

  • Localiser les tiles concernés (les tiles colorés) en fonction du personnage.

  • Tester chacun de ces tiles : si l'un d'entre eux est un mur, on renvoie 1 (collision).

  • Sinon, on renvoie 0 (pas de collision).

Localiser les tiles concernés

L'ensemble des tiles concernés formera un rectangle. Ce rectangle aura comme premier tile celui d'en haut à gauche, le tile de coordonnées (xmin,ymin), et comme dernier tile celui d'en bas à droite, le tile de coordonnées (xmax,ymax).

Déterminer ces quatre données sera très rapide : pour (xmin,ymin), il va falloir déterminer dans quel tile est le point en haut à gauche de notre rectangle de personnage. Pour déterminer (xmax,ymax), il va falloir déterminer dans quel tile 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 quel tile est un point est extrêmement rapide : notre monde est régulier, et le premier tile 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.

$x_{basdroite} = x + w - 1$$y_{basdroite} = y + h - 1$

De ce fait, nous avons :

$xmax = x_{basdroite}/LARGEUR_TILE$$ymax = y_{basdroite}/HAUTEUR_TILE$

Boucle de tests à faire

Une fois qu'on a déterminé le rectangle de tiles à tester, il faut tous 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 un tile, si on touche un mur, inutile d'aller plus loin : on retourne 1
  }
}

La vitesse de cet algo dépend directement de la taille de votre personnage. Si votre personnage est petit, on testera 2, voir 4, voir 6 tiles (tout dépend du chevauchement de tiles de votre personnage). Ce n'est pas fixe, regardez le dessin ci-dessus, le rectangle violet et le 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 tiles.

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

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 tiles à tester !

Pour les furieux de l'optimisation, on peut toujours aller plus loin :
Au lieu de tester tous les tiles entre xmin,ymin / xmax,ymax, on ne peut tester que ceux du bord du rectangle, et pas les tiles intérieurs. 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, seuls les tiles du bord du rectangle de tiles concernés peuvent être testés. Sur le dessin ci-dessus, on pourrait ne pas tester les 3 tiles au milieu du rectangle de tiles 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.

Tester un tile (version lente)

Dans la boucle qu'on aura faite, il faut donc tester un tile. La version lente consiste à récupérer le tile à tester, à récupérer sa boîte englobante, et lancer un algo 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.

Tester un tile (version optimale)

Nous testons un tile à la position i,j. Si nous le testons, c'est que le perso le chevauche. Il suffit juste de voir si ce tile est identifié comme un "mur" ou pas. C'est tout !

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 retrouve ensuite le double for. Dedans, pour chaque i,j concerné, on regarde l'indice du tile concerné, et on va voir dans le tableau props si ce tile 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'aucun tile mur n'a été touché, alors on renvoie 0 -> on ne touche pas.

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 faisons 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 frame 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 :

Image utilisateur

A 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 disparait.

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 grand, 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 grand, on redécoupe, quitte à relancer l'algo 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.

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 le 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 map. 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.

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 sprite, ils auront tous un lien vers la même map. Il n'y a pas une map 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 tiles.
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 ! ;)

Exemple de certificat de réussite
Exemple de certificat de réussite