Kruskals Algorithmus-Labyrinth-Generator

Kruskals Algorithmus ist ein Algorithmus zur Berechnung minimaler Spannbäume, der sich zur Labyrinthgenerierung anpassen lässt. Er eignet sich besonders gut zur Erstellung perfekter Labyrinthe. Eine Alternative zu Kruskals Algorithmus ist Prims Algorithmus, der ebenfalls ein Algorithmus zur Berechnung minimaler Spannbäume ist. Da beide jedoch identische Labyrinthe erzeugen und Kruskals Algorithmus schneller ist, habe ich auf die Implementierung von Prims Algorithmus verzichtet.

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

Der Kruskal-Algorithmus wurde von Joseph Bernard Kruskal Jr., einem amerikanischen Mathematiker, Statistiker und Informatiker, entwickelt. Er beschrieb den Algorithmus erstmals 1956 in seiner Arbeit „Über den kürzesten Spannbaum eines Graphen und das Problem des Handlungsreisenden“.

Der Algorithmus ist so konzipiert, dass er den minimalen Spannbaum (MST) eines Graphen findet, der sicherstellt, dass alle Knoten mit dem geringstmöglichen Gesamtgewicht der Kanten verbunden sind und gleichzeitig Zyklen vermeidet.

Wie Kruskals Algorithmus zur Labyrinthgenerierung funktioniert

Schritt 1: Initialisieren

• Jede Zelle im Labyrinth wird als separate Menge (eine einzigartige Komponente) betrachtet.
• Alle Wände zwischen benachbarten Zellen sollen als potenzielle Kanten aufgeführt werden.

Schritt 2: Wände sortieren

• Die Wände werden gemischt oder zufällig angeordnet. Bei der Implementierung als echter Kruskal-Algorithmus werden die Wände in zufälliger Reihenfolge sortiert (da die Labyrinthgenerierung keine Gewichte erfordert).

Schritt 3: Wände bearbeiten

• Durchlaufe die neu angeordneten Wände.
• Falls die beiden durch die Wand getrennten Zellen zu unterschiedlichen Mengen gehören (d. h., sie sind im Labyrinth noch nicht miteinander verbunden), wird die Wand entfernt und die Mengen werden zusammengeführt.
• Wenn sie sich bereits im selben Set befinden, überspringen Sie die Wand (um Zyklen zu vermeiden).

Schritt 4: Fahren Sie fort, bis der Vorgang abgeschlossen ist.

• Wiederholen Sie diesen Vorgang, bis alle Zellen miteinander verbunden sind und einen einzigen Spannbaum bilden.
• Am Ende ist jede Zelle ohne Schleifen oder isolierte Abschnitte mit den anderen verbunden.

Da Kruskals Algorithmus auf dem Zusammenführen von Mengen basiert, lässt er sich mithilfe des Union-Find-Algorithmus optimieren. Dieser bietet eine effiziente Möglichkeit, verbundene Zellen während der Labyrinthgenerierung zu verfolgen. Meine PHP-Implementierung des Union-Find-Algorithmus finden Sie hier: Link

Weitere Informationen

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

• Wilsons Algorithmus-Labyrinth-Generator
• Labyrinthgenerator mit wachsendem Baumalgorithmus
• Rekursiver Backtracker-Labyrinthgenerator