✔ Labyrinthgenerator, Performanceprobleme

S

schnuffie

Erfahrenes Mitglied
Hallo Algo-Experten,

ich habe einen Generator programmiert, der zufällige Labyrinthe erstellt. Dafür benutze ich die java.util.Random-Klasse. Über Backtracking bekomme ich raus, ob wenigstens ein Weg zum Ziel gefunden wird.

Zuerst erstelle ich Eingang am Rand in irgendeinem Viertel der Gesamtfläche, danach das Ziel im gegenüberliegenden Viertel, damit Eingang und Ziel stets voneinander entfernt sind. Das klappt auch sehr gut.

Das Problem sind die Wege und Mauern zu realisieren. Dazu habe ich schon verschiedene Möglichkeiten ausprobiert:

1. nur Mauern und dann per Zufall jeweils ein Weg-Element setzen, solange bis ein Weg gefunden wurde

2. nur Wege und dann per Zufall jeweils ein Mauer-Element setzen, bis nur noch ein Weg gefunden wurde

3. per Zufall Mauer- und Weg-Elemente setzen, bis ein Weg gefunden wurde

Alle 3 Möglichkeiten haben einen gravierenden Nachteil. Je größer das Labyrinth, desto länger dauert die Berechnung, weil ich für jedes Einzel-Element die recursive Wegberechnung durchführe. :(

Zeitdauer (ca.):
6x6 = 15s
10x10 = 3min
15x15 = 10min

Ein weiteres Problem besteht darin, daß ich > 15x15 stets "StackOverflow"-Error bekomme. Das liegt höchstwarscheinlich daran, daß der GC mit dem Aufräumen meiner Maps nicht mehr hinterher kommt. :mad:

In meiner Not fing ich an, ohne Weg-Check eine bestimmte Anzahl an Feldern mit Mauern per Zufall zu belegen und den Weg-Check danach erst durchzuführen. Die Performancegewinne halten sich in Grenzen (15x15 immernoch ca. 7min), dafür sind die so kreierten Labyrinthe öfters nicht lösbar (Weg = 0), also auch nicht der Weisheit letzter Schluß. :confused:

Eine andere Möglichkeit war, solange fertige Labyrinthe zu erzeugen, bis ich "per Zufall" mindestens einen Weg finde. Auch wenn ich nun die Wegfindung erst mit dem kompletten Labyrinth beginne, ist die Performance extrem schlecht (10x10 bereits > 10min), da ich nun viel zu viele "Nieten" bekomme, ehe ich ein Labyrinth mit wenigstens einem Weg erhalte. :suspekt:

Schlau wollte ich sein. Erstelle nun den Lösungsweg per Zufall und fülle den Rest mit Mauern und Wegen per Zufall auf. Die Performance ist toll, jedoch das Labyrinth viel zu leicht. Nun habe ich eine Vielzahl offensichtlicher Wege, also zu leicht. Mit nur Mauern aufzufüllen ist ebenfalls viel zu leicht. Die einzige Lösung sticht sofort ins Auge. :(

Gibt es nicht irgend einen sinnvolleren performanteren Weg zum Ziel zu kommen? :confused:

Bin schon arg am verzweifeln.:(
 
Danke Tom für den interessanten Link.

Habe die Sache gestern Abend mal versucht so umzustellen, bin aber mit dem Ergebnis auch nicht so zufrieden. Soweit ich verstanden habe, soll man erstmal generell nur Mauern haben. Danach eine Startposition wählen, wäre bei mir der Eingang, auch klar. Diese Position als Weg markieren, in die Liste der möglichen wege hinzufügen und anschließend aus dieser Liste wieder entfernen - klingt hier noch unlogisch, kommt aber noch. Alle Positionen rundherum aus der Liste (falls enthalten) entfernen und die möglichen Wege (also waagerecht und senkrecht) der Liste hinzufügen. Eine dieser möglichen Wegepositionen wählen und dort wieder beginnen, wo ich mit der Startposition begann. Das habe ich so auch gemacht, jedoch wird diese Liste erstmal ziemlich groß, ehe dann die Inhalte abgearbeitet worden. Das dauert! Die Performance ist auch hier nicht berauschend (Hälfte meiner vorherigen Versuche etwa), jedoch werden oft "StackOverflow"-Errors dabei geliefert. Alles in allem, suche also immernoch nach einem vernünftigem Weg. :suspekt:

Kann man nicht mit dem Ansatz "erst Lösungsweg generieren", dann "Irrwege rundherumbasteln" weiterkommen? Gibt's vielleicht eine einfache mathematische Formel dafür, auf die ich nur noch nicht gekommen bin? Denke da an das Backtracking, das für die Labyrinth-Lösung sehr gut und relativ schnell funktioniert, nur hier halt andersherum, wenn Ihr versteht, was ich meine. :confused:
 
Halli und Hallo,
also zum Stackoverflow... ich glaube nicht das ein Stackoverflow irgendwas mit dem GC zu tun hat, denn dann würde es eher out of memory heißen und würde bedeuten Du hast ein Speicherleck.
Du arbeitest rekursiv, also stimmt Deine Abbruchbedinnung vielleicht nicht, denn Stackoverflow, bedeutet es werden mehr aufrufe gemacht, die aber nicht retunieren als der Stack vertragen kann.
Der Ansatz den Du gerade beshreiben hast halte ich für klasse. Man baut einen weg, der von Start und Ziel führt und baut dann Mauern (Klötzchen) die den Weg nicht passieren dürfen.
Jetzt ist natürlich die Frage wie baut man den Weg?
Eine Bedingungsfrage muss ich aber stellen, sind nur horizontale und vertikale Richtungen erlaubt oder auch diagonale?

Ich nehme mal an das nur horizontale und vertikale Richtung für einen Weg erlaubt sind.

Eine Möglichkeit die ich sehe ist, man nimmt eine Anzahl Punkte in der Matrix und verbindet sie zu einem Weg, gemäß der obengenannten Prämisse.
Einer der Punkte ist Start der andere Ziel. Sollte eigentlich laufzeittechnisch keinproblem sein, kann nähmlich problemlos auch iterativ implementiert werden.

Viel Spaß und viel Glück

Takidoso
 
Genau Takidoso, zuerst hatte/habe ich den Weg anhand von zufälligen Koordinaten generiert (unter Einhaltung von Bedingungen, wie innerhalb des Labyrinths und eine gewisse Länge der Wegstrecke). Das klappt auch schon recht schnell. Noch paar kleine Bugs hab' ich drin (z.B. Wiedererreichen eines vorherigen Teilstücks = ungewollte Abkürzung), muß ich noch erkennen und "eliminieren".:)

Problematisch ist das anschließende "Auffüllen" mit Mauern und Irrwegen, das per Zufall viel zu lange dauert, da ich entweder bei jeder neuen Position prüfen muß, ob der Weg nicht ungewollt abgekürzt wurde oder solange generieren muß, bis der Weg nicht abgekürzt wurde. Mauern entlang des generierten weges sind allerdings auch keine Lösung, denn dann ist dieser Weg zu offensichtlich, zumal dann auch keine Irrwege mehr möglich sind.

Gesetzt dem Fall ich habe meinen (einzigen) Weg ohne Bug generiert bekommen und den doofen Stackoverflow-Error besiegen können, dann wäre jetzt noch das Performance-Problem, den Rest mit Mauern und Irrwegen so gut aufzufüllen, daß der Weg mit bloßem Auge nicht mehr zu sehen ist.:(

Wo sind die Mathematiker unter Euch, die sowas mit "links" *lol* erledigen?
Irgendwie stehe ich auf dem Schlauch.
 
Also irgendwie finde ich ist Dein Ansatz herrlich kompliziert, ich hätte da einen viel simpleren, vorausgesetzt ich verstehe Deine Bedinungen richtig...
Wenn ich Dich recht verstehe willst Du ein Labyrinth erstellen, was garantiert mindestens eine richtige Lösung hat, oder?

Nehmen wir mal an das wäre so...
dann würde ich grob mäßig follgendes Probieren

- erstelle eine 2 dimensionale Matrix für Labyrinth einer größe (n,m)
- wähle aus der Labyrinth-Matrix beliebiege Punkte der menge o
und stelle diese in einem Array in zufälliger Reihnfolge
- mit einer Schleife verbinde die Punkte in der gegebenen Reihnfolge
mit horizontalen und vertikalen Linien
(der einfachheithalber im idealfall mit einer maximal mit 2 linien)
********* damit hast Du den mindestens einen Weg *****

Nun die Mauern Produzieren

for (int y=0; i<n;y++)
{
for (x=0;x<m;x++)
{
if (labyrinth[x][y] != WEGSTÜCK)
{
labyrinth[x][y] = definiereMitMehrOderWenigerStarkemZufallMauerStück();
}
}
}

und fertig ist, wobei es durchaus sei kann das der Weg sich kreuzt, umso lustiger ist es, denn ein wesen was durch das Labyrinth geht könnte dann unversehens auch im Kreis gehen :-)

das sollte Laufzeittechnisch rappeldifatz gehen.

Takidoso
 
Genau weil ich eine einfachere und schnellere Lösung suche, steht dieser Beitrag hier. Irgendwer soll doch mal endlich meine Bretterwand vor den Augen wegräumen, damit ich auch wieder was sehe! :-)

Das mit dem Weg ist bei mir eine Liste der Positionen. Die hat nur die Einschränkung, nicht die kürzeste Verbindung zwischen Start und Ziel sein zu dürfen. Im Klartext soll die Elementanzahl mindestens ein Viertel aller Positionen sein.

So wie Du das gemacht hast, habe ich's auch versucht. Dabei kann es aber sein, daß im schlimmsten Fall der Weg "verbreitert" wird, will heißen, neben dem Weg zufällig ein neuer Weg entsteht. Nachteilig dabei wären nicht nur event. Abkürzungen, sondern auch wäre dieser Weg dann auf den ersten Blick zu erkennen, was natürlich nicht sein darf. Würde ich allerdings alle Nachbarpositionen verbieten, hätte ich dort nur Mauern und ein Irrweg wäre nicht möglich und dieser Weg wäre dann wieder auf den ersten Blick zu erkennen.

Denke ich immernoch viel zu kompliziert, takidoso? :confused:
 
Hi scnhuffie,
also wenn ich Dich nun recht verstehe möchtest Du einen besonders langen Weg, der sich nicht kreuzt (damit keine Abkürzungen bestehen und eben nur einen möglichen Weg, richtig?
Dann würde ich wie folgt vorgehen

Die Labyrintmatrix wird mit nur Mauern initialisiert

man produziert einen weg ähnlich wie vorher beschrieben nur mit der Prüfung das er selbst nicht kreuzt.

Unter der Prämisse das das Labyrint nur einen Eingang hat werden nun weitere Wege definiert, die nicht den Rand des Labyrinths durchstoßen, sich selbst kreuzen dürfen den Lösungsweg aber maixmal nur einmal und andere Wege, die den Lösungsweg kreuzen keinmal, andere Wege, die den Lösungsweg nicht kreuzen so oft sie wollen.

unter weg kreuzen einander verstehe ich heirbei sowohl eine "T- als auch eine "+ Keuzung"

wenn obige Regeln zur Weggenerierung gelingen, sollte das Labyrinth einen Lösungsweg haben mit einer Menge an garantierten Sackgassen und auch "Kreiseln", die aber keinen Alternativ weg zum eigetnlichen Lösungsweg führen.

bezüglich Speicheroptimierung, sollte man sich entweder nur die freien Felder, die als Weg fungieren, oder nur die belegten Plätze, die als Mauern fungieren in einer Map mit Koordinaten als Key merken, sol lassen sich erheblich größere Labyrinthe erstellen.

Noch größere lassen sich mit gleichem Speicher erstellen, wenn nur die Punkte, die diei Wege beschreiben in einer Map gemerkt werden, wobei eine Routine immer berechnet, ob eine Koordinate auf einen solchen Weg liegt.

Ich denke die Hautarbeit steckt in der Frage wie verhindert man das ein Weg einen anderen Kreuzt bzw. sich selbst.

Vermute mal das ist ein Graphentheoretisches Problem.

viel Spaß und viel Glück

Takidoso
 
Das ist schon ein Einfall, den ich bisher nicht hatte, takidoso. Jetzt komme ich schon ein ganzes Stück weiter. :)
Hatte bislang nur zufällige Punkte außerhalb des Lösungsweges gesetzt, die Idee mit generierten Irrwegen, die die Lösung nur einmal berühren dürfen, finde ich gut. Werde nun wie folgt vorgehen:

1. Lösungsweg generieren (bestimmte Länge, umgebende Punkte müssen erstmal Mauern sein)
2. n Irrwege generieren, die den Lösungsweg genau 1x "anbinden", ohne selbst zum Ziel zuführen
3. Rest mit Mauern auffüllen

Vielleicht kann ich so performancetechnisch schneller werden. Takidoso, hast mir erstmal gut weitergeholfen. Vielleicht bekomme ich das jetzt so hin, wie ich mir das vorstelle.

@Tom, auch Dank an Dich. Es ist interessant, was es alles in der Richtung schon fertig gibt, da mich aber die eigentliche Vorgehensweise brenned interessiert, soll es schon eine Eigententwicklung werden. Will schließlich was lernen.:)
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück