Ich habe mich in letzter Zeit mit der Generierung von Labyrinthen beschäftigt und habe mich dann erstmal für den Growing Tree Algorithmus entschieden. Bei diesem Algorithmus werden die Zellen des Labyrinths einer Liste hinzugefügt. Es wird dabei immer zuerst eine Zelle aus dieser Liste ausgewählt und dann zu einer zufälligen, angrenzenden und noch nicht besuchten Zelle ein Durchgang erschaffen. Diese Zelle wird dann der Liste hinzugefügt. Wenn es keine angrenzende Zelle gibt, so wird sie aus der Liste wieder entfernt. Das Labyrinth ist fertig, sobald die Liste leer ist.
Das Spannende ist, dass die Struktur des Labyrinths stark davon abhängt, wie die Zellen aus der Liste ausgesucht werden. Und genau hier bin ich stark am Überlegen, was sich am besten eignet. Ziel ist es, dass es Spaß macht und nicht frustrierend ist.
Wie lang sollte eine Sackgasse maximal sein?
Wie verschnörkelt soll der Weg sein?
Sollte es viele Abzweigungen geben oder längere Wege?

Ich habe hier eine Zusammenstellung, wie die verschiedenen Auswahlmethoden das Labyrinth verändert:

Das Letze ähnelt sehr dem Ersten von der Struktur. Es sollte aber jetzt klar sein, welche Auswirkungen es hat. Vieleicht sollte ich auch einen ganz anderen Algorithmus nehmen. Man muss beachten, dass man später in diesem Labyrinth rumläuft, mit Monstern, Schaltern, Items etc. Dazu können auch gerne Vorschläge gemacht werden. Auch werden Hilfsmittel benötigt, um den Ausgang leichter zu finden. Welche wären am besten dafür geeignet (Einwegkarten, Richtungsanzeige, Integrierte Hinweise...)?

mfg. Chris987

Die list_size-1 Methode ist ja nichts anderes als der Recursive backtracker. Das Problem hierbei ist, dass schnell sehr lange Sackgassen entstehen können. Müsste mal schauen wie sich die am besten vermeiden lassen. Die hier vorgestellten Labyrinthen sind alle perfekte Labyrinthen. Das heißt, es gibt keine Schleifen. Wäre es sinnvoll solche Schleifen generieren zu lassen? Zum einen gibt es Fluchtmöglichkeiten vor Monstern oder Ähnliches. Zum anderen wird der Schwierigkeitsgrad enorm erhöht, dadurch dass man im Kreis laufen kann. Da hilft auch die rechte Hand Regel nicht mehr.