AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Multimedia Delphi Pathfinding (A*) Hexagon (Sechseck)

Pathfinding (A*) Hexagon (Sechseck)

Ein Thema von Dearmon · begonnen am 21. Apr 2010 · letzter Beitrag vom 23. Apr 2010
Antwort Antwort
Seite 1 von 2  1 2   
Dearmon

Registriert seit: 23. Nov 2008
16 Beiträge
 
#1

Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 14:29
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
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#2

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 14:33
Das hast du schon gefunden: http://www.michael-puff.de/Developer/Delphi/Demos/ -> AStar.zip
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Dearmon

Registriert seit: 23. Nov 2008
16 Beiträge
 
#3

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 14:35
Das ist quadratisch, das bekomm ich halt nicht umbeschrieben :/
Ich bekomms nicht mal hin den H-Wert bei Sechsecken sinnvoll zu bestimmen -.-
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#4

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 15:09
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")
  Mit Zitat antworten Zitat
Benutzerbild von Khabarakh
Khabarakh

Registriert seit: 18. Aug 2004
Ort: Brackenheim VS08 Pro
2.876 Beiträge
 
#5

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 15:40
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.
Sebastian
Moderator in der EE
  Mit Zitat antworten Zitat
Dearmon

Registriert seit: 23. Nov 2008
16 Beiträge
 
#6

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 18:52
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.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#7

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 19:01
Wie sind die Felder angeordnet?
Hast du ein angepasstes Koordinatensystem?
Wie adressierst du die Felder?
  Mit Zitat antworten Zitat
Dearmon

Registriert seit: 23. Nov 2008
16 Beiträge
 
#8

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 19:26
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.
  Mit Zitat antworten Zitat
Benutzerbild von Khabarakh
Khabarakh

Registriert seit: 18. Aug 2004
Ort: Brackenheim VS08 Pro
2.876 Beiträge
 
#9

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 20:23
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 .
Sebastian
Moderator in der EE
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#10

Re: Pathfinding (A*) Hexagon (Sechseck)

  Alt 21. Apr 2010, 22:35
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
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:25 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz