Stack Überlaufen in einer Rekursion

[DirectFromHell]

Hallo,

ich versuche mich gerade an einem MineSweeper Klon (Die Frage passt trotzdem nicht in den Mulimedia Bereich). Jetzt bekomme ich wenn ich leere Felder aufdecken will einen Stack Überlauf. Ich benutzte eine Rekursive Prozedur um alle aufzudecken. Jetzt kommen ja solche Stack Überlaufungen ja eigentlich nur bei Endlosschleifen, und nicht einfach bei solch Rekursiven PR's. Also ich hoffe, dass ihr vielleicht aus dem Code sehen könnt warum ich diesen Fehler bekomme. Ich bin mit meinem Latein am Ende :gruebel:.

Delphi-Quellcode:

PROCEDURE TForm1.GetArea(x,y: Integer);
BEGIN (* PROC TForm1.GetArea *)
  field[x,y].hidden := false;
  field[x,y].q := false;
  IF field[x,y].Index = 14 THEN // 14 steht für ein leeres Feld, d.h. die umliegenden müssen aufgedeckt werden
  BEGIN (* IF field[x,y].Index = 14 *)
    IF (x>0) AND (y>0) THEN
      GetArea (x-1, y-1);
    IF x > 0 THEN
      GetArea (x-1, y);
    IF y > 0 THEN
      GetArea (x, y-1);
    IF x < 9 THEN
      GetArea (x+1, y);
    IF y < 9 THEN
      GetArea (x, y+1);
    IF (x<9) AND (y<9) THEN
      GetArea (x+1, y+1);
    IF (x<9) AND (y>0) THEN
      GetArea (x+1, y-1);
    IF (x<0) AND (y<9) THEN
      GetArea (x-1, y+1);
  END; (* IF field[x,y].Index = 14 *)
END; (* PROC TForm1.GetArea *)

Danke für alle antworten!

[Niko]

Hi,

du rufst für jedes der umliegenden Felder deine Methode rekursiv auf. Angenommen eines der umliegenden Felder enthält auch den Wert 14. Dann rufst du bei der Behandlung diese Feldes GetArea für das erste Feld wieder auf, was letztendlich zu einer Endlosrekursion und damit zum Stack-Überlauf führt.

Du musst also noch prüfen, ob das zu bearbeitende Feld nicht bereits aufgedeckt ist.

[Niels]

Da muss ich Niko zustimmen, du überprüfst auch Felder, die bereits aufgedeckt sind.
Ein Stack-Owerflow tritt aber nicht nur bei Endlosrekursionen auf. Auch bei anderen, sehr tiefen Rekursionen kann der Stapel überlaufen. Sehr tiefe Rekursionen können auch sehr langsam werden, weshalb man überlegen sollte, solche sachen nicht iterativ zu lösen. Das ist oft mehr Quellcode, aber läuft um einiges schneller

MfG Niels

[DirectFromHell]

Hmm also warum ich den Überlauf habe verstehe ich jetzt, aber wenn ich, wie Niko gesagt hat, überprüfe ob das schon aufgedeckt ist, dann passiert effektiv nichts, oder es kommt wieder zum Überlauf :(
Nur habe ich leider auch gar keine Idee wie ich das anders lösen könnte :( :(

[alzaimar]

Du musst nur die Felder, die Du bereits durchsucht hast, markieren. So ungefähr:

Delphi-Quellcode:

Procedure Foo (x,y);
Begin
  If Visited (x,y) then exit;
  Visited (x,y) := True;
...
End;

Rekursion ist hier sicherlich das Einfachste, aber es geht u.U. schneller... Aber, wenns Dir reicht...

[Khabarakh]

Und natürlich nicht vergessen, vor der nächsten Rekursion alle Elemente vom Array "Visited" (ich gehe mal trotz der runden Klammern davon aus, dass alzaimer ein solches gemeint hat :wink:) wieder auf false zu setzen.

[alcaeus]

Das rekursive Aufdecken musst du ja nur machen, wenn du auf ein "leeres" Feld klickst. In dem Fall markierst du das Feld als besucht, und rufst die Funktion nochmal rekursiv fuer alle umliegenden Felder auf.
@Khabarakh: Warum als unbesucht markieren? Sobald ich aufs Feld geklickt habe ist es fuer dieses Spiel aufgedeckt, und man braucht nicht mehr draufklicken. Erst wenn das Spiel neu gestartet wird, wird das Array zurueckgesetzt ;)

Greetz
alcaeus

[DirectFromHell]

Danke an alle! Das funktioniert jetzt. Hab das so gelöst:

Delphi-Quellcode:

PROCEDURE TForm1.GetArea(x,y: Integer);
BEGIN (* PROC TForm1.GetArea *)
  field[x,y].hidden := false;
  field[x,y].q := false;
  IF field[x,y].Index = 14 THEN
  BEGIN (* IF field[x,y].Index = 14 *)
    IF (x>0) AND (y>0) THEN
      IF field[x-1, y-1].hidden THEN
        GetArea (x-1, y-1);
    IF (x>0) THEN
      IF field[x-1, y].hidden THEN
        GetArea (x-1, y);
    IF (y>0) THEN
      IF field[x, y-1].hidden THEN
        GetArea (x, y-1);
    IF (x<9) THEN
      IF field[x+1, y].hidden THEN
        GetArea (x+1, y);
    IF (y<9) THEN
      IF field[x, y+1].hidden THEN
        GetArea (x, y+1);
    IF (x<9) AND (y<9) THEN
      IF field[x+1, y+1].hidden THEN
        GetArea (x+1, y+1);
    IF (x<9) AND (y>0) THEN
      IF field[x+1, y-1].hidden THEN
        GetArea (x+1, y-1);
    IF (x<0) AND (y<9) THEN
      IF field[x-1, y+1].hidden THEN
        GetArea (x-1, y+1);
  END; (* IF field[x,y].Index = 14 *)
END; (* PROC TForm1.GetArea *)

Das merkwürdige ist: Mache ich diese Überprüfung nicht, dann geht die Grafikdarstellung, mache ich sie, bekomme ich Zugriffsverletzugen...
Prozedur zum "anmalen":

Delphi-Quellcode:

PROCEDURE TForm1.paintmap;
VAR y, z: Integer;
BEGIN (* PROC TForm1.paintmap *)
  FOR y := 0 TO 8 DO
    FOR z := 0 TO 8 DO
    BEGIN (* FOR 0 TO 8 *)
      IF field[y, z].hidden THEN
        iGame.Canvas.Draw(y*16, z*16, symbols[15]^)
      ELSE (* ELSE field[y, z].hidden *)
        IF field[y,z].marked THEN
          iGame.Canvas.Draw (y*16, z*16, symbols[11]^)
        ELSE (* ELSE field[y,z].marked *)
          IF field[y,z].q THEN
            iGame.Canvas.Draw(y*16, z*16, symbols[13]^)
          ELSE (* ELSE field[y,z].q *)
            iGame.Canvas.Draw(y*16, z*16, symbols[field[y,z].index]^);
    END; (* FOR 0 TO 8 *)
END; (* PROC TForm1.paintmap *)