Générateur de labyrinthes arbres
Le code dans cet article a été écrit avec Code::Blocks et la SDL 2.
Vous pouvez trouver
ici un guide pour installer ces logiciels.
Bien qu'il soit basé sur la SDL, je n'utilise pas ses fonctions directement. J'ai écrit une petite bibliothèque
avec quelques fonctions basiques pour faciliter la compréhension et la portabilité dans un autre langage.
Vous pouvez en apprendre plus sur cette bibliothèque
ici.
Cet article décrit un générateur de labyrinthes que j'ai trouvé dans un magazine français (voir le lien en bas de
cette page).
L'idée est de construire un labyrinthe en faisant pousser des arbres à partir du bord de l'écran.
On commence par poser quelques troncs.
Puis on choisit un mur au hasard à l'intérieur du labyrinthe et on l'ajoute s'il se connecte a un autre.
Mais il doit toucher un seul autre mur. Il ne doit pas connecter 2 arbres ensemble parce que ça voudrait dire que
certaines cases seraient inaccessibles.
Ces règles semblent simples, mais on va voir que ça prend quelques étapes avant qu'on ait notre labyrinthe complet.
Représentation du labyrinthe
Il y a beaucoup de façons de représenter un labyrinthe. Fondamentalement une case doit avoir 4 cotés autour d'elle,
mais si on stocke tous les murs dans chaque case, il va y avoir des doublons:
Alors j'ai décidé de stocker seulement les cotés gauche et haut de chaque case. De cette façon vous pouvez voir
qu'il n'y a pas de doublon.
On aura juste besoin d'ajouter une ligne de murs en bas et à droite de toute la grille.
D'abord on va essayer de voir comment afficher le labyrinthe.
La taille de notre labyrinthe sera de 30 * 20 cases.
#define MAZE_WIDTH 30
#define MAZE_HEIGHT 20
Chaque case sera un carré de 20*20 pixels.
#define TILE_SIZE 20
Et les murs auront une largeur de 2 pixels.
#define WALL_WIDTH 2
La taille de l'écran sera définie par ces valeurs.
#define SCREEN_WIDTH (MAZE_WIDTH * TILE_SIZE + WALL_WIDTH)
#define SCREEN_HEIGHT (MAZE_HEIGHT * TILE_SIZE + WALL_WIDTH)
Maintenant on va écrire une simple routine qui dessine un mur dans la case (x, y).
Le mur sera soit horizontal, soit vertical, et il aura une largeur de WALL_WIDTH et une longueur de TILE_SIZE.
Il faut juste qu'on ajoute quelques pixels à la longueur du mur vertical pour être sur de remplir tous les trous.
void drawWall(int x, int y, bool isHorizontal, Color c)
{
int sx = x * TILE_SIZE;
int sy = y * TILE_SIZE;
if (isHorizontal == true)
{
int ex = sx + TILE_SIZE - 1;
int ey = sy + WALL_WIDTH - 1;
for (int yy = sy; yy <= ey; yy++)
for (int xx = sx; xx <= ex; xx++)
gfx.setPixel(xx, yy, c);
}
else
{
int ex = sx + WALL_WIDTH - 1;
int ey = sy + TILE_SIZE + WALL_WIDTH - 1;
for (int yy = sy; yy <= ey; yy++)
for (int xx = sx; xx <= ex; xx++)
gfx.setPixel(xx, yy, c);
}
}
Pour tester cette fonction on va dessiner tous les murs de notre labyrinthe.
Alors on va commencer par les murs haut et gauche de chaque case.
// draw the maze
for (int y = 0; y < MAZE_HEIGHT; y++)
for (int x = 0; x < MAZE_WIDTH; x++)
{
drawWall(x, y, false, Color(255, 255, 255));
drawWall(x, y, true, Color(255, 255, 255));
}
Et comme on l'a dit, on doit dessiner les cotés à droite et en bas de toute la grille.
for (int y = 0; y < MAZE_HEIGHT; y++)
drawWall(MAZE_WIDTH, y, false, Color(255, 255, 255));
for (int x = 0; x < MAZE_WIDTH; x++)
drawWall(x, MAZE_HEIGHT, true, Color(255, 255, 255));
Télécharger le code source
Télécharger l'exécutable pour Windows
Et on obtient le résultat voulu
Les données du labyrinthe
Maintenant qu'on sait comment dessiner notre labyrinthe, regardons comment ses données vont être stockées en
mémoire.
En suivant la représentation qu'on a choisi, chaque case va avoir un mur à gauche et en haut.
Un flag va nous dire si ils sont dessinés et chacun d'eux aura une couleur.
struct STile
{
bool topIsActive;
bool leftIsActive;
Color topColor;
Color leftColor;
};
Le labyrinthe sera un tableau de ces cases.
Comme on doit ajouter les cotés droit et bas du labyrinthe, ce tableau va avoir une ligne et une colonne de plus.
STile maze[MAZE_WIDTH + 1][MAZE_HEIGHT + 1];
On va initialiser ce tableau en mettant à false tous les flags des murs.
// init the maze
for (int y = 0; y <= MAZE_HEIGHT; y++)
for (int x = 0; x <= MAZE_WIDTH; x++)
{
maze[x][y].topIsActive = false;
maze[x][y].leftIsActive = false;
}
Maintenant dans cette partie on va essayer de dessiner seulement les bords de notre labyrinthe.
Donc on va mettre leurs flags à true.
// init left and right borders
for (int y = 0; y < MAZE_HEIGHT; y++)
{
maze[0][y].leftIsActive = true;
maze[0][y].leftColor = Color(255, 255, 255);
maze[MAZE_WIDTH][y].leftIsActive = true;
maze[MAZE_WIDTH][y].leftColor = Color(255, 255, 255);
}
// init top and bottom borders
for (int x = 0; x < MAZE_WIDTH; x++)
{
maze[x][0].topIsActive = true;
maze[x][0].topColor = Color(255, 255, 255);
maze[x][MAZE_HEIGHT].topIsActive = true;
maze[x][MAZE_HEIGHT].topColor = Color(255, 255, 255);
}
Et la fonction pour dessiner le labyrinthe va simplement appeler drawWall() pour chaque mur actif.
// draw the maze
for (int y = 0; y <= MAZE_HEIGHT; y++)
for (int x = 0; x <= MAZE_WIDTH; x++)
{
if (maze[x][y].leftIsActive == true)
drawWall(x, y, false, maze[x][y].leftColor);
if (maze[x][y].topIsActive == true)
drawWall(x, y, true, maze[x][y].topColor);
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Le résultat n'est peut-être pas facile à voir, mais on a bien un rectangle qui montre les limites de notre grille.
Pour garder la boucle principale simple, on va créer une classe pour décrire le labyrinthe dans un autre fichier.
Voici "maze.h"
#ifndef MAZE_H
#define MAZE_H
#include "Graphics.h"
#define MAZE_WIDTH 30
#define MAZE_HEIGHT 20
#define TILE_SIZE 20
#define WALL_WIDTH 2
struct STile
{
bool topIsActive;
bool leftIsActive;
Color topColor;
Color leftColor;
};
class CMaze
{
public:
CMaze();
void draw();
private:
void drawWall(int x, int y, bool isHorizontal, Color c);
STile tiles[MAZE_WIDTH + 1][MAZE_HEIGHT + 1];
};
#endif // MAZE_H
Et "maze.cpp"
#include "maze.h"
void CMaze::drawWall(int x, int y, bool isHorizontal, Color c)
{
[...]
}
CMaze::CMaze()
{
// init the maze
for (int y = 0; y <= MAZE_HEIGHT; y++)
for (int x = 0; x <= MAZE_WIDTH; x++)
{
tiles[x][y].topIsActive = false;
[...]
}
// init left and right borders
for (int y = 0; y < MAZE_HEIGHT; y++)
{
tiles[0][y].leftIsActive = true;
[...]
}
// init top and bottom borders
for (int x = 0; x < MAZE_WIDTH; x++)
{
tiles[x][0].topIsActive = true;
[...]
}
}
void CMaze::draw()
{
// draw the maze
for (int y = 0; y <= MAZE_HEIGHT; y++)
for (int x = 0; x <= MAZE_WIDTH; x++)
{
if (tiles[x][y].leftIsActive == true)
drawWall(x, y, false, tiles[x][y].leftColor);
if (tiles[x][y].topIsActive == true)
drawWall(x, y, true, tiles[x][y].topColor);
}
}
Maintenant dans "main.cpp" on a juste besoin de créer une instance de cette classe et d'appeler sa méthode draw().
CMaze maze;
[...]
maze.draw();
Télécharger le code source
Dans le programme suivant on va essayer de trouver les coordonnées des murs intérieurs du labyrinthe qui vont se
connecter aux troncs.
On va d'abord écrire une fonction pour choisir un de ces murs au hasard.
// choose a random wall inside maze
STile* chooseWall(bool& isHorizontal)
{
int x, y;
isHorizontal = (rand() & 1 ? false : true);
if (isHorizontal == true)
{
x = 1 + (rand() % (MAZE_WIDTH - 2));
y = 1 + (rand() % (MAZE_HEIGHT - 1));
}
else
{
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = 1 + (rand() % (MAZE_HEIGHT - 2));
}
return maze.getTile(x, y);
}
Ensuite, dans la boucle principale, on va appeler cette fonction et dessiner ce mur.
bool isHorizontal;
STile* tile = chooseWall(isHorizontal);
if (isHorizontal == true)
{
tile->topIsActive = true;
tile->topColor = Color(255, 0, 0);
}
else
{
tile->leftIsActive = true;
tile->leftColor = Color(0, 255, 0);
}
maze.draw();
Télécharger le code source
Télécharger l'exécutable pour Windows
Ca dessine les murs qu'on veut.
Maintenant on va sélectionner les troncs qui vont remplir le labyrinthe.
Dans la classe Maze on ajoute une fonction chooseTrunk() qui va choisir une case sur le bord.
// choose a random place to put a trunk
STile* CMaze::chooseTrunk(bool& isHorizontal)
{
int x, y;
int dir = rand() % 4;
if (dir == 0)
{
isHorizontal = true;
x = 0;
y = 1 + (rand() % (MAZE_HEIGHT - 1));
}
else if (dir == 1)
{
isHorizontal = true;
x = MAZE_WIDTH - 1;
y = 1 + (rand() % (MAZE_HEIGHT - 1));
}
else if (dir == 2)
{
isHorizontal = false;
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = 0;
}
else
{
isHorizontal = false;
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = MAZE_HEIGHT - 1;
}
return getTile(x, y);
}
Ensuite on va l'appeler dans le constructeur de Maze là où on initialise les flags des murs:
// init the trunks
for (int i = 0; i < NB_TRUNKS; ++i)
{
bool isHorizontal;
Color color(32 + rand() % 224,
32 + rand() % 224,
32 + rand() % 224);
while (true)
{
STile* tile = chooseTrunk(isHorizontal);
if (isHorizontal == true)
{
if (tile->topIsActive == false)
{
tile->topIsActive = true;
tile->topColor = color;
break;
}
}
else
{
if (tile->leftIsActive == false)
{
tile->leftIsActive = true;
tile->leftColor = color;
break;
}
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ca nous donne le même genre d'image qu'on a vu au début.
Malheureusement, le programme qu'on vient d'écrire n'est pas parfait et comme les troncs sont placés aléatoirement,
ce genre de choses peut arriver:
Comme on l'a dit, on ne veut pas que les arbres se connectent ensemble. Ici on peut voir que la case du coin est
isolée du reste du labyrinthe. Et on veut être capable d'atteindre chaque case du labyrinthe à partir d'une autre
case.
Donc on va avoir besoin d'une fonction pour tester si un mur va en toucher un autre avant qu'on le dessine.
La fonction qu'on va écrire va tester tous les murs qui touchent le coin en haut à gauche d'une case.
Pour simplifier le code, cette fonction utilise 4 sous-fonctions pour tester s'il y a un mur dans une des 4
directions (haut, bas, gauche ou droite).
bool CMaze::hasWallUp(int x, int y)
{
return getTile(x, y - 1)->leftIsActive;
}
bool CMaze::hasWallDown(int x, int y)
{
return getTile(x, y)->leftIsActive;
}
bool CMaze::hasWallLeft(int x, int y)
{
return getTile(x - 1, y)->topIsActive;
}
bool CMaze::hasWallRight(int x, int y)
{
return getTile(x, y)->topIsActive;
}
bool CMaze::checkIntersection(int x, int y)
{
if (hasWallUp(x, y) == true)
return true;
if (hasWallDown(x, y) == true)
return true;
if (hasWallLeft(x, y) == true)
return true;
if (hasWallRight(x, y) == true)
return true;
return false;
}
Ensuite on peut utiliser cette fonction quand on choisit un tronc pour tester si son extrémité touche un autre mur:
// choose a random place to put a trunk
STile* CMaze::chooseTrunk(bool& isHorizontal)
{
int x, y;
STile* tile;
while (true)
{
int dir = rand() % 4;
if (dir == 0)
{
isHorizontal = true;
x = 0;
y = 1 + (rand() % (MAZE_HEIGHT - 1));
if (checkIntersection(x + 1, y) == false)
break;
}
else if (dir == 1)
{
isHorizontal = true;
x = MAZE_WIDTH - 1;
y = 1 + (rand() % (MAZE_HEIGHT - 1));
if (checkIntersection(x, y) == false)
break;
}
else if (dir == 2)
{
isHorizontal = false;
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = 0;
if (checkIntersection(x, y + 1) == false)
break;
}
else
{
isHorizontal = false;
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = MAZE_HEIGHT - 1;
if (checkIntersection(x, y) == false)
break;
}
}
return getTile(x, y);
}
Télécharger le code source
Maintenant on a toutes les fonctions nécessaires pour dessiner le labyrinthe.
Mais quand on choisit le mur intérieur qu'on va ajouter, on doit tester s'il ne connecte pas 2 arbres.
Ca va être fait dans une fonction appelée checkWall()
// choose a random wall inside maze
void chooseWall()
{
int x, y;
Color c;
bool isHorizontal;
while(true)
{
isHorizontal = (rand() & 1 ? false : true);
if (isHorizontal == true)
{
x = 1 + (rand() % (MAZE_WIDTH - 2));
y = 1 + (rand() % (MAZE_HEIGHT - 1));
if (checkWall(x, y, isHorizontal, c) == false)
{
maze.getTile(x, y)->topIsActive = true;
maze.getTile(x, y)->topColor = c;
break;
}
}
else
{
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = 1 + (rand() % (MAZE_HEIGHT - 2));
if (checkWall(x, y, isHorizontal, c) == false)
{
maze.getTile(x, y)->leftIsActive = true;
maze.getTile(x, y)->leftColor = c;
break;
}
}
}
}
Cette fonction va appeler checkIntersection() à chaque extrémité du mur qu'on veut ajouter.
bool checkWall(int x, int y, bool& isHorizontal, Color& color)
{
Color c1, c2;
bool inter1, inter2;
inter1 = maze.checkIntersection(x, y, c1);
if (isHorizontal == true)
inter2 = maze.checkIntersection(x + 1, y, c2);
else
inter2 = maze.checkIntersection(x, y + 1, c2);
On veut connecter ce mur à un autre mais éviter de connecter 2 arbres ensemble.
Alors il y a 3 combinaisons possibles des valeurs de inter1 et inter2:
- Soit on ne touche aucun mur du tout. Dans ce cas on ne va pas tracer de mur. Parce qu'on veut qu'il soit
connecté à un autre.
- Ou bien on touche un mur des 2 cotés. Dans ce cas, on ne trace pas de mur non plus. Parce qu'on
connecterait 2 arbres ensemble ou on isolerait une case.
- Le 3ième cas est quand on touche un mur d'un coté mais pas de l'autre. Dans ce cas on trace notre mur qui
ajoutera une branche à un arbre.
Donc pour le 3ième cas, on doit tester si inter1 est à true et inter2 à false, ou le contraire.
if (inter1 == true && inter2 == false)
{
color = c1;
return false;
}
else if (inter1 == false && inter2 == true)
{
color = c2;
return false;
}
return true;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Notez que comme checkIntersection() teste toutes les directions, elle testera aussi s'il y a déjà un mur à
l'endroit où on on veut en ajouter un.
Vous avez peut-être aussi remarqué que j'ai modifié toutes les fonctions de test pour récupérer la couleur du mur
qu'on a touche, parce que je veux dessiner toutes les branches d'un arbre de la même couleur que son tronc.
Voici un exemple de ce que ce programme produit.
Le problème maintenant c'est que quand le programme finit le labyrinthe, il essaye de trouver un autre mur à
dessiner et il rentre dans une boucle sans fin.
Alors ça va vous dire qu'il ne répond pas quand vous essayerez de le fermer.
Pour détecter la fin du dessin on va ajouter un flag à chaque mur dans la structure STile, qui nous dira si on a
visité ce mur ou non.
struct STile
{
bool topIsActive;
bool leftIsActive;
Color topColor;
Color leftColor;
bool topVisited;
bool leftVisited;
};
Bien sur ces flags seront initialisés à false dans le constructeur de la classe Maze.
Ensuite, on va les mettre à true dans 2 cas:
- Soit on a dessiné un mur à cet endroit.
- Ou on a vérifié qu'il y avait 2 murs qui touchaient celui-ci. Ca veut dire qu'on ne pourra pas mettre de
mur là, même à l'avenir.
Le cas où aucun mur ne touche celui-ci n'est pas intéressant, parce qu'on pourrait en dessiner un dans le futur.
Alors on modifie la fonction checkWall() pour positionner ces flags:
bool checkWall(int x, int y, bool& isHorizontal, Color& color)
{
[...]
if (inter1 == true && inter2 == false)
{
if (isHorizontal == true)
maze.getTile(x, y)->topVisited = true;
else
maze.getTile(x, y)->leftVisited = true;
color = c1;
return false;
}
else if (inter1 == false && inter2 == true)
{
if (isHorizontal == true)
maze.getTile(x, y)->topVisited = true;
else
maze.getTile(x, y)->leftVisited = true;
color = c2;
return false;
}
else if (inter1 == true && inter2 == true)
{
if (isHorizontal == true)
maze.getTile(x, y)->topVisited = true;
else
maze.getTile(x, y)->leftVisited = true;
}
return true;
}
Maintenant, à la fin on devrait avoir marqué toutes les positions des murs intérieurs où on a vraiment dessiné un
mur ou là où n'a pas pu à cause des règles.
Donc la fonction pour tester la fin du dessin a seulement besoin de compter tous ces flags et de comparer ce nombre
au nombre total de murs intérieurs.
bool checkFinished()
{
int nbVisits = 0;
for (int x = 0; x < MAZE_WIDTH; x++)
for (int y = 0; y < MAZE_HEIGHT; y++)
{
if (maze.getTile(x, y)->topVisited == true)
nbVisits++;
if (maze.getTile(x, y)->leftVisited == true)
nbVisits++;
}
return (nbVisits == (MAZE_WIDTH - 1) * (MAZE_HEIGHT - 2) + (MAZE_WIDTH - 2) * (MAZE_HEIGHT - 1));
}
On va utiliser cette fonction au début de chooseWall() pour éviter d'entrer dans une boucle sans fin.
void chooseWall()
{
int x, y;
Color c;
bool isHorizontal;
while(true)
{
if (checkFinished() == true)
break;
Télécharger le code source
Télécharger l'exécutable pour Windows
Maintenant ce programme doit se terminer sans erreur.
Le programme original dans les magazine permettait aussi de créer des îles plutôt que des arbre.
Les îles sont des arbres qui poussent à l'intérieur du labyrinthe au lieu du bord, comme ceci:
Pour les démarrer, on doit simplement mettre des troncs n'importe-où à l'intérieur du labyrinthe au départ.
Bien sur, comme pour tous les murs, on doit tester s'ils touchent d'autres murs aussi.
// choose a random place to put an island
STile* CMaze::chooseIsland(bool& isHorizontal)
{
int x, y;
Color c;
while (true)
{
isHorizontal = (rand() & 1 ? false : true);
if (isHorizontal == true)
{
x = 1 + (rand() % (MAZE_WIDTH - 2));
y = 1 + (rand() % (MAZE_HEIGHT - 1));
if (checkIntersection(x, y, c) == false &&
checkIntersection(x + 1, y, c) == false)
break;
}
else
{
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = 1 + (rand() % (MAZE_HEIGHT - 2));
if (checkIntersection(x, y, c) == false &&
checkIntersection(x, y + 1, c) == false)
break;
}
}
return getTile(x, y);
}
CMaze::CMaze()
{
srand(time(NULL));
// init the maze
[...]
// init left and right borders
[...]
// init top and bottom borders
[...]
// init the trunks
[...]
// init the islands
for (int i = 0; i < NB_ISLANDS; ++i)
{
bool isHorizontal;
Color color(32 + rand() % 224,
32 + rand() % 224,
32 + rand() % 224);
STile* tile = chooseIsland(isHorizontal);
if (isHorizontal == true)
{
tile->topIsActive = true;
tile->topColor = color;
}
else
{
tile->leftIsActive = true;
tile->leftColor = color;
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Voici un exemple de labyrinthe avec des îles:
Une chose qui me déplait dans ce générateur c'est qu'il crée de longs couloirs le long des bords du labyrinthe.
C'est parce qu'il n'y a qu'un nombre limité de troncs.
Alors je voulais le modifier pour qu'il génère des troncs dynamiquement.
On va commencer sans aucun tronc, et on va modifier la fonction chooseWall() pour lui permettre de choisir des
cases sur le bord, qui deviendront des troncs.
void chooseWall()
{
int x, y;
Color c;
bool isHorizontal;
while(true)
{
if (checkFinished() == true)
break;
isHorizontal = (rand() & 1 ? false : true);
if (isHorizontal == true)
{
x = rand() % MAZE_WIDTH;
y = 1 + (rand() % (MAZE_HEIGHT - 1));
if (x == 0)
{
if (maze.checkIntersection(1, y, c) == false)
{
maze.getTile(x, y)->topIsActive = true;
maze.getTile(x, y)->topColor = Color(32 + rand() % 224,
32 + rand() % 224,
32 + rand() % 224);
break;
}
}
else if (x == MAZE_WIDTH - 1)
{
if (maze.checkIntersection(x, y, c) == false)
{
maze.getTile(x, y)->topIsActive = true;
maze.getTile(x, y)->topColor = Color(32 + rand() % 224,
32 + rand() % 224,
32 + rand() % 224);
break;
}
}
else if (checkWall(x, y, isHorizontal, c) == false)
{
maze.getTile(x, y)->topIsActive = true;
maze.getTile(x, y)->topColor = c;
break;
}
}
else
{
x = 1 + (rand() % (MAZE_WIDTH - 1));
y = rand() % MAZE_HEIGHT;
if (y == 0)
{
if (maze.checkIntersection(x, 1, c) == false)
{
maze.getTile(x, y)->leftIsActive = true;
maze.getTile(x, y)->leftColor = Color(32 + rand() % 224,
32 + rand() % 224,
32 + rand() % 224);
break;
}
}
else if (y == MAZE_HEIGHT - 1)
{
if (maze.checkIntersection(x, y, c) == false)
{
maze.getTile(x, y)->leftIsActive = true;
maze.getTile(x, y)->leftColor = Color(32 + rand() % 224,
32 + rand() % 224,
32 + rand() % 224);
break;
}
}
else if (checkWall(x, y, isHorizontal, c) == false)
{
maze.getTile(x, y)->leftIsActive = true;
maze.getTile(x, y)->leftColor = c;
break;
}
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Et voici un des labyrinthes produits par ce code:
Science et Vie Micro n°34