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

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

[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