[OT] Zufällige Labyrinthe programmieren

[Carsten]

Hallo zusammen,

ich stehe vor der Aufgabe, ein kleines Java-Programm zu programmieren, das
zufällige Labyrinthe (quasi virtuelle Irrgärten) erzeugen soll. Dabei steht
jetzt nicht die grafische Implementierung im Vordergrund, sondern die Logik
respektive der Entwurf eines effizienten und fehlerfreien Algorithmus. Daher
ist dieses Thema OT, weil es nicht javaspezifisch ist.

Das ganze soll in einem zweidimensionalem Array abgebildet werden (mit
variabler Größe). Wer Ideen oder interessante Quellen zu diesem Thema hat,
kann sie mir gerne mitteilen.

Gruss,
Carsten

[Ulrich Schramme]

Post by Carsten
Hallo zusammen,
ich stehe vor der Aufgabe, ein kleines Java-Programm zu programmieren, das
zufällige Labyrinthe (quasi virtuelle Irrgärten) erzeugen soll. Dabei steht
jetzt nicht die grafische Implementierung im Vordergrund, sondern die Logik
respektive der Entwurf eines effizienten und fehlerfreien Algorithmus. Daher
ist dieses Thema OT, weil es nicht javaspezifisch ist.
Das ganze soll in einem zweidimensionalem Array abgebildet werden (mit
variabler Größe). Wer Ideen oder interessante Quellen zu diesem Thema hat,
kann sie mir gerne mitteilen.
Gruss,
Carsten

Ich habe es ehrlich gesagt nicht selbst ausprobiert, aber vielleicht ist
das hier für Dich nützlich.

http://www.csc.uvic.ca/~csc225/2001F/Maze/MazeCode.html

[Carsten]

Post by Ulrich Schramme
Ich habe es ehrlich gesagt nicht selbst ausprobiert, aber vielleicht ist
das hier für Dich nützlich.
http://www.csc.uvic.ca/~csc225/2001F/Maze/MazeCode.html
--
-- Ulli
www.u-schramme.de

Hallo Ulli,

danke für den Tipp. Aber auf den ersten Blick scheint es so, dass der dort
abgebildete Algorithmus die KI zum Traversieren vom Eingang zum Ausgang des
Labyrinthes ist.

Viele Grüße

Carsten

P.S.: Das wird aber sicherlich später benötigt...

[Ulrich Schramme]

Post by Carsten

Post by Ulrich Schramme
Ich habe es ehrlich gesagt nicht selbst ausprobiert, aber vielleicht ist
das hier für Dich nützlich.
http://www.csc.uvic.ca/~csc225/2001F/Maze/MazeCode.html
--
-- Ulli
www.u-schramme.de

Hallo Ulli,
danke für den Tipp. Aber auf den ersten Blick scheint es so, dass der dort
abgebildete Algorithmus die KI zum Traversieren vom Eingang zum Ausgang des
Labyrinthes ist.
Viele Grüße
Carsten
P.S.: Das wird aber sicherlich später benötigt...

Ja, Du hast recht. Wie gesagt, ich hatte nur kurz einen Blick darauf
geworfen. Hier ist meine Google - Suche:

http://www.google.de/search?as_q=java+maze+algorithm&num=10&hl=de&ie=UTF-8&oe=UTF-8&btnG=Google+Suche&as_epq=&as_oq=&as_eq=&lr=&as_ft=i&as_filetype=&as_qdr=all&as_occt=any&as_dt=i&as_sitesearch=

Das hat eine ganze Masse Treffer gebracht. Vielleicht ist ja doch noch
was dabei.

[Carsten]

Post by Ulrich Schramme
Ja, Du hast recht. Wie gesagt, ich hatte nur kurz einen Blick darauf

http://www.google.de/search?as_q=java+maze+algorithm&num=10&hl=de&ie=UTF-8&oe=UTF-8&btnG=Google+Suche&as_epq=&as_oq=&as_eq=&lr=&as_ft=i&as_filetype=&as_qdr=all&as_occt=any&as_dt=i&as_sitesearch=

Post by Ulrich Schramme
Das hat eine ganze Masse Treffer gebracht. Vielleicht ist ja doch noch
was dabei.
--
-- Ulli
www.u-schramme.de

O.k. Maze bringt wirklich viele Treffer, kannte Maze bisher nicht. Das hilft
sicherlich weiter.

Gruss,
Carsten

[Hendrik Lipka]

Post by Carsten
Das ganze soll in einem zweidimensionalem Array abgebildet werden (mit
variabler Größe). Wer Ideen oder interessante Quellen zu diesem Thema hat,
kann sie mir gerne mitteilen.

wie wäre es mit
http://www.google.com/search?q=maze+generator

hli

[Ilja Preuß]

Post by Carsten
Hallo zusammen,
ich stehe vor der Aufgabe, ein kleines Java-Programm zu
programmieren, das zufällige Labyrinthe (quasi virtuelle Irrgärten)
erzeugen soll. Dabei steht jetzt nicht die grafische Implementierung
im Vordergrund, sondern die Logik respektive der Entwurf eines
effizienten und fehlerfreien Algorithmus. Daher ist dieses Thema OT,
weil es nicht javaspezifisch ist.
Das ganze soll in einem zweidimensionalem Array abgebildet werden (mit
variabler Größe). Wer Ideen oder interessante Quellen zu diesem Thema
hat, kann sie mir gerne mitteilen.

Habe ich selber mal programmiert. Grund-Idee ist ganz einfach: Ein Labyrinth
besteht aus einem Gitter von Räumen, wobei jeder Raum mit jedem seiner vier
angrenzenden entweder verbunden sein kann, oder halt nicht.

Ein Labyrinth kann dann folgendermaßen aufgebaut werden:

1) Initialisiere alle Räume so, dass sie nicht miteinander verbunden und
noch nicht bearbeitet sind. Initialisiere die Menge der zu bearbeitenden
Räume als leer.
2) Wähle einen zufälligen Raum und markiere ihn als bearbeitet
3) Füge alle noch nicht bearbeiteten Nachbarräume des aktuellen Raumes zur
Menge der zu bearbeitenden Räume hinzu
4) Ist die Menge der zu bearbeitenden Räume leer, so bist Du fertig
5) Wähle zufällig einen Raum aus der Menge der zu bearbeitenden Räume
6) Verbinde den ausgewählten Raum mit einem seiner bereits bearbeiteten
Nachbarräume
7) Weiter bei 3)

Hoffe, das hilft,

Ilja

[Carsten]

Post by Ilja Preuß
Habe ich selber mal programmiert. Grund-Idee ist ganz einfach: Ein Labyrinth
besteht aus einem Gitter von Räumen, wobei jeder Raum mit jedem seiner vier
angrenzenden entweder verbunden sein kann, oder halt nicht.
1) Initialisiere alle Räume so, dass sie nicht miteinander verbunden und
noch nicht bearbeitet sind. Initialisiere die Menge der zu bearbeitenden
Räume als leer.
2) Wähle einen zufälligen Raum und markiere ihn als bearbeitet
3) Füge alle noch nicht bearbeiteten Nachbarräume des aktuellen Raumes zur
Menge der zu bearbeitenden Räume hinzu
4) Ist die Menge der zu bearbeitenden Räume leer, so bist Du fertig
5) Wähle zufällig einen Raum aus der Menge der zu bearbeitenden Räume
6) Verbinde den ausgewählten Raum mit einem seiner bereits bearbeiteten
Nachbarräume
7) Weiter bei 3)
Hoffe, das hilft,
Ilja

Hallo Ilja,

vielen Dank für deinen Tipp und dem Algo. Wie kann ich es jedoch erreichen,
das der Endpunkt immer unten liegt? Wenn ich einen der Nachbarräume per
Random ermittelt habe, werden die anderen auf "bearbeitet" gesetzt? Wenn
nicht, könnte es passieren, dass die Raumbreite (also der "Gang") varriiert,
oder? Ebenso die Tatsache, dass es unerreichbare Räume geben könnte, wie
z.B. einabgrenztes Rechteck ohne Eingang.

Gruss,
Carsten

[Ralf Rosenkranz]

Hallo Carsten

... Wie kann ich es jedoch erreichen,
das der Endpunkt immer unten liegt? ...

ein sehr anschauliches Demo plus Anleitung fand ich hier:
http://www.mazeworks.com/mazegen/index.htm

Grüße Ralf

[Carsten]

Post by Ralf Rosenkranz
Hallo Carsten

... Wie kann ich es jedoch erreichen,
das der Endpunkt immer unten liegt? ...

http://www.mazeworks.com/mazegen/index.htm
Grüße Ralf
--
http://free-java-3d-chat-download.3dc.de
Mail an: voltax(at)... plus diese Domain

Danke Ralf,

diese Seite habe ich eben auch gefunden, und sie erklärt das Prinzip auch am
Einfachsten.

Gruss und schönes Wochenende

Carsten

[Guido Weber]

Hallo

ich habe mal einen Labyrinth-generator ungefähr nach Iljas Verfahren
geschrieben. Der einzige Unterschied ist, daß der Algorithmus einen
Gang so weit wie möglich verlängert, und nicht einen zufälligen Raum
aus den zu bearbeitenden Räumen auswählt.
Die Labyrinthe die man damit erzeugt haben alle die eigenschaft, daß
es von jedem Raum zu jedem anderen genau einen Weg gibt. Den Ein- und
Ausgang kann man daher irgendwo am Rand hinlegen (bei mir immer oben
links und unten rechts.
Wen Interesse besteht, kann ich den Sourcecode gerne mal mailen, es
ist auch gleich noch eine Anzeige und ein paar verschiedene animierte
Lösungsverfahren dabei.

Gruß
Guido

Post by Ilja Preuß

Post by Carsten
Hallo zusammen,
ich stehe vor der Aufgabe, ein kleines Java-Programm zu
programmieren, das zufällige Labyrinthe (quasi virtuelle Irrgärten)
erzeugen soll. Dabei steht jetzt nicht die grafische Implementierung
im Vordergrund, sondern die Logik respektive der Entwurf eines
effizienten und fehlerfreien Algorithmus. Daher ist dieses Thema OT,
weil es nicht javaspezifisch ist.
Das ganze soll in einem zweidimensionalem Array abgebildet werden (mit
variabler Größe). Wer Ideen oder interessante Quellen zu diesem Thema
hat, kann sie mir gerne mitteilen.

Habe ich selber mal programmiert. Grund-Idee ist ganz einfach: Ein Labyrinth
besteht aus einem Gitter von Räumen, wobei jeder Raum mit jedem seiner vier
angrenzenden entweder verbunden sein kann, oder halt nicht.
1) Initialisiere alle Räume so, dass sie nicht miteinander verbunden und
noch nicht bearbeitet sind. Initialisiere die Menge der zu bearbeitenden
Räume als leer.
2) Wähle einen zufälligen Raum und markiere ihn als bearbeitet
3) Füge alle noch nicht bearbeiteten Nachbarräume des aktuellen Raumes zur
Menge der zu bearbeitenden Räume hinzu
4) Ist die Menge der zu bearbeitenden Räume leer, so bist Du fertig
5) Wähle zufällig einen Raum aus der Menge der zu bearbeitenden Räume
6) Verbinde den ausgewählten Raum mit einem seiner bereits bearbeiteten
Nachbarräume
7) Weiter bei 3)
Hoffe, das hilft,
Ilja

[Wanja Gayk]

Guido Weber said...

Post by Guido Weber
Hallo
ich habe mal einen Labyrinth-generator ungefähr nach Iljas Verfahren
geschrieben. Der einzige Unterschied ist, daß der Algorithmus einen
Gang so weit wie möglich verlängert, und nicht einen zufälligen Raum
aus den zu bearbeitenden Räumen auswählt.
Die Labyrinthe die man damit erzeugt haben alle die eigenschaft, daß
es von jedem Raum zu jedem anderen genau einen Weg gibt. Den Ein- und
Ausgang kann man daher irgendwo am Rand hinlegen (bei mir immer oben
links und unten rechts.
Wen Interesse besteht, kann ich den Sourcecode gerne mal mailen, es
ist auch gleich noch eine Anzeige und ein paar verschiedene animierte
Lösungsverfahren dabei.

Yo,immer her damit :-)

Gruss,
-Wanja-

[Guido Weber]

Hallo

unter http://dgmt-weber.de/Labyrinth.jar ist das Wunderwerk zu
finden. Die Benutzerführung ist zwar ... naja ... aber man kann
sich hoffentlich zurechtfinden.

Wenn jemand sich angeregt fühlt, eine Möglichkeit zum Ausdruck
des Labyrinths einzubauen, fände ich das richtig gut ;-)

Guido

Post by Wanja Gayk
Guido Weber said...

Post by Guido Weber
Hallo
ich habe mal einen Labyrinth-generator ungefähr nach Iljas Verfahren
geschrieben. Der einzige Unterschied ist, daß der Algorithmus einen
Gang so weit wie möglich verlängert, und nicht einen zufälligen Raum
aus den zu bearbeitenden Räumen auswählt.
Die Labyrinthe die man damit erzeugt haben alle die eigenschaft, daß
es von jedem Raum zu jedem anderen genau einen Weg gibt. Den Ein- und
Ausgang kann man daher irgendwo am Rand hinlegen (bei mir immer oben
links und unten rechts.
Wen Interesse besteht, kann ich den Sourcecode gerne mal mailen, es
ist auch gleich noch eine Anzeige und ein paar verschiedene animierte
Lösungsverfahren dabei.

Yo,immer her damit :-)
Gruss,
-Wanja-

[Wanja Gayk]

Guido Weber said...

Post by Guido Weber
Hallo
unter http://dgmt-weber.de/Labyrinth.jar ist das Wunderwerk zu
finden. Die Benutzerführung ist zwar ... naja ... aber man kann
sich hoffentlich zurechtfinden.

Yo, klappt schon. Du solltest Generation und Lösung des Labyrinths aber
in einen eigenen Thread verlagern, dem du ab und zu mal ein Yield()
gibst. Ich habe zum Spass mal 500x500 als Größe angegeben und das
Programm nahm die komplette CPU-Zeit in Anspruch und regierte nicht mehr
auf Eingaben (z.B. dem verschieben der Scrollpanes).
Ich schätze "SwingUtilities.invokeLater(Runnable r)" wäre dafür super
geeignet.

Gruss,
-Wanja-

[Paul Ebermann]

Post by Wanja Gayk
Yo, klappt schon. Du solltest Generation und Lösung des Labyrinths aber
in einen eigenen Thread verlagern, dem du ab und zu mal ein Yield()
gibst. Ich habe zum Spass mal 500x500 als Größe angegeben und das
Programm nahm die komplette CPU-Zeit in Anspruch und regierte nicht mehr
auf Eingaben (z.B. dem verschieben der Scrollpanes).
Ich schätze "SwingUtilities.invokeLater(Runnable r)" wäre dafür super
geeignet.

SwingUtities.invokeLater sorgt ja gerade dafür,
dass die Handlung eben doch im UI-Thread ausgeführt
wird, so dass der nicht zum Neuzeichnen bzw.
Verarbeiten von Maus-Ereignissen kommt.

Also lieber einen neuen Thread (new Thread(...).start()),
und von dem aus eventuell ein paar Mal zwischendurch
mit invokeLater das (Zwischen)Ergebnis ausgeben.


Paul

[Wanja Gayk]

Paul Ebermann said...

Post by Paul Ebermann
SwingUtities.invokeLater sorgt ja gerade dafür,
dass die Handlung eben doch im UI-Thread ausgeführt
wird, so dass der nicht zum Neuzeichnen bzw.
Verarbeiten von Maus-Ereignissen kommt.
Also lieber einen neuen Thread (new Thread(...).start()),
und von dem aus eventuell ein paar Mal zwischendurch
mit invokeLater das (Zwischen)Ergebnis ausgeben.

Recht hast du.. Bummer!

Gruss,
-Wanja-

[Guido Weber]

Wäre schon nett, sowas zu haben. Ich war aber ehrlich gesagt
einfach zu faul um mir so viel Umstand zu machen :-(

Es kommen ja dann noch ein paar Dinge dazu: die Buttons
deaktivieren, damit nicht zwei Threads auf den gleichen
Daten rumrechnen; vielleicht noch einen Abbrechen-Knopf ...

Guido

Post by Wanja Gayk
Paul Ebermann said...

Post by Paul Ebermann
SwingUtities.invokeLater sorgt ja gerade dafür,
dass die Handlung eben doch im UI-Thread ausgeführt
wird, so dass der nicht zum Neuzeichnen bzw.
Verarbeiten von Maus-Ereignissen kommt.
Also lieber einen neuen Thread (new Thread(...).start()),
und von dem aus eventuell ein paar Mal zwischendurch
mit invokeLater das (Zwischen)Ergebnis ausgeben.

Recht hast du.. Bummer!
Gruss,
-Wanja-

[Jochen Theodorou]

Post by Carsten
Hallo zusammen,
ich stehe vor der Aufgabe, ein kleines Java-Programm zu programmieren, das
zufällige Labyrinthe (quasi virtuelle Irrgärten) erzeugen soll. Dabei steht
jetzt nicht die grafische Implementierung im Vordergrund, sondern die Logik
respektive der Entwurf eines effizienten und fehlerfreien Algorithmus. Daher
ist dieses Thema OT, weil es nicht javaspezifisch ist.
Das ganze soll in einem zweidimensionalem Array abgebildet werden (mit
variabler Größe). Wer Ideen oder interessante Quellen zu diesem Thema hat,
kann sie mir gerne mitteilen.

Also ich würde das so ähnlich wie Ilja machen allerdings nicht genauso.
Du hast einen Start und ein Ziel.
1.) Ich würde also von Start und Ziel aus einen Weg wachsen lassen und
zwar so lange bis sich die beiden getroffen haben.
2.) Erstellen eines Randes, der aus den unverbundenen Verbindungen des
Randes des Weges und den Verbindungen der Seiten des Feldes besteht.
3.) Eine Verbindung ist bestandteil des Randes, wenn die Verbindung
nicht den Zielweg mit einem weiteren Teil des Zielweges verbindet.
4.) Eine Verbindung aus dem Rand per Zufall auswählen und setzen. Den
Raum hinzufügen und markieren, dass das nicht der Zielweg ist.
5.) Alle Verbindungen des Raumes vom Rand löschen.
6.) Alle Verbindungen des Raumes zum Rand hinzufügen wenn diese
Verbindung keinen neuen Weg zum Zielweg schafft und noch nicht
gesetzt ist.
6.) wieder zu 4, Abbruch kann entweder sein, wenn der Rand hier leer
ist und-oder wenn eine Maximale Anzahl zu belegender Räume erreicht
wurde.

Eine Modifikation wäre es mit einer gewissen Wahrscheinlichkeit neue
Verbindungen zum Zielweg zuzulassen.

mit Union-Find ist der Algorithmus glaube ich nicht sonderlich lang...

Gruss theo

[Carsten]

Post by Jochen Theodorou
Also ich würde das so ähnlich wie Ilja machen allerdings nicht genauso.
Du hast einen Start und ein Ziel.
1.) Ich würde also von Start und Ziel aus einen Weg wachsen lassen und
zwar so lange bis sich die beiden getroffen haben.
2.) Erstellen eines Randes, der aus den unverbundenen Verbindungen des
Randes des Weges und den Verbindungen der Seiten des Feldes besteht.
3.) Eine Verbindung ist bestandteil des Randes, wenn die Verbindung
nicht den Zielweg mit einem weiteren Teil des Zielweges verbindet.
4.) Eine Verbindung aus dem Rand per Zufall auswählen und setzen. Den
Raum hinzufügen und markieren, dass das nicht der Zielweg ist.
5.) Alle Verbindungen des Raumes vom Rand löschen.
6.) Alle Verbindungen des Raumes zum Rand hinzufügen wenn diese
Verbindung keinen neuen Weg zum Zielweg schafft und noch nicht
gesetzt ist.
6.) wieder zu 4, Abbruch kann entweder sein, wenn der Rand hier leer
ist und-oder wenn eine Maximale Anzahl zu belegender Räume erreicht
wurde.
Eine Modifikation wäre es mit einer gewissen Wahrscheinlichkeit neue
Verbindungen zum Zielweg zuzulassen.
mit Union-Find ist der Algorithmus glaube ich nicht sonderlich lang...
Gruss theo

Hi Theo,

danke für den Tipp. Ich habe momentan eine interessante Methode gefunden.
Deine werde ich auch später testen.

Viele Grüße
Carsten

[Wanja Gayk]

Carsten said...

Post by Carsten
Hallo zusammen,
ich stehe vor der Aufgabe, ein kleines Java-Programm zu programmieren, das
zufällige Labyrinthe (quasi virtuelle Irrgärten) erzeugen soll. Dabei steht
jetzt nicht die grafische Implementierung im Vordergrund, sondern die Logik
respektive der Entwurf eines effizienten und fehlerfreien Algorithmus. Daher
ist dieses Thema OT, weil es nicht javaspezifisch ist.

Nimm Bausteine, für geraden (2 Stück) und kurven (4 Stück) din Start und
einen Endpunkt. Bau daraus eine Strecke von A nach B.
Im Folgenden gruppier Zufällige Bausteine um diese Strecke rum.

Gruss,
-Wanja-