Pathfinding mit A*

[Luckie]

Ich habe mich heute Nachmittag mal drangesetzt und habe versucht den obigen Algorithmus zum Finden eines Pfades zu implementieren. Also so halb funktionieren tut es schon mal. Ich habe mich an die Beschreibung von dieser Seite gehalten: http://www.policyalmanac.org/games/a...torial_de.html .

Nur irgendwie bleibt mein Algorithmus auf halben Weg stecken, das heißt, er landet in einer Endlosschleife. Desweitern, wenn ich das Hindernis bis an die Oberkante des Spielfeldes mache, bleibt er auch stecken. Und ich finde den Fehler in meinem Algorithmus einfach nicht. Ich weiß, dass der Code bestimmt nicht sehr performant ist und auch nicht unbedingt den kürzesten Wg findet, aber ich will überhaupt erstmal einen Weg finden. :-?

Ich glaube, hier Sourcecode zu posten ist etwas schlecht, da man es im Zusammenhang sehen muss. Deswegen hänge ich mal den Source an. Ich denke, der Source spricht für sich.

[Luckie]

Ich habe jetzt auch den horizontalen Abstand für die geschätzte Entfernung zum Ziel mit einbezogen:

Delphi-Quellcode:

List.H := (Abs(Abs((Dest.X - i)) + (Abs(Dest.Y - j)))) * 10;

Jetzt hängt er gleich beim ersten mal in einer Endlosschleife. :gruebel:

[Pr0g]

Ich hatte vor einiger Zeit mal diesen Artikel genutzt um A* Pathfinding für die Geister in einen Pacman Klon zu realisieren. Vielleicht fällt dir ja mit dessen Hilfe auf, was bei dir fehlt, oder nicht richtig umgesetzt wurde.

[Airblader]

@Luckie

Zwar nichts zum Problem, aber warum machst du ein Abs() um die Summe zweier anderer Abs()-gekapselten Rechnungen?
Da diese 100% positiv sind und eine Summe zweier positiver Werte sicher nicht negativ ist, ist die äußerste abs() sinnlos ;)

air

[mimi]

Wenn ich den Beitrag richtig verstanden habe, habe ich vermutlich den fehler gefunden und evtl. eine lösung für dich(ich habes nicht gestet).

Meiner meinung nach berechnes du den H wert falsch.

Delphi-Quellcode:

   if Dest.X > Start.X then
        List.H := (Dest.X - i) * 10
      else
        List.H := (i - Dest.X) * 10;

Laut tutorial musst du nicht einfach die Horizontale länge bereichnen sondern auch die vertikal damit meine ich folgendes für die Richtung Rechts:

Delphi-Quellcode:

if Dest.X > Start.x then begin
  Liste.H:=(Dest.X - i)+Dest.Y-j * 10
end;

das müste eigentlich so gehen.
damit meine ich folgendes:
du berechnes vom Start zum Ziel Punkt und berechnes den abstand. Angenommen das Ziel ist unten Rechts und der Start Oben Linx. Dazwischen währen jetzt hindernisse. Jetzt musst du die Horizontale richtung berechnen und anschließnd die Vertiklae richtung und anschließnd zusammen addieren.
So habe ich es verstanden.

Bin mir aber nicht sicher aber das richtig ist.

[Luckie]

Zitat:

Zitat von mimi

Meiner meinung nach berechnes du den H wert falsch.

Ja, da suche ich auch gerade den Fehler. Ich habe es jetzt so:

Delphi-Quellcode:

      if Dest.X > Start.x then
      begin
        dx := Dest.X - i;
      end
      else if Dest.X < Start.X then
      begin
        dx := i - Dest.X;
      end
      else
        dx := Dest.X;

      if Dest.y > Start.y then
      begin
        dy := Dest.y - j;
      end
      else if Dest.Y < Start.Y then
      begin
        dy := j - Dest.y;
      end
      else
        dy := Dest.Y;

Aber er bleibt trotzdem wieder stecken. :evil:

[Airblader]

Versuchs doch nochmal auf die kurze Weise:

Delphi-Quellcode:

List.H := (Abs(Dest.X - i) + Abs(Dest.Y - j)) * 10;

air

[Luckie]

Habe ich auch schon versucht, das klappt auch nicht. Im obigen Code war ein Fehler. So stimmt es:

Delphi-Quellcode:

      if Dest.X > i then
      begin
        dx := Dest.X - i;
      end
      else if Dest.X < i then
      begin
        dx := i - Dest.X;
      end
      else
        dx := Dest.X;

      if Dest.y > j then
      begin
        dy := Dest.y - j;
      end
      else if Dest.Y < j then
      begin
        dy := j - Dest.y;
      end
      else
        dy := Dest.Y;
      List.H := (dx + dy) * 10;

Jetzt kommt er bis zum Ziel, aber nur bis ein Kästchen vor das Ziel, so dass er aus der Schleife nicht rauskommt:

Delphi-Quellcode:

  while (Dest.X <> Start.X) or (Dest.Y <> Start.Y) do
  begin
    Application.ProcessMessages;
    Start := FindPath(Maze, Start, Dest);
    SetLength(Path, length(Path) + 1);
    Path[length(Path) - 1] := Start;
    SetLength(OpenList, 0);
    Sleep(250);
    DrawSquare(2, 3, SPACING, clGreen);
    InvalidateRect(Handle, nil, True);
  end;

[Amateurprofi]

Michael,

versuche mal folgendes

in TForm1.Button1Click
ersetze

Delphi-Quellcode:

while (Dest.X - 1 <> Start.X) or (Dest.Y - 1 <> Start.Y) do

durch

Delphi-Quellcode:

while (abs(dest.x-start.x)>1) or (abs(dest.y-start.y)>1) do

in FindPath
ersetze

Delphi-Quellcode:

if Dest.X > Start.X then
   List.H := (Dest.X - i) * 10
else
   List.H := (i - Dest.X) * 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;

durch

Delphi-Quellcode:

dx:=abs(dest.x-i);
dy:=abs(dest.y-j);
list.f:=dx*dx+dy*dy;

dx und dy mußt Du natürlich lokal deklarieren.

keine Garantie, aber bei mir funktioniert das.

Gruß, Klaus

[Luckie]

Hm, danke. Für diese eine Situation scheint es zu klappen. Aber wenn ich das Ziel auf 6,4 versetze oder die Mauer oben zu mache, dann geht es schon nicht mehr. :gruebel:

Im ersten Posting jetzt noch mnal mein aktueller Code.

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

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.
   :gruebel:

[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 :P , 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. :gruebel:

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