Pathfinding (A*) Hexagon (Sechseck)

[Dearmon]

Soo als es tut mir echt leid aber ich bin anscheinend intellektuell nicht fähig genug das Listensystem hin zu bekommen.
Ich hab jetzt versucht den A* Algorithmus dem aus dem tut von "Michael Puff" (Siehe Post 2) nach zu empfinden, da er meines Erachtens nach relativ Ressourcen freundlich ist, weil er nicht die ganze Map berechnet, sondern Feld für Feld von Start zu Stop.
Im Moment hab ich meine Felder so eingerichtet, dass jedes seine 6 Nachbarn kennt. Hinzu kommen Informationen wie Typ (Wand, Wald, …), Kosten (Gras = 1, Wald = 2, …), Position (X und Y), Vorgänger, Ausrichtung (in welche Richtung der Spieler guckt wenn er das Feld betreten sollte) und die F,G,H Kosten.

Delphi-Quellcode:

TFeld = Class(TObject)
Private
FNachbar: Array[0..5] of TFeld;
FPos: TPoint;
FTyp: Integer; 
FARichtung: Integer;
FKosten: Integer;
FOwner: TFeld;
FF, FH, FG: Integer;
…..

So, den Anfang der Berechnung bekomm ich evtl. noch hin, die Nummerierung der Ausrichtung und die der Position der Nachbarn ist dieselbe: Oben 0 und dann im Uhrzeiger sinn an jede Kante die nächste Zahl sodass oben links neben der 0 die 5 ist. Zu Anfang rechne ich jetzt quasi das:

Delphi-Quellcode:

For i:= 0 to 5 do
  Begin
     If Not CurrFeld.Nachbar[i].Typ = -1 then  // Feld ist begehbar      
       With CurrFeld.Nachbar[i] do
         Begin
           Owner := CurrFeld;  // Vorgänger übergeben
           Ori := I;  // Ausrichtung des Spielers übergeben
           G := CurrFeld.G + GetTurns(CurrFeld.Ori, i) + Kosten;  // Derzeitige G Kosten + Kosten für die Drehung 
                                                                  // +Begehkostendes Feldes
 
           H := GetH(Pos, Target.Pos);  // Voraussichtliche Kosten
           F := H + G;
         End;
  End;

Wie immer leider nur Theorie, weiß diesmal nicht mal obs wirklich Sinn macht so, aber ich hab vor allem jetzt überhaupt garkeinen Plan wie ich das mit den Listen anfangen soll, also das System im Allgemeinen ist klar: eine offene Liste wo die einzelnen Sechsecke berechnet werden und eine geschlossene, wo der endgültige Weg eingetragen wird. Nur bekomm ich das nun mal nicht hin, also ich rede nicht von Effizienz oder Schnelligkeit, sondern lediglich von der Umsetzung in irgendeinem Weg.

Wenn mir vllt jemand eine Listenstruktur darstellen oder anders helfen könnte, wäre ich sehr dankbar. Aus dem "puren" source code der Stardemo werde ich leider nicht schlau :/

Danke

[Khabarakh]

Warum änderst du nicht direkt Luckies Code ab? 75% des Codes solltest du doch direkt übernehmen können und mit den Listen musst du dich überhaupt nicht befassen, wenn du nicht willst .

Oder du findest noch eine Implementierung, die für beliebige Graphen funktioniert, das wäre natürlich das Optimum .

[Dearmon]

Das Problem beim reinen kopieren ist, dass ich garantiert später Probleme beim Erweitern haben werde, wenn ich die Logik dahinter nicht verstehe. Im Grunde genommen bekomm ich das mit den Listen vllt sogar doch hin, aber ich hab noch eine Frage die mir vllt ja sogar jemand beantworten kann.

http://img689.imageshack.us/img689/556/squares2.jpg

Angenommen Grün wäre der Start, Rot das Ziel und Blau eine Wand. Das erste Feld, was in die Geschlossene Liste kommt, wäre das Feld mit der 1 da es den niedrigsten H-Wert hat. Danach kommt Feld 2 in die Geschlossene, aus demselben Grund.
So und jetzt versteh ich nicht wie es weiter geht. Die 2 ist umringt von Mauern und in dem Algo wird das Feld mit der 1 nicht mehr berücksichtigt, da in der Schleife abgebrochen wird wenn das Feld bereits in der Geschlossene ist.
Wie oder wo kommt es jetzt dazu, dass der Weg oberhalb des Startpunktes weitergeführt wird?

[jfheins]

Zitat von Dearmon:

Angenommen Grün wäre der Start, Rot das Ziel und Blau eine Wand. Das erste Feld, was in die Geschlossene Liste kommt, wäre das Feld mit der 1 da es den niedrigsten H-Wert hat. Danach kommt Feld 2 in die Geschlossene, aus demselben Grund.

So wie ich es verstanden habe: Falsch.
0. Das grüne Feld kommt in die geschlossene Liste
1. Zuerst kommen Felder 1 und 3 (3 ist das über dem grünen) in die offene Liste
2. Die offene Liste wird dann sortiert nach dem f-Wert. (Feld 1 an erster Stelle weil geringerer f-Wert als 3)
3. Das erste Element der offenen Liste wird herausgenommen und in die geschlossenen Liste getan. (Hier Feld 1) Danach werden alle Nachbarfelder, die begehbar sind und nicht in der geschlossenen Liste sind, in die offenen Liste getan (hier Feld 2)
4. Die offenen Liste wird sortiert. Das Element mit dem niedrigsten f-Wert wird genommen. (Hier Feld 2)
5. Feld 2 wird behandelt. (siehe Schritt 3) Es werden keine passenden Nachbarfelder gefunden. Es ist aber ja noch Feld 3 in der offenen Liste (aus Schritt 1)
6. siehe Schritt 2
7. siehe Schritt 3

[Dearmon]

Also du meinst, wenn ein Feld quasi keine Möglichkeit mehr hat weiter zu kommen (Weil Wände im weg sind) wird der Weg bis dahin einfach verworfen und das nächste Feld mit den geringsten Gesamtkosten aus der offenen Liste wird betrachtet?

Okay, das heißt dann dass ich einfach nur die Felder, die in der Geschlossenen sind, aus der Offenen löschen muss nicht wahr? Danke, das prob ich erst mal aus.

[Khabarakh]

Ich bin mir nicht sicher, ob du es richtig verstanden hast. Wird ein Knoten betreten, kommt er sofort aus dem Open Set:

Code:

         remove x from openset
         add x to closedset

Genauso gibt es keinen "aktuellen Weg", bei dem es "nicht mehr weiter geht" und den man dann "verwerfen" kann. Du hast immer nur einen aktuellen Knoten, nämlich den nächsten aus dem Open Set, der auch zwischen zwei Wegen "hin- und herspringen" könnte.