Ellers Algorithmus-Labyrinthgenerator

Der Eller-Algorithmus ist ein Labyrinthgenerierungsalgorithmus, der effizient perfekte Labyrinthe (Labyrinthe ohne Schleifen und mit genau einem Pfad zwischen je zwei Punkten) zeilenweise erzeugt. Er erzeugt Labyrinthe ähnlich dem Kruskal-Algorithmus, jedoch indem er jeweils nur eine Zeile generiert, ohne das gesamte Labyrinth im Speicher ablegen zu müssen. Dadurch eignet er sich zur Generierung sehr großer Labyrinthe auf leistungsschwachen Systemen und zur prozeduralen Inhaltsgenerierung.

Ein perfektes Labyrinth ist ein Labyrinth, in dem es genau einen Weg von jedem Punkt des Labyrinths zu jedem anderen Punkt gibt. Das bedeutet, dass man sich nicht im Kreis drehen kann, sondern oft auf Sackgassen stößt, die einen zwingen, umzudrehen und zurückzugehen.

Die hier generierten Labyrinthkarten enthalten eine Standardversion ohne Start- und Zielpositionen, so dass Sie diese selbst bestimmen können: Es gibt eine Lösung von jedem Punkt des Labyrinths zu jedem anderen Punkt. Wenn Sie sich inspirieren lassen möchten, können Sie eine vorgeschlagene Start- und Zielposition aktivieren - und sogar die Lösung zwischen den beiden Punkten sehen.

Über den Eller-Algorithmus

Der Eller-Algorithmus wurde von David Eller eingeführt.

Der Algorithmus zeichnet sich durch seinen effizienten, zeilenweisen Ansatz zur Labyrinthgenerierung aus und eignet sich daher ideal für unendliche oder in Echtzeit generierte Labyrinthe. Er wird häufig in der Literatur zur prozeduralen Inhaltsgenerierung und Labyrinthgenerierung zitiert, jedoch konnte ich keine Primärquellen finden, die seine ursprüngliche Veröffentlichung detailliert beschreiben.

Wie der Eller-Algorithmus zur Labyrinthgenerierung funktioniert

Der Eller-Algorithmus verarbeitet jeweils eine Zeile und verwaltet und modifiziert dabei Gruppen verbundener Zellen. Er gewährleistet die Konnektivität, vermeidet Schleifen und erweitert das Labyrinth effizient nach unten.

Theoretisch lassen sich damit unendliche Labyrinthe erzeugen. Um jedoch sicherzustellen, dass das erzeugte Labyrinth auch tatsächlich lösbar ist, muss irgendwann auf die Logik der "letzten Zeile" umgeschaltet werden, um das Labyrinth zu beenden.

Schritt 1: Initialisierung der ersten Zeile

• Weisen Sie jeder Zelle in der Zeile eine eindeutige Set-ID zu.

Schritt 2: Verbinden Sie einige benachbarte Zellen horizontal

• Benachbarte Zellen werden zufällig zusammengeführt, indem ihnen dieselbe Set-ID zugewiesen wird. Dadurch werden horizontale Übergänge sichergestellt.

Schritt 3: Vertikale Verbindungen zur nächsten Zeile erstellen

• Für jede in der Zeile vorkommende Gruppe muss mindestens eine Zelle nach unten verbunden sein (um die Konnektivität sicherzustellen).
• Wähle zufällig eine oder mehrere Zellen aus jedem Satz aus, um sie mit der nächsten Zeile zu verbinden.

Schritt 4: Zur nächsten Zeile wechseln

• Setzen Sie die vertikalen Verbindungen fort, indem Sie den entsprechenden Zellen unten dieselbe Set-ID zuweisen.
• Weisen Sie allen nicht zugewiesenen Zellen neue Set-IDs zu.

Schritt 5: Wiederholen Sie die Schritte 2–4, bis die letzte Reihe erreicht ist.

• Fahren Sie mit der Verarbeitung Zeile für Zeile fort.

Schritt 6: Die letzte Zeile verarbeiten

• Stellen Sie sicher, dass alle Zellen in der letzten Zeile zur selben Gruppe gehören, indem Sie alle verbleibenden separaten Gruppen zusammenführen.

Weitere Informationen

Wenn Ihnen dieser Beitrag gefallen hat, könnten Ihnen auch diese Vorschläge gefallen:

• Kruskals Algorithmus-Labyrinth-Generator
• Wilsons Algorithmus-Labyrinth-Generator
• Rekursiver Backtracker-Labyrinthgenerator