Algorithme générer un labyrinthe aléatoire

Messages postés
5
Date d'inscription
mercredi 18 mars 2009
Statut
Membre
Dernière intervention
24 avril 2009
- - Dernière réponse : bzrd
Messages postés
25
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
Afficher la suite 

15 réponses

Meilleure réponse
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
3
Merci
Tu es sûr pour le ن ?

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 202 internautes nous ont dit merci ce mois-ci

Commenter la réponse de bzrd
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
2
Merci
Salut,

Le plus simple pour faire un labyrinthe c'est :

1- créer une matrice NxM de cases dont chaque case contient 4 murs
2- choisir une case de départ aléatoirement (case courante)
3- empiler les coordonnées de la case courante
4- si aucune des 4 cases voisines n'a 4 murs aller en 8-
5- choisir aléatoirement une des cases voisines ayant 4 murs
6- supprimer le mur entre la case courant et la case destinataire (suppression dans la case courante et dans la case destinataire)
7- case courante=case destinataire et aller en 3-
8- si la pile est vide aller en 10
9- dépiler une case et aller en 4
10-FIN

C'est à peu près tout !
En pratique, pour simplifier certains tests, on crée une matrice (N+2)x(M+2) pour avoir une "bordure", et cette bordure est initialisée non pas avec 4 murs mais avec 0 (comme ça on ne sort pas du cadre dans les phases 4- et 5-). Bien sûr il faut choisir la case de départ en dehors de cette bordure.

Pour faire un vrai labyrinthe il n'y a plus qu'à créer une entrée et une sortie.
Cet algorithme permet de créer un labyrinthe avec un seul chemin entre 2 cases distinctes.

Cordialement
Commenter la réponse de bzrd
Messages postés
5
Date d'inscription
mercredi 18 mars 2009
Statut
Membre
Dernière intervention
24 avril 2009
2
2
Merci
Bon bas je crois que la bulle m'attend :s jsuis vraiment pas fait pour ce genre de chose :( :(
Commenter la réponse de Hucanabis
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
2
Merci
// 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 ...
Commenter la réponse de bzrd
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
1
Merci
Salut,

En principe ça doit te donner des labyrinthes de ce type :

+--+--+--+--+--+--+--+
|        |        |  |
+--+--+  +  +--+  +  +
|     |  |     |     |
+  +  +  +--+  +--+  +
|  |  |        |  |  |
+--+  +--+--+--+  +  +
|     |        |     |
+  +--+  +  +--+  +--+
|        |           |
+--+--+--+--+--+--+--+

Avec un seul chemin entre 2 cases distinctes et ni porte ni entrée (sauf si tu décides d'en mettre en ouvrant deux murs externes).
Je pense que c'est ce que veut ton prof ...
Commenter la réponse de bzrd
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
1
Merci
On va y penser !
NB je viens de voir qu'il y a une petite erreur sur un strcat_s : un sizeof(buffer1) à la place d'un sizeof(buffer2).

S+
Commenter la réponse de bzrd
Messages postés
5
Date d'inscription
mercredi 18 mars 2009
Statut
Membre
Dernière intervention
24 avril 2009
2
0
Merci
Ha merci beaucoup pour l'aide:)
Mais je n'arrive toujours pas a réaliser son algorithme comme on me le demande :( c'est a dire avec Début, Fin, SI, les boucles etc...et oui quand je vous disais que je n'y connaissais rien en algorithme c'est vraiment rien :(
Commenter la réponse de Hucanabis
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
0
Merci
Tu ne voudrais quand même pas que je te fournisse l'organigramme !

De toute façon, c'est facile : tu ajoutes "0- DEBUT" et tu as déjà "10-FIN".
Ajouter en "0.5 - Initialisation d'une pile".
Tu as un SI en lignes 4 et 8.
Les boucles sont faciles à trouver ("aller en ...")
Eventuellement, en 10- tu peux ajouter l'affichage du labyrinthe avant la FIN.

Allez, un (petit) effort !
Commenter la réponse de bzrd
Messages postés
5
Date d'inscription
mercredi 18 mars 2009
Statut
Membre
Dernière intervention
24 avril 2009
2
0
Merci
Merci bcp pour ton aide et ta patience :)
Je vais essayer de me débrouiller. Mais ce n'est pas par fainéantise que je demande sans cesse des explications, c'est que j'ai vraiment du mal :s je n'ai malheureusement pas la logique pour ce genre de matiére :s
Encore merci :)
Commenter la réponse de Hucanabis
Messages postés
5
Date d'inscription
mercredi 18 mars 2009
Statut
Membre
Dernière intervention
24 avril 2009
2
0
Merci
Re dsl de te déranger^^
Mais en faite mon prof' veux un générateur aléatoire de labyrinthe, et non un labyrinthe standart avec une porte et une sortie:s je ne sais donc pas si ce que tu m'a dis s'applique a mon cas:s
Commenter la réponse de Hucanabis
Messages postés
1
Date d'inscription
samedi 13 novembre 2010
Statut
Membre
Dernière intervention
13 novembre 2010
0
Merci
Bonjour tout le monde,

J'ai un projet dans le même genre à réaliser, mais je ne comprend pas bien, les explications, est'il possible que quelqu'un m'aide un peu s'il vous plait?

Merci
Commenter la réponse de loulou8453
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
0
Merci
Salut,
Dis-moi ce que tu ne comprends pas et j'essaierai de t'aider (si j'ai le temps).

Pour t'avancer, il suffit de coder les cases comme suit :
1=Haut, 2=Droite, 4=Bas et 8=Gauche
Avec ça, la case [0, 0] de l'exemple ci-dessous, serait codée (1+4+8)=13, soit pas de mur à droite, et la [0, 6] vaudrait (1+2+8)=11 -- pas de mur en bas.
0 1 2 3 4 5 6
+--+--+--+--+--+--+--+
0| | | |
+--+--+ + +--+ + +
1| | | | |
+ + + +--+ +--+ +
2| | | | | |
+--+ +--+--+--+ + +
3| | | |
+ +--+ + +--+ +--+
4| | |
+--+--+--+--+--+--+--+

Donc une case avec 4 murs est codée 15 (1+2+4+8).
Voilà il suffit de savoir générer un nombre aléatoire et gérer une pile.

Cordialement
Commenter la réponse de bzrd
Messages postés
25
Date d'inscription
vendredi 13 octobre 2006
Statut
Membre
Dernière intervention
25 mars 2011
12
0
Merci
Désolé, le dessin est mal passé !

..0..1..2..3..4..5..6
.+--+--+--+--+--+--+--+
0|........|........|..|
.+--+--+..+..+--+..+..+
1|.....|..|.....|.....|
.+..+..+..+--+..+--+..+
2|..|..|........|..|..|
.+--+..+--+--+--+..+..+
3|.....|........|.....|
.+..+--+..+..+--+..+--+
4|........|...........|
.+--+--+--+--+--+--+--+

On est obligé de mettre des . de couleur blanche ! Quelle horreur !
Commenter la réponse de bzrd
Messages postés
14681
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
5 décembre 2019
90
0
Merci
Hello,
@bzrd: je penses que tu pourrais en faire une source et la déposer sur le site. ça pourrait en aider plus d'un...

@+
Buno
----------------------------------------
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Rejoignez mon réseau professionnel sur Viadeo
Commenter la réponse de BunoCS
Messages postés
2
Date d'inscription
mercredi 26 janvier 2011
Statut
Membre
Dernière intervention
7 novembre 2012
0
Merci
ارجوكم فل يساعدني احد في لعبة المتاهة بلغة باسكال و ليكن البرنامج بسيطا وقابلا للتنفيذ جزاكم الله خيرا
Commenter la réponse de redabochra