Algorithme labyrinthe correction

Version imprimable

27/04/2009, 22h01
Daminou27

Algorithme labyrinthe correction

Bonsoir,
Voila je dois réaliser un algorithme pour générer automatiquement des labyrinthe. Je voudrais savoir si cet algorithme est correct ou si il y aurai des amélioration à lui apporter....ou s'il ne ressemble a rien même^^. Je suis ouvert à vos critique^^ merci :

Initialisation :

– Une matrice L[N][M] donnée ;
– k ← 0 ;
– Pour i de 0 `a N faire :
Si (i impair et j impair) alors :
| L[i][j]← k ;
| k = k + 1;
| Sinon: L[i][j]← −1 ;
FIN “Si” ;
FIN “Pour” ;

– Pour i de 0 `a N faire :
Si (i impair et j impair) alors :
| L[i][j]← k ;
| k = k + 1;
| Sinon: L[i][j]← −1 ;
FIN “Si” ;
FIN “Pour” ;

Pour NbCasesAZero, le nombre de cases à 0 : NbCasesAZero = 1 ;
Tant que NbCasesAZero < N ×M faire :
| Prendre au hasard (x, y) tel que :
| L[x][y] = −1 et (x impair ou y impair7) ;
Si x impair alors :
d ← L[x][y − 1] − L[x][y + 1] ;
Si d > 0 alors :
| L[x][y] ← L[x][y + 1] ;
| Propager la valeur L[x][y + 1] à partir du point (x, y − 1) (en 4-connexité) pour les
| Cases contenant la valeur L[x][y − 1]8 ;
Sinon, si d < 0 alors :
| L[x][y] ← L[x][y − 1] ;
| Propager la valeur L[x][y − 1] `a partir du point (x, y + 1) (en 4-connexité) pour les
| cases contenant la valeur L[x][y + 1]8 ;
FIN “Si” ;

Sinon (y impair) :
d ← L[x − 1][y] − L[x + 1][y] ;
Si d > 0 alors :
| L[x][y] ← L[x + 1][y] ;
| Propager la valeur L[x + 1][y] `a partir du point (x − 1, y) (en 4-connexité) pour les
| cases contenant la valeur L[x − 1][y]8 ;
Sinon, si d < 0 alors :
| L[x][y] ← L[x − 1][y] ;
| Propager la valeur L[x − 1][y] `a partir du point (x + 1, y) (en 4-connexité) pour les
| cases contenant la valeur L[x + 1][y]8 ;
FIN “Si” ;

FIN “Si” ;

FIN “Tant que”.
FIN “Pour” ;
28/04/2009, 04h59
Garulfo

Tu pourrais faire un effort de présentation.
C'est à peu près illisible.
28/04/2009, 10h04
Invité(e)
Bonjour,

Dans les deux premières boucle POUR sont en fait les mêmes
Dans ces mêmes boucles, seul i varie, jamais j.

Il faudrait aussi détailler
Code:

1 2 | Prendre au hasard (x, y) tel que : | L[x][y] = −1 et (x impair ou y impair7) ;
Sinon, une meilleure indentation serait souhaitable.

EDIT :

Avec

Code:

Tant que NbCasesAZero < N xM faire :

Tu ne sortira de la boucle que quand l'ensemble du tableau sera à 0... Je ne suis pas sur que ce soit souhaitable pour un labyrinthe.

Code réindenté (sauf erreur)

Code:

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
 
Initialisation :
 
Une matrice L[N][M] donnée ;
k  := 0 ;
Pour i de 0 à N faire :
	Si (i impair et j impair) alors :
		L[i][j] := k ;
		k = k + 1;
	Sinon:
		L[i][j] := -1 ;
	FIN Si ;
FIN Pour ;
 
Pour i de 0 à N faire :
	Si (i impair et j impair) alors :
		L[i][j] := k ;
		k = k + 1;
	Sinon:
		L[i][j] := -1 ;
	FIN Si ;
FIN Pour ;
 
Pour NbCasesAZero, le nombre de cases  0 : NbCasesAZero = 1 ;
	Tant que NbCasesAZero < N ×M faire :
 		Prendre au hasard (x, y) tel que L[x][y] = -1 et (x impair ou y impair7) ;
 
		Si x impair alors :
 
			d  := L[x][y - 1] - L[x][y + 1] ;
			Si d > 0 alors :
				L[x][y]  := L[x][y + 1] ;
				Propager la valeur L[x][y + 1]  partir du point (x, y - 1) (en 4-connexité) pour les 
				Cases contenant la valeur L[x][y - 1]8 ;
			Sinon, si d < 0 alors :
				L[x][y]  := L[x][y - 1] ;
				Propager la valeur L[x][y - 1] à partir du point (x, y + 1) (en 4-connexité) pour les
				cases contenant la valeur L[x][y + 1]8 ;
			FIN Si ;
 
		Sinon (y impair) :
 
			d  := L[x - 1][y] - L[x + 1][y] ;
			Si d > 0 alors :
				L[x][y]  := L[x + 1][y] ;
				Propager la valeur L[x + 1][y] à partir du point (x - 1, y) (en 4-connexité) pour les
				cases contenant la valeur L[x - 1][y]8 ;
			Sinon, si d < 0 alors :
				L[x][y]  := L[x - 1][y] ;
				Propager la valeur L[x - 1][y] à partir du point (x + 1, y) (en 4-connexité) pour les cases contenant la valeur L[x + 1][y]8 ;
			FIN Si ;
 
		FIN Si ;
 
	FIN Tant que.
FIN Pour ;

28/04/2009, 19h09
Daminou27

Tout d'abort merci beaucoup pour votre aide et votre rapidité :). Je compté le remettre un peu plus en ordre mais je vois qu'on m'a devancé merci beaucoup :). J'ai plusieurs petite question:
D'abord j'ai pas trop compris les modifs apportées :s. Je préféré vous préciser que mon niveau en algorithme est très bas :s (niveau scolaire).
Ensuite j'ai pu voir sur internet qu'il y avais plusieurs solution pour résoudre cet algorithme mais j'ai pas réussi a trouver lequel correspond a celui donné ci-dessus.
merci d'avance