unit Path_finding_fini;

interface
uses
SysUtils, windows ;

const
  taille_x = 35 ; // taille en X de la map de jeu
  taille_y = 35 ; // taille en Y de la map de jeu
  comp = 5 ; // quantité de mur : 2 = beaucoup, 9 = peu

type
  carte = Array[0..(taille_y-1)] of Array[0..(taille_x-1)] of integer ; // type map


function initialisation_map() : carte ;
procedure visible(map : carte);
function nomb_noeud(map : carte) : integer ;
function distance(x, y : integer) : integer ;
function flamme(map : carte; ix, iy, x, y : integer) : carte;




//=======================ATTENTION=========================//
//dans une matrice, les coordonnées s'écrivent : map[Y, X] //
//=========================================================//


var
  ix, iy : integer; // coordonnée d'un premier noeud(case) sur la map
  jx, jy : integer; // coordonnée d'un deuxième noeud(case) sur la map
  x, y : integer;   // coordonnée
  nomb, temp, lim, nmax, imax, dis  : integer ; // variables
  map : carte ;  // matrice représentant la carte

               
implementation
//------------------------------------------------------------------------------
{fonction d'initialisation de la map}
function initialisation_map() : carte ;
begin
randomize();

    for y := 0 to (taille_y-1) do
       begin
       for x := 0 to (taille_x-1) do
         begin
         map[y,x] := 1
         end;
       end;

  for y := 4 to 5 do
    begin
    for x := 3 to 8 do map[y,x] := 0;
    end;

  for y := 6 to 13 do
    begin
    for x := 5 to 6 do map[y,x] := 0;
    end;

  for y := 4 to 5 do
    begin
    for x := 10 to 15 do map[y,x] := 0;
    end;

  for y := 6 to 13 do
    begin
    for x := 10 to 11 do map[y,x] := 0;
    end;

  for y := 12 to 13 do
    begin
    for x := 10 to 15 do map[y,x] := 0;
    end;

  for y := 8 to 9 do
    begin
    for x := 10 to 13 do map[y,x] := 0;
    end;

  for y := 8 to 9 do
    begin
    for x := 10 to 13 do map[y,x] := 0;
    end;

  for y := 4 to 5 do
    begin
    for x := 17 to 22 do map[y,x] := 0;
    end;

  for y := 4 to 5 do
    begin
    for x := 17 to 22 do map[y,x] := 0;
    end;

  for y := 6 to 9 do
    begin
    for x := 17 to 18 do map[y,x] := 0;
    end;

  for y := 8 to 9 do
    begin
    for x := 17 to 22 do map[y,x] := 0;
    end;

  for y := 8 to 13 do
    begin
    for x := 21 to 22 do map[y,x] := 0;
    end;

  for y := 12 to 13 do
    begin
    for x := 17 to 22 do map[y,x] := 0;
    end;

  for y := 4 to 5 do
    begin
    for x := 17 to 22 do map[y,x] := 0;
    end;

  for y := 6 to 9 do
    begin
    for x := 17 to 18 do map[y,x] := 0;
    end;

  for y := 4 to 5 do
    begin
    for x := 24 to 29 do map[y,x] := 0;
    end;

  for y := 6 to 13 do
    begin
    for x := 26 to 27 do map[y,x] := 0;
    end;

  for y := 16 to 25 do
    begin
    for x := 5 to 6 do map[y,x] := 0;
    end;

  for y := 16 to 17 do
    begin
    for x := 5 to 10 do map[y,x] := 0;
    end;

  for y := 20 to 21 do
    begin
    for x := 5 to 8 do map[y,x] := 0;
    end;

  for y := 16 to 17 do
    begin
    for x := 5 to 10 do map[y,x] := 0;
    end;

  for y := 16 to 25 do
    begin
    for x := 12 to 13 do map[y,x] := 0;
    end;

  for y := 16 to 25 do
    begin
    for x := 15 to 16 do map[y,x] := 0;
    end;

  for y := 16 to 17 do
    begin
    for x := 17 to 18 do map[y,x] := 0;
    end;

  for y := 18 to 19 do
    begin
    for x := 18 to 19 do map[y,x] := 0;
    end;

  for y := 20 to 21 do
    begin
    for x := 19 to 20 do map[y,x] := 0;
    end;

  for y := 22 to 23 do
    begin
    for x := 20 to 21 do map[y,x] := 0;
    end;








  {définition du départ et de l'arrivé}
  map[0,0] := -1 ;
  map[(taille_y - 1),(taille_x - 1)] := -1 ;
  result := map ;
end;
//------------------------------------------------------------------------------
{procedure pour afficher la map}
procedure visible(map : carte);
begin
  for y := 0 to (taille_y-1) do
     begin
     for x := 0 to (taille_x-1) do
       begin
       SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                          FOREGROUND_green);
       if map[y,x] >= 1 then write(' ');    // blanc
       if map[y,x] = 0 then write('#');    // mur
       SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                          FOREGROUND_red);
       if map[y,x] = (-1) then write('a'); // chemin
       SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                          FOREGROUND_blue);
       write('|')                          // séparation entre les cases
       end;
     writeln(' ');
     end;
end;
//------------------------------------------------------------------------------
{fonction déterminant le nombre de noeud libre (sans mur) }
function nomb_noeud(map : carte) : integer ;
begin
  nomb := 0;
  for x := 0 to (taille_x-1) do
     begin
     for y := 0 to (taille_y-1) do
       begin
       if (map[y,x] = (0)) then nomb := nomb + 1;     //servira de cas d'arrêt
       end;
     end;
  result := ((taille_x*taille_y) - nomb);
end;
//------------------------------------------------------------------------------
{fonction déterminant la distance entre le noeud n_1 de coordonnée (ix,iy) et le noeud d'arrivé}
function distance(x, y : integer) : integer ;
begin
  if taille_x <= taille_y then nmax := (taille_x - 1)
                          else nmax := (taille_y - 1);
  if x <= y then imax := x
            else imax := y ;
  result := ((nmax - imax)*2);
end;

//------------------------------------------------------------------------------
{Algorithme de transition des flammes}
function flamme(map : carte; ix, iy, x, y : integer) : carte;
begin
  lim := 1 ;
  dis := distance(0, 0);
  map[0,0] := 2;
  while lim <= (dis) do
    begin
    for temp := 0 to lim do
      begin
      if (lim - temp) < taille_y then
        begin
        if temp < taille_x then
          begin
          if (map[(lim - temp),temp] <> 0) then
            begin
            if (map[(lim - temp),(temp - 1)] = (1 + lim)) or (map[(lim - temp - 1),temp] = (1 + lim)) then
              begin
              map[(lim - temp),temp] := (2 + lim);
              end;
            end;
          end;
        end;
      end;
    lim := lim + 1;
    end;

  map[iy, ix] := 2 ;
  dis := 0 ;
  nmax := map[x,y];
  map[y,x] := (-1);

  while (map[0,0] = 2) and (dis <= nmax) do      //rentre la valeur -1 dans le chemin le plus court
   begin
    dis := dis + 1 ;
    temp := nmax - dis; // valeur suivant à trouver
    lim := 0 ;

    if (map[y-1,x] = temp) and (lim = 0) and (dis mod 2 = 0) then
      begin
        map[y,x] := (-1) ;
        lim :=  1 ;
      end;

    if (map[y+1,x] = temp) and (lim = 0) and (dis mod 2 = 0) then
      begin
        map[y,x] := (-1) ;
        lim := 2 ;
      end;

    if (map[y,x-1] = temp) and (lim = 0) and (dis mod 2 = 0) then
      begin
        map[y,x] := (-1) ;
        lim := 3 ;
      end;

    if (map[y,x+1] = temp) and (lim = 0) then
      begin
        map[x,y] := (-1) ;
        lim := 4 ;
      end;

    if (map[y,x-1] = temp) and (lim = 0) and (dis mod 2 = 1) then
      begin
        map[y,x] := (-1) ;
        lim := 3 ;
      end;

    if (map[y+1,x] = temp) and (lim = 0) and (dis mod 2 = 1) then
      begin
        map[y,x] := (-1) ;
        lim := 2 ;
      end;

    if (map[y-1,x] = temp) and (lim = 0) and (dis mod 2 = 1) then
      begin
        map[y,x] := (-1) ;
        lim :=  1 ;
      end;

    case lim of
    1 : y := y-1;
    2 : y := y+1;
    3 : x := x-1;
    4 : x := x+1;
    end;
   end;

  if map[0,0] = 2 then
    begin
      map[0,0] := (-1) ;
      SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                          FOREGROUND_red);
      writeln('ERREUR, il n"y a pas de chemin entre le point initial et le point d"arrive');
    end ;

 result := map
end;
//------------------------------------------------------------------------------
end.
 