unit aufgabe4_u;
(*) Geschrieben von Benito van der Zander

  Namennotation:
    YYYY_xx
Name  /\  Typ
  Trennzeichen

  Typ:
    x                                          x
  Allgemeine Information:             Genauere Information:
  p:Pointer auf:                       Beliebiegertyo


  b: Booleanwert                       x: Boolean (kann weggelassen werden)
                                       b: ByteBool
                                       l: LongBool
                                       w: WordBool;

  c: Cardinalwert (ohne Vorzeichen)    x: Cardinal (kann weggelassen werden)
                                       b: Byte
                                       w: Word
                                       l: LongWord
  i: Integerwert (mit Vorzeichen)
                                       x: Integer  (kann weggelassen werden)
                                       s: ShortInt
                                       k: SmallInt
                                       l: LongInt
                                       i: Int64

  t: Text                              c: Char
                                       s: String

  k: Komponenten                       p: TPaintBox

  v:VCL-Objekte                        c: TCanvas
                                       b: TBitmap
-----------------------------------------------------------------
  x:Benutzerdefiniert                  nb: TNeueBewertungen
                                       nr: TNeueRichtungslinien
                                       k: TKanal
(*)

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  ExtCtrls, Menus,math;
type Tfeld=record
  wasser_b:boolean;
end;
type TAktBewertung=record
  x_i,y_i:integer;
  bx_i,by_i:integer;
  wert_i:integer;
end;
type TNeueRichtungslinie=record
  sx_i,sy_i:integer;
  zx_i,zy_i:integer;
  rx_i,ry_i:integer;
  wert_i:integer;
end;
type TKanal=array of array of TFeld;
type TNeueBewertungen=array of TAktBewertung;
type TNeueRichtungslinien=array of TNeueRichtungslinie;
type
  TForm1 = class(TForm)
    paintbox1: TPaintBox;
    MainMenu1: TMainMenu;
    Programm1: TMenuItem;
    berechnen1: TMenuItem;
    Hhe1: TMenuItem;
    Breite1: TMenuItem;
    procedure FormCreate(Sender: TObject);
    procedure paintbox1Paint(Sender: TObject);
    procedure paintbox1MouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure berechnen1Click(Sender: TObject);
    procedure Hhe1Click(Sender: TObject);
    procedure Breite1Click(Sender: TObject);
  private
    { Private-Deklarationen}
  public
    { Public-Deklarationen}
    procedure WM_ERASEBKGND(var mes:Tmessage);message WM_ERASEBKGND;
  end;

var
  Form1: TForm1;
  Kanal_xk:TKanal;
  startx_i,starty_i,zielx_i,ziely_i:integer;
  schiffx_i,schiffy_i:integer;
  bschiffx_i,bschiffy_i:integer;
implementation

{$R *.DFM}

//--------------Fügt eine Bewertung in ein Array of Bewertung ein---------------
procedure AddBewertung(var bewertungen_xnb:TNeueBewertungen; x_i,y_i,wert_i,bx_i,by_i,ax_i,ay_i:integer);
begin
inc(wert_i,abs(bx_i-ax_i));
inc(wert_i,abs(by_i-ay_i));
{if high(bewertungen_xnb)>0 then
  if bewertungen_xnb[high(bewertungen_xnb)].wert_i=wert_i then
    exit;}
setlength(bewertungen_xnb,length(bewertungen_xnb)+1);//Vergrößert dass Array
bewertungen_xnb[high(bewertungen_xnb)].x_i:=x_i;   //Kopiert die Koordinaten
bewertungen_xnb[high(bewertungen_xnb)].y_i:=y_i;   //"        "      "
bewertungen_xnb[high(bewertungen_xnb)].bx_i:=bx_i; //"        "      "
bewertungen_xnb[high(bewertungen_xnb)].by_i:=by_i; //"        "      "
{if bx_i<>ax_i then inc(wert_i)
else if by_i<>ay_i then inc(wert_i);}
//wert_i:=wert_i+max(abs(bx_i-ax_i)*2,abs(by_i-ay_i)*2); //Berechnet den Wert, wobei gleiche Bewegungskoordinaten eien niedrigeren (=besseren) Wert erzeugen
bewertungen_xnb[high(bewertungen_xnb)].wert_i:=wert_i ; //Kopiert den Wert
end;

//--------------Fügt eine Richtungslinie in ein Array of Richtungslinie ein---------------
procedure AddRichtungsLinie(var bewertungen_xnr:TNeueRichtungslinien; sx_i,sy_i,zx_i,zy_i,rx_i,ry_i,wert_i:integer);
var neueBewertung_i:integer;
begin
{form1.paintbox1.Canvas.Brush.Color:=clBlue;
form1.paintbox1.Canvas.TextOut(zx_i*25,form1.paintbox1.height-zy_i*25-25,IntToStr(wert_i));//}
neueBewertung_i:=length(bewertungen_xnr); //Berechnet die Größe des Arrays
if neueBewertung_i<> 0 then
  if bewertungen_xnr[high(bewertungen_xnr)].wert_i<wert_i then //Ist ein im Array enthaltender Wert
   exit; //kleiner als der aktuelle, wird abgebrochen

setlength(bewertungen_xnr,neueBewertung_i+1); //vergrößert das Array
bewertungen_xnr[neueBewertung_i].sx_i:=sx_i; //Kopiert die Koordinaten
bewertungen_xnr[neueBewertung_i].sy_i:=sy_i; // "       "      "
bewertungen_xnr[neueBewertung_i].zx_i:=zx_i; // "       "      "
bewertungen_xnr[neueBewertung_i].zy_i:=zy_i; // "       "      "
bewertungen_xnr[neueBewertung_i].rx_i:=rx_i; // "       "      "
bewertungen_xnr[neueBewertung_i].ry_i:=ry_i; // "       "      "
bewertungen_xnr[neueBewertung_i].wert_i:=wert_i ;//Kopiert den Wert
//sleep(500);
end;

//----------------------------Berechnet den Weg---------------------------------
procedure TForm1.berechnen1Click(Sender: TObject);
var i_i,i2_i,posx_i,posy_i,rx_i,ry_i,bx_i,by_i,vx_i,vy_i:integer;
    bewertungen_xaai:array of array of integer;
    neueBewertungen1_xnb,neueBewertungen2_xnb:TNeueBewertungen;
    richtungen_xnr:TNeueRichtungslinien;
    reststrecke_i,bremszeit_i,schritte_i:integer;
begin
setlength(bewertungen_xaai,length(kanal_xk),length(kanal_xk[0])); //Macht bewertungen und kanal gleich groß
for i_i:=0 to high(bewertungen_xaai) do //Durchläuft das bewertungsarray
  for i2_i:=0 to high(bewertungen_xaai[i_i]) do
    bewertungen_xaai[i_i,i2_i]:=1000000; //und setzt alles auf 1000000

i_i:=0;
setlength(neueBewertungen1_xnb,1); //Iniitzialiesiert das neueBewertungen1 array
neueBewertungen1_xnb[0].x_i:=zielx_i; //Position: Zielfeld
neueBewertungen1_xnb[0].y_i:=ziely_i;
neueBewertungen1_xnb[0].bx_i:=0;
neueBewertungen1_xnb[0].by_i:=0;
neueBewertungen1_xnb[0].wert_i:=0;

setlength(neueBewertungen2_xnb,0);//Leert das neueBewertungen2 array
while i_i<1000 do begin
  for i2_i:=0 to high(neueBewertungen1_xnb) do begin //Durchläuft das neueBewertungen1 array
    if bewertungen_xaai[neueBewertungen1_xnb[i2_i].x_i,neueBewertungen1_xnb[i2_i].y_i]<=neueBewertungen1_xnb[i2_i].wert_i then continue;
    bewertungen_xaai[neueBewertungen1_xnb[i2_i].x_i,neueBewertungen1_xnb[i2_i].y_i]:=neueBewertungen1_xnb[i2_i].wert_i; //Setzt den Wert ins Bewertungenarray
    if (neueBewertungen1_xnb[i2_i].x_i=startx_i)and(neueBewertungen1_xnb[i2_i].y_i=starty_i) then //Wenn das Startfeld markiert ist
      i_i:=990;//goto SchleifenEnde; //abbrechen

    for vx_i:=max(0,neueBewertungen1_xnb[i2_i].x_i-1) to min(high(kanal_xk),neueBewertungen1_xnb[i2_i].x_i+1) do
      for vy_i:=max(0,neueBewertungen1_xnb[i2_i].y_i-1) to min(high(kanal_xk[0]),neueBewertungen1_xnb[i2_i].y_i+1) do begin
        if ((vx_i=neueBewertungen1_xnb[i2_i].x_i)and(vy_i= neueBewertungen1_xnb[i2_i].y_i))or(not Kanal_xk[vx_i,vy_i].wasser_b) then
          continue;
        AddBewertung(neueBewertungen2_xnb,vx_i,vy_i,neueBewertungen1_xnb[i2_i].wert_i+1,neueBewertungen1_xnb[i2_i].x_i-vx_i,neueBewertungen1_xnb[i2_i].y_i-vy_i,neueBewertungen1_xnb[i2_i].bx_i,neueBewertungen1_xnb[i2_i].by_i);
      end;
  end;
  //Vertauscht die Bewertungsarrays                       
  neueBewertungen1_xnb:=neueBewertungen2_xnb;
  setlength(neueBewertungen2_xnb,0); //und löscht dass zweite
  inc(i_i);
end;

posx_i:=startx_i; //Setzt die aktuelle Position auf das Startfeld
posy_i:=starty_i;
schritte_i:=0; //Setzt die benötigten Schritte auf 0
while (posx_i<>zielx_i)or(posy_i<>ziely_i) do begin
  setlength(richtungen_xnr,0); //Setzt die Richtungen auf 0
  //Links testen
  for i_i:=posx_i-1 downto 0 do //Durch läuft die X-Achse bis zukm linken Rand
    if (bewertungen_xaai[i_i,posy_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,i_i,posy_i,-1,0,bewertungen_xaai[i_i,posy_i]) //Wird es in das Richtungslinie geschrieben
     else //ansonsten
      break; //wird abgebrochen

  //Rechts testen
  for i_i:=posx_i+1 to high(kanal_xk) do //Durch läuft die X-Achse bis zukm rechten Rand
    if (bewertungen_xaai[i_i,posy_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,i_i,posy_i,+1,0,bewertungen_xaai[i_i,posy_i]) //Wird es in das Richtungslinie geschrieben
     else //ansonsten
      break; //wird abgebrochen

  //Oben testen
  for i_i:=posy_i-1 downto 0 do //Durch läuft die Y-Achse bis zum oberen Rand
    if (bewertungen_xaai[posx_i,i_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,posx_i,i_i,0,-1, bewertungen_xaai[posx_i,i_i])//Wird es in das Richtungslinie geschrieben
    else //ansonsten
      break; //wird abgebrochen

  //unten testen
  for i_i:=posy_i+1 to high(kanal_xk[0]) do //Durch läuft die Y-Achse bis zum unteren Rand
    if (bewertungen_xaai[posx_i,i_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,posx_i,i_i,0,+1, bewertungen_xaai[posx_i,i_i])//Wird es in das Richtungslinie geschrieben
    else //ansonsten
      break; //wird abgebrochen

  //testet nach oben, links bis zum Rand
  for i_i:=1 to min(high(kanal_xk),high(kanal_xk[0])) do begin
    if (posx_i-i_i<0)or(posy_i-i_i<0) then break; //Wenn die Zahl am Rand ist, wird abgebrochen
    if (bewertungen_xaai[posx_i-i_i,posy_i-i_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,posx_i-i_i,posy_i-i_i,-1,-1, bewertungen_xaai[posx_i-i_i,posy_i-i_i])//Wird es in das Richtungslinie geschrieben
     else //ansonsten
      break; //wird abgebrochen
  end;

  //testet nach oben, links bis zum Rand
  for i_i:=1 to min(high(kanal_xk),high(kanal_xk[0])) do begin
    if (posx_i+i_i>high(kanal_xk))or(posy_i-i_i<0) then break; //Wenn die Zahl am Rand ist, wird abgebrochen
    if (bewertungen_xaai[posx_i+i_i,posy_i-i_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,posx_i+i_i,posy_i-i_i,+1,-1, bewertungen_xaai[posx_i+i_i,posy_i-i_i])//Wird es in das Richtungslinie geschrieben
     else //ansonsten
      break; //wird abgebrochen
  end;

  //testet nach oben, links bis zum Rand
  for i_i:=1 to min(high(kanal_xk),high(kanal_xk[0])) do begin
    if (posx_i-i_i<0)or(posy_i+i_i>high(kanal_xk[0])) then break; //Wenn die Zahl am Rand ist, wird abgebrochen
    if (bewertungen_xaai[posx_i-i_i,posy_i+i_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,posx_i-i_i,posy_i+i_i,-1,+1, bewertungen_xaai[posx_i-i_i,posy_i+i_i]) //Wird es in das Richtungslinie geschrieben
     else //ansonsten
      break; //wird abgebrochen
  end;

  //testet nach oben, links bis zum Rand
  for i_i:=1 to min(high(kanal_xk),high(kanal_xk[0])) do begin
    if (posx_i+i_i>high(kanal_xk))or(posy_i+i_i>high(kanal_xk[0])) then break; //Wenn die Zahl am Rand ist, wird abgebrochen
    if (bewertungen_xaai[posx_i+i_i,posy_i+i_i]<1000) then //Ist das Feld aus Wasser
      AddRichtungsLinie(richtungen_xnr,posx_i,posy_i,posx_i+i_i,posy_i+i_i,+1,+1, bewertungen_xaai [posx_i+i_i,posy_i+i_i])//Wird es in das Richtungslinie geschrieben
     else //ansonsten
      break; //wird abgebrochen
  end;

  //Sucht die Richtungslinie mit dem kleinesten Wert 
  i2_i:=0;
  for i_i:=0 to high(richtungen_xnr) do
    if richtungen_xnr[i2_i].wert_i>richtungen_xnr[i_i].wert_i then i2_i:=i_i;

  //Merkt sich die Richtungskoordinaten
  rx_i:=richtungen_xnr[i2_i].rx_i;
  ry_i:=richtungen_xnr[i2_i].ry_i;

  //Iniitzialiesiert die Bewegungswerte mit (0,0)
  bx_i:=0;
  by_i:=0;


  bremszeit_i:=0; //Iniitzialiesiert die zum bremsen benötigter Zeit (0 min)

  //Berechnet die Strecke zwischen Ziel und Start
  if rx_i<>0 then
    reststrecke_i:=abs(richtungen_xnr[i2_i].sx_i-richtungen_xnr[i2_i].zx_i)
  else
    reststrecke_i:=abs(richtungen_xnr[i2_i].sy_i-richtungen_xnr[i2_i].zy_i);

  //Solange fahren, bis es am Ziel ist
  while (posx_i<>richtungen_xnr[i2_i].zx_i) or (posy_i<>richtungen_xnr[i2_i].zy_i) do begin
    //Wenn die restliche Strecke kleiner ist als der Bremsweg
    if reststrecke_i<bremszeit_i then begin
      //muss abgebremst werden

      //Berechnung der Bremszeit mit der Bremsung
      if bx_i<>0 then
        bremszeit_i:=bremszeit_i-abs(bx_i)
       else
        bremszeit_i:=bremszeit_i-abs(by_i);

      //Bremsen
      if bx_i-rx_i<>0 then
        bx_i:=bx_i-rx_i;
      if by_i-ry_i<>0 then
        by_i:=by_i-ry_i;
    end else begin //Wenn nicht, kann beschleunigt werden, wenn auch bei einer Bechleunigung, die
      if bremszeit_i+max(abs(bx_i),abs(by_i))<reststrecke_i then begin  //Bremszeit nicht den Restweg übertrift
        //Beschleunigen
        bx_i:=bx_i+rx_i;
        by_i:=by_i+ry_i;

        //Neue Bremszeit
        if bx_i<>0 then
          bremszeit_i:=bremszeit_i+abs(bx_i)
         else
          bremszeit_i:=bremszeit_i+abs(by_i);
      end;
    end;
    //berechnet die Reststrecke
    if bx_i<>0 then
      reststrecke_i:=reststrecke_i-abs(bx_i)
     else if by_i<>0 then
      reststrecke_i:=reststrecke_i-abs(by_i);

    //Fahren
    posx_i:=posx_i+bx_i;
    posy_i:=posy_i+by_i;
    //Wegteil darstellen
    Paintbox1.Canvas.Brush.Color:=clYellow;
    Paintbox1.Canvas.Rectangle(posx_i*25,paintbox1.height-posy_i*25,posx_i*25+25,paintbox1.height-posy_i*25-25);
//    paintbox1.Canvas.TextOut(posx_i*25,paintbox1.height-posy_i*25-25,IntToStr(bx_i)+'|'+IntToStr(by_i));}
    inc(schritte_i); //Anzahl schritte erhöhen
//  Sleep(100);
  end;
end;
Caption:='Weg gefunden: '+InttoStr(schritte_i)+' Schritte'; //ausgeben der Schrittzahl
end;

//-------------------------Zeichnet den Kanal und den Weg-----------------------
procedure TForm1.paintbox1Paint(Sender: TObject);
var x_i,y_i:integer;
    bitmap_vb:TBitmap;
begin
//Erzeugt die Doppelbuffer Bitmap
bitmap_vb:=TBitmap.Create;
bitmap_vb.Width:=paintbox1.Width;
bitmap_vb.Height:=paintbox1.Height;
try
  with bitmap_vb.Canvas do begin
    for x_i:=0 to high(kanal_xk) do //Durchläuft den Kanal
      for y_i:=0 to high(kanal_xk[x_i]) do begin
        if Kanal_xk[x_i,y_i].wasser_b then //Bei Wasser
          brush.Color:=$00FE8001 //die Farber blau einschalten
       else
          brush.Color:=$0045C064;//sonst grün
       Rectangle(x_i*25,paintbox1.height-y_i*25,x_i*25+25,paintbox1.height-y_i*25-25); //Zeichnen
      end;

    brush.Color:=clLime; //HellGrüne Farbe einstellen
    Ellipse(startx_i*25,paintbox1.height-starty_i*25,startx_i*25+25, paintbox1.height-starty_i*25-25); //Startkreis zeichnen
    brush.Color:=clRed; //Farbe Rot einstellen
    Ellipse(zielx_i*25,paintbox1.height-ziely_i*25,zielx_i*25+25, paintbox1.height-ziely_i*25-25); //Zielkreis zeichnen
  end;
  paintbox1.Canvas.Draw(0,0,bitmap_vb); //in die Paintbox kopieren
finally
  bitmap_vb.free;
end;
if Caption<>'BWInf Aufgabe 4 (Tanker im Zuse-Kanal)' then //Wenn der Titel verändert wurdde
  Caption:='BWInf Aufgabe 4 (Tanker im Zuse-Kanal)'; //wird er wiederhergestellt                                        
end;

//----------------------- Verarbeitet Kanal veränderungen ----------------------
procedure TForm1.paintbox1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
var X_i,Y_i:integer;
begin
x_i:=x div 25; //Nummer von X
y_i:={y div }(paintbox1.Height- y) div 25; //Nummer von Y
if X_i>high(kanal_xk) then exit; //Prüft ob X oder
if Y_i<0 then exit; //Y außerhalb des Bereiches sind, und bricht bei true ab

case button of
  mbLeft:  //Bei linkem Mausklick
    Kanal_xk[x_i,y_i].wasser_b:=not Kanal_xk[x_i,y_i].wasser_b; //Gras->Wasser->Gras

  mbRight: begin //bei rechtem Mausklick
      zielx_i:=x_i; //wird das Zielfeld festgelegt
      ziely_i:=y_i;
    end;

  mbMiddle: begin //Bei mittlerem Mausklick
      startx_i:=x_i;//wird das Startfeld festgelegt
      starty_i:=y_i;
    end;
end;
paintbox1.Refresh;//Update der Darstelllun
end;



procedure TForm1.Hhe1Click(Sender: TObject);
begin
setlength(kanal_xk,length(kanal_xk),StrToInt(InputBox('Tanker im Zuse-Kanal','Bitte geben sie die gewünsche Höhe ein',IntToStr(length(kanal_xk[0]))))); //einstellen der neuen Höhe
end;

procedure TForm1.Breite1Click(Sender: TObject);
begin
setlength(kanal_xk,StrToInt(InputBox('Tanker im Zuse-Kanal','Bitte geben sie die gewünsche Breite ein',IntToStr(length(kanal_xk)))),length(kanal_xk[0])); //einstellen der neuen Breite
end;

//------------------------------Daten iniitizialiesieren------------------------
procedure TForm1.FormCreate(Sender: TObject);
var x_i,y_i:integer; //Schleifenvariablen
begin
setlength(kanal_xk,30,5); //Größe iniitizialiesieren
for x_i:=0 to high(kanal_xk) do
  for y_i:=0 to high(kanal_xk[x_i]) do
    Kanal_xk[x_i,y_i].wasser_b:=true; //Alle auf Wasser setzten
end;

//------------verhindert das störende Flackern des Hintergundes----------------
procedure TForm1.WM_ERASEBKGND(var mes:Tmessage);
begin                         
  mes.Result:=1;
end;
end.


