Generator labiryntu algorytmów Kruskala
Opublikowano: 16 lutego 2025 17:59:50 UTC
Generator labiryntu wykorzystujący algorytm Kruskala do stworzenia idealnego labiryntu. Ten algorytm ma tendencję do tworzenia labiryntów ze średniej długości korytarzami i wieloma ślepymi zaułkami, a także dość prostymi rozwiązaniami.Kruskal's Algorithm Maze Generator
Algorytm Kruskala to algorytm minimalnego drzewa rozpinającego, który można dostosować do generowania labiryntów. Jest szczególnie skuteczny w tworzeniu idealnych labiryntów. Alternatywą dla algorytmu Kruskala jest algorytm Prima, który również jest algorytmem minimalnego drzewa rozpinającego, ale ponieważ generują identyczne labirynty, a algorytm Kruskala działa szybciej, nie zawracałem sobie głowy implementacją algorytmu Prima.
Idealny labirynt to labirynt, w którym istnieje dokładnie jedna ścieżka z dowolnego punktu w labiryncie do dowolnego innego punktu. Oznacza to, że nie można kręcić się w kółko, ale często napotyka się ślepe zaułki, które zmuszają do zawrócenia.
Wygenerowane tutaj mapy labiryntu zawierają domyślną wersję bez pozycji początkowej i końcowej, więc możesz sam o tym zdecydować: będzie rozwiązanie z dowolnego punktu w labiryncie do dowolnego innego punktu. Jeśli chcesz się zainspirować, możesz włączyć sugerowaną pozycję początkową i końcową - a nawet zobaczyć rozwiązanie między nimi.
O algorytmie Kruskala
Algorytm Kruskala został stworzony przez Josepha Bernarda Kruskala Jr., amerykańskiego matematyka, statystyka i informatyka. Po raz pierwszy opisał algorytm w 1956 r. w swojej pracy „On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”.
Algorytm ma na celu znalezienie minimalnego drzewa rozpinającego (MST) grafu, zapewniając, że wszystkie wierzchołki są połączone przy użyciu minimalnej możliwej całkowitej wagi krawędzi, unikając przy tym cykli.
Jak działa algorytm Kruskala w generowaniu labiryntów
Krok 1: Zainicjuj
- Każdą komórkę w labiryncie traktuj jako osobny zestaw (unikalny komponent).
- Wymień wszystkie ściany pomiędzy sąsiadującymi komórkami jako potencjalne krawędzie.
Krok 2: Sortowanie ścian
- Przetasuj lub losowo uporządkuj ściany. Jeśli zaimplementujesz to jako prawdziwy algorytm Kruskala, posortuj ściany w losowej kolejności (ponieważ generowanie labiryntu nie wymaga wag).
Krok 3: Przetwarzaj ściany
- Przejdź przez pomieszane ściany.
- Jeśli dwie komórki rozdzielone ścianą należą do różnych zestawów (czyli nie są jeszcze połączone w labiryncie), usuń ścianę i połącz zestawy.
- Jeśli znajdują się już w tym samym zestawie, pomiń ścianę (aby uniknąć cykli).
Krok 4: Kontynuuj do zakończenia
- Powtarzaj ten proces, aż wszystkie komórki zostaną połączone, tworząc pojedyncze drzewo rozpinające.
- Na końcu każda komórka jest połączona z pozostałymi bez tworzenia pętli lub izolowanych sekcji.
Ponieważ algorytm Kruskala opiera się na łączeniu zestawów, można go zoptymalizować, używając algorytmu Union-Find, który zapewnia wydajny sposób śledzenia połączonych komórek podczas generowania labiryntu. Moją implementację algorytmu Union-Find w PHP można zobaczyć tutaj: Zestaw rozłączny (algorytm Union-Find) w PHP