Einzelnen Beitrag anzeigen

Edlmann

Registriert seit: 19. Nov 2010
212 Beiträge
 
#1

Mal wieder AStar - und seine Tücken

  Alt 11. Jan 2011, 19:53
Guten Abend liebe DP, ich arbeite im Moment an einer Wegfindung zu einem simplen (wohl doch nicht so simplen) 2D-Shooter, mit dem ich mich
in OpenGL und die Wegfindung einarbeiten wollte. Der OpenGL-part funktioniert mittlerweile soweit, doch bei der Pfadfindung scheitere ich.
Ich wollte den AStar-Algorithmus benutzen, da dieser eigentlich DER Wegfindungsalgorithmus zu seien scheint. Das Prinzip dahinter habe ich schon verstanden,
mein Problem ist aber, dies in eine Klasse zu integrieren.

Die Wegfindung sieht bisher wie folgt aus:

Delphi-Quellcode:
//Sucht die Zelle mit dem niedrigstem Wert um den Punkt X, Y
function TGegner.FindLowest(X, Y: Integer) : TPoint;
var xx, yy, low, lowx, lowy: Integer;
begin
    low := Map_AStar[x,y];
   for xx := -1 to 1 do
     for yy := -1 to 1 do
     if not((xx <> 0) and (yy <> 0)) then
        if (Map_AStar[x+xx,y+yy] < Low) and (Map_AStar[x+xx,y+yy] > 0) and (xx <> yy) then
        begin
        Low := Map_AStar[x+xx,y+yy];
        LowX := x+xx;
        LowY := Y+yy;
        end;
   Result.X := LowX;
   Result.Y := LowY;
end;

//Füllt alle (direkten) Nachbarn, die ungleich 0 sind, mit einer bestimmten Zahl
procedure TGegner.FillNachbarn(X, Y: Integer; Value: Integer);
var xx, yy: Integer;
begin
   for xx := -1 to 1 do
     for yy := -1 to 1 do
        if not((xx <> 0) and (yy <> 0)) and (Map_AStar[xx + x, yy + y] = 0) then
          Map_AStar[xx + x, yy + y] := Value;
end;

//Findet einen Pfad von der angegebenen Position zu dem Gegner
procedure TGegner.FindPath(AX, AY: Integer);
var n, x, y: Integer;
begin
    for x := 0 to Form1.ClientWidth div TileSize do
      for y := 0 to Form1.ClientHeight div TileSize do
        Map_AStar[x,y] := Map[x,y];
   SetLength(Path, 1);
   FillNachBarn(AX, AY, 1);
   n := 1;
   repeat
    for x := 0 to Form1.ClientWidth div TileSize do
      for y := 0 to Form1.ClientHeight div TileSize do
      if Map_AStar[x, y] = n then
         FillNachbarn(x, y, n+1);
    inc(n);
   until Map_AStar[WallX,WallY] <> 0;
   x := SX;
   y := SY;
   n := 0;
   repeat
    SetLength(Path, n+1);
    Path[n].X := FindLowest(x, y).X;
    Path[n].Y := FindLowest(x, y).Y;
    x := Path[n].X;
    y := Path[n].Y;
    inc(n);
   //ShowMessage(IntToStr(X) + ' : ' + IntToSTr(Y) + ' : ' + IntToSTr(n));
   until (Map_Astar[x, y] = 1) or (n >= 100);
   if n < 100 then
   begin
   Path[Length(Path)].X := AX;
   Path[Length(Path)].Y := AY;
   PathPosition := 0;
   end
   else
   ShowMessage('Kein Pfad gefunden');
end;
Wobei hier Map ein 2D-Array vom Typ Integer ist, indem steht ob ein Feld eine Wand oder eben keine Wand ist, und Map_AStar ist dieses Array vom Algorhytmus aufbearbeitet. Theoretisch funktioniert das schon soweit, allerdings bewegt sich mein Gegner noch nicht dahin wo er soll, und die Wegfindung führt hin und wieder zu Zugriffsverletzungen.
Ich habe den Quelltext mal angehängt, ich hoffe einer von euch kann mir helfen.

Lg und schönen Abend,
Edlmann
Angehängte Dateien
Dateityp: rar AStar-Selfmade.rar (198,6 KB, 12x aufgerufen)
  Mit Zitat antworten Zitat