Mal wieder AStar - und seine Tücken

[Edlmann]

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

[Deep-Sea]

Also zuerst einmal hast du ein Speicherleck in der Funktion DrawMap. Du erzeugst ständig eine TBitmap aber gibst sie nie wieder frei. Ändere das also schon mal so ab:

Delphi-Quellcode:

begin
  Bild := TBitmap.Create;
  try
    // Mach was mit "Bild".
  finally
    Bild.Free;
  end;
end;

[Edit1]
Zum Fehlerhaften bewegen:
In Unit1 hast du angegeben, dass die Feldgröße 40 Pixel beträgt, in der Unit Zombie aber nur 25. Das wird dann natürlich nix, wenn du eine Konstante zwei mal an Unterschiedlichen stellen deklarierst und ihr verschiedene Werte zu weißt.


[Edit2]
Zur AV:
In der Funktion FindPath steht ja folgendes:

Delphi-Quellcode:

   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);

Die Variable x enthält des öfteren extrem hohe Werte, so das du versuchst auf ein Element im Array Map_Astar zuzugreifen, was nicht existiert. Warum genau x solche Werte enthält? Da bin ich jetzt zu faul zum suchen für *gg*


Alles in allem aber nichts, was man nicht in kurzer Zeit mit wenig Auffand hätte selbst finden können :wink:

[Edlmann]

Mmh...werd ich mir mal anschauen, allerdings erklärt keiner dieser Fehler, warum sich das Programm hin und wieder komplett verabschiedet und
den Rechner mit ins Nirvana nimmt...hatte es jetzt schon zwei mal, dass sich mein kompletter Rechner bei der Pfadfindung aufgehangen hat, und zwar so weit,
dass nichtmal mehr windows task-manager zu erreichen war...Warum X manchmal so hohe Werte enthält werde ich mir mal anschauen, vielen Dank schonmal...
und dass mit der Rechteckgröße...*Autsch* hätt mal nicht nur in der Gegner Unit nach dem Fehler suchen sollen ^^

[Edit]
Okey, die falsche Konstante war Schuld an der chaotischen Bewegung des Gegners.

Und die Pfadfindung führte manchmal zur Zugriffsverletzung, weil an einer Stelle noch alte Konstanten (die ich zur Entwicklung des AStar-Algorythmus benutzt habe)
übergeblieben waren und nicht durch die Gegner-spezifischen Variablen ersetzt waren...

Und das X so extrem hohe Werte enthält, lag daran, dass ich die beiden Variablen lowx und lowy nicht initialisiert habe...
Okey, nächstmal 15 mal, nicht nur 5mal durch den Quelltext schauen und Fehler suchen...und überall suchen ^^
danke für den Denkanstoß Deep-Sea
[/Edit]

[Deep-Sea]

Wenn der Arbeitsspeicher voll ist, dann erklärt das evtl. schon, warum dein ganzes System nicht mehr so mag wie du es gerne hättest :wink:
Tipp: Deklariere nur EINE Konstante und nicht zwei dafür (oder mach die Zuweisung wenigstens so: "Konstante2 = Konstante1").

(Des weiteren gehen die Tipps was das Entwickeln von Spielen angeht hier meistens dazu zu raten, die Logik (in deinem Fall also wohl die Unit Zombie) von der Grafikausgabe zu trennen. Aber das ist ggf. ein anderes Thema.)

[DeddyH]

Zitat:

Zitat von Deep-Sea (Beitrag 1074105)

Des weiteren gehen die Tipps was das Entwickeln von Spielen angeht hier meistens dazu zu raten, die Logik (in deinem Fall also wohl die Unit Zombie) von der Grafikausgabe zu trennen.

Was ja nicht nur für Spiele gilt ;)

[Edlmann]

Das ist im aktuellem Spiel getrennt, die Logik läuft über einen Timer, die Ausgaben über die Funktion Application.OnIdle ;)
und ich habe die zweite Konstante gelöscht, war auch eigentlich nicht geplant da zwei raus zu machen...sinds aber iwie geworden ^^

Danke nochmal,
Edlmann