Generator Labiryntu Polowanie i Zabijanie

Algorytm Hunt and Kill to w rzeczywistości zmodyfikowana wersja rekurencyjnego backtrackera. Modyfikacja polega na systematycznym skanowaniu (lub „polowaniu”) w poszukiwaniu nowej komórki, od której można kontynuować, gdy nie ma już możliwości dalszego przeszukiwania, w przeciwieństwie do prawdziwego przeszukiwania rekurencyjnego, które zawsze wraca do poprzedniej komórki na stosie.

Dzięki temu algorytm ten 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 regułami. Wersja zaimplementowana tutaj wchodzi w tryb „polowania” tylko wtedy, gdy nie może oddalić się 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 (tj. algorytmu rekurencyjnego backtrackera), z tą różnicą, że gdy nie może oddalić się od bieżącej pozycji, systematycznie skanuje (lub „poluje”) labirynt w poszukiwaniu nowej komórki, od której może rozpocząć działanie. Algorytm składa się z dwóch głównych faz: chodzenia i polowania.

Jak działa algorytm „Poluj i zabij” 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 losowego, nieodwiedzonego sąsiada.
• Przejdź do sąsiada, oznacz go jako odwiedzony i utwórz ścieżkę pomię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 przynajmniej jednego odwiedzonego sąsiada.
• Połącz tę komórkę z odwiedzonym sąsiadem, aby wznowić fazę chodzenia.
• Powtarzaj, aż odwiedzisz wszystkie komórki.

Dalsza lektura

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

• Rekurencyjny generator labiryntu Backtracker
• Generator labiryntu algorytmów Wilsona
• Generator labiryntu algorytmów Kruskala