Discussion :

[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 :

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]

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]

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]

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 !