Générer un labyrinthe sous forme de matrice carrée

**eldoir** · 13/03/2012, 18h26

Bonjour,
Je rencontre un problème dans mon TP.
Voilà l'énoncé :

"On veut réaliser un programme permettant à une souris S de trouver un morceau de fromage F dans un labyrinthe. La souris ne se déplace que case par case et pas en diagonale. Pour le labyrinthe :
Il s'agit d'une matrice carrée 10*10 de caractères.
' ' = espace vide
'*' = mur
'S' = point de départ
'F' = point d'arrivée.

Écrire la procédure creerLaby (var lab : labyrinthe) qui crée un labyrinthe caractère par caractère et ligne par ligne, de façon à initialiser la matrice carrée lab de type labyrinthe. On s'assurera que des murs entourent le labyrinthe, pour les cases internes, on veut 20% de murs. Le départ et l'arrivée sont placés au hasard dans les cases vides restantes."

J'ai déjà écrit :

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
procedure creerLabyrinthe (var lab : labyrinthe); // NI LE DÉPART NI L'ARRIVÉE N'ONT ÉTÉ ENCORE PLACÉS
var i,j,aleat : integer;
begin
	for i := 1 to Nmax do // Mur de gauche
		lab[i,1] := '*';
	for i := 1 to Nmax do // Mur de droite
		lab[i,Nmax] := '*';
	for j := 2 to Nmax-1 do
		lab[1,j] := '*'; // Mur du haut
	for j := 2 to Nmax-1 do
		lab[Nmax,j] := '*'; // Mur du bas
	randomize;
	for i := 2 to Nmax-1 do // L'intérieur du labyrinthe, sans compter les murs
		for j := 2 to Nmax - 1 do // Idem
		begin
			aleat := random(5) + 1; // Nombre aléatoire entre 1 et 5
			case aleat of
				1 : lab[i,j] := '*' // 1 fois sur 5 il y aura un mur
				else
					lab[i,j] := ' ' // 4 fois sur 5 un vide
			end
		end
end;

Voilà quelques question que je me pose :
- J'ai facilement trouvé comment créer les murs, mais pour l'intérieur, comment faire 20% de murs ? L'intérieur du labyrinthe est une matrice 8*8 = 64 n'est pas divisible par 5 ! Du coup, j'ai fait un peu différemment dans mon code, il y a pour chaque case de l'intérieur du labyrinthe 1 chance sur 5 que ça soit un mur, mais ce n'est pas ce qui est demandé :S
- Comment ensuite placer au hasard le départ et l'arrivée dans les cases vides restantes ?

Merci d'avance de vos réponses

**Roland Chastain** · 13/03/2012, 23h06

Bonjour !

Il y a quelque chose qui ne va pas dans la répartition des caractères entre les quatre murs. Si la répartition est faite au pur hasard (comme c'est le cas), ça ne fera pas des couloirs ni des murs. L'énoncé précise bien que la souris ne se déplace pas en diagonale. Il y a donc une condition à ajouter, pour que les "briques" soient placées convenablement. Par exemple, on pourrait s'assurer que pour chaque case vide, il y a au moins une autre case vide qui la touche par l'un de ses côtés, ou quelque chose comme ça.

**eldoir** · 13/03/2012, 23h50

Bonjour et merci à toi

Oui je voyais bien ce problème mais j'en ai un plus important qui m'empêche d'avancer (jusqu'à rencontrer ce problème justement) , c'est le fait qu'on demande 20% de murs internes...
20% c'est 1/5 or il n'y a que 64 cases internes et 64 n'est pas divisible par 5 c'est ça qui me trouble...
Si on prend en compte les murs alors il doit y avoir 20 murs à l'intérieur du labyrinthe (sans compter les murs extérieurs), mais là mon problème c'est que je ne vois pas du tout comment générer ça... et je vois encore moins comment rendre le labyrinthe cohérent comme tu me le précises !

**Roland Chastain** · 14/03/2012, 02h59

Pas si facile cet exercice !

Il me semble clair d'après ce que tu dis que le pourcentage est une indication approximative : 64/5=12,8 donc treize. Je ne vois pas d'autre façon de comprendre l'énoncé et, à mon avis, la solution que tu proposes est acceptable.

Le point intéressant et plus difficile (me semble-t-il), c'est plutôt de s'assurer qu'il y a bien un chemin de la souris au fromage. Je ne sais pas trop comment je ferais cela.

Voyons... Il faut qu'il y ait toujours un chemin d'une case vide à une autre quelconque. Pratiquement, toute case vide doit toucher au moins deux autres cases vides. On ne compte pas les cases qui se touchent par les coins, vu que ce n'est pas un passage !

**Paul TOTH** · 14/03/2012, 09h47

le principe général de construction d'un labyrinthe aléatoire est toujours le même

on part de l'entrée (ou la sortie peu importe) et on creuse un tunnel dans une direction aléatoire à chaque case jusqu'à ce qu'il ne soit plus possible de creuser sans tomber sur une case vide. On obtient un tunnel unique qui serpente. Pour continue il suffit de prendre au hasard une des case vide et de tenter de creuser une bifurcation selon le même principe. Et on répète l'opération jusqu'à ne plus pouvoir creuser (ou avoir atteins les 20% demandés)

**Roland Chastain** · 14/03/2012, 12h37

Envoyé par Paul TOTH

on part de l'entrée (ou la sortie peu importe) et on creuse un tunnel dans une direction aléatoire à chaque case jusqu'à ce qu'il ne soit plus possible de creuser sans tomber sur une case vide.

Une fois dit, ça paraît évident !

@eldoir
J'ai mis la main à la pâte. Je suis parti de tes idées, mais j'ai procédé un peu différemment comme tu le verras. Le programme donne un résultat correct pour ton exercice. Cependant le véritable principe de la solution se trouve dans le message de Paul Toth. Voici quand même ce que j'ai écrit :

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
{Free Pascal 2.6}
 
PROGRAM Labyrinthes ;
 
TYPE Labyrinthe=Array [1..10, 1..10] of Char ;
 
VAR Lab : Labyrinthe ;
 
PROCEDURE Generation ( var L : Labyrinthe ) ;
  var
    x, y : Byte ;
    nbi : Byte ;// Nombre de briques int‚rieures
 
  procedure MurExterieur ;
    var x, y : Byte ;
    begin
      for x:=1 to 10 do
      begin
        L [x,1]:='*' ;
        L [x,10]:='*' ;
      end ;
      for y:=1 to 10 do
      begin
        L [1,y]:='*' ;
        L [10,y]:='*' ;
      end ;
    end ;
 
  function nbac : Byte ; // Nombre de briques "autour" de la case (ayant un côté en commun)
    var n : Byte ;
    begin
      n:=0 ;
      if L[x,y+1]='*' then n:=n+1 ;
      if L[x,y-1]='*' then n:=n+1 ;
      if L[x+1,y]='*' then n:=n+1 ;
      if L[x-1,y]='*' then n:=n+1 ;
      nbac:=n ;
    end ;
 
  begin
    MurExterieur ;
    Randomize ;
    nbi:=0 ;
    repeat
 
      x:=random(7)+2 ;
      y:=random(7)+2 ;
      if nbac < 2
      then
        begin
        L[x,y]:='*' ;
        nbi:=nbi+1 ;
        end
      else L[x,y]:=' ' ;
 
    until nbi/64 > 20/100;
  end ;
 
PROCEDURE Affichage ( L : Labyrinthe ) ;
  var x, y : Byte ;
  begin
    for y:=1 to 10 do
    begin
      for x:=1 to 10 do
      begin
        write(L[x,y]) ;
      end ;
      writeln ;
    end ;
  end ;
 
BEGIN
  Generation(Lab) ;
  Affichage(Lab) ;
END.

**Roland Chastain** · 14/03/2012, 13h15

Envoyé par Paul TOTH

Et on répète l'opération jusqu'à ne plus pouvoir creuser (ou avoir atteins les 20% demandés)

Ce qui est embarrassant dans l'exercice en question, c'est qu'avec 20% de murs on ne peut pas faire un labyrinthe !

**eldoir** · 14/03/2012, 18h36

@Roland Chastain
Tout d'abord, merci de te pencher sur mon cas,
J'ai testé ton code et il me donne des trucs... étranges

Je suis pourtant certain de ne pas être la source du problème.
Plusieurs trucs me chiffonnent à l'exécution :
- Le mur de droite ne s'affiche pas (?)
- L'intérieur du labyrinthe est bizarrement généré !
Tous les murs se trouvent dans la moitié du gauche de l'intérieur du labyrinthe

Peut-être un erreur vient-elle du random(7)+2 ?
Tu voulais générer un nombre entre 2 et 9, soit à l'intérieur du labyrinthe ?
Là je crois que random(7)+2 ça génère un nombre entre 2 et 8 puisque random(7) génère un nombre entre 0 et 6.
Il faudrait utiliser random(8)+2 non ?
Je ne suis qu'en L1 et tout ça me paraît compliqué ok on commence à voir les pointeurs et je n'ai aucun problème j'ai très bien compris mais là cette génération de labyrinthe ça me tue, c'est juste la première question du TP sur les 10 questions donc je ne pense pas que la réponse soit censée être aussi compliquée

Merci de m'aider c'est génial

**eldoir** · 14/03/2012, 18h47

En fait c'est un TP sur les pointeurs mais je ne crois pas qu'on ait besoin d'en utiliser pour coder la procédure creerLabyrinthe.
Voilà à quoi ressemble l'exemple sur ma feuille de TP :

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
 // Exemple donné dans le TP ( S = Souris, F = Fromage)
{ * * * * * * * * * *
  * S * *       *   *	
  *         *       *	
  * * * * * * *   * * 	
  * * * * *         *	
  * *   * * * * *   *	
  *     * F         *	
  *   * * * *   * * *	
  *             * * *	
  * * * * * * * * * * }
 
// Après résolution :
{ * * * * * * * * * *
  * . * * . . . * . *	
  * . . . . * . . . *	
  * * * * * * * . * *	
  * * * * *     . . *	
  * *   * * * * * . *	
  *     * S . . . . *	
  *   * * * *   * * *	
  *             * * *	
  * * * * * * * * * * }

La souris va jusqu'au fromage et elle laisse des '.' derrière elle.

**Roland Chastain** · 14/03/2012, 19h33

Envoyé par eldoir

@Roland Chastain
Tout d'abord, merci de te pencher sur mon cas,
J'ai testé ton code et il me donne des trucs... étranges

Je suis pourtant certain de ne pas être la source du problème.
Plusieurs trucs me chiffonnent à l'exécution :
- Le mur de droite ne s'affiche pas (?)
- L'intérieur du labyrinthe est bizarrement généré !
Tous les murs se trouvent dans la moitié du gauche de l'intérieur du labyrinthe

Il y a manifestement quelque chose qui m'échappe ! Car je viens à l'instant de réessayer le code que j'ai posté : sur mon ordinateur, il fonctionne très bien, sans aucun des symptômes que tu décris. Mystère !

Envoyé par eldoir

Peut-être un erreur vient-elle du random(7)+2 ?
Tu voulais générer un nombre entre 2 et 9, soit à l'intérieur du labyrinthe ?
Là je crois que random(7)+2 ça génère un nombre entre 2 et 8 puisque random(7) génère un nombre entre 0 et 6.
Il faudrait utiliser random(8)+2 non ?

Bien vu ! J'ai mal compté en effet. Mais la seule conséquence de cette erreur est qu'il n'y a jamais de briques dans la neuvième colonne. Cela n'explique pas les problèmes d'affichage.

Envoyé par eldoir

Merci de m'aider c'est génial

Du moins en avais-je l'intention !

**eldoir** · 14/03/2012, 20h06

Eh bien, je viens de re-copier-coller dans un nouveau fichier ton code et
voilà ce que le programme m'affiche à l'exécution :

**********
** *
** *
****
**
***
****
*****
**
**********

Ou encore :

**********
* *
*****
* *
***
*****
* *
*****
**
**********

Voire :

**********
* * **
**
*****
***
* ***
***
****
**
**********

Etc, etc... Vraiment bizarre !

**Paul TOTH** · 15/03/2012, 04h42

Ne faudrait-il pas initialiser tout le tableau au départ et pas seulement les bords ? quel est le contenu des cases non affectées par Generation() ?

**Roland Chastain** · 15/03/2012, 07h53

Envoyé par Paul TOTH

Ne faudrait-il pas initialiser tout le tableau au départ et pas seulement les bords ? quel est le contenu des cases non affectées par Generation() ?

C'est ça ! Il y a en effet une partie des cases qui ne reçoit jamais de valeur. Merci pour le coup d'œil !

Si on ajoute la ligne suivante à la fin de la procedure MurExterieur, le code que j'avais proposé fonctionnera correctement :

Code :

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

for x:=2 to 9 do for y:=2 to 9 do L [x,y]:=#32 ;

Mais en faisant de nouveaux essais je constate que mon algorithme n'est pas bon : il n'empêche pas que des "poches" ne se forment. C'est la petite proportion de briques qui m'a fait illusion.

@eldoir
Sais-tu finalement comment on doit comprendre l'énoncé, concernant la proportion de murs ? Dans l'exemple que tu as reproduit, la proportion n'est pas du tout de 20%.

**eldoir** · 15/03/2012, 14h04

Je suis actuellement en TP,
Et mon prof m'a demandé de faire autrement.
Il nous avait donné le TP mais n'en étant pas l'auteur il n'a pas dû en prendre connaissance.
Du coup, dans ma procédure de création de labyrinthe, j'ai reproduit à l'identique l'exemple qu'on a sur le TP et si mon programme marche, si j'arrive à la fin de mon programme à la même chose que sur l'exemple du TP, alors j'aurais réussi.
Donc vous l'aurez compris, j'abandonne, je vais faire autrement

Générer un labyrinthe sous forme de matrice carrée

Free Pascal

Discussions similaires

Partager

Partager