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.