Algorithme générer un labyrinthe aléatoire
Hucanabis
Messages postés
5
Date d'inscription
mercredi 18 mars 2009
Statut
Membre
Dernière intervention
24 avril 2009
-
18 mars 2009 à 10:22
bzrd Messages postés 20 Date d'inscription vendredi 13 octobre 2006 Statut Membre Dernière intervention 25 mars 2011 - 7 janv. 2011 à 09:46
bzrd Messages postés 20 Date d'inscription vendredi 13 octobre 2006 Statut Membre Dernière intervention 25 mars 2011 - 7 janv. 2011 à 09:46
A voir également:
- Générateur de labyrinthe
- Générateur labyrinthe - Meilleures réponses
- Algorithme labyrinthe - Meilleures réponses
- Générateur de nombre ✓ - Forum PHP
- Generateur de nom de jeu ✓ - Forum Flash
- Générateur de lettre ✓ - Forum VB.NET
- Générateur de pseudo - Forum Visual Basic
- Generateur de nom ✓ - Forum C++ & C++ .NET
13 réponses
bzrd
Messages postés
20
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
36
5 janv. 2011 à 11:49
5 janv. 2011 à 11:49
// Voilà mon source final ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define LIGNES 10
#define COLONNES 20
#define HAUT 1
#define DROIT 2
#define BAS 4
#define GAUCHE 8
#define CLOS HAUT+DROIT+BAS+GAUCHE
typedef struct _sPILE_
{
int x;
int y;
} sPILE;
/* Protos obligatoires si le main est en première fonction, préférable de toutes façons */
void initialisation_carte();
void creerLaby();
int tester(int x, int y);
void Afficher();
/* Les globales */
int gLaby[LIGNES][COLONNES];
sPILE gPile[LIGNES*COLONNES]; // a priori on empile au maximum 1 fois chaque case
int gNiveauPile;
int main()
{
gNiveauPile = 0;
initialisation_carte(); // Laby est en globale, pas besoin de passer en paramètre
creerLaby();
Afficher();
}
void Afficher()
{
int i, j;
char buffer1[COLONNES*3+1]; // ligne pour les cases (ex: "| | | |")
char buffer2[COLONNES*3+1]; // ligne pour les murs horizontaux entre les cases (ex: "+--+--+ +--+")
// nb. Dans cette fonction on peut utiliser strcat au lieu de strcat_s, en supprimant le 2nd paramètres
// mais certains compilateurs mettent un warning
// La ligne du haut est fermée
for (i=0; i<COLONNES; i++)
printf("+--");
printf("+\n");
for(i=0; i<LIGNES; i++)
{
buffer1[0] = buffer2[0] = 0; // RAZ buffer - on peut aussi mettre '\0'
for(j=0; j<COLONNES; j++)
{
// le mur droit est traité par la case à droite
// le mur haut par la case du dessous
if (gLaby[i][j] & GAUCHE)
strcat_s(buffer1, sizeof(buffer1), "| ");
else
strcat_s(buffer1, sizeof(buffer1), " ");
if (gLaby[i][j] & BAS)
strcat_s(buffer2, sizeof(buffer2), "+--");
else
strcat_s(buffer2, sizeof(buffer1), "+ ");
}
// affichage d'un ligne de case, de son mur droit, de la ligne de murs, et de son + final
printf("%s|\n%s+\n", buffer1, buffer2);
}
}
void initialisation_carte ()
{
int i,j;
for(i=0; i<LIGNES; i++) // je remplis ma matrice de murs à CLOS (que des murs)
{
for(j=0; j<COLONNES; j++)
{
gLaby[i][j] = CLOS;
}
}
}
// renvoie 1 si au moins une case voisine accessible (à CLOS)
int tester(int x, int y)
{
int i, j;
for (i=-1; i<2; i++)
for (j=-1; j<2; j++)
{
if (i*j==0 && i!=j) // tester uniquement les 4 directions (N, E, S, O)
{
if (x+i<0 || x+i>=LIGNES || y+j<0 || y+j>=COLONNES)
continue;
if (gLaby[x+i][y+j] == CLOS)
return 1;
}
}
return 0;
}
void creerLaby()
{
int i, j;
int di, dj;
int alea;
int dir;
srand((unsigned int)time(NULL)); // intialiser le générateur aléatoire
alea = rand();
i = alea%LIGNES; // première case au hasard
alea = rand();
j = alea%COLONNES;
// empiler la première case
gPile[gNiveauPile].x = i;
gPile[gNiveauPile].y = j;
gNiveauPile++;
while (gNiveauPile > 0)
{
// tester les 4 cases d'à côté
if (tester(i, j) == 0)
{
// aucune case autour de [i,j] n'est à CLOS
// on dépile
gNiveauPile--;
if (gNiveauPile > 0)
{
i = gPile[gNiveauPile].x;
j = gPile[gNiveauPile].y;
}
continue;
}
for (;;) // tant qu'on n'a pas trouvé une case OK (il y en a au moins une)
{
dir = rand()%4;
switch(dir)
{
case 0:
dj=1; di=0;
dir = DROIT;
break;
case 1:
dj=0; di=1;
dir = BAS;
break;
case 2:
dj=-1; di=0;
dir = GAUCHE;
break;
case 3:
dj=0; di=-1;
dir = HAUT;
break;
}
if (i+di<0 || i+di>=LIGNES || j+dj<0 || j+dj>=COLONNES || gLaby[i+di][j+dj] != CLOS)
continue; // hors limites, ou case déjà traitée
// que des murs, on peut ouvrir.
// printf("i=%d, j=%d, dir=%s\n", i, j, di==1 ? "Droit":dj==1 ? "Bas" : di==-1 ? "Gauche": "Haut");
// ouvrir le mur dans la case courante
gLaby[i][j] &= ~dir; // on enlève le bit correspondant au mur
// ouvrir le mur dans la case destination (on peut optimiser ...)
if (dir==HAUT)
gLaby[i+di][j+dj] &= ~BAS;
if (dir==BAS)
gLaby[i+di][j+dj] &= ~HAUT;
if (dir==GAUCHE)
gLaby[i+di][j+dj] &= ~DROIT;
if (dir==DROIT)
gLaby[i+di][j+dj] &= ~GAUCHE;
// empiler la nouvelle case
i = i+di;
j = j+dj;
gPile[gNiveauPile].x = i;
gPile[gNiveauPile].y = j;
gNiveauPile++;
break;
}
}
}
// Je suis sûr que l'indentation va disparaître, mais bon ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define LIGNES 10
#define COLONNES 20
#define HAUT 1
#define DROIT 2
#define BAS 4
#define GAUCHE 8
#define CLOS HAUT+DROIT+BAS+GAUCHE
typedef struct _sPILE_
{
int x;
int y;
} sPILE;
/* Protos obligatoires si le main est en première fonction, préférable de toutes façons */
void initialisation_carte();
void creerLaby();
int tester(int x, int y);
void Afficher();
/* Les globales */
int gLaby[LIGNES][COLONNES];
sPILE gPile[LIGNES*COLONNES]; // a priori on empile au maximum 1 fois chaque case
int gNiveauPile;
int main()
{
gNiveauPile = 0;
initialisation_carte(); // Laby est en globale, pas besoin de passer en paramètre
creerLaby();
Afficher();
}
void Afficher()
{
int i, j;
char buffer1[COLONNES*3+1]; // ligne pour les cases (ex: "| | | |")
char buffer2[COLONNES*3+1]; // ligne pour les murs horizontaux entre les cases (ex: "+--+--+ +--+")
// nb. Dans cette fonction on peut utiliser strcat au lieu de strcat_s, en supprimant le 2nd paramètres
// mais certains compilateurs mettent un warning
// La ligne du haut est fermée
for (i=0; i<COLONNES; i++)
printf("+--");
printf("+\n");
for(i=0; i<LIGNES; i++)
{
buffer1[0] = buffer2[0] = 0; // RAZ buffer - on peut aussi mettre '\0'
for(j=0; j<COLONNES; j++)
{
// le mur droit est traité par la case à droite
// le mur haut par la case du dessous
if (gLaby[i][j] & GAUCHE)
strcat_s(buffer1, sizeof(buffer1), "| ");
else
strcat_s(buffer1, sizeof(buffer1), " ");
if (gLaby[i][j] & BAS)
strcat_s(buffer2, sizeof(buffer2), "+--");
else
strcat_s(buffer2, sizeof(buffer1), "+ ");
}
// affichage d'un ligne de case, de son mur droit, de la ligne de murs, et de son + final
printf("%s|\n%s+\n", buffer1, buffer2);
}
}
void initialisation_carte ()
{
int i,j;
for(i=0; i<LIGNES; i++) // je remplis ma matrice de murs à CLOS (que des murs)
{
for(j=0; j<COLONNES; j++)
{
gLaby[i][j] = CLOS;
}
}
}
// renvoie 1 si au moins une case voisine accessible (à CLOS)
int tester(int x, int y)
{
int i, j;
for (i=-1; i<2; i++)
for (j=-1; j<2; j++)
{
if (i*j==0 && i!=j) // tester uniquement les 4 directions (N, E, S, O)
{
if (x+i<0 || x+i>=LIGNES || y+j<0 || y+j>=COLONNES)
continue;
if (gLaby[x+i][y+j] == CLOS)
return 1;
}
}
return 0;
}
void creerLaby()
{
int i, j;
int di, dj;
int alea;
int dir;
srand((unsigned int)time(NULL)); // intialiser le générateur aléatoire
alea = rand();
i = alea%LIGNES; // première case au hasard
alea = rand();
j = alea%COLONNES;
// empiler la première case
gPile[gNiveauPile].x = i;
gPile[gNiveauPile].y = j;
gNiveauPile++;
while (gNiveauPile > 0)
{
// tester les 4 cases d'à côté
if (tester(i, j) == 0)
{
// aucune case autour de [i,j] n'est à CLOS
// on dépile
gNiveauPile--;
if (gNiveauPile > 0)
{
i = gPile[gNiveauPile].x;
j = gPile[gNiveauPile].y;
}
continue;
}
for (;;) // tant qu'on n'a pas trouvé une case OK (il y en a au moins une)
{
dir = rand()%4;
switch(dir)
{
case 0:
dj=1; di=0;
dir = DROIT;
break;
case 1:
dj=0; di=1;
dir = BAS;
break;
case 2:
dj=-1; di=0;
dir = GAUCHE;
break;
case 3:
dj=0; di=-1;
dir = HAUT;
break;
}
if (i+di<0 || i+di>=LIGNES || j+dj<0 || j+dj>=COLONNES || gLaby[i+di][j+dj] != CLOS)
continue; // hors limites, ou case déjà traitée
// que des murs, on peut ouvrir.
// printf("i=%d, j=%d, dir=%s\n", i, j, di==1 ? "Droit":dj==1 ? "Bas" : di==-1 ? "Gauche": "Haut");
// ouvrir le mur dans la case courante
gLaby[i][j] &= ~dir; // on enlève le bit correspondant au mur
// ouvrir le mur dans la case destination (on peut optimiser ...)
if (dir==HAUT)
gLaby[i+di][j+dj] &= ~BAS;
if (dir==BAS)
gLaby[i+di][j+dj] &= ~HAUT;
if (dir==GAUCHE)
gLaby[i+di][j+dj] &= ~DROIT;
if (dir==DROIT)
gLaby[i+di][j+dj] &= ~GAUCHE;
// empiler la nouvelle case
i = i+di;
j = j+dj;
gPile[gNiveauPile].x = i;
gPile[gNiveauPile].y = j;
gNiveauPile++;
break;
}
}
}
// Je suis sûr que l'indentation va disparaître, mais bon ...
