> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> C

> Programmez sur votre Nintendo DS !

> Annexes

> Les labyrinthes

> Lecture du tutoriel

Les labyrinthes

Par

PODS et Avatar

Gambit2099 et Avatar

Gautier Berthou (snake_48)

Mise à jour : 14/10/2009

Difficulté : Facile Facile

282 visites depuis 7 jours, classé 354/786

Nous allons apprendre comment utiliser les labyrinthes pour guider des personnages contrôlés par l'IA, pour éviter, entre autres, de marcher sur des murs ou d'autres personnages

...

Retour en haut

Retour en haut

Les labyrinthes

Vous vous doutez sûrement qu'il est difficile de créer un système aussi complexe qu'un labyrinthe. Ici, il n'est pas question de générer un labyrinthe, mais de pouvoir créer une IA se déplaçant à l'intérieur, sans jamais heurter les murs qui le composent, en arrivant toujours à l'endroit voulu (sauf s'il est entouré de murs :-°

). Mais en fait, grâce à PALib, cette tâche est rendue la plus simple possible.
En effet, il existe plusieurs méthodes pour aller d'un point à un autre. Celle utilisée par PALib est la méthode A* (A star). Cette méthode allège les temps de calcul, mais le chemin emprunté n'est pas forcément le plus court (ça dépend de la qualité de l'algorithme). Un tutoriel sur le site à cette adresse montre en détail l'algorithme A*.

Il faut penser en tiles : définir la taille d'un carré représentant l'unité utilisée par le labyrinthe (par exemple 8x8). Puis, il faut songer aux dimensions du labyrinthe. Elles peuvent être tout ce que vous voulez, mais le labyrinthe doit être absolument un carré. Donc, si vous utilisez un rectangle, vous devrez déclarer le carré à la longueur maximale de la scène, et donc certaines tiles ne seront pas utilisées, mais pas de problème

...

Donc nous allons initialiser le système de labyrinthes avec void PA_InitAstar(u16 lx, u16 ly); où lx est le nombre de tiles dans les X du labyrinthe et ly est le nombre de tiles dans les Y du labyrinthes.
Par exemple, si votre scène est un écran, et que vos tiles doivent mesurer 8*8 pixels, alors vous initialiserez le système ainsi :
Code : C

1	PA_InitAstar(32,32); //N'oubliez pas, c'est un carré !

Ou si vous préférez les divisions, voici l'équivalent :
Code : C

1	PA_InitAstar(256/8,256/8);

Cette fonction initialise une variable globale : maze (tableau de u16).

Comment utiliser cette variable ?

Pour y accéder, il faut faire :
Code : C

1	maze[x/TAILLE_TILE][y/TAILLE_TILE]

Maintenant, il faut mettre notre labyrinthe dans la variable maze.
Il existe un "code" permettant de mettre notre labyrinthe dans maze :

0 : rien ; le personnage peut passer
1 : point de départ ; position du personnage
2 : arrivée du personnage
5 : mur ; le personnage ne peut pas passer

Donc, si nos tiles mesurent 8*8 pixels, et que le tile (32;16;40;24) doit être un mur, il faudra écrire :
Code : C

1	maze[32/8][16/8]=5;

Ce qui est l'équivalent de :
Code : C

1	maze[4][2]=5;

Comment connaître le déplacement à effectuer ?

Avec s8 PA_Astar(u16 lx, u16 ly); prenant les mêmes arguments que void PA_InitAstar(u16 lx, u16 ly); .
La fonction retourne un entier qui peut être analysé comme ceci (pour des tiles de 8*8 pixels) :
Code : C

switch(PA_Astar(256/8,256/8))
{
    case 1: // Gauche
        x-=8;
        break;
    case 2: // Droite
        x+=8;
        break;
    case 3: // Haut
        y-=8;
        break;
    case 4: // Bas
        y+=8;
        break;
    default:
        break;
}

Voilà, c'est tout, vous êtes dorénavant capable de réaliser une IA pouvant se déplacer dans un labyrinthe

...

Retour en haut

Retour en haut

4 commentaires pour "Les labyrinthes"

Note moyenne : 3.57 / 4 (65 votes)

Pseudo	Commentaire
agranger36	# Posté le 14/10/2009 à 14:58:19
Mieu vaut avec que sans!! Blog Twitter close Ville : Châteauroux Pays : France métropolitaine	Bonne technique même si une utilisation d'un algorithme de pathfinding serait plus pratique
spider-mario	# Posté le 14/10/2009 à 16:14:19
Ville : Montigny-lès-cormeilles Pays : France métropolitaine Études : INSA Rouen	C'est exactement ce en quoi ça consiste... C'est juste qu'il a déjà été implémenté par les auteurs de la PALib.
yoch	# Posté le 10/04/2011 à 17:51:14
	C'est dommage de donner aux zéros l'impression que coder un pathfinding ou même un générateur de labyrinthe est hors de leur portée. Sinon, c'est vrai qu'il est bon de connaitre cette possibilité. Comprendre la messagerie électronique Introduction à la programmation dynamique Le backtracking par l'exemple : résoudre un sudoku Bloquer du contenu avec le fichier hosts - La commande sed Modifier une application Windows
snake_48	# Posté le 10/04/2011 à 19:13:18
Il me manque un bit. Études : INSA Lyon	Pourquoi donc (en ce qui concerne le pathfinding) ? Il est bien mentionné qu'il y a un tuto sur l'algo A... Programmez sur votre Wii ! \| Programmez sur votre Nintendo DS ! \| Charger des fichiers .OBJ \| Introduction au scripting avec Python Création d'un moteur physique (en cours)* Langages connus : AS3, Batch, C, C++, HTML, Java, Javascript, PHP, Python. Programme sur : PC, Nintendo DS, Wii. o----}=========>