Discussion :

[timmalos]

Bonjour à tous. Je viens à vous car je suis completement perdu dans ma fonction.
Le principe est très simple, j'ai créé il y a plus d'un an une fonction de génération aléatoire de labyrinthe à laquelle je passais un paramètre unique : mes labyrinthes créés sont donc carrés et elle marche à la perfection.

Mais cette année, le projet a evolué, je suis passé à Lazarus et je voudrais créer des labyrinthes en X * Y. Je change donc le dim_X ci-dessous en lui ajoutant 1 ou 2, mais impossible de résoudre mon problème, la fonction génère un labyrinthe sans les dernières colonnes rajoutées.

J'ai tout repris sur papier, fait de multiples essais mais je n'y arrive pas. Si l'un d'entre vous veut se poser sur le problème ça serait vraiment très sympa.

Merci d'avance,
Tim


Le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//Genere le fichier .txt à l'oupout rentré, de dimension voulue.
procedure generer_lab(outpout:string;dim:integer);
var lab : t_gen;
	dim_x,dim_y,dim_Finale:integer;
	continue,rand,x1,x2,y1,y2,i,j:integer;
	v1,v2,NbMurs:integer;
	MH : t_gen;
	MV : t_gen;
	rendu : t_gen_final;
	fichier:text;
begin
	dim_x := dim;
	dim_y := dim;
	dim_Finale := 2*dim+1;
	randomize;
	NbMurs := 0;
	//Initialisation des tableaux de murs
    For i := 0 To dim_x-1 do
		For j := 0 To dim_y-1 do
			lab[i,j] := i * dim_y + j;
 
	For i := 0 To dim_x-1 do
		For j := 0 To dim_y-2 do
			MH[i,j] := 1;
 
	For i := 0 To dim_x-2 do
		For j := 0 To dim_y-1 do
			MV[i,j] := 1;
	//On va maintenant enlever nos murs 1 par 1
	While NbMurs <> ((dim_x*dim_y)-1) do
	Begin
		continue := 0;
		rand := random(2)+1;
		Case rand of
			1:begin//Murs Horizontaux
				x1 := random(dim_x);
				y1 := random(dim_y-1);
				If (MH[x1,y1] = 1) Then
					begin
					continue := 1;
					x2 := x1;
					y2 := y1 + 1	;
				end;
			end;
			2:begin//Murs Verticaux
				x1 := random(dim_x-1);
				y1 := random(dim_y);
				If MV[x1,y1] = 1 Then
					begin
					continue := 1;
					x2 := x1+1;
					y2 := y1;
				end;
			end;
		End;
		If continue = 1 Then // (= Si un mur a été trouvé)
		Begin
			v1:=lab[x1,y1];
			v2:=lab[x2,y2];
			If v1 <> v2 Then
			Begin
				// On enlève le mur
				Case rand of
					1:
						MH[x1][y1] := 0;
			        2:
						MV[x1][y1] := 0;
				End;
				// On met la même valeur dans les cases de la chaîne
 
				NettoieCellules(lab, x2, y2, dim_x, dim_y, v1, v2);
 
				NbMurs := NbMurs+1;
			End;
 
		End;
	End;
 
	//Maintenant, on a 2 tableaux avec des murs horizontaux et verticaux, tres facile a utiliser.
	//On doit cependant les traiter pour pouvoir creer notre tableaux de la forme souhaitée dans le TP.
	//Et ce ne fut pas une partie de plaisir.
 
	//On met des trous de partout
	For i := 1 To dim_Finale do
		For j := 1 To dim_Finale do
			rendu[i,j]:=' ';
	//On met des M sur la premiere et derniere ligne
	For i := 1 to dim_Finale do
		rendu[1,i]:= 'M';
	For i := 1 to dim_Finale do
		rendu[dim_Finale,i]:= 'M';
	//On met des M sur la premiere colonne et derniere colonne.
	For i := 1 to dim_Finale do
		begin
		rendu[i,1]:= 'M';
		rendu[i,dim_Finale]:= 'M';
		end;
	// On met les murs la ou ils doivent etre en sachant que la dimension finale va etre multipliée par 2 puis additionée à 1.
	For i := 0 To dim_x-2 do
		Begin
		For j := 0 To dim_y-1 do
			If (MV[i,j] = 1) Then
				Begin
				rendu[2*(i+1)+1,j*2+1]:= 'M';
				rendu[2*(i+1)+1,j*2+2]:= 'M';
				rendu[2*(i+1)+1,j*2+3]:= 'M';
				End;
		End;
	For i := 0 To dim_x-1 do
		Begin
		For j := 0 To dim_y-2 do
			If (MH[i,j] = 1) Then
				Begin
				rendu[i*2+1,(j+1)*2+1]:= 'M';
				rendu[i*2+2,(j+1)*2+1]:= 'M';
				rendu[i*2+3,(j+1)*2+1]:= 'M';
				End;
		End;
	//On met l'entrée et la sortie sur les cotés du labyrinthe ou on est sur qu'il n'y a aucun mur devant.
	rendu[(random(dim_Finale div 2)+1)*2,1]:='E';
	rendu[(random(dim_Finale div 2)+1)*2,dim_Finale]:='S';
 
	//On ecrit le fichier
	assign (fichier,outpout);
	rewrite(fichier);
 
	For i := 1 To dim_Finale do
		Begin
		For j := 1 To dim_Finale do
			Write(fichier,rendu[i,j]);
		Writeln(fichier,'');
		End;
	close(fichier);
End;

[mick605]

Salut

Comment fonctionne ton algorithme ? Comment est stocké ton labyrinthe ?
Normalement, le principe de ton algorithme devrait fonctionner quelque soit la dimension du labyrinthe ... Je n'arrive pas bien a comprendre ta technique. Tu aurais peut être du séparer ta procedure en plusieurs sous procedures ...

Voici quelques techniques de générations de labyrinthe :
http://ilay.org/yann/articles/maze/

Bonne chance

[timmalos]

Bonsoir. Merci de votre réponse tout d'abord. J'avais bien entendu suivi le lien que vous m'avez donné il y a un an et j'avais choisi la méthode "Unicité de chemin et aléa" qui semblait donner de meilleurs resultats pour de grandes matrices.

J'ai donc fait cette implementation qui est toute la premiere partie de la fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
dim_x := dim;
	dim_y := dim;
	dim_Finale := 2*dim+1;
	randomize;
	NbMurs := 0;
	//Initialisation des tableaux de murs
    For i := 0 To dim_x-1 do
		For j := 0 To dim_y-1 do
			lab[i,j] := i * dim_y + j;
 
	For i := 0 To dim_x-1 do
		For j := 0 To dim_y-2 do
			MH[i,j] := 1;
 
	For i := 0 To dim_x-2 do
		For j := 0 To dim_y-1 do
			MV[i,j] := 1;
	//On va maintenant enlever nos murs 1 par 1
	While NbMurs <> ((dim_x*dim_y)-1) do
	Begin
		continue := 0;
		rand := random(2)+1;
		Case rand of
			1:begin//Murs Horizontaux
				x1 := random(dim_x);
				y1 := random(dim_y-1);
				If (MH[x1,y1] = 1) Then
					begin
					continue := 1;
					x2 := x1;
					y2 := y1 + 1	;
				end;
			end;
			2:begin//Murs Verticaux
				x1 := random(dim_x-1);
				y1 := random(dim_y);
				If MV[x1,y1] = 1 Then
					begin
					continue := 1;
					x2 := x1+1;
					y2 := y1;
				end;
			end;
		End;
		If continue = 1 Then // (= Si un mur a été trouvé)
		Begin
			v1:=lab[x1,y1];
			v2:=lab[x2,y2];
			If v1 <> v2 Then
			Begin
				// On enlève le mur
				Case rand of
					1:
						MH[x1][y1] := 0;
			        2:
						MV[x1][y1] := 0;
				End;
				// On met la même valeur dans les cases de la chaîne
 
				NettoieCellules(lab, x2, y2, dim_x, dim_y, v1, v2);
 
				NbMurs := NbMurs+1;
			End;
 
		End;
	End;
 
	//Maintenant, on a 2 tableaux avec des murs horizontaux et verticaux, tres facile a utiliser.
	//On doit cependant les traiter pour pouvoir creer notre tableaux de la forme souhaitée dans le TP.
	//Et ce ne fut pas une partie de plaisir.

Et comme le precisent les derniers commentaires, je veux en fait des labyrinthes sous la forme suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
M M   M   M   M M M   M M   M M         M
M M M M MMM MMM M M MMM MMM M M MMM M M M
M   M     M M M       M   M M M M   M M S
MMMMM MMM M M MMMMM MMMMM M M MMMMMMM M M
M   M   M           M         M   M   M M
M M MMMMM M MMM MMMMMMMMM MMMMMMM MMM M M
M M M   M M M M     M   M     M       M M
M MMMMM MMM M M MMMMMMM M MMM M M M MMMMM
M       M     M     M     M   M M M     M
MMM M MMMMMMM MMM MMM M MMMMMMMMM M MMM M
M   M   M       M   M M         M M   M M
MMM MMM M MMMMMMM M M M M M MMM M M MMMMM
M     M M M     M M   M M M M M M M   M M
MMMMM MMMMM MMMMMMM MMMMMMMMM M MMMMM M M
M         M       M       M M M M M M   M
M MMMMMMMMMMM MMMMMMM M MMM M MMM M M MMM
M   M       M   M     M               M M
MMM M M MMM MMM MMM M MMM M M M M M MMM M
M     M M M   M M   M   M M M M M M     M
MMMMM MMM M MMM M MMM MMM MMMMM MMMMMMMMM
M   M M   M   M     M   M M           M M
M MMM MMM MMM M MMM MMM MMM MMMMM MMM M M
M       M       M     M M       M M   M M
MMM MMM MMM M M MMM MMMMMMM M MMM MMMMM M
M     M   M M M   M   M     M M         M
M MMMMMMMMMMMMM MMM M MMMMM M MMM M MMM M
E   M       M   M M M M   M M M M M   M M
MMMMM MMMMMMMMMMM MMM M MMMMMMM M MMM M M
M M       M   M   M           M   M M M M
M MMMMMMM MMM M MMMMMMMMM MMMMMMMMM M M M
M   M M M M     M       M M       M   M M
M MMM M M MMMMM MMMMM M M M MMMMMMM MMMMM
M       M   M M   M   M       M         M
MMM MMM M M M M MMMMMMM M MMMMM MMMMM MMM
M M   M   M   M       M M     M   M     M
M MMMMM MMMMM M MMMMMMMMMMM MMMMM M MMM M
M M       M M   M M M   M       M M   M M
M MMMMMMM M MMM M M MMM MMMMM MMM MMMMMMM
M             M                 M       M
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

D'ou la derniere partie du code, et je pense que c'est elle qui pose problème, car les tests semblent montrer que les tableaux MV et MH [pour murs verticaus/horizontaux] sont bien remplis, mais je n'arrive vraiment pas à trouver ou.

[timmalos]

J'ai finalement résolu mon problème en trifouillant bien. Si quelqu'un a besoin de la solution, qu'il n’hésite pas à me MP.


Merci pour l'aide apportée, bonne continuation,
Tim

[Alcatîz]

Si quelqu'un a besoin de la solution, qu'il n'hesite pas à me MP.

Ce serait encore mieux de la poster directement sur le forum.

[Paul TOTH]

Ce serait encore mieux de la poster directement sur le forum.

attends, si tout le monde se mettait à donner des solutions sur ce forum il deviendrait une source d'information formidable pour développeur en herbe...c'est pas le but tout de même ?

[timmalos]

Je suis bien d'accord avec vous, et je m'excuse de m'être mal exprimé, mais ce n'est pas une raison pour être médisant... Je suis sur qu'il vous est déjà arrivé de mettre des messages sur ce forum sans avoir forcément le temps de l'approfondir.

Le problème c'est que ce n'est pas un bout de code en lui même qui répond à une problématique donnée, juste une erreur bête que j'ai fait par rapport aux index de mes tableaux. Donc je vais poster ma fonction ci-dessous, mais je doute qu'elle soit utile pour quiconque Et si quelqu'un a besoin d'aide pour la même problématique, je serai heureux de l'aider sans problèmes !

Je prefère terminer mon programme et le partager en exemple (COmme je l'ai deja fait ici : http://www.developpez.net/forums/d93...ie-labyrinthe/) que donner quelques bouts qui ne veulent rien dire sur différents posts.

Donc voici la fonction dont rien n'a fondamentalement changé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
{Procedures de Generation du Labyrinthe Aleatoire}
Procedure CLabyrinthe.NettoieCellules(var alab:t_gen; ax2, ay2, adim_x, adim_y, av1, av2:integer);
Begin
	alab[ax2,ay2] := av1;
	If (ax2 > 0) And (alab[ax2 - 1,ay2] = av2) Then
		NettoieCellules(alab, ax2 - 1, ay2, adim_x, adim_y, av1, av2);
	If (ax2 < adim_x-1) And (alab[ax2 + 1,ay2] = av2) Then
		NettoieCellules(alab, ax2 + 1, ay2, adim_x, adim_y, av1, av2);
	If (ay2 > 0) And (alab[ax2,ay2 - 1] = av2) Then
		NettoieCellules(alab, ax2, ay2 - 1, adim_X, adim_y, av1, av2);
	If (ay2 < adim_y-1) And (alab[ax2,ay2 + 1] = av2) Then
		NettoieCellules(alab, ax2, ay2 + 1, adim_x, adim_y, av1, av2);
End;
procedure CLabyrinthe.GenererLab(aoutpout:string;adimx,adimy:integer);
var lab : t_gen;
	dim_x,dim_y,dim_Finale_x,dim_Finale_y:integer;
	continue,rand,x1,x2,y1,y2,x,y:integer;
	v1,v2,NbMurs:integer;
	MH : t_gen;
	MV : t_gen;
	rendu : t_gen_final;
	fichier:text;
begin
        dim_x := adimx;
	dim_y := adimy;
	dim_Finale_X := 2*dim_x+1;
        dim_Finale_Y := 2*dim_y+1;
	randomize;
	NbMurs := 0;
	//Initialisation des tableaux de murs
         For x := 0 To dim_x-1 do
		For y := 0 To dim_y-1 do
			lab[x,y] := x * dim_y + y;
 
	For x := 0 To dim_x-1 do
		For y := 0 To dim_y-2 do
			MH[x,y] := 1;
 
	For x := 0 To dim_x-2 do
		For y := 0 To dim_y-1 do
		    MV[x,y] := 1;
	//On va maintenant enlever nos murs 1 par 1
	While NbMurs <> ((dim_x*dim_y)-1) do
	Begin
		continue := 0;
		rand := random(2)+1;
		Case rand of
			1:begin//Murs Horizontaux
				x1 := random(dim_x);
				y1 := random(dim_y-1);
				If (MH[x1,y1] = 1) Then
					begin
					continue := 1;
					x2 := x1;
					y2 := y1 + 1	;
				end;
			end;
			2:begin//Murs Verticaux
				x1 := random(dim_x-1);
				y1 := random(dim_y);
				If MV[x1,y1] = 1 Then
					begin
					continue := 1;
					x2 := x1+1;
					y2 := y1;
				end;
			end;
		End;
		If continue = 1 Then // (= Si un mur a été trouvé)
		Begin
			v1:=lab[x1,y1];
			v2:=lab[x2,y2];
			If v1 <> v2 Then
			Begin
				// On enlève le mur
				Case rand of
 
                                1:
						MH[x1][y1] := 0;
			        2:
						MV[x1][y1] := 0;
				End;
				// On met la même valeur dans les cases de la chaîne
 
				NettoieCellules(lab, x2, y2, dim_x, dim_y, v1, v2);
 
				NbMurs := NbMurs+1;
			End;
 
		End;
	End;
 
        {s := '';
        For i := 0 to dim_y-2 do
            s := s+FloatToStr(MH[dim_x-1][i])+'//';
        Showmessage(s);  }
	//Maintenant, on a 2 tableaux avec des murs horizontaux et verticaux, tres facile a utiliser.
 
        //On met des trous de partout
	For x := 0 To dim_Finale_X -1 do
		For y := 0 To dim_Finale_Y -1 do
			rendu[x,y]:=' ';
	//On met des M sur la premiere et derniere ligne
	For x := 0 to dim_Finale_X - 1 do begin
		rendu[x,0]:= 'M';
		rendu[x,dim_Finale_Y-1]:= 'M';
        End;
	//On met des M sur la premiere colonne et derniere colonne.
	For y := 0 to dim_Finale_Y-1 do
		begin
		rendu[0,y]:= 'M';
		rendu[dim_Finale_X-1,y]:= 'M';
		end;
	// On met les murs la ou ils doivent etre en sachant que la dimension finale va etre multipliée par 2 puis additionée Ã* 1.
	For x := 0 To dim_x-2 do
		Begin
		For y := 0 To dim_y-1 do
			If (MV[x,y] = 1) Then
				Begin
				rendu[2*(x+1),y*2+0]:= 'M';
				rendu[2*(x+1),y*2+1]:= 'M';
				rendu[2*(x+1),y*2+2]:= 'M';
                                //ShowMessage(FloatToStr(i)+'//'+FloatToStr(j)+'//'+rendu[2*(i+1)+1,j*2+1]+'//'+rendu[2*(i+1)+1,j*2+2]+'//'+rendu[2*(i+1)+1,j*2+3]+'//')
				End;
		End;
	For x := 0 To dim_x-1 do
		Begin
		For y := 0 To dim_y-2 do
			If (MH[x,y] = 1) Then
				Begin
			        rendu[x*2  ,(y+1)*2]:= 'M';
				rendu[x*2+1,(y+1)*2]:= 'M';
				rendu[x*2+2,(y+1)*2]:= 'M';
                                //ShowMessage(FloatToStr(i*2+1)+'//'+FloatToStr((j+1)*2+1)+'//'+FloatToStr(i)+'//')
				End;
		End;
	//On met l'entrée et la sortie sur les cotés du labyrinthe
	rendu[0,(random(dim_Finale_Y div 2)+1)*2-1]:='E';
	rendu[dim_Finale_X-1,(random(dim_Finale_Y div 2)+1)*2-1]:='S';
	//On ecrit le fichier
	assign (fichier,aoutpout);
	rewrite(fichier);
 
	For y := 0 To dim_Finale_Y-1 do
		Begin
		For x := 0 To dim_Finale_X-1 do
			Write(fichier,rendu[x,y]);
		Writeln(fichier,'');
		End;
	close(fichier);
End;

Bonne journée,
Tim

[Paul TOTH]

on te taquine

mais voila le problème est résolu avec une réponse, si quelqu'un veux faire du labyrinthe se fil lui est utile...sans ta dernière réponse il restait sur sa faim

[timmalos]

C'est pas faux
Merci pour votre temps passé à moderer ces forums.
A bientot