Pathfinding mit A*

[Luckie]

Zitat von Amateurprofi:

Übrigens : wenn Die Mauer offen ist, funktioniert das Programm auch, wenn Du die Position des Zielfeldes auf 6/4 oder 6/3 stellst.

Auf 6/4 ja aber auf 6/3 nicht mehr:

Delphi-Quellcode:

function FindPath(Maze: TMazeArray; Start, Dest: TPoint): TPoint;
var
  i, j              : Integer;
  List              : TOpenList;
  dx, dy            : integer;
begin
  for i := Start.X - 1 to Start.X + 1 do
  begin
    for j := Start.Y - 1 to Start.Y + 1 do
    begin
      if ((i = Start.X) and (j = Start.Y)) // Startfeld nicht in die Liste übernehmen
        or (Maze[i, j].Wall) // Hindernis nicht in die Liste übernehmen
        or (i = 0) // linker Spielfeldrand nicht in die Liste übernehmen
        or (j = 0) // oberer Speilfeldrand nicht in die Liste übernehmen
        or (i = COUNT) // rechter Spielfeldrand nicht in die Liste übernehmen
        or (j = COUNT) then // unterer Spielfeldrand nicht in die Liste übernehmen
        Continue;
      List.Square.X := i;
      List.Square.Y := j;
      dx := abs(dest.x - i);
      dy := abs(dest.y - j);
      List.H := (dx + dy) * 10;
      // Diagonale Felder
      if ((Start.X - 1 = i) and (Start.Y - 1 = j)) // oben links
        or ((Start.X - 1 = i) and (Start.Y + 1 = j)) // unten links
        or ((Start.X + 1 = i) and (Start.Y - 1 = j)) // oben rechts
        or ((Start.X + 1 = i) and (Start.Y + 1 = J)) then // unten rechts
        List.G := 14
      else
      // alle anderen
        List.G := 10;
      List.F := List.G + List.H;
      OpenListAdd(List);
    end;
  end;

  for i := 0 to length(OpenList) - 1 do
  begin
    DrawSquare(OpenList[i].Square.X, OpenList[i].Square.Y, SPACING, clYellow);
    TextOutFValue(OpenList[i].Square.X, OpenList[i].Square.Y, SPACING, clYellow, OpenList[i].F);
  end;
  //DrawRect(OpenList[MinFInList(OpenList)].Square.X, OpenList[MinFInList(OpenList)].Square.Y, SPACING, clBlue);
  result.X := OpenList[MinFInList(OpenList)].Square.X;
  result.Y := OpenList[MinFInList(OpenList)].Square.Y;
end;

Zitat:

Warum ?:
Weil das Programm immer das erste Feld mit der kürzesten Distanz zum Zielfeld wählt und nicht merkt, daß der Weg über 3/2 bereits erfolglos probiert wurde und daß es eine Alternative gibt.

Wie kan man das vermeiden? In meinem verlinkten Artikel stand was drinne, dass man sich das vorherige feld merken müsse. hat das damit was zu tun? Oder wie berücksichtige ich den Fall mit der Sackgasse?

Hier noch mal die Beschreibung des Algorithmusses:

Zitat:

1. Beginne mit Startpunkt A und füge ihn einer "offenen" Liste von Quadraten hinzu. Diese Liste ist vergleichbar mit einer Einkaufsliste; zu diesem Zeitpunkt ist nur ein Element in der Liste, aber wir können weiter Elemente später hinzufügen. Sie enthält möglicherweise auch Quadrate, die nicht auf dem von Dir gewünschten Weg liegen. Aus diesem Grunde enthält diese Liste grundsätzlich Quadrate, die überprüft werden müssen. Habe ich gemacht.
2. Schaue Dir alle erreich- bzw. begehbaren Quadrate, die an das Startquadrat A grenzen, an, und ignoriere dabei Quadrate, welche Wände, Wasser oder anderes nicht begehbares Terrain darstellen. Füge sie der o.g. Liste hinzu und merke für jedes dieser Quadrate das Startquadrat A als seinen Vorgänger. Diese Beziehung eines Quadrates zu seinem Vorgänger wird später wichtig, wenn wir den Pfad entlanggehen wollen; dazu später mehr. Habe ich gemacht.
3. Wirf das Startquadrat A aus Deiner bisherigen, offenen Liste und füge es zu einer anderen, "geschlossenen" Liste von Quadraten hinzu, die Du Dir aber jetzt noch nicht anzuschauen brauchst. Hab eich nicht gemacht, da ich nur mit einer Liste arbeite.
4. Entferne es aus der offenen Liste und füge es der geschlossenen Liste hinzu.
5. Prüfe alle angrenzenden Quadrate und füge sie der offenen Liste hinzu, sofern sie:
   • kein Hindernis darstellen, also begehbar sind
   • sich nicht bereits in der offenen Liste befinden
   • sich nicht in der geschlossenen Liste befinden
   und trage für jedes dieser Quadrate das aktuelle Quadrat als Vorgängerquadrat ein. Hm, ja, da komme ich etwas ins Straucheln.
6. Falls eines der umliegenden Quadrate sich bereits in der offenen Liste befindet, prüfe, ob der Pfad vom aktuellen Quadrat zu solch einem Quadrat ein besserer ist, mit anderen Worten, ob der G-Wert für dieses Quadrat geringer wäre, wenn wir vom aktuellen Quadrat aus dorthin gehen würden. Wenn nicht, unternimm gar nichts.
   Falls jedoch die G-Kosten dieses Quadrates geringer würden, wenn wir vom aktuellen Quadrat aus dorthin gehen würden, ändere das Vorgängerquadrat dieses Quadrats auf das aktuelle Quadrat (richte dann den Zeiger im Diagramm oben auf das aktuelle Quadrat). Schließlich berechne sowohl den F- als auch den G-Wert dieses Quadrats neu. Falls dies etwas verwirrend sein sollte, findest Du eine Darstellung weiter unten. Und hier fehlt mir auch die Umsetzung in Code.