Generator labiryntu algorytmów Kruskala

Algorytm Kruskala to algorytm minimalnego drzewa rozpinającego, który można zaadaptować do generowania labiryntów. Jest on 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ą one 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ł go w 1956 roku w artykule „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 składnik).
• 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 implementujesz to jako prawdziwy algorytm Kruskala, posortuj ściany w losowej kolejności (ponieważ generowanie labiryntu nie wymaga wag).

Krok 3: Przetwarzaj ściany

• Przechodź przez pomieszane ściany.
• Jeśli dwie komórki oddzielone ścianą należą do różnych zestawów (tzn. 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 pętli lub izolowanych sekcji.

Ponieważ algorytm Kruskala opiera się na scalaniu zbiorów, można go zoptymalizować za pomocą algorytmu Union-Find, który zapewnia efektywny sposób śledzenia połączonych komórek podczas generowania labiryntu. Moją implementację algorytmu Union-Find w PHP można zobaczyć tutaj: Link

Dalsza lektura

Jeśli podobał Ci się ten wpis, mogą Cię zainteresować również poniższe sugestie:

• Generator labiryntów algorytmów Ellera
• Generator Labiryntu Polowanie i Zabijanie
• Generator algorytmu rosnącego drzewa