Generator labiryntu algorytmów Wilsona
Opublikowano: 16 lutego 2025 19:33:12 UTC
Generator labiryntu wykorzystujący algorytm Wilsona do stworzenia idealnego labiryntu. Ten algorytm generuje wszystkie możliwe labirynty o danym rozmiarze z tym samym prawdopodobieństwem, więc teoretycznie może generować labirynty o wielu mieszanych układach, ale ponieważ jest więcej możliwych labiryntów z krótszymi korytarzami niż dłuższymi, częściej będziesz je widzieć.Wilson's Algorithm Maze Generator
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 go bezstronną 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, więc nie zawracałem sobie głowy implementacją algorytmu Aldousa-Brodera tutaj.
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 pierwotnie wprowadził ten algorytm w 1996 r. podczas badań nad losowymi drzewami rozpinającymi i łańcuchami 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 tworzenia idealnie jednolitych 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ą losowego spaceru.
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ą losową komórkę i oznacz ją jako odwiedzoną. Służy ona jako punkt początkowy labiryntu podczas generowania.
Krok 3: Losowy spacer z usuwaniem pętli
- Wybierz nieodwiedzaną komórkę i rozpocznij losowy spacer (poruszając się w losowych kierunkach).
- Jeśli ś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 nieodwiedzanych komórek i wykonuj losowe spacery, aż każda komórka znajdzie się w labiryncie.