Le labyrinthe

Soit un labyrinthe quelconque qui a une entrée et une sortie, ainsi qu'au moins un chemin menant de l'entrée vers la sortie. On veut faire le programme qui trouve l'un de ces chemins. Le principe est simple: nous allons explorer une direction et si elle ne donne aucun résultat, on reprendra une autre direction dans le labyrinthe (une autre branche de l'arbre récursif).

Nous allons étudier quelques détails d'un parcours dans un labyrinthe:

- dans un labyrinthe nous avons quatre directions: nord, est, sud, ouest

- on avance dans le labyrinthe, il faut laisser une trace du passage dans le labyrinthe, car si on a un mur isolé dans le labyrinthe, il ne faut pas tourner à l'infini autour de ce mur

- si à un certain moment on est bloqué, alors on efface le chemin parcouru jusqu'au dernier "carrefour" rencontré dans le labyrinthe et on essaie un autre chemin partant de ce carrefour

- si on est à l'arrivée alors on initialise une variable "trouvé" à true, pour indiquer qu'il ne faut plus effacer la trace laissée derrière, car il faut quand même visualiser le chemin trouvé.

Voyons maintenant l'algorithme :

- l'algorithme sera une procédure qui admet deux paramètres: "ligne" et "colonne"; ils représentent la position en cours

- le point d'appui est atteint quand "ligne" et "colonne" sont égales aux coordonnées du point d'arrivée (la sortie du labyrinthe)

- si on n'est pas au point d'arrivée alors:

1) - on laisse une trace dans le labyrinthe à la position en cours

2) - on affiche le labyrinthe avec la trace

3) - on essaie les quatre directions

- si on peut aller dans une de ces quatre directions (il n'y a pas de mur devant) alors on recommence l'algorithme avec la nouvelle position, celle qui va dans la direction choisie

- si on a essayé toutes les directions alors si "trouvé" est "false" (on n'a pas trouvé la sortie), on efface le chemin.

Remarque: cet algorithme ne trouve pas le meilleur chemin; il trouve simplement un chemin; de plus la longueur du chemin et le temps mis pour le trouver dépend du labyrinthe, de l'emplacement de l'entrée et de la sortie, et du sens qu'on a choisi pour l'exploration des directions d'un carrefour; ici on explore les directions dans l'ordre suivant: nord, ouest, sud, est.

Voici le programme correspondant :

type lab = array[1..15] of string[40];
 
const l: lab = ('$$$$$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$',
 '$ $$ $ $$$ $$ $$ $$$$ $ $ $$$',
 '$ $ $$$$$$$$$ $$$$$$ $ $ $',
 '$ $$ $$$$ $$ $$$$$ $$$ $$$$$',
 '$ $ $$ $ $ $$$ $$$$$ $ $$$ $',
 '$ $$ $ $$$ $$$$$$$$$ $ $$ $$$$ $$$ $ $',
 '$ $ $$ $ $ $$$$$ $ $ $',
 '$$$$ $ $$ $$$$ $$$$ $$ $$$ $$$$$$ $$$',
 '$$ $ $ $$ $$ $$$$ $$ $$',
 '$$ $$$$$$$$ $$$$$ $$$$ $ $$ $$$$$ $$$$$$',
 '$$ $  $$ $',
 '$$ $$$ $$ $$$$$ $$$ $$$ $$$$$$ $$ $ $$ $',
 '$$ $$$ $$ $$ $$$ $$ $$ $$$ $$$$$$$$$',
 '$$ $ $$$$ $$ $$',
 '$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ $$$$$$');
 
 dx: array[0..3] of integer = (0, -1, 0, 1);
 dy: array[0..3] of integer = (-1, 0, 1, 0);
 
var t: lab;
 trouve: boolean;
 
procedure tform1.aff_labyrinthe;
var ligne, colonne: integer;
begin
 image1.picture.bitmap.canvas.font.size := 8;
 for ligne := 1 to 15 do
 for colonne := 1 to 40 do
  begin
 case t[ligne][colonne] of
 '$': with image1.picture.bitmap.canvas do
 begin
 brush.Style := bsSolid;
 brush.color := clBlack;
 pen.color := clBlack;
 rectangle((colonne - 1) * 15, (ligne - 1) * 15, colonne * 15, ligne * 15);
 end;
 '*': with image1.picture.bitmap.canvas do
 begin
 brush.Style := bsClear;
 font.color := clBlue;
 textOut((colonne - 1) * 15 + 5, (ligne - 1) * 15 + 2, '*');
 end;
 ' ': with image1.picture.bitmap.canvas do
 begin
 brush.Style := bsSolid;
 brush.color := clWhite;
 pen.color := clWhite;
 rectangle((colonne - 1) * 15, (ligne - 1) * 15, colonne * 15, ligne * 15);
 end;
 end;
 end;
end;
 
procedure tform1.avancer(ligne, colonne: integer);
var i: integer;
begin
 if not trouve then
 if (ligne = 1) and (colonne = 7) then
 begin
 trouve := true;
 edit1.text := 'trouvé';
 end
 else
 begin
 t[ligne][colonne] := '*';
 aff_labyrinthe; image1.refresh;
 for i := 0 to 3 do
 if t[ligne + dy[i]][colonne + dx[i]] = ' ' then
 avancer(ligne + dy[i], colonne + dx[i]);
  if not trouve then
 begin
 t[ligne][colonne] := ' ';
 aff_labyrinthe; image1.refresh;
 end;
 end;
end;
 
procedure TForm1.FormCreate(Sender: TObject);
var tb: tbitmap;
begin
 move(l, t, sizeof(l));
 trouve := false;
 tb := tbitmap.create;
 tb.width := 15 * 40;
 tb.height := 15 * 15; //--- nb d'elems de t; high(t)
 image1.picture.bitmap := tb;
 image1.autosize := true;
 aff_labyrinthe;
end;
 
 
 
procedure TForm1.Button1Click(Sender: TObject);
begin
 edit1.text := 'recherche en cours...'; edit1.refresh;
 avancer(15, 34);
 aff_labyrinthe;
end;

Télécharger le code source Delphi