Autor Beitrag
ene
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 779
Erhaltene Danke: 1

Vista, XP, W2K
Delphi, .Net, Deutsch und Englisch
BeitragVerfasst: Di 20.03.07 09:00 
moin ich bekomme einen Stack Overflow bei folgendem Codeaufbau:

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
Function IsValid(Const x,y,z: Integer): Integer;
Begin
  If (x >= Low(Mitte)) And (x <= High(Mitte)) And (y >= Low(Mitte[x])) And (y <= High(Mitte[x])) Then Result:= Mitte[x,y,z] Else Result:= 0;
End;


Function GetLongestLine(x,y,Tiefe: Integer): Boolean;
Var Zwischen: Boolean;
Begin
  Result:= False; Zwischen:= False;

    try
    Mitte[x,y,1]:= 0;
    If IsValid(x-1,y-1,0) = 1 Then Zwischen:= GetLongestLine(x-1,y-1,Tiefe+1);
    If IsValid(x  ,y-1,0) = 1 Then Zwischen:= GetLongestLine(x  ,y-1,Tiefe+1Or Zwischen;
    If IsValid(x+1,y-1,0) = 1 Then Zwischen:= GetLongestLine(x+1,y-1,Tiefe+1Or Zwischen;
    If IsValid(x-1,y  ,0) = 1 Then Zwischen:= GetLongestLine(x-1,y  ,Tiefe+1Or Zwischen;
//    If IsValid(x+1,y  ,0) = 1 Then Zwischen:= GetLongestLine(x+1,y  ,Tiefe+1) Or Zwischen;
//    If IsValid(x-1,y+1,0) = 1 Then Zwischen:= GetLongestLine(x-1,y+1,Tiefe+1) Or Zwischen;
//    If IsValid(x  ,y+1,0) = 1 Then Zwischen:= GetLongestLine(x  ,y+1,Tiefe+1) Or Zwischen;
//    If IsValid(x+1,y+1,0) = 1 Then Zwischen:= GetLongestLine(x+1,y+1,Tiefe+1) Or Zwischen;
    except
    on E: Exception do Writeln(E.Message, E.HelpContext);
    end;


    If Tiefe > Laenge Then Begin
      Laenge:= Tiefe;
      Zwischen:= True;
    End;

    If Zwischen Then Begin
      Mitte[x,y,1]:= 2;  
      Result:= True;
    End;
  End;


Das ist ein A* Algorithmus, Mitte ist ein Array Of Array Of Array [0..2] Of Byte. Sprich eine zweidimensionale Matrix, die zu jedem Punkt 2 Werte enthalten kann. So wie sie jetzt da steht, läufts, aber wenn ich restlichen Kommentare rausnehme um mehr Felder abzuprüfen, bekomme ich beim IsValid() einen StackOverflow und ich verstehs nicht :( Ich kann die Funktion auch leider nicht rausnehmen, weil mein Abfragen größer als das Array sein können. Bei einem Punkt am Rand werden alle 8 umschliessenden Werte überprüft.

Hat jemand das verstanden? Ansonsten bitte einfach nachfragen und vielen Dank im Vorraus.


Moderiert von user profile iconUGrohne: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Di 20.03.2007 um 10:12
ene Threadstarter
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 779
Erhaltene Danke: 1

Vista, XP, W2K
Delphi, .Net, Deutsch und Englisch
BeitragVerfasst: Di 20.03.07 10:18 
Ok, IsValid rufe ich jetzt als StdCall auf und dann habe ich den StackOverflow in der rekursiven Funktion...aber keinen Plan warum :(
wdbee
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 628
Erhaltene Danke: 1



BeitragVerfasst: Di 20.03.07 10:35 
Wenn rekursive Aufrufe von Funktionen zu einem Stack Overflow führen, gibt es zwei mögliche Gründe:

1. Der Alg. ist zwar richtig, aber es werden zu viele bzw. zu große lokale Variablen (z.B. Arrays [0..Sehr Groß]) verwendet.
2. Der Alg. ist falsch, weil er nie terminiert.

Um 2. zu prüfen, kannst du mal eine globale Variable mit 0 initialisieren und bei jedem Aufruf der Funktion inkrementieren. Wenn der Stackoverflow auftritt, kannst du den Wert der Variablen mit der Exception anzeigen lassen. Dann siehst du, wie oft die Rekursion auftritt.
ene Threadstarter
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 779
Erhaltene Danke: 1

Vista, XP, W2K
Delphi, .Net, Deutsch und Englisch
BeitragVerfasst: Di 20.03.07 11:10 
Also ich habe mal einen Zähler eingebaut und der StackOverflow tritt ja nach Bedingungen im Algo nach unterschiedlichen Durchläufen auf. Also würde ich mal sagen, dass er falsch terminiert ist, oder?

Die Frage die sich mir dabei noch stellt ist, warum er "teilweise" funktioniert, wenn ich nur nach oben oder unten suche :confused: Das Ergebnis ist dann zwar falsch, aber es wird ein Ergebnis geliefert.
ene Threadstarter
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 779
Erhaltene Danke: 1

Vista, XP, W2K
Delphi, .Net, Deutsch und Englisch
BeitragVerfasst: Di 20.03.07 11:29 
Ich habs, ich hab den falschen Wert in die geschlossene Liste gesetzt, dann klappt auch. Vielen Dank!