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:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:

  var
    i, j, u, bestes_Kosten, bestes_nummer: Integer;
    offene_liste, abgearbeitete_Liste, hinderniss_Liste, buffer_Liste: Array of TFeldInfo;
    aktuelle_FeldInfo, abgearbeitete_Feldinfo, neue_FeldInfo: TFeldinfo;
    ziel_gefunden, schon_vorhanden: Boolean;
    Anzahl_offen, Anzahl_abgearbeitet: Integer;
    Buffer_schritte: Array of TSchritt;
  begin
    Schritte_Anzahl := 0;
    Setlength(Schritt, 0);
    //überprüfen ob Start Definiert ist;
    if((Start_x = -1) Or (Start_y = -1)) then
    begin
        result := 4;
        exit;
    end;

    //überprüfen ob Start im Intervall liegt
    if((Start_x >= Karte.read_grosse_x()) Or (Start_y >= Karte.read_grosse_y())) then
    begin
        result := 5;
        exit;
    end;

    //überprüfen ob Ziel Definiert ist;
    if((Ziel_x = -1) Or (Ziel_y = -1)) then
    begin
        result := 2;
        exit;
    end;

    //überprüfen ob Ziel im Intervall liegt
    if((Ziel_x >= Karte.read_grosse_x()) Or (Ziel_y >= Karte.read_grosse_y())) then
    begin
        result := 3;
        exit;
    end;

    // Die Start Information anlegen
      neue_Feldinfo.Pos_x := Start_x;
      neue_Feldinfo.Pos_y := Start_y;
      neue_Feldinfo.kosten_ziel := errechneter_weg(neue_Feldinfo.Pos_x, neue_Feldinfo.Pos_y);
      neue_Feldinfo.kosten_hierher := 0;
      Setlength(offene_Liste, 2);
      Anzahl_offen := 1;
      offene_liste[1] := neue_Feldinfo;
      anzahl_abgearbeitet := 0;
    // Hier gehts jetzt Richtig los^^
      ziel_gefunden := FALSE;
      Repeat
        // Rausfinden welches die geringsten gesamtkosten hat
        //dazu wird das erste Element aus der liste genommen
        aktuelle_Feldinfo := Offene_Liste[1];
        bestes_kosten := aktuelle_Feldinfo.kosten_gesamt;
        bestes_nummer := 1;

        // und dann werden die gesamtkosten mit allen andern ELementen aus der offenen Liste verglichen
        for i:=1 to anzahl_offen do
        begin
          aktuelle_Feldinfo := offene_liste[i];
         // Form1.Memo1.Lines.Add('Nummer: ' + inttostr(i) + ' Kosten: ' + inttostr(offene_liste[i].kosten_gesamt));

          if(aktuelle_Feldinfo.kosten_gesamt < bestes_kosten) then
          begin
            bestes_kosten := aktuelle_Feldinfo.kosten_gesamt;
            bestes_nummer := i;
          end;
        end;

        aktuelle_Feldinfo := offene_liste[bestes_nummer];
        //Das Beste ist gefunden
        //Nun wird das ELement überprüft ob es schon das Ziel ist
   //     Form1.Memo1.Lines.Add('x:' + inttostr(aktuelle_Feldinfo.Pos_x) + 'y:' + inttostr(aktuelle_Feldinfo.Pos_y));

        if(aktuelle_Feldinfo.kosten_ziel = 0) then
        begin
          Ziel_gefunden := TRUE;
          break;
        end;

        // Das Ziel wurde noch nicht gefunden
        // die 8 rundherum in die offene Liste aufnehmen
        for i:= -1 to +1 do
        begin
          for j:= -1 to +1 do
          begin
            // überprüfen ob die Elemente schon in der abgearbeiten Liste sind
            // Position überprüfen
            if(Aktuelle_Feldinfo.Pos_x + i < 1) OR (Aktuelle_Feldinfo.Pos_x + i > Karte.read_grosse_x) then
              continue;
            if(Aktuelle_Feldinfo.Pos_y + j < 1) OR (Aktuelle_Feldinfo.Pos_y + j > Karte.read_grosse_y) then
              continue;
            // Testen ob das Feld Passierbar ist
            if(Karte.read_kosten_feld(Aktuelle_Feldinfo.Pos_x + i, Aktuelle_Feldinfo.Pos_y + j) = 0) then
                continue;

            schon_vorhanden := FALSE;
            for u:= 1 to anzahl_abgearbeitet do
            begin
              abgearbeitete_Feldinfo := abgearbeitete_Liste[u];
              if(abgearbeitete_Feldinfo.Pos_x = Aktuelle_Feldinfo.Pos_x + i) and (abgearbeitete_Feldinfo.Pos_y = Aktuelle_Feldinfo.Pos_y + j) then
              begin
                schon_vorhanden := TRUE;
                break;
              end;
            end;

            for u:=1 to anzahl_offen do
            begin
              abgearbeitete_Feldinfo := offene_liste[u];
              if(abgearbeitete_Feldinfo.Pos_x = Aktuelle_Feldinfo.Pos_x + i) and (abgearbeitete_Feldinfo.Pos_y = Aktuelle_Feldinfo.Pos_y + j) then
              begin
                schon_vorhanden := TRUE;
                break;
              end;
            end;

            // Das Element ist schon vorhanden
            if(schon_vorhanden = TRUE) then
              continue;

            //Die Position hinzufügen

            neue_Feldinfo.Pos_x := Aktuelle_Feldinfo.Pos_x + i;
            neue_Feldinfo.Pos_y := Aktuelle_Feldinfo.Pos_y + j;

            // Die kosten dahin bestimmen
            if( abs(i + j) = 1) then
              neue_Feldinfo.kosten_hierher := Aktuelle_Feldinfo.kosten_hierher + 2*Karte.read_kosten_feld(neue_Feldinfo.Pos_x, neue_Feldinfo.Pos_y)
            else
              neue_Feldinfo.kosten_hierher := Aktuelle_Feldinfo.kosten_hierher + 3*Karte.read_kosten_feld(neue_Feldinfo.Pos_x, neue_Feldinfo.Pos_y);

              neue_Feldinfo.kosten_ziel := errechneter_weg(neue_Feldinfo.Pos_x, neue_Feldinfo.Pos_y);
              neue_Feldinfo.kosten_gesamt := neue_Feldinfo.kosten_hierher + neue_Feldinfo.kosten_ziel;
            //Zur Offenen Liste hinzufügen
            // erstmal alles in einen Buffer schreiben da bei Setlength der Inhalt gelöscht wird
            Setlength(Buffer_liste, anzahl_offen+1);
            for u:=1 to anzahl_offen do
              Buffer_liste[u] := offene_Liste[u];

            anzahl_offen := anzahl_offen + 1;
            Setlength(offene_Liste, anzahl_offen+1);
            for u:=1 to anzahl_offen-1 do
              offene_Liste[u] :=Buffer_liste[u];

            offene_Liste[anzahl_offen] := neue_Feldinfo;

          end;
        end;
        // das benutzte Element in die Abgearbeite Liste schieben
        Setlength(Buffer_liste, anzahl_abgearbeitet+1);
        for u:=1 to anzahl_abgearbeitet do
          Buffer_liste[u] := Abgearbeitete_Liste[u];

        anzahl_abgearbeitet := anzahl_abgearbeitet + 1;
        Setlength(Abgearbeitete_Liste, anzahl_abgearbeitet+1);
        for u:=1 to anzahl_abgearbeitet-1 do
          Abgearbeitete_Liste[u] :=Buffer_liste[u];

        Abgearbeitete_Liste[anzahl_abgearbeitet] := offene_Liste[bestes_nummer];

        //Es aus der offenen Liste löschen
        for u:= bestes_nummer to anzahl_offen-1 do
        begin
          Offene_liste[u] := Offene_liste[u+1];
        end;

        Setlength(Buffer_liste, anzahl_offen);
        for u:=1 to anzahl_offen-1 do
          Buffer_liste[u] := offene_Liste[u];

        anzahl_offen := anzahl_offen - 1;
        Setlength(offene_Liste, anzahl_offen+1);

        for u:=1 to anzahl_offen do
          offene_Liste[u] :=Buffer_liste[u];
      //form1.Memo1.Lines.Add(inttostr(Anzahl_offen));
      Until (anzahl_offen = 0) or (Ziel_gefunden = True);



      if(Ziel_gefunden = True) then
      begin
        repeat
          Schritte_Anzahl := Schritte_Anzahl + 1;
          for i:= -1 to +1 do
          begin
            for j:= -1 to +1 do
            begin
              //Erstmal schauen welches Element angrenzt
              if(i = 0) and (j = 0) then
                continue;
              begin
                for u:= 1 to Anzahl_abgearbeitet do
                begin


                  if(abgearbeitete_Liste[u].Pos_x = aktuelle_Feldinfo.Pos_x + i) and (abgearbeitete_Liste[u].Pos_y = aktuelle_Feldinfo.Pos_y + j) then
                  begin
                    //showmessage('x: ' + inttostr(abgearbeitete_Liste[u].Pos_x ) + ' y:' + inttostr(abgearbeitete_Liste[u].Pos_y) + ' kosten: ' + inttostr(Karte.read_kosten_feld(abgearbeitete_Liste[u].Pos_x, abgearbeitete_Liste[u].Pos_y)));
                    if(Karte.read_kosten_feld(abgearbeitete_Liste[u].Pos_x, abgearbeitete_Liste[u].Pos_y) > 0) then
                    begin
                      // schauen welches Element die geringsten kosten haben
                      if(abgearbeitete_Liste[u].kosten_hierher < neue_Feldinfo.kosten_hierher ) then
                      begin
                        //Form1.Memo1.Lines.Add('Kosten Karte: '+inttostr(Karte.read_kosten_feld(abgearbeitete_Liste[u].Pos_x, abgearbeitete_Liste[u].Pos_y)));
                        neue_Feldinfo := abgearbeitete_Liste[u];
                      end;
                    end;
                  end;
                end;
              end;
            end;
          end;
          // schritte dazuzählen
          Setlength(Buffer_Schritte, Schritte_anzahl);
          For i:= 1 to Schritte_anzahl-1 do
            Buffer_Schritte[i] := Schritt[i];

          Setlength(Schritt, Schritte_Anzahl+1);
          For i:= 1 to Schritte_anzahl-1 do
            Schritt[i] := Buffer_Schritte[i];

          Schritt[Schritte_anzahl].x := aktuelle_Feldinfo.Pos_x;
          Schritt[Schritte_anzahl].y := aktuelle_Feldinfo.Pos_y;

          aktuelle_Feldinfo := neue_Feldinfo;
        //  Form1.Memo1.Lines.Add(inttostr(anzahl_abgearbeitet));

        UNtil aktuelle_Feldinfo.kosten_hierher = 0;
        result := 0;
      end
      else
        result := 1;
  end;