Generator Labiryntu Polowanie i Zabijanie
Opublikowano: 16 lutego 2025 20:55:38 UTC
Generator labiryntu wykorzystujący algorytm Hunt and Kill do tworzenia idealnego labiryntu. Ten algorytm jest podobny do Recursive Backtracker, ale ma tendencję do generowania labiryntów z nieco krótszymi, krętymi korytarzami.Hunt and Kill Maze Generator
Algorytm Hunt and Kill jest w rzeczywistości zmodyfikowaną wersją Recursive Backtracker. Modyfikacja polega na systematycznym skanowaniu (lub „polowaniu”) w poszukiwaniu nowej komórki, od której można kontynuować, gdy nie można iść dalej, w przeciwieństwie do prawdziwego wyszukiwania rekurencyjnego, które zawsze wraca do poprzedniej komórki na stosie.
Z tego powodu ten algorytm można łatwo dostosować do generowania labiryntów o różnym wyglądzie i charakterze, po prostu wybierając częstsze wchodzenie w tryb „polowania” lub zgodnie z określonymi zasadami. Wersja zaimplementowana tutaj wchodzi w tryb „polowania” tylko wtedy, gdy nie może oddalić się dalej od bieżącej komórki.
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 Hunt and Kill
Algorytm Hunt and Kill to prosta, ale skuteczna metoda generowania labiryntów. Jest on nieco podobny do przeszukiwania w głąb (czyli algorytmu Recursive Backtracker), z tą różnicą, że gdy nie może przejść dalej od bieżącej pozycji, systematycznie skanuje (lub „poluje”) labirynt, aby znaleźć nową komórkę, od której można zacząć. Algorytm składa się z dwóch głównych faz: chodzenia i polowania.
Jak działa algorytm Hunt and Kill w generowaniu labiryntów
Krok 1: Zacznij od losowej komórki
- Znajdź losową komórkę w siatce i oznacz ją jako odwiedzoną.
Krok 2: Faza chodzenia (spacer losowy)
- Wybierz losowo wybranego sąsiada, którego nigdy nie odwiedzałeś.
- Przejdź do sąsiadującej komórki, oznacz ją jako odwiedzoną i wytycz ścieżkę między poprzednią i nową komórką.
- Powtarzaj, aż nie będzie już żadnych nieodwiedzonych sąsiadów.
Krok 3: Faza polowania (cofanie się poprzez skanowanie)
- Przejrzyj siatkę wiersz po wierszu (lub kolumna po kolumnie).
- Znajdź pierwszą nieodwiedzoną komórkę, która ma co najmniej jednego odwiedzonego sąsiada.
- Połącz tę komórkę z odwiedzonym sąsiadem, aby wznowić fazę chodzenia.
- Powtarzaj, aż odwiedzisz wszystkie komórki.