Kruskals Algorithmus-Labyrinth-Generator

Der Algorithmus von Kruskal ist ein minimaler Spannbaumalgorithmus, der für die Labyrinthgenerierung angepasst werden kann. Er ist besonders effektiv für die Erstellung perfekter Labyrinthe. Eine Alternative zu Kruskals Algorithmus ist Prims Algorithmus, der ebenfalls ein minimaler Spannbaumalgorithmus ist. Da sie jedoch identische Labyrinthe generieren und Kruskals Algorithmus schneller läuft, habe ich mich nicht darum gekümmert, Prims Algorithmus zu implementieren.

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

Kruskals Algorithmus wurde von Joseph Bernard Kruskal Jr. entwickelt, einem amerikanischen Mathematiker, Statistiker und Informatiker. Er beschrieb den Algorithmus erstmals 1956 in seinem Aufsatz „On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem“.

Der Algorithmus ist darauf ausgelegt, den minimalen Spannbaum (MST) eines Graphen zu finden und dabei sicherzustellen, dass alle Knoten mit dem minimal möglichen Gesamtkantengewicht verbunden sind und gleichzeitig Zyklen vermieden werden.

Wie der Kruskal-Algorithmus zur Labyrinthgenerierung funktioniert

Schritt 1: Initialisieren

• Behandeln Sie jede Zelle im Labyrinth als separaten Satz (eine eindeutige Komponente).
• Listen Sie alle Wände zwischen benachbarten Zellen als potenzielle Kanten auf.

Schritt 2: Wände sortieren

• Mischen oder ordnen Sie die Wände zufällig an. Wenn Sie es als echten Kruskal-Algorithmus implementieren, sortieren Sie die Wände in zufälliger Reihenfolge (da für die Labyrinthgenerierung keine Gewichte erforderlich sind).

Schritt 3: Wände bearbeiten

• Durchlaufen Sie die neu angeordneten Wände.
• Wenn die beiden durch die Wand getrennten Zellen zu unterschiedlichen Sets gehören (d. h., sie sind im Labyrinth noch nicht verbunden), entfernen Sie die Wand und führen Sie die Sets zusammen.
• Wenn sie sich bereits im selben Set befinden, überspringen Sie die Wand (um Zyklen zu vermeiden).

Schritt 4: Weiter bis zum Abschluss

• Wiederholen Sie diesen Vorgang, bis alle Zellen 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, kann er mithilfe des Union-Find-Algorithmus optimiert werden, der eine effiziente Möglichkeit bietet, verbundene Zellen während der Labyrinthgenerierung zu verfolgen. Sie können meine PHP-Implementierung des Union-Find-Algorithmus hier sehen: Disjunkte Menge (Union-Find-Algorithmus) in PHP