Tutorial Pathfinding
Wilkommen zu meinen Tutorial zum Pathfinding.
Inhaltsverzeichnis
Geeignete Welten
Diese Methode geht davon aus das sich unsere virtuelle Welt aus lauter Quadraten zusammensetzt. Jedes dieser Felder wird für die Wegberechnung erstmal vereinfacht, in dem davon ausgegangen wird, das ein Feld entweder begehbar ist, oder nicht. (Oder sogar Felder haben die zwar begehbar sind aber gemieden werden solten.)
Nun wird weiter davon ausgegangen, dass eine Einheit von einen Feld nur in 8 (bzw. 4) Richtungen, nämlich in die 8 (4) benachbarten Felder bewegen kann.
Von dem nächsten Feld kann sich die Einheit logischerweise weiter in ein nächstes Feld bewegen allerdings immer nur in 8 Richtungen. Wer sich so manches 2D Strategie-Spiel genau anschaut dem fällt sicher auf, dass es dort genauso ist.
Wir wollen zum Beispiel aus einer solchenso Karte,
eine "PathMap" erzeugen,
um zu wissen wie das Objekt auf die andere Seite kommt.
Wichtige Tastur Befehle des Beispiel Programmes(mit Quelltext):
- F1: Pathmap vor dem füllen anzeigen
- F2: Pathmap anzeigen
- F3: Draufsicht mit Gitter;
Aufbau des Beispiel-Programmes:
Alles wesentliche bis auf das Pathfinding befindt sich in der SpielFeldUnit. Hier haben wir unser Feld definiert.
TPlayer=(plnone,pl1,pl2,plNeutral); TFeld= object public Owner:TPlayer; end;
Und unser gesamtes Spielfeld welche einen Zweifachen Array davon enthält.
TSpielFeld=class(TPersistent)
private
FWidth:Word;
FHeight:Word;
procedure ZeichneSpielFeld;
procedure ZeichneEinheiten;
public
Feld: array of array of TFeld;
Einheit:array of TEinheit;
SelectedUnitIndex:Integer;
function ErstelleEinheit(const EinheitenTyp:TEinheitenTyp;const NewOwner:TPlayer;const XPos,YPos:Word):Boolean;
Die Größe davon spiegeln die Variablen FWidth und FHeight wieder. Außerdem sind hier, wie man sehen ebenfalls unsere Einheiten gespeichert. Die Variable SelectedUnitIndex , gibt an welche davon gerade ausgewählt wurde.
procedure Draw; procedure SetSize(NewWidth,NewHeight:Word); procedure Update;
SetSize benutzt man um die Größe zu ändern, dabei werden allerdings alle Einheiten gelöscht. Ruft man Draw auf so wird ZeichneSpielFeld und ZeichneEinheiten aufgerufen um alles zu zeichenen. Der regelmäßge Aufruf von Update sorgt dafür das sich überhaupt Bewegung ins Spiel kommt.
procedure Save(FileName:String); procedure Load(FileName:String); procedure FloodFill(Player:TPlayer); procedure OnSelection(Selected: Integer;Button: TMouseButton);
FloodFill stellt den Besitzer aller Felder auf den Angegebenen Spieler, und OnSelection wertet Selections-Ereignisse aus.
TBefehlsTyp=(BT_STAND,BT_MOVE);
TEinheitenTyp=Word;
TAnimation=record
Pos:Word;
Length:Word;
Typ:TAnimationType;
end;
TBefehl=record
Case Typ:TBefehlsTyp of
BT_STAND:();
BT_MOVE:(X,Y:Word);
end;
TEinheit=class
public
Ani:TAnimation;
Befehl:TBefehl;
X,Y:Word;
Owner:TPlayer;
Typ:TEinheitenTyp;
constructor Create(VomTyp:TEinheitenTyp;NewOwner:TPlayer;XPos,YPos:Word);overload;
Constructor Create;overload;
procedure Draw;
procedure Update;
function GetRealX:Double;
function GetRealY:Double;
end;
Eine Einheit ist normalerweise animiert und führt ürgend eine Animation aus. Alle Daten wie eine Einheit gerade zu Zeichnen(draw) ist, sind hier verwahrt. Die Funktionen GetRealX und GetRealY sorgen dafür das die Einheit abhänig von ihrer Animation und groben Position, an der richtigen Stelle gezeichnet werden. Die Funktion Update einer Einheit ist die Wichtigste da sie regelt welche Aktion und Animation die Einheit als nächstes machen soll.
procedure TEinheit.Update; begin Inc(Ani.Pos); if not((Ani.Pos >= Ani.Length) or (Ani.Typ = ANI_STAND))then exit;
Als erstes wird die Animantions Phase 1 weiter gestellt. Weitergemacht wird nur wenn die Einheit entweder eine Animtion abgeschlossen hat, oder nichts zu tun hat.
case Befehl.Typ of
BT_STAND:
begin
if (Ani.Pos >= Ani.Length) then Ani.Pos := 0;
Ani.Typ := ANI_STAND;
Ani.Length := 1000;
end;
Wenn die Einheit wirklich stehen soll dann wird höchstens die Animation Position mal zurückgesetzt.
BT_MOVE:
begin
if (X = Befehl.x) and (Y = Befehl.Y) then
begin //Ziel erreicht
Befehl.typ := BT_STAND ;
Ani.Pos := 0;
Ani.Typ := ANI_STAND;
Ani.length := 1000;
exit;
end;
Wenn die Einheit den Befehl hat sich zu bewegen, aber ihr Ziel schon erreicht hat, dann erhält sie Befehl zu stehen und wir sind fertig.
Ani.Pos := 0;
Ani.Typ :=FindPath(Befehl.X,Befehl.Y,self); ;//Hier muss der variante Teil hin
Ani.Length := 10;
case Ani.Typ of
ANI_MOVE_LEFT : X := X-1;
ANI_MOVE_Right: X := X+1;
ANI_MOVE_UP : Y := Y+1;
ANI_MOVE_DOWN : Y := Y-1;
ANI_MOVE_LEFTDOWN: begin X:= X-1; Y:= Y-1 end;
ANI_MOVE_RIGHTDOWN: begin X:= X+1; Y:= Y-1 end;
ANI_MOVE_LEFTUP: begin X:= X-1; Y:= Y+1 end;
ANI_MOVE_RIGHTUP: begin X:= X+1; Y:= Y+1 end;
end;
if SpielFeld.Feld[X,Y].Owner <> Owner then Ani.Length := Ani.Length*LangsamkeitsFaktor;
end;
end;
end;
Nun sind wir soweit gekommen das wir unser Einheit eine Animation zuweisen wollen, aber noch nicht wissen welche das sein soll. Daher rufen wir die function FindPath aus der Pathfinding8 Unit auf.
Die eigentliche Wegfindungs-Routine
Vorbereiten der "Pathmap"-Variable
Um dem Computer unser Level verständlich zu machen, wird in diese Variable:
Pathmap: array of array of Integer;
unser gesamtes Level übertragen.
Dabei beschreiben folgende Konstanten die einzelen Felder.
const Feld_ist_Ziel= 0; Feld_ist_gesperrt= -1; Feld_ist_frei= -8; Feld_ist_feindlich =-9; Feld_ist_StartFeld= -10;
Unsere Pathmap wird allerdings um 1 Feld in jede Richtung größer als unser SpielFeld sein. Dieser äußere Rand wird eine Art Abgrenzung für unser SpielFeld.
SetLength(Pathmap ,SpielFeld.width +2,SpielFeld.height +2);
for X := 0 to SpielFeld.Width +1 do
begin
Pathmap[X,0] := Feld_ist_Gesperrt;
Pathmap[X,SpielFeld.Height+1] := Feld_ist_Gesperrt;
end;
for Y := 0 to SpielFeld.Height +1 do
begin
Pathmap[0,Y] := Feld_ist_Gesperrt;
Pathmap[SpielFeld.width+1,Y] := Feld_ist_Gesperrt;
end;
Dann müssen wir natürlich noch unsere Felder eintragen.
for X := 0 to SpielFeld.Width-1 do
for Y := 0 to SpielFeld.Height-1 do
begin
if SpielFeld.Feld[X,Y].Owner = plneutral then Pathmap[X+1,Y+1] := Feld_ist_Gesperrt
else if SpielFeld.Feld[X,Y].Owner = TEinheit(Einheit).owner then
Pathmap[X+1,Y+1] := Feld_ist_Frei
else
Pathmap[X+1,Y+1] := Feld_ist_feindlich;
end;
Felder vom Spieler plneutral sollen in meinen Beispiel-Programm gesperrt sein. Andernfalls wird überprüft ob dass Feld vom Feind oder von uns Kontrolliert wird.
Natürlich dürfen alle Felder auf denen schon Einheiten stehen nicht betreten werden.
for X := 0 to High(SpielFeld.Einheit) do Pathmap[SpielFeld.Einheit[X].X+1,SpielFeld.Einheit[X].Y+1] := Feld_ist_Gesperrt ;
Nun müssen wir noch die Einheit eintragen, für die wir den Weg berechnen.
Pathmap[TEinheit(Einheit).X+1,TEinheit(Einheit).Y+1] := Feld_ist_StartFeld;
Jetzt müssen wir überprüfen, ob die Einheit vielleicht schon direkt vor dem Ziel, steht welches aber besetzt ist. Sollte dies so sein so sind wir fertig da wir nichts zu berechen haben.
if (Pathmap[ZielX+1,ZielY+1] = Feld_ist_Gesperrt)
and (Betrag(TEinheit(Einheit).X - ZielX) <= 1 )
and (Betrag(TEinheit(Einheit).Y -ZielY) <=1) then
begin
result := ANI_STAND;
exit;
end;
Ansonsten tragen wir unser Ziel in die Pathmap ein.
Pathmap[ZielX+1,ZielY+1] := Feld_ist_Ziel ;
Nun haben wir unsere Pathmap vorbereitet. Sie könnte nun so aussehen:
Datei:tutorial pathfinding Beispiel1-NewPathmap.png
Füllen der "Pathmap"
var Pathmap: array of array of Integer; x,y:Integer; Weg:Integer; LX,HX:Integer; LY,HY:Integer; Fertig:Boolean ;
Wir starten eine Schleife in der die Pathmap gefüllt wird:
Weg:= -1;//Weg+1=0
Fertig := false;
while not Fertig and (Weg < MAX_ENTFERNUNG) do
begin
Weg:=Weg+1;
Es ist Sinnvoll mit einen kleinen Füll-Breich anzufangen dieser wird durch LX, HX, LY, HY begrenzt.
LX := ZielX+1 -Weg-1;
HX := ZielX+1 +Weg+1;
LY := ZielY+1 -Weg-1;
HY := ZielY+1 +Weg+1;
if LX < 1 then LX := 1;
if LY < 1 then LY := 1;
if HX > SpielFeld.Width then HX :=SpielFeld.Width;
if HY > SpielFeld.Height then HY := SpielFeld.Height;
Nun prüfen wir jedes Feld im Füll-Bereich ob es an ein Feld angrenzt was den aktuellen Weg-Wert hat. Wir brauchen übrigens Felder die Gesperrt sind, oder schon einen positven besitzen nicht mehr beachten.
for X:= LX to HX do
for Y:= LY to HY do
if Pathmap[X,Y] <= Feld_ist_frei then
{Wenn das Feld noch nicht berechnet und begehbar ist}
if (Pathmap[x-1,y]=Weg)
or (Pathmap[x+1,y]=Weg)
or (Pathmap[x,y-1]=Weg)
or (Pathmap[x,y+1]=Weg)
or (Pathmap[x-1,y-1]=Weg)
or (Pathmap[x+1,y-1]=Weg)
or (Pathmap[x-1,y+1]=Weg)
or (Pathmap[x+1,y+1]=Weg) then
Normalerweise würden wir jetzt jedes Feld(außer es ist das Ziel) um 1 erhöhen da wir aber auch feindliche Felder haben, müssen wir diese auch noch beachten:
case Pathmap[X,Y] of
Feld_ist_feindlich:Pathmap[X,Y]:= Weg + LangsamkeitsFaktor;
Feld_ist_StartFeld:
begin
Fertig := true;
end;
else
{Feld_ist_frei:}
Pathmap[X,Y]:= Weg +1;
end;
end;
Ein Feld welches den Wert der Variable Weg + 1 hat, wird logischerweise im nächsten Durchlauf der Schleife den Wert der Variable Weg haben. Es wird dann die Bedinung des angrenzenden Feldes erfüllen. Dadurch ist auch klar warum das auf feindlichen Gebiet drei mal so lange dauert.... es dauer einfach 3 Runden statt 1 bis das Feld den gleichen Wert wie die Weg-Variable hat Es entsteht somit eine Außdehnung der Zahlen um das ZielFeld(Wert 0) herum. Jedes Feld das so eine postive Zahl erhalten hat bescheibt somit die Entfernung zum Ziel. Machen wir dass so lange bis wir das "StartFeld" mit einer Zahl überschreiben würden, so wäre diese Zahl die Entfernung zum Ziel.
Versuch doch mal sofort zu sagen ob die Einheit oben oder unten rum sich bewegen soll:
Datei:tutorial pathfinding Beispiel2-Spiel.png
Dank unser Pathmap ist viel einfacher wenn man weis wie es geht:
Datei:tutorial pathfinding Beispiel2-Pathmap.png
Richtige Animation auswählen
Nun braucht man sich nur noch das Feld suchen welches an StartFeld angrenzt und den Aktuellen Wert von Weg hat. Und entspechend die Animation wählen. (Das Feld welches die Überschreibung vom Ziel-Feld veranlast hätte)
X:= TEinheit(Einheit).X +1;
Y:= TEinheit(Einheit).Y +1;
if (Pathmap[X+1,Y] = Weg) then Result := ANI_MOVE_RIGHT
else if (Pathmap[X-1,Y] = Weg) then Result := ANI_MOVE_LEFT
else if (Pathmap[X,Y+1] = Weg) then Result := ANI_MOVE_UP
else if (Pathmap[X,Y-1] = Weg) then Result := ANI_MOVE_DOWN
else if (Pathmap[X-1,Y-1] = Weg) then Result := ANI_MOVE_LEFTDOWN
else if (Pathmap[X+1,Y-1] = Weg) then Result := ANI_MOVE_RIGHTDOWN
else if (Pathmap[X-1,Y+1] = Weg) then Result := ANI_MOVE_LEFTUP
else if (Pathmap[X+1,Y+1] = Weg) then Result := ANI_MOVE_RIGHTUP
else Result := ANI_STAND;
end;
Ich hoffe mein Tutorial, hat euch gefallen und ihr könnt damit ürgendetwas anfangen.
Euer Flo
