[Free Pascal] Générer un labyrinthe sous forme de matrice carrée

[eldoir]

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 :

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]

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]

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]

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]

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]

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 :

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]

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]

@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]

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 :

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]

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]

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]

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]

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 :

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]

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