Pathfinding mit A*

[Luckie]

@AmatuerProfi: Ich habe mal deinen Code kommentiert. Stimmt das so:

Delphi-Quellcode:

////////////////////////////////////////////////////////////////////////////////
//  FindPath
//  Comment: A* Algorithmus
//  Zusammenfassung der A*-Methode
//
//  1) Füge das Startquadrat der offenen Liste hinzu.
//  2) Wiederhole das Folgende:
//  a) Suche in der offenen Liste nach dem Quadrat mit dem niedrigsten F-Wert. Wir bezeichnen dieses Quadrat im
//     Folgenden als das aktuelle Quadrat.
//  b) Verschiebe es in die geschlossene Liste.
//  c) Für jedes der 8 an das aktuelle Quadrat angrenzenden Quadrate:
//     Wenn es nicht begehbar ist oder sich bereits in der geschlossenen Liste befindet, ignoriere es; andernfalls
//     mach das Folgende:
//     Wenn es nicht in der offenen Liste ist, füge es der offenen Liste hinzu. Trage das aktuelle Quadrat als
//     Vorgängerquadrat dieses Quadrats ein. Trage zusätzlich die Werte für die F-, G- und H-Kosten dieses Quadrates
//     ein.
//     Falls es bereits in der offenen Liste ist, prüfe, ob der Pfad vom aktuellen Quadrat zu ihm - gemessen am
//     G-Wert -, besser ist, als der Pfad von seinem eingetragenen Vorgängerquadrat (ein geringerer G-Wert bedeutet
//     einen besseren Pfad). Falls dem so ist, ändere sein Vorgängerquadrat auf das aktuelle Quadrat und berechne
//     seine Werte für G und F neu. Sofern Du Deine offene Liste nach dem F-Wert sortiert hast, ist möglicherweise
//     eine Neusortierung dieser Liste erforderlich, um dieser Veränderung Rechnung zu tragen.
//
//  d) Beende den Prozess, falls:
//     Du das Zielquadrat in die geschlossene Liste verschoben hast; in diesem Fall hast Du den Pfad ermittelt
//     kein Zielquadrat gefunden werden konnte und die offene Liste leer ist; in diesem Fall gibt es keinen Pfad.
//
//  3) Sichere den Pfad. Der Pfad erschließt sich, indem Du vom Zielquadrat aus Quadrat für Quadrat rückwärts
//     schreitend das Startquadrat erreichst

function FindPath: boolean;
var
  i, xx, yy         : Integer;
  NewField, ActField: TOpenList;

  // Feld in die offene Liste aufnehmen
  procedure AddNewField;
  begin
    with newfield, square do
    begin
      predecessor := actfield.square;
      g := actfield.g;
      if (x = predecessor.x) or (y = predecessor.y) then
        inc(g, 10)
      else
        inc(g, 14);
      h := 10 * (abs(x - dest.x) + abs(y - dest.y));
      f := h + g;
    end;
    ListAdd(OpenList, NewField);
  end;

  // Feldwerte (H, G und F) berechnen und Vorgängerfeld zu ordnen
  procedure AdjustFieldData(i: integer);
  var
    gg              : integer;
  begin
    with openlist[i], actfield.square do
    begin
      gg := actfield.G;
      if (x = square.x) or (y = square.y) then
        inc(gg, 10)
      else
        inc(gg, 14);
      if gg < g then
      begin
        g := gg;
        f := g + h;
        predecessor := actfield.square;
      end;
    end;
  end;

begin
  Abort := False;
  SetLength(OpenList, 0);
  SetLength(ClosedList, 0);
  FillChar(NewField, SizeOf(NewField), 0);
  NewField.Square := Start;
  // Startfeld in die offene Liste einfügen (1)
  ListAdd(OpenList, NewField);
  repeat // (2)
    Application.ProcessMessages;
    if Abort then
      break;
    // Feld mit den geringsten Wegkosten ermitteln
    i := ClosestField; // (2a)
    // selbiges Feld in die geschlossene Liste übernehmen
    MoveToClosedList(i, ActField); // (2b)
    with NewField, ActField.square do
      // einmal um das Feld drumrumgehen (2c)
      for xx := Max(X - 1, 1) to Min(X + 1, count) do
        for yy := Max(Y - 1, 1) to Min(Y + 1, count) do
          //
          if ((xx <> X) or (yy <> Y)) and not wall[xx, yy] then
          begin
            Square := Point(xx, yy);
            // wenn es nicht in der geschlossenen Liste existiert, ignorieren
            if not Exists(ClosedList, Square, i) then
              // aber in der geschlossenen, Feld bewerten
              if Exists(OpenList, Square, i) then
                AdjustFieldData(i)
              // ansonsten hinzufügen  
              else
                AddNewField
          end;
  until (int64(ActField.Square) = int64(Dest)) or (length(OpenList) = 0);  // (2d)
  result := (length(OpenList) > 0) and not abort;
end;

Danke xineohp, werde ich mir mal angucken.