Tutorial Pathfinding: Unterschied zwischen den Versionen

Version vom 24. November 2005, 17:27 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 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"