Discussion :

[redvivi]

Bonjour à tous !

Tout d'abord, merci de lire mon message ! je vous presente mon probleme, je voudrais construire un labyrinthe et créer un algorithme permettant de trouver le chemin vers la sortie, l'entree se fait au sud ouest et la sortie au nord est.

J'ai donc creer un labyrinthe dont chaque case est representée par 4 cellules de tableau (Nord, Sud, Est, Ouest) representée elle-meme par des booleens). Mon probleme est que je ne vois pas comment créer un chemin aleatoire (qui a une solution), c'est à dire à partir de la case sud-ouest, tester les 4 directions, puis une fois que la direction est validée, se positionner sur la case determinée par la direction precedemment choisie et tester et ainsi de suite. Dans une case il y a 4 cellules, les booleans sont representé comme ceci:

N E
W S

Voici 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
program testando;
uses wincrt,
     wingraph;
const h=16; v=16;
type tableau=array[1..2*h,1..2*v] of boolean;
var i,r,s:integer;
    L:tableau;
 
 
 
procedure initialisation (var L:tableau; h,v:integer);
var x,r,s:integer;
 
begin
     {Toutes les cellules à false}
     for r:=1 to 2*h do
          for s:=1 to 2*v do
              begin L[r,s]:=false
              end;
 
     {Détermination de l'entree SW} 
     L[2,1]:=true
 
 
 
 
    { for r:=1 to 2*h do
         for s:=1 to 2*v do
             begin x:=random(2);
                   L[r,s]:=false;
                   if x=1
                   then L[r,s]:=true
             end; }
 
 
 
    {Toutes les cellules exterieurs à false}
   { for r:=1 to 2*h do
          begin
               L[r,1]:=false ;
               L[r,2*v]:=false ;
          end;
 
    for s:=1 to 2*v do
          begin
               L[1,s]:=false ;
               L[2*h,s]:=false ;
          end;   }
 
end;
 
procedure creation_du_chemin (var L:tableau); {ne fonctionne pas, erreur de raisonnement}
var a,b,x,i1,j1,i2,j2,i3,j3:integer;
 
begin  a:=1;
       b:=1;
               begin if (a=1) and (b<>1)
                     then
                         begin
                              x:=random(3) ;
                              if x=0 then L[2*a-1,2*b]:= true else
                              if x=1 then L[2*a,2*b-1]:=true else
                              if x=2 then L[2*a,2*b]:=true ;
                         end
                     else if (a=1) and (b=1)
                          then
                              begin
                                   x:=random(2) ;
                                   if x=0 then L[2*a-1,2*b]:= true else
                                   if x=1 then L[2*a,2*b]:=true;
                              end
                              else if (a<>1) and (b=1)
                                   then
                                       begin
                                            x:=random(2) ;
                                            if x=0 then L[2*a-1,2*b]:= true else
                                            if x=1 then L[2*a,2*b]:=true else
                                            if x=2 then L[2*a-1,2*b-1]:=true ;
                                       end
                                   else if (a<>0) and (b<>0)
                                        then
                                            begin
                                                 x:=random(3);
                                                 if x=0 then L[2*a-1,2*b]:= true else
                                                 if x=1 then L[2*a,2*b-1]:=true else
                                                 if x=2 then L[2*a,2*b]:=true else L[2*a-1,2*b-1]:=true;
                                            end;
 
 
               end; 
 
 
 
end;
 
 
 
 
 
 
 
 
procedure representation (L:tableau);
var a,b,i1,j1,i2,j2,i3,j3,i4,j4:integer;
 
 
 
begin  for a:= 1 to h do  {scan horizontal sur les colonnes paires, S}
          for b:= 1 to v do
               begin i1:=2*a; j1:=2*b-1 ;
                     if L[i1,j1]=false
                     then segment(2*a-2,2*b-2,2*a,2*b-2);
               end; 
 
      for a:= 1 to h do  { scan horizontal sur les colonnes impaires, W}
           for b:= 1 to v do
               begin i2:=2*a-1; j2:=2*b-1 ;
                     if L[i2,j2]=false
                     then segment(2*a-2,2*b-2,2*a-2,2*b);
               end;
 
      for b:= 1 to v do { scan vertical sur les lignes impaires, E}
           for a:= 1 to h do
               begin i3:=2*a; j3:=2*b ;
                     if L[i3,j3]=false
                     then segment(2*a,2*b,2*a,2*b-2);
               end;
 
     for b:= 1 to v do { scan vertical sur les lignes paires, N }
           for a:= 1 to h do
               begin i4:=2*a-1; j4:=2*b ;
                     if L[i4,j4]=false
                     then segment(2*a-2,2*b,2*a,2*b);
               end;
 
 
 
end;
 
 
 
 
begin  debutgraphe;
       echelle(-1,34,-1,34);           
       deplace(0,0);
       initialisation(L,h,v);
       creation_du_chemin(L);
       representation(L) ;
       fingraphe;
end.

Merci d'avance !

[Alcatîz]

Bonjour !

Il me semble que la récursivité s'appliquerait très bien à la résolution du problème : une fonction, qui reçoit en entrée de quelle direction elle vient, qui teste une des directions restantes en s'appelant elle-même. Au fur et à mesure, un arbre pourrait être construit; quand une branche n'a pas de solution, elle est "coupée".

Exemple :

0. Départ en bas à gauche.
1. Test de la case "est" : ça passe, on démarre une branche "est" et on continue.
2. Test de la case "est" : ça passe, on greffe une sous-branche "est" à la branche. L'arbre devient "est-est".
3. Test de la case "est" : ça ne passe pas.
4. Test de la case "nord" : ça passe, on greffe une sous-branche "nord". L'arbre devient "est-est-nord".
5. Test de la case "est" : ça ne passe pas.
6. Test de la case "nord" : ça ne passe pas.
7. Test de la case "ouest" : ça ne passe pas. La branche "nord" est morte et on retourne à l'arbre "est-est" du point 2.
... et ainsi de suite.

Lorsque l'arrivée est atteinte, l'arbre complet donne la solution !

[redvivi]

J'ai un peu de mal à me representer la structure de l'algorithme donnant la solution, avez vous un exemple de ce type ?

Ce que vous m'avez proposé represente la solution du probleme, comment voyez vous la creation du chemin ? Un algorithme de la meme forme ?

Merci d'avance !

[redvivi]

Je suis à 2 doigts de devenir dingue, voici un simple programme:

Code :

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

1
2
3
4
5
6
7
 
uses wincrt ;
var x:real;
 
begin
 x:=random(4)  ;
writeln(x) ;

Je ne comprend pas, cette fonction renvoie toujours 4 ! Alors que normalement elle devrait renvoyer un nombre entre 0 et 3 non ?

Merci d'avance !

[Emmanuel Delahaye]

Je suis à 2 doigts de devenir dingue, voici un simple programme:

Code :

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

1
2
3
4
5
6
7
 
uses wincrt ;
var x:real;
 
begin
 x:=random(4)  ;
writeln(x) ;

Je ne comprend pas, cette fonction renvoie toujours 4 ! Alors que normalement elle devrait renvoyer un nombre entre 0 et 3 non ?

Oui. Ceci fonctionne correctement :

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
 
program snippet;
 
 procedure main;
 var
  x:real;
  i:integer;
 begin
  randomize; { pour un demarrage de la sequence non repetitif }
 
  for i := 0 to 10 do
  begin
   x:=random(4);
   writeln(x);
  end;
 end;
 
begin
 main;
 readln;
end.

Je (re-)débute le Pascal, alors je ne maitrise pas l'affichage...

[redvivi]

Merci de m'avoir proposé une solution, mais je n'ai pas compris dans mon programme pourquoi la fonction random(3) n'assigne pas à x directement sa valeur . Aurais-je loupé quelquechose ?