Tutorial Pathfinding: Unterschied zwischen den Versionen

Aus DGL Wiki
Wechseln zu: Navigation, Suche
K (Richtige Animation auswählen)
K (Daß -> Dass)
 
(13 dazwischenliegende Versionen von 4 Benutzern werden nicht angezeigt)
Zeile 6: Zeile 6:
 
Jedes dieser Felder wird für die Wegberechnung erstmal vereinfacht, in dem davon ausgegangen wird,
 
Jedes dieser Felder wird für die Wegberechnung erstmal vereinfacht, in dem davon ausgegangen wird,
 
das ein Feld entweder begehbar ist, oder nicht.
 
das ein Feld entweder begehbar ist, oder nicht.
(Oder sogar Felder haben die zwar begehbar sind aber gemieden werden solten.)
+
(Oder sogar Felder haben die zwar begehbar sind aber gemieden werden sollten.)
  
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.
+
Nun wird weiter davon ausgegangen, dass eine Einheit von einem Feld nur in 8 (bzw. 4) Richtungen, nämlich in die 8 (4) benachbarten Felder bewegen kann.
  
 
[[Bild:Tutorial_pathfinding_BewegungsRichtungen.png]]
 
[[Bild:Tutorial_pathfinding_BewegungsRichtungen.png]]
  
Von dem nächsten Feld kann sich die Einheit logischerweise weiter in ein nächstes Feld bewegen allerdings immer nur in 8 Richtungen.
+
Von dem Feld kann sich die Einheit logischerweise weiter in ein nächstes Feld bewegen, allerdings - wie schon erklärt - immer nur in 8 Richtungen.
 
Wer sich so manches 2D Strategie-Spiel genau anschaut dem fällt sicher auf, dass es dort genauso ist.
 
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,
+
Wir wollen zum Beispiel aus einer solchen Karte,
  
 
[[Bild:Tutorial_pathfinding_Beispiel1-Spiel.png]]
 
[[Bild:Tutorial_pathfinding_Beispiel1-Spiel.png]]
Zeile 23: Zeile 23:
 
[[Bild:Tutorial_pathfinding_Beispiel1-Pathmap.png]]
 
[[Bild:Tutorial_pathfinding_Beispiel1-Pathmap.png]]
  
um zu wissen wie das Objekt auf die andere Seite kommt.
+
um zu wissen, wie das Objekt auf die andere Seite kommt.
  
Wichtige Tastur Befehle des [http://www.delphigl.com/res/tutorials/pathfinding/http://www.delphigl.com/do_download.php?f=5225 Beispiel Programmes(mit Quelltext)]:
+
Wichtige Tastur Befehle des [http://www.delphigl.com/do_download.php?f=5225 Beispiel Programmes(mit Quelltext)]:
  
*'''F1''': Pathmap vor dem füllen anzeigen
+
*'''F1''': Pathmap vor dem Füllen anzeigen
 
*'''F2''': Pathmap anzeigen
 
*'''F2''': Pathmap anzeigen
 
*'''F3''': Draufsicht mit Gitter;
 
*'''F3''': Draufsicht mit Gitter;
Zeile 33: Zeile 33:
 
Aufbau des Beispiel-Programmes:
 
Aufbau des Beispiel-Programmes:
  
Alles wesentliche bis auf das Pathfinding befindt sich in der SpielFeldUnit.
+
Alles wesentliche, bis auf das Pathfinding, befindet sich in der SpielFeldUnit.
 
Hier haben wir unser Feld definiert.
 
Hier haben wir unser Feld definiert.
  
<pascal>
+
<source lang="pascal"> TPlayer=(plnone,pl1,pl2,plNeutral);
  TPlayer=(plnone,pl1,pl2,plNeutral);
 
 
 
 
   TFeld= object
 
   TFeld= object
 
   public
 
   public
  Owner:TPlayer;
+
    Owner:TPlayer;
 
   end;
 
   end;
</pascal>
+
</source>
  
Und unser gesamtes Spielfeld welche einen Zweifachen Array davon enthält.
+
Und unser gesamtes Spielfeld, welches einen zweifachen Array davon enthält.
  
<pascal>
+
<source lang="pascal"> TSpielFeld=class(TPersistent)
  TSpielFeld=class(TPersistent)
 
 
   private
 
   private
 
     FWidth:Word;
 
     FWidth:Word;
Zeile 59: Zeile 56:
 
     SelectedUnitIndex:Integer;
 
     SelectedUnitIndex:Integer;
 
     function ErstelleEinheit(const EinheitenTyp:TEinheitenTyp;const NewOwner:TPlayer;const XPos,YPos:Word):Boolean;
 
     function ErstelleEinheit(const EinheitenTyp:TEinheitenTyp;const NewOwner:TPlayer;const XPos,YPos:Word):Boolean;
</pascal>
+
</source>
  
Die Größe davon spiegeln die Variablen FWidth und FHeight wieder.
+
Die Größe davon spiegeln die Variablen FWidth und FHeight wider.
Außerdem sind hier, wie man sehen ebenfalls unsere Einheiten gespeichert.
+
Außerdem sind hier, wie man sehen kann, ebenfalls unsere Einheiten gespeichert.
Die Variable SelectedUnitIndex , gibt an welche davon gerade ausgewählt wurde.
+
Die Variable SelectedUnitIndex gibt an, welche davon gerade ausgewählt wurde.
  
<pascal>
+
<source lang="pascal">   procedure Draw;
  procedure Draw;
 
 
   procedure SetSize(NewWidth,NewHeight:Word);
 
   procedure SetSize(NewWidth,NewHeight:Word);
 
   procedure Update;
 
   procedure Update;
</pascal>
+
</source>
  
 
SetSize benutzt man um die Größe zu ändern, dabei werden allerdings alle Einheiten gelöscht.
 
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.
+
Ruft man Draw auf so wird ZeichneSpielFeld und ZeichneEinheiten aufgerufen um alles zu zeichnen.
Der regelmäßge Aufruf von Update sorgt dafür das sich überhaupt Bewegung ins Spiel kommt.
+
Der regelmäßge Aufruf von Update sorgt dafür, das überhaupt Bewegung ins Spiel kommt.
  
<pascal>
+
<source lang="pascal">   procedure Save(FileName:String);
  procedure Save(FileName:String);
 
 
   procedure Load(FileName:String);
 
   procedure Load(FileName:String);
 
   procedure FloodFill(Player:TPlayer);
 
   procedure FloodFill(Player:TPlayer);
 
   procedure OnSelection(Selected: Integer;Button: TMouseButton);
 
   procedure OnSelection(Selected: Integer;Button: TMouseButton);
</pascal>
+
</source>
  
FloodFill stellt den Besitzer aller Felder auf den Angegebenen Spieler,  
+
FloodFill stellt den Besitzer aller Felder auf den angegebenen Spieler,  
 
und OnSelection wertet Selections-Ereignisse aus.
 
und OnSelection wertet Selections-Ereignisse aus.
  
<pascal>
+
<source lang="pascal"> TBefehlsTyp=(BT_STAND,BT_MOVE);
  TBefehlsTyp=(BT_STAND,BT_MOVE);
 
 
   TEinheitenTyp=Word;
 
   TEinheitenTyp=Word;
  
Zeile 115: Zeile 109:
 
     function GetRealY:Double;
 
     function GetRealY:Double;
 
   end;
 
   end;
</pascal>
+
</source>
  
Eine Einheit ist normalerweise animiert und führt ürgend eine Animation aus.
+
Eine Einheit ist normalerweise animiert und führt irgend eine Animation aus.
Alle Daten wie eine Einheit gerade zu Zeichnen(draw) ist, sind hier verwahrt.
+
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 Funktionen GetRealX und GetRealY sorgen dafür, dass die Einheit abhängig von ihrer Animation und groben Position, an der richtigen Stelle gezeichnet wird.
Die Funktion Update einer Einheit ist die Wichtigste da sie regelt welche Aktion und Animation die Einheit als nächstes machen soll.
+
Die Funktion Update einer Einheit ist die Wichtigste, da sie regelt, welche Aktion und Animation die Einheit als nächstes machen soll.
  
<pascal>
+
<source lang="pascal">procedure TEinheit.Update;
procedure TEinheit.Update;
 
 
begin
 
begin
 
   Inc(Ani.Pos);
 
   Inc(Ani.Pos);
 
   if not((Ani.Pos >= Ani.Length) or (Ani.Typ = ANI_STAND))then exit;
 
   if not((Ani.Pos >= Ani.Length) or (Ani.Typ = ANI_STAND))then exit;
</pascal>
+
</source>
  
Als erstes wird die Animantions Phase 1 weiter gestellt.
+
Als erstes wird die Animations-Phase 1 weiter gestellt.
Weitergemacht wird nur wenn die Einheit entweder eine Animtion abgeschlossen hat, oder nichts zu tun hat.
+
Weitergemacht wird nur, wenn die Einheit entweder eine Animation abgeschlossen hat, oder nichts zu tun hat.
  
<pascal>
+
<source lang="pascal"> case Befehl.Typ of
  case Befehl.Typ of
 
 
     BT_STAND:
 
     BT_STAND:
 
     begin
 
     begin
Zeile 140: Zeile 132:
 
       Ani.Length := 1000;
 
       Ani.Length := 1000;
 
     end;
 
     end;
</pascal>
+
</source>
  
Wenn die Einheit wirklich stehen soll dann wird höchstens die Animation Position mal zurückgesetzt.
+
Wenn die Einheit wirklich stehen soll, wird höchstens die Animations-Position mal zurückgesetzt.
<pascal>
+
<source lang="pascal">   BT_MOVE:
    BT_MOVE:
 
 
     begin
 
     begin
 
       if (X = Befehl.x) and (Y = Befehl.Y) then
 
       if (X = Befehl.x) and (Y = Befehl.Y) then
Zeile 154: Zeile 145:
 
         exit;
 
         exit;
 
       end;
 
       end;
</pascal>
+
</source>
  
 
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.
 
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.
  
<pascal>
+
<source lang="pascal">     Ani.Pos := 0;
    Ani.Pos := 0;
 
 
     Ani.Typ :=FindPath(Befehl.X,Befehl.Y,self);  ;//Hier muss der variante Teil hin
 
     Ani.Typ :=FindPath(Befehl.X,Befehl.Y,self);  ;//Hier muss der variante Teil hin
 
     Ani.Length := 10;
 
     Ani.Length := 10;
Zeile 177: Zeile 167:
 
   end;
 
   end;
 
end;
 
end;
</pascal>
+
</source>
  
 
Nun sind wir soweit gekommen das wir unser Einheit eine Animation zuweisen wollen, aber noch nicht wissen welche das sein soll.
 
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.
+
Daher rufen wir die function FindPath aus der Pathfinding Unit auf.
  
 
==Die eigentliche Wegfindungs-Routine==
 
==Die eigentliche Wegfindungs-Routine==
Zeile 188: Zeile 178:
 
Um dem Computer unser Level verständlich zu machen, wird in diese Variable:
 
Um dem Computer unser Level verständlich zu machen, wird in diese Variable:
  
<pascal>
+
<source lang="pascal">
 
Pathmap: array of array of Integer;
 
Pathmap: array of array of Integer;
</pascal>
+
</source>
  
 
unser gesamtes Level übertragen.
 
unser gesamtes Level übertragen.
  
Dabei beschreiben folgende Konstanten die einzelen Felder.
+
Dabei beschreiben folgende Konstanten die einzelnen Felder.
  
<pascal>
+
<source lang="pascal">
 
const
 
const
 
   Feld_ist_Ziel= 0;
 
   Feld_ist_Ziel= 0;
Zeile 203: Zeile 193:
 
   Feld_ist_feindlich =-9;
 
   Feld_ist_feindlich =-9;
 
   Feld_ist_StartFeld= -10;
 
   Feld_ist_StartFeld= -10;
</pascal>
+
</source>
 
Unsere Pathmap wird allerdings um 1 Feld in jede Richtung größer als unser SpielFeld sein.
 
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.
 
Dieser äußere Rand wird eine Art Abgrenzung für unser SpielFeld.
  
<pascal>
+
<source lang="pascal">
 
   SetLength(Pathmap ,SpielFeld.width +2,SpielFeld.height +2);
 
   SetLength(Pathmap ,SpielFeld.width +2,SpielFeld.height +2);
 
   for X := 0 to SpielFeld.Width +1 do
 
   for X := 0 to SpielFeld.Width +1 do
Zeile 219: Zeile 209:
 
     Pathmap[SpielFeld.width+1,Y] := Feld_ist_Gesperrt;
 
     Pathmap[SpielFeld.width+1,Y] := Feld_ist_Gesperrt;
 
   end;
 
   end;
</pascal>
+
</source>
  
 
Dann müssen wir natürlich noch unsere Felder eintragen.
 
Dann müssen wir natürlich noch unsere Felder eintragen.
  
<pascal>
+
<source lang="pascal">
 
   for X := 0 to SpielFeld.Width-1 do
 
   for X := 0 to SpielFeld.Width-1 do
 
   for Y := 0 to SpielFeld.Height-1 do
 
   for Y := 0 to SpielFeld.Height-1 do
Zeile 233: Zeile 223:
 
     Pathmap[X+1,Y+1] := Feld_ist_feindlich;
 
     Pathmap[X+1,Y+1] := Feld_ist_feindlich;
 
   end;
 
   end;
</pascal>
+
</source>
  
 
Felder vom Spieler plneutral sollen in meinen Beispiel-Programm gesperrt sein.
 
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.
+
Andernfalls wird überprüft ob das Feld vom Feind oder von uns kontrolliert wird.
  
Natürlich dürfen alle Felder auf denen schon Einheiten stehen nicht betreten werden.
+
Natürlich dürfen alle Felder, auf denen schon Einheiten stehen, nicht betreten werden.
  
<pascal>
+
<source lang="pascal">
 
   for X := 0 to High(SpielFeld.Einheit) do
 
   for X := 0 to High(SpielFeld.Einheit) do
 
   Pathmap[SpielFeld.Einheit[X].X+1,SpielFeld.Einheit[X].Y+1] := Feld_ist_Gesperrt ;
 
   Pathmap[SpielFeld.Einheit[X].X+1,SpielFeld.Einheit[X].Y+1] := Feld_ist_Gesperrt ;
</pascal>
+
</source>
  
 
Nun müssen wir noch die Einheit eintragen, für die wir den Weg berechnen.
 
Nun müssen wir noch die Einheit eintragen, für die wir den Weg berechnen.
  
<pascal>
+
<source lang="pascal">
 
   Pathmap[TEinheit(Einheit).X+1,TEinheit(Einheit).Y+1] := Feld_ist_StartFeld;
 
   Pathmap[TEinheit(Einheit).X+1,TEinheit(Einheit).Y+1] := Feld_ist_StartFeld;
</pascal>
+
</source>
  
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.  
+
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.  
  
<pascal>
+
<source lang="pascal">
 
   if  (Pathmap[ZielX+1,ZielY+1] = Feld_ist_Gesperrt)
 
   if  (Pathmap[ZielX+1,ZielY+1] = Feld_ist_Gesperrt)
 
   and (Betrag(TEinheit(Einheit).X - ZielX) <= 1 )
 
   and (Betrag(TEinheit(Einheit).X - ZielX) <= 1 )
Zeile 261: Zeile 251:
 
     exit;
 
     exit;
 
   end;
 
   end;
</pascal>
+
</source>
  
 
Ansonsten tragen wir unser Ziel in die Pathmap ein.
 
Ansonsten tragen wir unser Ziel in die Pathmap ein.
<pascal>
+
<source lang="pascal">
 
   Pathmap[ZielX+1,ZielY+1] := Feld_ist_Ziel ;
 
   Pathmap[ZielX+1,ZielY+1] := Feld_ist_Ziel ;
</pascal>
+
</source>
  
 
Nun haben wir unsere Pathmap vorbereitet.
 
Nun haben wir unsere Pathmap vorbereitet.
 
Sie könnte nun so aussehen:
 
Sie könnte nun so aussehen:
  
[[Bild:tutorial_pathfinding_Beispiel1-NewPathmap.png]]
+
[[Bild:Tutorial_pathfinding_Beispiel1-NewPathmap.png]]
  
 
=== Füllen der "Pathmap" ===
 
=== Füllen der "Pathmap" ===
  
<pascal>
+
<source lang="pascal">
 
var
 
var
 
   Pathmap: array of array of Integer;
 
   Pathmap: array of array of Integer;
Zeile 283: Zeile 273:
 
   LY,HY:Integer;
 
   LY,HY:Integer;
 
   Fertig:Boolean ;
 
   Fertig:Boolean ;
</pascal>
+
</source>
  
 
Wir starten eine Schleife in der die Pathmap gefüllt wird:
 
Wir starten eine Schleife in der die Pathmap gefüllt wird:
  
<pascal>
+
<source lang="pascal">
 
   Weg:= -1;//Weg+1=0
 
   Weg:= -1;//Weg+1=0
 
   Fertig := false;
 
   Fertig := false;
Zeile 293: Zeile 283:
 
   begin
 
   begin
 
     Weg:=Weg+1;
 
     Weg:=Weg+1;
</pascal>
+
</source>
  
Es ist Sinnvoll mit einen kleinen Füll-Breich anzufangen dieser wird durch LX, HX, LY, HY begrenzt.
+
Es ist sinnvoll, mit einen kleinen Füll-Breich anzufangen. Dieser wird durch LX, HX, LY, HY begrenzt.
  
<pascal>
+
<source lang="pascal">
 
     LX := ZielX+1 -Weg-1;
 
     LX := ZielX+1 -Weg-1;
 
     HX := ZielX+1 +Weg+1;
 
     HX := ZielX+1 +Weg+1;
Zeile 307: Zeile 297:
 
     if HX > SpielFeld.Width then HX :=SpielFeld.Width;
 
     if HX > SpielFeld.Width then HX :=SpielFeld.Width;
 
     if HY > SpielFeld.Height then HY := SpielFeld.Height;
 
     if HY > SpielFeld.Height then HY := SpielFeld.Height;
</pascal>
+
</source>
  
Nun prüfen wir jedes Feld im Füll-Bereich ob es an ein Feld angrenzt was den aktuellen Weg-Wert hat.
+
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.
+
Wir brauchen übrigens Felder die gesperrt sind oder bereits einen positven Wert besitzen nicht mehr beachten.
  
<pascal>
+
<source lang="pascal">
 
     for X:= LX to HX do
 
     for X:= LX to HX do
 
     for Y:= LY to HY do
 
     for Y:= LY to HY do
Zeile 326: Zeile 316:
 
     or (Pathmap[x-1,y+1]=Weg)
 
     or (Pathmap[x-1,y+1]=Weg)
 
     or (Pathmap[x+1,y+1]=Weg)  then
 
     or (Pathmap[x+1,y+1]=Weg)  then
</pascal>
+
</source>
  
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:
+
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:
  
<pascal>
+
<source lang="pascal">
 
     case Pathmap[X,Y] of
 
     case Pathmap[X,Y] of
  
Zeile 343: Zeile 333:
 
     end;
 
     end;
 
   end;
 
   end;
</pascal>
+
</source>
  
Ein Feld welches den Wert der Variable Weg + 1 hat,  
+
Ein Feld, welches den Wert der Variable Weg + 1 hat,  
 
wird logischerweise im nächsten Durchlauf der Schleife den Wert der Variable Weg haben.
 
wird logischerweise im nächsten Durchlauf der Schleife den Wert der Variable Weg haben.
Es wird dann die Bedinung des angrenzenden Feldes erfüllen.
+
Es wird dann die Bedingung 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
+
Dadurch ist auch klar, warum das auf feindlichem Gebiet drei mal so lange dauert.... es dauert 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.
+
Es entsteht somit eine Ausdehnung der Zahlen um das ZielFeld (Wert 0) herum.
Jedes Feld das so eine postive Zahl erhalten hat bescheibt somit die Entfernung zum Ziel.
+
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.
+
Machen wir das 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:
+
Versuch doch mal sofort zu sagen, ob sich die Einheit oben oder unten rum bewegen soll:
  
[[Bild:tutorial_pathfinding_Beispiel2-Spiel.png]]
+
[[Bild:Tutorial_pathfinding_Beispiel2-Spiel.png]]
  
 
Dank unser Pathmap ist viel einfacher wenn man weis wie es geht:
 
Dank unser Pathmap ist viel einfacher wenn man weis wie es geht:
  
[[Bild:tutorial_pathfinding_Beispiel2-Pathmap.png]]
+
[[Bild:Tutorial_pathfinding_Beispiel2-Pathmap.png]]
  
 
=== Richtige Animation auswählen ===
 
=== Richtige Animation auswählen ===
  
Nun braucht man sich nur noch das Feld suchen welches an StartFeld angrenzt und den Aktuellen Wert von Weg hat.
+
Nun braucht man sich nur noch das Feld suchen, welches an StartFeld angrenzt, den aktuellen Wert von Weg hat und entspechend die Animation wählen (das Feld, welches die Überschreibung vom Ziel-Feld veranlaßt hätte).
Und entspechend die Animation wählen.
 
(Das Feld welches die Überschreibung vom Ziel-Feld veranlast hätte)
 
  
<pascal>
+
<source lang="pascal">
 
   X:= TEinheit(Einheit).X +1;
 
   X:= TEinheit(Einheit).X +1;
 
   Y:= TEinheit(Einheit).Y +1;
 
   Y:= TEinheit(Einheit).Y +1;
Zeile 383: Zeile 371:
 
   else Result := ANI_STAND;
 
   else Result := ANI_STAND;
 
end;
 
end;
</pascal>
+
</source>
  
  
Ich hoffe mein Tutorial, hat euch gefallen und ihr könnt damit ürgendetwas anfangen.
+
Ich hoffe, mein Tutorial hat euch gefallen und ihr könnt damit irgendetwas anfangen.
  
 
Euer [[Benutzer:Flo|Flo]]
 
Euer [[Benutzer:Flo|Flo]]
 +
 +
 +
== Dateien ==
 +
* {{ArchivLink|file=tut_pathfinding_vcl|text=Beispiel Delphi-VCL-Quelltext und Windows-Binaries}}
 +
 +
{{TUTORIAL_NAVIGATION|-|[[Tutorial_pathfinding2]]}}
 +
 +
[[Kategorie:Tutorial|Pathfinding]]

Aktuelle Version vom 18. März 2012, 16:58 Uhr

Wilkommen zu meinen Tutorial zum Pathfinding.

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 sollten.)

Nun wird weiter davon ausgegangen, dass eine Einheit von einem Feld nur in 8 (bzw. 4) Richtungen, nämlich in die 8 (4) benachbarten Felder bewegen kann.

Tutorial pathfinding BewegungsRichtungen.png

Von dem Feld kann sich die Einheit logischerweise weiter in ein nächstes Feld bewegen, allerdings - wie schon erklärt - 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 solchen Karte,

Tutorial pathfinding Beispiel1-Spiel.png

eine "PathMap" erzeugen,

Tutorial pathfinding Beispiel1-Pathmap.png

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, befindet 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, welches 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 wider. Außerdem sind hier, wie man sehen kann, 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 zeichnen. Der regelmäßge Aufruf von Update sorgt dafür, das ü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 irgend eine Animation aus. Alle Daten, wie eine Einheit gerade zu Zeichnen(draw) ist, sind hier verwahrt. Die Funktionen GetRealX und GetRealY sorgen dafür, dass die Einheit abhängig von ihrer Animation und groben Position, an der richtigen Stelle gezeichnet wird. 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 Animations-Phase 1 weiter gestellt. Weitergemacht wird nur, wenn die Einheit entweder eine Animation 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, wird höchstens die Animations-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 Pathfinding 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 einzelnen 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 das 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:

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 bereits einen positven Wert 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 Bedingung des angrenzenden Feldes erfüllen. Dadurch ist auch klar, warum das auf feindlichem Gebiet drei mal so lange dauert.... es dauert einfach 3 Runden statt 1 bis das Feld den gleichen Wert wie die Weg-Variable hat Es entsteht somit eine Ausdehnung 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 das 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 sich die Einheit oben oder unten rum bewegen soll:

Tutorial pathfinding Beispiel2-Spiel.png

Dank unser Pathmap ist viel einfacher wenn man weis wie es geht:

Tutorial pathfinding Beispiel2-Pathmap.png

Richtige Animation auswählen

Nun braucht man sich nur noch das Feld suchen, welches an StartFeld angrenzt, den aktuellen Wert von Weg hat und entspechend die Animation wählen (das Feld, welches die Überschreibung vom Ziel-Feld veranlaßt 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 irgendetwas anfangen.

Euer Flo


Dateien


Vorhergehendes Tutorial:
-
Nächstes Tutorial:
Tutorial_pathfinding2

Schreibt was ihr zu diesem Tutorial denkt ins Feedbackforum von DelphiGL.com.
Lob, Verbesserungsvorschläge, Hinweise und Tutorialwünsche sind stets willkommen.