Algorithmus zur Erstellung eines Labyrinthes?
-
Hallo,
ich programmiere gerade ein kleines Spiel. Hierbei geht es einfach darum einen Weg durch das Labyrinth zu finden... Nun habe ich ein 100x100 großes Feld und ich habe ehrlich gesagt keine Lust den Ganzen Kram mit Mauern, Start- und Zielfeld und Sonderfeldern manuell einzugeben...
Gibt es für die Erstellung eines Labyrinthes allegemein einen Algorithmus oder muss ich mich selber an die Arbeit machen und einen schreiben?
Beachte: Es geht nur um die Erstellung und nicht um Pathfinding...Gruß Speedy_92
-
Also bei Gimp gibt es was http://docs.gimp.org/2.2/de/plug-in-maze.html, weiß aber nicht ob es da immer (nur) eine Lösung gibt und wie du das willst.
-
productline schrieb:
Also bei Gimp gibt es was http://docs.gimp.org/2.2/de/plug-in-maze.html, weiß aber nicht ob es da immer (nur) eine Lösung gibt und wie du das willst.
Not Found The requested URL /2.2/de/plug-in-maze.html, was not found on this server. Apache/1.3.33 Server at docs.gimp.org Port 80
-
Eine einfache Möglichkeit zum Erstellen von Labyrinthen ist die Tiefensuche. Dazu geht man folgendermaßen vor:
Man beginnt mit einem regelmäßigen Gitter, in dem jede Zelle von vier Wänden begrenzt ist und jede Zelle als noch nicht besucht markiert ist.
Nun wählt man eine beliebige Startzelle und ruft für die Nachbarzellen in zufälliger Reihenfolge eine Tiefensuche auf. Wenn eine Zelle zum ersten Mal besucht wird, dann wird die entsprechende Mauer zur Vorgängerzelle eingerissen und von dort aus die Nachbarn weiter rekursiv durchsucht.Das ganze ergibt Dir dann ein Labyrinth in dem alle Zellen miteinander verbunden sind und das keine Kreiswege enthält. Wenn Du auch noch Kreise haben willst, dann kannst Du ja anschließend noch gezielt weitere Mauern einreißen.
Das steht übrigens in diesem für Informatik-Interessierte imo sehr empfehlenswerten Buch:
Taschenbuch der Algorithmen | ISBN: 9783540763932
-
Jester schrieb:
Eine einfache Möglichkeit zum Erstellen von Labyrinthen ist die Tiefensuche. Dazu geht man folgendermaßen vor:
Man beginnt mit einem regelmäßigen Gitter, in dem jede Zelle von vier Wänden begrenzt ist und jede Zelle als noch nicht besucht markiert ist.
Nun wählt man eine beliebige Startzelle und ruft für die Nachbarzellen in zufälliger Reihenfolge eine Tiefensuche auf. Wenn eine Zelle zum ersten Mal besucht wird, dann wird die entsprechende Mauer zur Vorgängerzelle eingerissen und von dort aus die Nachbarn weiter rekursiv durchsucht.Das ganze ergibt Dir dann ein Labyrinth in dem alle Zellen miteinander verbunden sind und das keine Kreiswege enthält. Wenn Du auch noch Kreise haben willst, dann kannst Du ja anschließend noch gezielt weitere Mauern einreißen.
Das steht übrigens in diesem für Informatik-Interessierte imo sehr empfehlenswerten Buch:
Taschenbuch der Algorithmen | ISBN: 9783540763932Vielen Dank. Hört sich interessant an
Ich denke ich werde das mal versuchen zu implementieren
-
Speedy_92 schrieb:
productline schrieb:
Also bei Gimp gibt es was http://docs.gimp.org/2.2/de/plug-in-maze.html, weiß aber nicht ob es da immer (nur) eine Lösung gibt und wie du das willst.
Not Found The requested URL /2.2/de/plug-in-maze.html, was not found on this server. Apache/1.3.33 Server at docs.gimp.org Port 80