Ellers Algorithmus-Labyrinthgenerator

Ellers Algorithmus ist ein Algorithmus zur Labyrinthgenerierung, der mithilfe eines zeilenweisen Ansatzes effizient perfekte Labyrinthe (Labyrinthe ohne Schleifen und mit einem einzigen Pfad zwischen zwei beliebigen Punkten) erzeugt. Er erzeugt Labyrinthe ähnlich dem Kruskal-Algorithmus, erzeugt dabei jedoch jeweils nur eine Zeile, ohne dass das gesamte Labyrinth im Speicher abgelegt werden muss. Dadurch eignet er sich gut für die Generierung sehr großer Labyrinthe auf sehr begrenzten Systemen und für die Generierung prozeduraler Inhalte.

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 Ellers Algorithmus

Ellers Algorithmus wurde von David Eller eingeführt.

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

Wie Ellers Algorithmus zur Labyrinthgenerierung funktioniert

Ellers Algorithmus verarbeitet jeweils eine Zeile und behält dabei Gruppen verbundener Zellen bei und ändert sie. Er stellt die Konnektivität sicher, vermeidet Schleifen und erweitert das Labyrinth effizient nach unten.

Theoretisch können damit unendliche Labyrinthe erzeugt werden. Um jedoch sicherzustellen, dass das erzeugte Labyrinth tatsächlich lösbar ist, muss an einem bestimmten Punkt zur Logik „Letzte Reihe“ gewechselt werden, um das Labyrinth zu beenden.

Schritt 1: Initialisieren Sie die erste Zeile

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

Schritt 2: Einige benachbarte Zellen horizontal verbinden

• Füge benachbarte Zellen zufällig zusammen, indem du ihnen die gleiche Set-ID zuweist. Dadurch stellst du sicher, dass horizontale Übergänge vorhanden sind.

Schritt 3: Vertikale Verbindungen zur nächsten Reihe herstellen

• Für jeden Satz, der in der Zeile erscheint, muss mindestens eine Zelle nach unten verbunden sein (um die Konnektivität sicherzustellen).
• Wählen Sie nach dem Zufallsprinzip eine oder mehrere Zellen aus jedem Satz aus, um sie mit der nächsten Zeile zu verbinden.

Schritt 4: Zur nächsten Zeile wechseln

• Führen Sie die vertikalen Verbindungen weiter, indem Sie den entsprechenden Zellen darunter 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 Reihe bearbeiten

• Stellen Sie sicher, dass alle Zellen in der letzten Zeile zum selben Satz gehören, indem Sie alle verbleibenden separaten Sätze zusammenführen.