Pathfinding (A*) Hexagon (Sechseck)

[Dearmon]

Hallo Leute :),

wie im Titel schon beschrieben möchte ich etwas übers Pathfinding bei hexagonalen Spielfeldern wissen.
Ich habe vor ein Strategiespiel zu schreiben, mehr oder weniger, und wollte jetzt zuerst einmal eine Art KI zu entwerfen.
Dafür wichtig ist:
-Das Spielfeld soll aus kleinen Sechsecken bestehen
-Man hat jede Runde Bewegungspunkte
-jeder Bewegung auf ein neues Feld kostet 1 Bewegungspunk
-jede Drehung auf einem Feld (also in eine der sechs Richtungen des Feldes) kostet 1 Bewegungspunkt
-besonderes Terrain kostet mehr Bewegungspunkte (z.B. 2 Punkt pro Bewegung) beim Überqueren. Bsp. dafür wäre so etwas wie ein Feld mit Reißnägeln oder einfach Wasser.

Die „KI“ soll dabei dem Spieler als eine Art Berater, bzw. Navigation zur Seite stehen. Der Spieler selbst kann Angaben machen wie: „Bitte keine Nägel“, oder „Bitte Wasserweg benutzen“ und die „KI“ zeigt einem dann einen möglichen Weg.

Ich finde dafür ist Pathfinding gerad zu prädestiniert:
Man kann den Feldern spezifische Eigenschaften geben, sodass sie nicht begehbar sind (Falls der Spieler keine Nägel möchte), oder sie in der Bewegungspunktwertung doppelt zählen lassen (Feld kostet 2 Punkte pro Bewegung).

Mein Problem ist nur dass ich das einfach nicht hin bekomme. Ich habe versucht die unzähligen Tutorials zu A* bei Quadraten umzuschreiben, aber das übersteigt anscheinend meine Kompetenz :/.
Hat das vllt. schon mal jemand umgesetzt? Speziell mit der Berücksichtigung der Bewegungskosten bei der Drehung? Oder hat vllt. sogar jemand ein Tutorial zur generellen Pathfinding bei Hexagons? Vllt. kann ich das ja dann selber erweitern. Bin für jede Hilfe dankbar :wink:

[Luckie]

Das hast du schon gefunden: http://www.michael-puff.de/Developer/Delphi/Demos/ -> AStar.zip

[Dearmon]

Das ist quadratisch, das bekomm ich halt nicht umbeschrieben :/
Ich bekomms nicht mal hin den H-Wert bei Sechsecken sinnvoll zu bestimmen -.-

[jfheins]

Ich hab da noch 2 Themen in petto, wo es auch um ein hexagonales Raster geht, vielleicht helfen die dir weiter ;)
http://www.delphipraxis.net/internal...t.php?t=175132
http://www.delphi-forum.de/viewtopic.php?t=98529
Und es gibt hier ja auch ein Pathfinding-Tut: http://www.delphipraxis.net/internal...ct.php?t=85844

Im Prinzip hast du doch das eine Mal vier Nachbarn, und das andere Mal 6. Wenn du ein geeignetes Koordinatensystem hast, ist es kein Problem diese Nachbarn zu ermitteln. Und für den Algorithmus ist das dann doch eigentlich egal (Ich vermute mal, der Algo braucht sowas wie "Bestimme Nachbarn" um die möglichen Folgefelder zu ermitteln und sowas wie "Bestimme Kosten von Feld XY")

[Khabarakh]

Habe ich das richtig verstanden: Die Einheiten bewegen sich von Mittelpunkt zu Mittelpunkt und nicht auf den Kanten (á la Catan)?

Zitat:

Zitat von Dearmon

Speziell mit der Berücksichtigung der Bewegungskosten bei der Drehung?

Das kannst du mit einem kleinen Trick umsetzen, ohne A* modifizieren zu müssen: Du machst aus jeder Koordinate sechs Knoten, einen für jede Richtung. Jeder Knoten (vom Rand abgesehen) besitzt dann drei Kanten: Eine zum Knoten des benachbarten Feldes in Bewegungsrichtung mit eben dieser Richtung und zwei zu den Knoten des gleichen Feldes mit Drehung um +/- 60°.

Zitat:

Zitat von Dearmon

Ich bekomms nicht mal hin den H-Wert bei Sechsecken sinnvoll zu bestimmen -.-

Solange der Algorithmus nicht spürbar langsam wird, würde ich erstmal auf die euklidische Distanz setzen. Ansonsten könntest du die Taxi-Metrik auf Sechsecke umschreiben. Vielleicht noch die minimal benötige Anzahl von Drehungen, um überhaupt in Richtung Ziel zu schauen, dazuzählen.

[Dearmon]

Vielen danke schon mal für die Antworten.

@Khabarakh, Jap von Mittelpunkt zu Mittelpunkt, deswegen ja auch 6 Richtungen. Das mit den Eckpunkten hab ich noch nicht ganz verstanden, muss ich mir später nochmal angucken ^^

Mit H hab ich nochmal n bisschen rumgespielt, zz. sieht meine Funktion so aus (habs noch nicht getestet, aber in der Theorie funktioniert es):

Delphi-Quellcode:

function GetDestY(APlayer, ATarget: TPoint): Integer;
var
  OriX, OriY: Integer;
Begin
  OriX := ATarget.X - APlayer.X;          // Dient zur Überprüfung des Standortes
  OriY := ATarget.Y - APlayer.Y;          // des Spielers im Bezug zum Ziel (oben links, oben rechts, etc.)

  if ((OriX >= 0) and (OriY >= 0)) or     // Ist der Spieler oben links    
     ((OriX <= 0) and (OriY <= 0)) then   // oder unten rechts vom Ziel?
    Result := ATarget.Y - Round((ATarget.X - APlayer.X) div 2) - APlayer.Y  // Zu gehende Felder berechnen
  else                                    // Spieler ist oben rechts, oder unten links vom Ziel.
    Result := ATarget.Y + Round((ATarget.X - APlayer.X) div 2) - APlayer.Y; // Zu gehende Felder berechnen
End;

function GetDestX(APlayer, ATarget: TPoint): Integer;
Begin
  Result := ATarget.X - APlayer.X;  // Zu gehende Felder berechnen
End;

function GetH(APlayer, ATarget: TPoint): Integer;
Begin
  Result := Abs(GetDestY(APlayer, ATarget)) + Abs(GetDestX(APlayer, ATarget));  // Beträge der zu gehenden Felder addieren
End;

GetDestY berechnet wie weit der Spieler (unabhängig vom drehen) auf der Y-Achse runter oder hoch muss, um so zum Ziel zu stehen dass er nur noch diagonal gehen muss.

GetDestX berechnet wie weit der Spieler (unabhängig vom drehen) diagonal gehen muss, um zum Ziel zu kommen.

GetH addiert dann beide Beträge um die gesamten zu begehenden Felder zu berechnen.

[jfheins]

Wie sind die Felder angeordnet?
Hast du ein angepasstes Koordinatensystem?
Wie adressierst du die Felder?

[Dearmon]

http://img263.imageshack.us/img263/5...interlace2.gif

Meinst du mit adressieren wie ich sie verwalte? Theoretisch durch ein einfaches Array of Array of Integer Grid, da die Felder atm nur eine Information enthalten. Also so etwas wie -1 = Blockiert, -4 = Wald etc. Sprich Feld[1][1] := -1.

[Khabarakh]

Zitat:

Zitat von Dearmon

GetDestY berechnet wie weit der Spieler (unabhängig vom drehen) auf der Y-Achse runter oder hoch muss, um so zum Ziel zu stehen dass er nur noch diagonal gehen muss.

GetDestX berechnet wie weit der Spieler (unabhängig vom drehen) diagonal gehen muss, um zum Ziel zu kommen.

GetH addiert dann beide Beträge um die gesamten zu begehenden Felder zu berechnen.

Japp, so habe ich mir das auch vorgestellt :thumb: .

[jfheins]

Also für die Entfernung hätte ich auch noch eine Idee:

Delphi-Quellcode:

function Convert(a: TPoint): TPoint;
begin // Konvertiert die Punkte in ein schiefes, gerade Koordinatensystem
Result.X := a.X - 1;
Result.Y := a.Y - 1 - (a.X - 1) div 2;
end;

function GetH(APlayer, ATarget: TPoint): Integer;
var
  Player2, Target2, diff: TPoint;
begin
  Player2 := Convert(APlayer);
  Target2 := Convert(ATarget);
  diff.X := Player2.X - Target2.X;
  diff.Y := Player2.Y - Target2.Y;

  Result := Min(Abs(diff.X) + Abs(diff.Y), Abs(diff.X+diff.Y) + Min(Abs(diff.X), ABS(diff.Y)))

  if (diff.X <> 0) and (diff.Y <> 0) and (diff.X + diff.Y <> 0) then
    Result := Result +1; // Drehung kostet einen Schritt
// Wenn es kein gradliniger Weg ist, kommt mindestens eine Drehung vor
end;

Aber ob das besser/schneller ist, musst du schon selber wissen ;)
(Ich hab einfach mal die Koordinaten in "mein" Koordinatensystem konvertiert und "meine" Norm angewendet ...)

Was den A* angeht, sollte der nicht allzuschwer zu implementieren sein. Ich glaube fast, es ist schwieriger einen bestehenden anzupassen als selber kurz einen neu zu programmieren ;)

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

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

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.