Pathfinding mit A*

[Amateurprofi]

Hallo Michael,

wenn die Mauer oben zu ist, dann wirst Du mit Deiner Methode die für den nächsten Schritt verfügbaren Felder zu ermitteln, nicht weiterkommen.
Wenn die Mauer oben zu ist, und du von 2/3 startest, geht das Programm auf 3/3, dann auf 3/2, und dann pendelt es zwischen 3/2 und 3/3 hin und her.

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.

Die Methode, die Strecke von einem Feld zum Zielfeld zu berechnen, hatte ich Dir ja gegeben und die ist auch korrekt.
Im Prinzip stelle Dir die Strecke von einem Feld zum Zielfeld als die Hypothenuse eines rechtwinkligen Dreiecks vor. Die Katheten sind dann die Strecken von i nach dest.x und von j nach dest.y

dx:=abs(dest.x-i);
dy:=abs(dest.y-j);

hierbei kann natürlich eine der Strecken 0 sein (rein theoretisch auch beide, aber bei Deinem Programm wird diese Situation schon vorher abgefangen)

Die Länge der Hypothenuse (also der Strecke von einem Feld zum Zielfeld) wäre dann Sqrt(dx^2 + dy^2), jedenfalls hat das Herr Pythagoras gesagt.
Da Du aber nicht die Länge der Strecke brauchst, sondern nur die Information, bei welchem Feld die Strecke am kürzesten ist, kannst Du Sqrt() weglassen (andernfalls mußt Du List.F als Single, Double etc. deklarieren).

Geh mal auf die Seite www.matheprisma.uni-wuppertal.de/Module/BackTr
und schau Dir unter "Labyrinth" an wie solch ein Backtracking Verfahren funktioniert.

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

[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.
   

[mimi]

Zitat:

Wie kan man das vermeiden? In meinem verlinkten Artikel stand was drinne, dass man sich das vorherige feld merken müsse

.
Ja du musst das fehld von dem du kommst in die Geschlossende liste einfügen

Zitat:

hat das damit was zu tun? Oder wie berücksichtige ich den Fall mit der Sackgasse?

Du musst am einfachsten Sackgassen in der Karte als solche defnieren. Das stand auch irgenwo im Tutorial.

[Amateurprofi]

Hallo Michael,
ich hab das mal etwas umgeschrieben - entspricht jetzt den Vorgaben und scheint zu funktionieren.
Ist allerdings unter delphi 2005 geschrieben, aber das sollte kein größeres Problem sein.

Du kannst jetzt Startfeld/Zielfeld und Mauern mit der Maus setzen.
Startfeld setzen : Shift Taste drücken und Feld klicken
Zielfeld setzen : Ctrl Taste drücken und Feld klicken
Mauerfeld setzten/entfernen : Feld klicken
Der Stop-Button stoppt die Pfadsuche (falls was nicht funktioniert und das Programm sich festfrißt).

Gruß, Klaus

[Luckie]

Danke, das war mehr als ich erwartet habe , nur jetzt habe ich es ja wieder nicht selber geschrieben. Wo lag denn mein eigentlicher Denkfehler? Desweiteren wollte ich den Code für einen Artikel nehmen, da es für Delphi, da wohl so wa snoch nicht gibt. Und dazu müsste ich den Code natürlich verstehen, deine Kommentare sind aber etwas kurz geraten.

Kennst du zufälligerweise auch noch einen einfachen Algorithmuss, um ein Labyrinth zu erzeugen?

[Amateurprofi]

Tja, Michael, was soll ich dazu sagen ?:

Ich bin einfach mal auf die Seite gegangen, auf die der Link in Deinem Beitrag verweist und hab mir dort die Erklärungen durchgelesen. Besser als dort kann man den Ablauf eigentlich nicht beschreiben.

Und Dein Fehler?:

Zitat:

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.

Zitat:

Zusammenfassung der A*-Methode
Gut. Jetzt, wo Du Dich durch die Erklärung gearbeitet hast, wollen wir die einzelnen Schritte noch einmal zusammenfassen:

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

Zitat:

Kennst du zufälligerweise auch noch einen einfachen Algorithmuss, um ein Labyrinth zu erzeugen?

Nein, kann doch aber nicht so schwer sein.

Gruß, Klaus

[Luckie]

Sprich, was mich ins Schleudern gebracht hat, war die Tatsaxhe, dass ich mich nicht genau an die Anleitung gehalten habe.

[xineohp]

moin,

zum Thema Labyrinth erzeugen, bin ich grade auf ein interessantes Pdf gestoßen, vielleich hilft dir das weiter:
Hier

[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.