Creer un labyrinthe avec Turbo Pascal ( I need some help!!)

[invitea3008494]

Voila le sujet

Je doit représenter un labyrinthe de cette façon :
Les cellules sont repérées par des couples d'entiers (i,j).
Pour chaque cellule (i,j), 4 booléens appelés N,S,E,W indiquent si on peut ou non gagner la cellule au nord (i,j+1), au sud (i,j-1) , à l'est (i+1,j) ou à l'ouest (i,j-1).

• Créer un labyrinthe en choisissant chacun des booléens N et E de façon aléatoire (les booléens S et W seront calculés).
• Faire une représentation graphique.
• Trouver un algorithme permettant de traverser le labyrinthe du coin SW au coin NE si c'est possible.

J'ai réussi à affiché un labyrinthe où le nord et l'est de chaque case est choisi au hasard.
La chose a faire maintenant c'est de créé un algorithme qui permette de tracer un chemin qui traverse le labyrinthe si il y a une solution...

Voilà ce que j'ai commencé a faire( j'utilise la bibliothèque Wingraph):


program labyrinthe;
uses wincrt,wingraph;

type abscisse = array[0..50] of integer;
ordonnee = array[0..50] of integer;
deplacement = array[1..50,1..50] of boolean;

procedure contour_laby (Long,Larg:integer; var x:abscisse; var yrdonnee);
var i,j:integer;
begin echelle_ortho(-1,Long+1,-1,Larg+1);
for i:=0 to Long do x[i]:=i;
for j:=0 to Larg do y[j]:=j;
deplace(x[0],y[0]);
trace(x[0],y[Larg]);trace(x[Long-1],y[Larg]);
deplace(x[Long],y[Larg]);
trace(x[Long],y[0]);trace(x[Long-Long+1],y[0]);
end;

procedure autorisation_deplacement (Long,Larg:integer; var N,S,E,W:deplacement);
var i,j,D,F:integer;
begin
Randomize;
for i:=1 to Long do begin
for j:=1 to Larg do begin D:=random(100);
if D<50 then N[j,i]:=FALSE else N[i,j]:=TRUE;
F:=random(200);
if F<100 then E[i,j]:=TRUE else E[i,j]:=FALSE;
end;
end;

for j:=1 to Larg do begin
E[Long,j]:=False;
W[1,j]:=False;
end;

for i:=1 to Long do begin
S[i,1]:=False;
N[i,Larg]:=False;
end;

S[1,1]:=True;
N[Long,Larg]:=True;


if N[1,1]=False then E[1,1]:=True;
if N[Long,Larg-1]=False then E[Long-1,Larg]:=True;

for i:=1 to Long-1 do begin
for j:=1 to Larg do if E[i,j]=True then W[i+1,j]:=True
else W[i+1,j]:=False;
end;

for i:=1 to Long do begin
for j:=1 to Larg-1 do if N[i,j]=True then S[i,j+1]:=True
else S[i,j+1]:=False;
end;
end;

procedure trace_laby (Long,Larg:integer; N,E:deplacement; x:abscisse; yrdonnee);
var i,j:integer;
begin
for i:=1 to Long do begin
for j:=1 to Larg do begin
if N[i,j]=False then
begin
deplace(x[i-1],y[j]);
trace(x[i],y[j]);
end;
if E[i,j]=False then
begin
deplace(x[i],y[j-1]);
trace(x[i],y[j]);
end;
end;
end;
end;

var Long,Larg,x1,y1,k,l,i:integer;
x:abscisse;
yrdonnee;
N,S,E,W:deplacement;
gauche,droite,avant,arriere:bo olean;

begin
debutgraphe;
repeat
write('Entrez la LONGUEUR de votre labyrinthe (supérieure à 0 et inférieure à 50) :');
readln(Long);
until (Long>0) and (Long<=50);
repeat
write('Entrez la LARGEUR de votre labyrinthe (supérieure à 0 et inférieure à 50) :');
readln(Larg);
until (Larg>0) and (Larg<=50);
contour_laby (Long,Larg,x,y);
autorisation_deplacement (Long,Larg,N,S,E,W);
trace_laby (Long,Larg,N,E,x,y);
fingraphe;
end.
-----

[JPL]

Rappel de la charte du forum :

La courtoisie est de rigueur sur ce forum : pour une demande de renseignements bonjour et merci devraient être des automatismes.

D'autre part les codes doivent être insérés dans une balise Code pour garder les indentations nécessaires à la lisibilité.

[invitec7217a00]

Bonjour,
les tableaux N,S et E,W sont redondants, tu pourrais n'avoir qu'un tableau "arêtes verticales" et un tableau "arêtes horizontales" (ce qui te permet d'avoir deux fois moins de tableaux, et également de réduire leur longueur de 1 puisque chacun de tes tableaux a une cellule inutilisée).
Dans ta fonction qui décide aléatoirement des adjacences, au lieu de :

for i:=1 to Long do begin
for j:=1 to Larg do begin D:=random(100);
if D<50 then N[j,i]:=FALSE else N[i,j]:=TRUE;
F:=random(200);
if F<100 then E[i,j]:=TRUE else E[i,j]:=FALSE;
end;

tu peux t'arrêter à Long-1 et Larg-1, sinon tu fais des calculs inutiles.

Pour ce qui est d'aller d'un point à un autre, cela se fait par un parcours d'arbre (en largeur pour avoir un plus court chemin).

[invitea3008494]

Bonjour :
Ta remarque et pertinente mais par exemple le nord de la case suivante N[long,2] a besoin d'être déterminé donc on ne peut pas restreindre i de 1 a Long-1?
Merci

et si quelqu'un a une idée pour la suite du problème n'hésitez pas!! Merci

[A voir en vidéo sur Futura]

[invitec7217a00]

Ce que je veux dire c'est que tu peux utiliser juste deux matrices du genre :
vertical : array[1..Long,1..Larg-1];
horizontal : array[1..Long-1,1..Larg];

Au fait, je viens de voir que tu as une erreur dans la partie que je t'ai recopié, tu as mis N[j,i] au lieu de N[i,j].

Une idée pour quelle suite? Si c'est chercher le chemin entre tes deux points, je t'ai dit que tu peux le faire avec un parcours d'arbre.

[invite0d8da966]

Bonjour,

Je n'ai pas regarder l'ensemble de tes fonctions , mais moi j'aurais défini ton labyrinthe avec un table à 2 dimensions d'un type record :

Type TOuvertures = record
  N,S,E,W : Boolean;
end;

Type TLabyrinthe = array [1..50, 1..50] of TOuvertures;

Ca me parait plus simple ... On peut rajouter aussi des infos dans TOuvertures si besoin.

[invitea3008494]

Bonjours
Voila mon programme est presque fini. mon dernier souci est le suivant:

j'ai réussi a tracer un chemin qui part du début du labyrinthe et qui arrive a la fin, par contre il reste les traits de chemin qui se dirige vers des impasse puis qui font demi tour et j'aimerai les supprimé pour obtenir une ligne continue qui va du départ a l'arrivée...*

quelqu'un a une idée??

Voila le programme

program labyrinthe;
uses wincrt,wingraph,winprocs;

type abscisse = array[0..50] of integer;
ordonnee = array[0..50] of integer;
deplacement = array[1..50,1..50] of boolean;

procedure contour_laby (Long,Larg:integer; var x:abscisse; var y:ordonnee);
var i,j:integer;
begin couleur(0);
echelle_ortho(-1,Long+1,-1,Larg+1);
for i:=0 to Long do x[i]:=i;
for j:=0 to Larg do y[j]:=j;
deplace(x[0],y[0]);
trace(x[0],y[Larg]);trace(x[Long-1],y[Larg]);
deplace(x[Long],y[Larg]);
trace(x[Long],y[0]);trace(x[Long-Long+1],y[0]);
end;

procedure autorisation_deplacement (Long,Larg:integer; var N,S,E,W:deplacement);
var i,j,D,F:integer;
begin
Randomize;
for i:=1 to Long do begin
for j:=1 to Larg do begin D:=random(100);
if D<50 then N[i,j]:=FALSE else N[i,j]:=TRUE;
F:=random(200);
if F<100 then E[i,j]:=TRUE else E[i,j]:=FALSE;
end;
end;

for j:=1 to Larg do begin
E[Long,j]:=False;
W[1,j]:=False;
end;

for i:=1 to Long do begin
S[i,1]:=False;
N[i,Larg]:=False;
end;

S[1,1]:=True;
N[Long,Larg]:=True;
if N[1,1]=False then E[1,1]:=True;
if N[Long,Larg-1]=False then E[Long-1,Larg]:=True;

for i:=1 to Long-1 do begin
for j:=1 to Larg do if E[i,j]=True then W[i+1,j]:=True
else W[i+1,j]:=False;
end;

for i:=1 to Long do begin
for j:=1 to Larg-1 do if N[i,j]=True then S[i,j+1]:=True
else S[i,j+1]:=False;
end;
end;

procedure trace_laby (Long,Larg:integer; N,E:deplacement; x:abscisse; y:ordonnee);
var i,j:integer;
begin
couleur(0);
for i:=1 to Long do begin
for j:=1 to Larg do begin
if N[i,j]=False then
begin
deplace(x[i-1],y[j]);
trace(x[i],y[j]);
end;
if E[i,j]=False then
begin
deplace(x[i],y[j-1]);
trace(x[i],y[j]);
end;
end;
end;
end;

La suite...

[invitea3008494]

function on_vient_de_l_est(x1,y1,x2,y2, k,l:integer; var N,S,E,W:deplacement; var gauche,droite,avance:boolean): boolean;
begin
if (x2=x1-1) and (y2=y1)
then begin
on_vient_de_l_est:=True;
gauche:=S[k,l];
droite:=N[k,l];
avance:=W[k,l];
end
else on_vient_de_l_est:=False;
end;

function on_vient_du_sud(x1,y1,x2,y2,k, l:integer; var N,S,E,W:deplacement; var gauche,droite,avance:boolean): boolean;
begin
if (y2=y1+1) and (x2=x1)
then begin
on_vient_du_sud:=True;
gauche:=W[k,l];
droite:=E[k,l];
avance:=N[k,l];
end
else on_vient_du_sud:=False;
end;

function on_vient_du_nord(x1,y1,x2,y2,k ,l:integer; var N,S,E,W:deplacement; var gauche,droite,avance:boolean): boolean;
begin
if (x2=x1) and (y2=y1-1)
then begin
on_vient_du_nord:=True;
gauche:=E[k,l];
droite:=W[k,l];
avance:=S[k,l];
end
else on_vient_du_nord:=False;
end;

function on_vient_de_l_ouest(x1,y1,x2,y 2,k,l:integer;var N,S,E,W:deplacement;var gauche,droite,avance:boolean): boolean;
begin
if (x2=x1+1) and (y2=y1)
then begin
on_vient_de_l_ouest:=True;
gauche:=N[k,l];
droite:=S[k,l];
avance:=E[k,l];
end
else on_vient_de_l_ouest:=False;
end;

var Long,Larg,x1,y1,x2,y2,k,l,i:in teger;
xfin1,yfin1,xfin2,yfin2,x3,y3: real;
x:abscisse;
y:ordonnee;
N,S,E,W:deplacement;
gauche,droite,avance:boolean;

begin
debutgraphe;
repeat
write('Entrez la LONGUEUR de votre labyrinthe (supérieure à 0 et inférieure à 50) :');
readln(Long);
until (Long>0) and (Long<=50);
repeat
write('Entrez la LARGEUR de votre labyrinthe (supérieure à 0 et inférieure à 50) :');
readln(Larg);
until (Larg>0) and (Larg<=50);

repeat begin
efface_fenetre;
contour_laby (Long,Larg,x,y);
autorisation_deplacement (Long,Larg,N,S,E,W);
trace_laby (Long,Larg,N,E,x,y);
x1:=x[0];
y1:=y[0];
xfin1:=long-1/2;
yfin1:=larg+1/2;
xfin2:=1/2;
yfin2:=-1/2;
k:=1;
l:=1;
couleur(5);
deplace(x1+1/2,y1);
trace(x1+1/2,y1+1/2);
if N[k,l]=True then begin trace(x1+1/2,y1+1/2+1);
x2:=x1;
y2:=y1+1;
l:=l+1;
end
else if E[k,l]=True then begin trace(x1+1/2+1,y1+1/2);
x2:=x1+1;
y2:=y1;
k:=k+1;
end;
repeat if on_vient_de_l_est(x1,y1,x2,y2, k,l,N,S,E,W,gauche,droite,avan ce)=True
then begin
x1:=x2;
y1:=y2;
if gauche=True then begin trace(x1+1/2,y1+1/2-1);
x2:=x1;
y2:=y1-1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l-1;
end
else if avance=True then begin trace(x1+1/2-1,y1+1/2);
x2:=x1-1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k-1;
end
else if droite=True then begin trace(x1+1/2,y1+1/2+1);
x2:=x1;
y2:=y1+1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l+1;
end
else if (gauche=False) and (avance=False) and (droite=false)
then begin trace(x1+1/2+1,y1+1/2);
x2:=x1+1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k+1;
end;
end
else if on_vient_du_sud(x1,y1,x2,y2,k, l,N,S,E,W,gauche,droite,avance )=True
then begin
x1:=x2;
y1:=y2;
if gauche=True then begin trace(x1+1/2-1,y1+1/2);
x2:=x1-1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k-1;
end
else if avance=true then begin trace(x1+1/2,y1+1/2+1);
x2:=x1;
y2:=y1+1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l+1;
end
else if droite=True then begin trace(x1+1/2+1,y1+1/2);
x2:=x1+1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k+1;
end
else if (gauche=False) and (avance=False) and (droite=False)
then begin trace(x1+1/2,y1+1/2-1);
x2:=x1;
y2:=y1-1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l-1;
end;
end
else if on_vient_de_l_ouest(x1,y1,x2,y 2,k,l,N,S,E,W,gauche,droite,av ance)=true
then begin
x1:=x2;
y1:=y2;
if gauche=True then begin trace(x1+1/2,y1+1/2+1);
x2:=x1;
y2:=y1+1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l+1;
end
else if avance=True then begin trace(x1+1/2+1,y1+1/2);
x2:=x1+1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k+1;
end
else if droite=true then begin trace(x1+1/2,y1+1/2-1);
x2:=x1;
y2:=y1-1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l-1;
end
else if (gauche=False) and (avance=False) and (droite=False)
then begin trace(x1+1/2-1,y1+1/2);
x2:=x1-1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k-1;
end;
end
else if on_vient_du_nord(x1,y1,x2,y2,k ,l,N,S,E,W,gauche,droite,avanc e)=true
then begin
x1:=x2;
y1:=y2;
if gauche=true then begin trace(x1+1/2+1,y1+1/2);
x2:=x1+1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k+1;
end
else if avance=true then begin trace(x1+1/2,y1+1/2-1);
x2:=x1;
y2:=y1-1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l-1;
end
else if droite=true then begin trace(x1+1/2-1,y1+1/2);
x2:=x1-1;
y2:=y1;
x3:=x2+1/2;
y3:=y2+1/2;
k:=k-1;
end
else if (gauche=False) and (avance=False) and (droite=False)
then begin trace(x1+1/2,y1+1/2+1);
x2:=x1;
y2:=y1+1;
x3:=x2+1/2;
y3:=y2+1/2;
l:=l+1;
end
end;
until (x3=xfin1) and (y3=yfin1) or (x3=xfin2) and (y3=yfin2);
end;
until (x3=xfin1) and (y3=yfin1);
fingraphe;
end.

Merci a vous!

[JPL]

As-tu vraiment lu mon message n° 2 jusqu'au bout ?

[invite0d8da966]

Salut,

En effet, Jérôme, ton code serait beaucoup plus lisible si tu respectais une certaine indentation ( des espaces ou tes Tabulations pour décaller des blocs, des sous blocs , etc...) .

Ensuite, si je puis me permettre, ton code est trop linéaire... Tu utilises un langage évolué qu'est le Pascal et tu ne t'en sers pas du tout.
Alors si le seul but de ton projet est de faire le labyrinthe ça peut aller, mais si ton prof jette un oeil au code , il risque de s'arracher les cheveux.

Essaye un maximum de factoriser ton code, d'utiliser la récursivité (si mathématiquement tes algos ressemblent à des suites ), d'utiliser une certaine règle de nommage... Et je ne parle même pas d'utiliser la puissance de l'Objet qui facilite grandement les choses quand on sait l'utiliser.

La clé dans la programmation, c'est la méthode , surtout si ça t'intéresse vraiment ! C'est important !

Désolé de ne pas t'aider plus car je pense que tu bosses intensément sur ton sujet !

Bon Courage