Stack-Overflow abfangen

[Sinthuor]

Habe ein Programm das die Länge eines vorhandenen Weges von einem Starpunkt zu einem Zielpunkt berechnen soll:
X0000
00000
00000
00000
0000X
Das klappt, solange in dem Weg keine "Kreise" auftreten (Abzweigungen sind kein Problem):
XXX00
X00X0
X0XXX
X0X0X
XXX0X
etwa liefert als Länge 12;
Problematisch wird es sobald ein Weg vor dem Ziel einen "Kreis bildet":
XXXXX
X000X
XXXXX
X0000
XXXXX
Hier kommt es zu einer Endlosschleife und dadurch zu einem Stackoverflow - den ich abfangen und stattdessen eine Fehlermeldung ausgeben möchte.

Mein Code:

Delphi-Quellcode:

class function TFelder.RestWeg(Sender: TObject; last: integer): integer;
var counter,a,b,c,d: integer;
begin
  counter:=0;
      if (TFelder(Sender).Fxpos=5) and (TFelder(Sender).Fypos=5) then counter:=0 //Ziel
else  if (felder[TFelder(Sender).Fxpos, TFelder(Sender).Fypos-1].Ftyp<>'Weg') then counter:=11 //Falls keine Verbingung von Start zu Ziel vorhanden 
else
  begin
    a:=10; b:=10; c:=10; d:=10;

    if (TFelder(Sender).Fypos>1) and (last<>2) then //last gibt die "Richtung" an, von der gezählt wird 
                                                    //-> somit keine Umkehr möglich, wass abermals zu einer Endlosschleife führen würde
    a:=Restweg(felder[TFelder(Sender).Fxpos, TFelder(Sender).Fypos-1], 4)+1;
    
    if (TFelder(Sender).Fypos<5) and (last<>4) then
    b:=Restweg(felder[TFelder(Sender).Fxpos, TFelder(Sender).Fypos]+1, 2)+1;

    if (TFelder(Sender).Fxpos>1) and (last<>1) then
    c:=Restweg(felder[TFelder(Sender).Fxpos-1, TFelder(Sender).Fypos], 3)+1;

    if (TFelder(Sender).Fxpos<5) and (last<>3) then
    d:=Restweg(felder[TFelder(Sender).Fxpos+1,   TFelder(Sender).Fypos], 1)+1;

    counter:=min(a,b);
    counter:=min(counter,c);
    counter:=min(counter,d);
  end;

  result:=counter;
end;

Aufgerufen wird das ganze durch einen Buttonclick:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
begin
CreepLife.text:=inttostr(Tfelder.RestWeg(felder[0,0],0));

Würde den Fehler gerne einfach mit Try ... Except ... End abfangen, und eine Fehlermeldung "Unerlaubter Weg" ausgeben - bin daran jedoch gescheitert.

[Luckie]

Lass es laufen und guck, was für eine Exception dir Delphi wirft und genau die fängst du dann in einem try-except-Block ab.

[himitsu]

Oder merk dir, wo du schon überall warst und laß es garnicht erst so weit kommen. :angle2:

[Sinthuor]

Zitat:

Zitat von Luckie (Beitrag 1116857)

Lass es laufen und guck, was für eine Exception dir Delphi wirft und genau die fängst du dann in einem try-except-Block ab.

Ist eine Exception der Klasse EStackOverflow.
Habe auch schon versucht diese mit try...except aufzufangen (bzw. auch generell jede), das hat aber nicht funktioniert.
Kann mir jemand sagen, wo genau das try bzw. das except in den code gehört?

[DeddyH]

Du hast eine Rekursion programmiert. Diese definiert sich eben dadurch, dass eine Routine sich selbst aufruft. Nun darfst Du selbst überlegen, wo ein try-except-Block überall Sinn macht, oder Du beachtest himitsus Hinweis und versuchst eine Endlos-Rekursion (wirklich endlos ist sie ja nicht, wie Du gerade schmerzvoll erfährst) im Vorfeld zu vermeiden, was die sauberere Lösung wäre.

[brechi]

uebergib in jeder rekursion die rekusrionstiefe mit, und brich frühzeitig ab (z.b. tiefe 30)

[Sinthuor]

Zitat:

Zitat von brechi (Beitrag 1116870)

uebergib in jeder rekursion die rekusrionstiefe mit, und brich frühzeitig ab (z.b. tiefe 30)

Das war eine super Lösung für mich. Vielen Dank! :-D

[FredlFesl]

Zitat:

Zitat von Sinthuor (Beitrag 1116876)

Zitat:

Zitat von brechi (Beitrag 1116870)

uebergib in jeder rekursion die rekusrionstiefe mit, und brich frühzeitig ab (z.b. tiefe 30)

Das war eine super Lösung für mich. Vielen Dank! :-D

Das ist keine Lösung, sondern ein Workaround. Denn wenn ein Weg mal länger als 30 Einheiten sein sollte, findest du ihn mit dieser Methode nicht mehr.

[jaenicke]

Mal abgesehen davon, dass es extrem viel länger dauert, wenn man sich nicht merkt wo man schon war...

[himitsu]

Bedenkt aber, daß man auch etwas mehr Speicher benötigt, wenn man sich den Weg merkt, da dieses für jede Rekusrionsebene einzeln gepeichert (kopiert und erweitert) werden muß.
Also vorallem, wenn man es mit auf den Stack legen würde.

[SirThornberry]

Delphi-Quellcode:

Bedenkt aber, daß man auch etwas mehr Speicher benötigt, wenn man sich den Weg merkt, da dieses für jede Rekusrionsebene einzeln gepeichert (kopiert und erweitert) werden muß.

Da hast du einen Denkfehler.
Man muss sich maximal so viel Felder merken wie es insgesamt gibt (nicht alle Kombinationen). Zudem kann man auch noch mit Bits arbeiten (Pro Feld ein Bit) und schon benötigt man gar nicht mehr sooo viel Speicher.

[FredlFesl]

Echt? Ich würde der Matrix ein weiteres Feld gönnen (Visited:Boolean).
Betrete ich das Feld, prüfe ich, ob Visited=True, wenn ja, beende ich die Routine, ich war ja schon mal da.
Ansonsten setze ich Visited=True, suche nach weiteren Wegen und nehme aber nur die Nachbarfelder mit ins Boot, die ich noch nicht besucht habe.

Dann rufe ich mich selbst mit allen Nachbarkandidaten rekursiv auf.

Bevor ich die Routine verlasse, setze ich Visited wieder auf False:

Delphi-Quellcode:

Procedure TMatrix.Visit (Source : TPoint; Path : TPath);
Begin
  If Source = FinalDestination then
     Success(Path)
  Else If not Self.Visited[Source] Then begin
    Self.Visited[Source] := True;
    Foreach Neighbor in Source.Neighbors do 
      If not Self.Visited[Neighbor] Then
        Visit(Neighbor, Path+Neighbor)
    Self.Visited[Source] := False;
  End
End;

[himitsu]

OK, einen Denkfehler hab ich schon, wenn man die betretenen Felder wieder frei gibt, sobald mein wieder eine Ebene zurück geht, dann stimmt es. :oops:

[FredlFesl]

Oder einfach gleich A* nehmen, schließlich will er ja einen Weg von A->B finden.

[Luckie]

Das ist mir auch schon die ganze zeit im Kopf rumgeschwirrt. Hie rgibt es ein Demo und ein Tutorial: http://www.michael-puff.de/Programmierung/Delphi/Demos/

[Delphi-Laie]

Zitat:

Zitat von Sinthuor (Beitrag 1116853)

Problematisch wird es sobald ein Weg vor dem Ziel einen "Kreis bildet":
...
Hier kommt es zu einer Endlosschleife und dadurch zu einem Stackoverflow - den ich abfangen und stattdessen eine Fehlermeldung ausgeben möchte.

Das Problem ist hier nicht, irgendwelche Exceptions abzufangen (die auf ein grundlegende(ere)s Problem hindeuten), sondern der Fehler im Suchalgorithmus: Die Endlosschleifen entstehen m.E., weil es beim Suchen des Wegen gestattet ist, teilweise rückwärts zu gehen.

Ein korrekter Algorithmus wird bei diesen kleinen Feldern nie zu einem Stacküberlauf führen.