Rekurencyjny generator labiryntu Backtracker

Rekurencyjny algorytm backtrackera to w rzeczywistości uniwersalny algorytm przeszukiwania w głąb. W przypadku generowania labiryntu jest on nieznacznie modyfikowany, aby wybierać ścieżkę losowo, natomiast w przypadku faktycznego wyszukiwania zazwyczaj przeszukiwałoby się każdy poziom w kolejności liniowej. Zazwyczaj prowadzi to do powstawania labiryntów z długimi, krętymi korytarzami i bardzo długim, krętym rozwiązaniem.

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.

Rekurencyjny algorytm backtrackera to metoda przeszukiwania w głąb, która pozwala na generowanie idealnych labiryntów (labiryntów bez pętli i z pojedynczą ścieżką między dowolnymi dwoma punktami). Jest prosty, wydajny i tworzy atrakcyjne wizualnie labirynty z długimi, krętymi korytarzami.

Pomimo nazwy, nie musi być ona koniecznie implementowana za pomocą rekurencji. Często jest implementowana w podejściu iteracyjnym z wykorzystaniem kolejki LIFO (czyli stosu). W przypadku bardzo dużych labiryntów, użycie rekurencji z większym prawdopodobieństwem spowoduje przepełnienie stosu wywołań, w zależności od języka programowania i dostępnej pamięci. Kolejkę LIFO można łatwiej dostosować do obsługi dużych ilości danych, nawet przechowując ją na dysku lub w bazie danych, jeśli dostępna pamięć jest niewystarczająca.

Jak to działa

Algorytm działa w oparciu o metodę przeszukiwania w głąb opartą na stosie. Oto opis krok po kroku:

1. Wybierz komórkę początkową i oznacz ją jako odwiedzoną.
2. Dopóki istnieją nieodwiedzone komórki:Spójrz na sąsiednie komórki, które nie zostały jeszcze odwiedzone.Jeśli istnieje co najmniej jeden nieodwiedzony sąsiad:Losowo wybierz jednego z nieodwiedzonych sąsiadów.Usuń przegrodę między bieżącą komórką a wybranym sąsiadem.Przejdź do wybranego sąsiada i oznacz go jako odwiedzonego.Przenieś bieżącą komórkę na stos.Jeśli nie istnieją nieodwiedzeni sąsiedzi:Wróć się, zdejmując ostatnią komórkę ze stosu.
3. Kontynuuj ten proces, aż stos będzie pusty.

Ciekawostką dotyczącą tego algorytmu jest to, że działa on zarówno jako generator labiryntu, jak i narzędzie do jego rozwiązywania. Jeśli uruchomisz go na już wygenerowanym labiryncie i zatrzymasz po osiągnięciu wyznaczonego punktu końcowego, stos będzie zawierał rozwiązanie labiryntu.

Właściwie mam dwie wersje tego algorytmu używane na tej stronie: opartą na kolejce LIFO do generowania labiryntów na tej stronie i opartą na rekurencji do rozwiązywania labiryntów, a także labiryntów generowanych przez inne algorytmy (w ten sposób powstają mapy z rozwiązaniami). Posiadanie dwóch różnych wersji jest tylko dla sportu, bo jestem nerdem, który uważa to za interesujące – każda z nich mogłaby działać w obu przypadkach ;-)

Dalsza lektura

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

• Generator Labiryntu Polowanie i Zabijanie
• Generator labiryntów algorytmów Ellera
• Generator labiryntu algorytmów Kruskala