Tutorial Pathfinding

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.

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,

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, 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 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:

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:

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

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

• Beispiel Delphi-VCL-Quelltext und Windows-Binaries

Vorhergehendes Tutorial: -	Zur Übersicht	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.