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
21
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
- 27 janv. 2011 à 18:10
Bonjour
Voila je me présente, je suis en première année de DUT Service et Réseaux de Communication et je dois présenter un dossier présentant l'algorithme pour générer des labyrinthe aléatoirement. Malheureusement je ne trouve que la programmation en C (et Dieux c'est que la programmation et les algorithmes ne sont pas mes occupations favorites:s) , et n'ayant jamais étudier ce langage je n'y comprend rien. Auriez-vous quelque astuce ou explication a me donner?
Merci d'avance
A voir également:

15 réponses

bzrd
Messages postés
21
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
39
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 ...
5