Stack Overflow bei Wegfindung

[Guybrush Threepwood]

Ich hab gestern mal zufällig ein altes Programm von mir ausgegraben bei dem ich versucht hatte eine Wegfindung zu programmieren. Ziel dabei war es das man einem "Roboter" einen Start- und Zielpunkt gibt und dieser dann den kürzesten Weg auf einer vordefinierten Karte mit Hindernissen findet.

Ich hab mir das so gedacht das ich einen Baum anlege der jeden Möglichen weg abbildet. Danach suche ich dann welcher Zweig als schnellstes zum Ziel führt und markiere diesen. Als letztes wird dieser Weg abgegangen.

Jeder dieser Schritte läuft rekursiv ab und wenn ich nur eine ganz kleine einfache Karte mache funktioniert es auch. Wird die Karte aber etwas größer bekomme ich im Wegfindungsteil immer einen Stackoverflow. Ich bin bisher davon ausgegangen das ich da irgendwo einen Fehler drin habe und habe mal eine Logdatei mit jedem Punkt der abgeprüft wird angelegt. Dabei ist mir aufgefallen das die Datei 21413 Einträge enthält und dann wohl der Overflow auftritt.

Könnte es auch sein das der ganze Algorithmus das Problem ist und einfach zu viele Rekursionen auftreten weshalb dann der Overflow auftritt oder denkt ihr das es einfach nur ein Fehler in der Umsetzung ist?

[Bubble]

Es wird die Rekursionstiefe sein. Verwende besser ein anderes Verfahren.

[nic_power]

Hallo,

bei einigen Betriebssystemen wird für den Stack eine feste, maximale Größe verwendet. Ist dieser Wert erreicht, dann steht für die Rekursion kein Speicher mehr zur Verfügung und es wird eine entsprechende Fehlermeldung generiert. Bei Unix-Varianten läßt sich dieser Wert in der Regel problemlos ändern (je nach Derivat ist ein Rekompilieren des Kernels notwendig).

Allerdings kommt mir der Wert 21413 recht niedrig vor. Poste doch mal den Code.

Nic

[geloescht_Newlukai]

Ich hab mir das so gedacht das ich einen Baum anlege der jeden Möglichen weg abbildet. Danach suche ich dann welcher Zweig als schnellstes zum Ziel führt und markiere diesen. Als letztes wird dieser Weg abgegangen.

In der Tat ist das ziemlich aufwendig. Es gibt da aber einen ganz brauchbaren Algorithmus, den ich vor ein paar Monaten mal umsetzen mußte (hab' ihn sogar noch optimiert).

1. Markiere alle direkten Nachbarn (rechts/links, oben/unten) des Zielpunkts mit 1
   
2. Markiere jeden direkten Nachbarn der mit 1 markierten Felder mit 2
   
3. usw. ...
   
4. Folge nun vom Startpunkt aus dem Weg der mit der kleinsten Schrittzahl beginnt
   

Jetzt kann es passieren (bei geschickter Hindernisaufstellung), daß man den "Weg einsperrt":

xxx

x

xxx

Der Algorithmus folgt der kleinsten Schrittzahl, stößt auf ein Hindernis und findet nicht mehr heraus.

Und die Lösung des Problems war dann meine Optimierung. Du mußt im Hintergrund ein 2. Feld (BOOL) aufbauen, mit welchem Du die bereits benutzten Wege markierst. So kannst Du dann wieder solange zurück, bis der Weg wieder frei ist und einen neuen suchen.

Mit diesem Algorithmus ist der Speicherverbrauch wahrscheinlich niedriger.

[Guybrush Threepwood]

Hört sich für mich nach dem Djirski (oder so) Algorithmus an über den ich mal kurz was gelesen habe

Ich wollte das Programm eigentlich nicht posten weil es wie gesagt ein altes ist und ich jetzt nich so viel Arbeit reinstecken wollte. Fands halt nur nochmal interessant.

Ich denke ich weiß jetzt auch wo das Problem liegt. Ich habe zwar verhinder das er wenn er z.B. ein Feld nach unten gegangen ist direkt wieder nach oben geht, aber ich vermute er läuft einfach eine größere Endlosschleife. Wenn ich also mal wieder Lust hab mich eingehender damit zu befassen muss ich mir wohl was anderes Überlegen, vielleicht komme ich dann auf deinen Vorschlag zurück Newlukai

Falls sich trotzdem jemand für das Programm interessiert hab ich es mal angehangen.

Robo.txt

[nic_power]

Hallo,

hmm. also bei mir terminiert das Programm nach einer Sekunde ohne Fehlermeldung und hinterläßt ca. 130.000 Einträge in der log-Datei. Soll das so sein?

Nic

[Guybrush Threepwood]

Jein

Die Fehlermeldung kommt nur im Debugmodus in der FindeWege Funktion, beim normalen Starten kommt keine Meldung. Ich sehe auch gerade das es gar kein Stack Overflow mehr ist sondern eine Access Violation...das kommt davon wenn man die Meldung immer direkt weg klickt :floet:

Wenn du die main Funktion foglerndermaßen änderst dann funktioniert es sogar und du kannst sehen wie es gedacht war.

int main()

{

	cKarte[2][1] = '#';

	for (int i=0; i<24; i++)

		printf ("%s\n",cKarte[i]);


	stream = fopen ("c:\\log.txt","w");

	Roboter Robi(1,1,8,10);

	Robi.StarteRoboter();

	fclose(stream);

	return 0;

}

[/PHP]

Dadurch ist der Weg natürlich sehr eingeschränkt und gibt dem Programm nicht viele Möglichkeiten. Wie gesagt ich vermute das er auf einer größeren Fläche einfach Kreise geht...