Generator labiryntu algorytmów Wilsona

Algorytm Wilsona to metoda losowego spaceru z wymazaną pętlą, która generuje jednorodne drzewa rozpinające do tworzenia labiryntów. Oznacza to, że wszystkie możliwe labirynty o danym rozmiarze mają takie samo prawdopodobieństwo wygenerowania, co czyni ją nieobciążoną techniką generowania labiryntów. Algorytm Wilsona można uznać za ulepszoną wersję algorytmu Aldousa-Brodera, ponieważ generuje labirynty o identycznych cechach, ale działa znacznie szybciej, dlatego nie zawracałem sobie głowy implementacją algorytmu Aldousa-Brodera.

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 Wilsona

Algorytm Wilsona służący do generowania jednorodnych drzew rozpinających przy użyciu losowej ściany wymazanej za pomocą pętli został stworzony przez Davida Bruce'a Wilsona.

Wilson po raz pierwszy wprowadził ten algorytm w 1996 roku, badając losowe drzewa rozpinające i łańcuchy Markowa w teorii prawdopodobieństwa. Chociaż jego praca dotyczyła głównie matematyki i fizyki statystycznej, algorytm ten został od tego czasu szeroko przyjęty do generowania labiryntów ze względu na jego zdolność do generowania idealnie jednorodnych labiryntów.

Jak działa algorytm Wilsona w generowaniu labiryntów

Algorytm Wilsona gwarantuje, że końcowy labirynt będzie w pełni połączony i pozbawiony pętli poprzez iteracyjne tworzenie ścieżek z nieodwiedzanych komórek za pomocą losowych spacerów.

Krok 1: Zainicjuj

• Zacznij od siatki wypełnionej ścianami.
• Zdefiniuj listę wszystkich możliwych komórek przejściowych.

Krok 2: Wybierz losową komórkę początkową

• Wybierz dowolną komórkę i oznacz ją jako odwiedzoną. Będzie ona punktem początkowym labiryntu podczas generowania.

Krok 3: Spacer losowy z kasowaniem pętli

• Wybierz nieodwiedzaną komórkę i rozpocznij losowy spacer (poruszając się w losowych kierunkach).
• Jeżeli ścieżka dotrze do już odwiedzonej komórki, usuń wszelkie pętle na ścieżce.
• Gdy ścieżka dotrze do odwiedzonego regionu, oznacz wszystkie komórki na ścieżce jako odwiedzone.

Krok 4: Powtarzaj, aż odwiedzisz wszystkie komórki:

• Kontynuuj wybieranie nieodwiedzonych komórek i wykonuj losowe spacery, aż każda komórka będzie częścią labiryntu.

Dalsza lektura

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

• Generator labiryntów algorytmów Ellera
• Generator algorytmu rosnącego drzewa
• Rekurencyjny generator labiryntu Backtracker