Tutorial Pathfinding: Unterschied zwischen den Versionen

Aus DGL Wiki
Wechseln zu: Navigation, Suche
K (Richtige Animation auswählen)
(Geeignete Welten)
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/res/tutorials/pathfinding/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.
  
Zeile 45: Zeile 45:
 
</pascal>
 
</pascal>
  
Und unser gesamtes Spielfeld welche einen Zweifachen Array davon enthält.
+
Und unser gesamtes Spielfeld, welches einen zweifachen Array davon enthält.
  
 
<pascal>
 
<pascal>
Zeile 61: Zeile 61:
 
</pascal>
 
</pascal>
  
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>
 
<pascal>
Zeile 72: Zeile 72:
  
 
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>
 
<pascal>
Zeile 82: Zeile 82:
 
</pascal>
 
</pascal>
  
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.
  
Zeile 117: Zeile 117:
 
</pascal>
 
</pascal>
  
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, daß 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>
 
<pascal>
Zeile 129: Zeile 129:
 
</pascal>
 
</pascal>
  
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>
 
<pascal>
Zeile 142: Zeile 142:
 
</pascal>
 
</pascal>
  
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>
 
<pascal>
 
     BT_MOVE:
 
     BT_MOVE:
Zeile 180: Zeile 180:
  
 
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==

Version vom 26. November 2005, 22:01 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, daß 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 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 irgendetwas anfangen.

Euer Flo