Rekurencyjny generator labiryntu Backtracker

Algorytm rekurencyjnego backtrackera jest w rzeczywistości ogólnym przeszukiwaniem w głąb. Gdy jest używany do generowania labiryntu, jest nieznacznie modyfikowany, aby wybierać ścieżkę losowo, podczas gdy gdy jest używany do rzeczywistych celów wyszukiwania, zazwyczaj przeszukiwałoby się każdy poziom w kolejności liniowej. Zwykle tworzy labirynty 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.

Algorytm rekurencyjnego backtrackera to metoda wyszukiwania w głąb w celu generowania idealnych labiryntów (labiryntów bez pętli i z jedną ścieżką między dwoma punktami). Jest prosty, wydajny i tworzy wizualnie atrakcyjne labirynty z długimi, krętymi korytarzami.

Pomimo nazwy, nie musi być koniecznie implementowana za pomocą rekurencji. Często jest implementowana w podejściu iteracyjnym za pomocą kolejki LIFO (czyli stosu). W przypadku bardzo dużych labiryntów, użycie rekurencji bardziej prawdopodobnie 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 utrzymując kolejkę na dysku lub w bazie danych, jeśli dostępna pamięć jest niewystarczająca.

Jak to działa

Algorytm działa przy użyciu podejścia wyszukiwania w głąb opartego na stosie. Oto podział krok po kroku:

1. Wybierz komórkę początkową i oznacz ją jako odwiedzoną.
2. Chociaż istnieją komórki nieodwiedzane:
   • Przyjrzyj się sąsiednim komórkom, które jeszcze nie zostały odwiedzone.
   • Jeśli istnieje przynajmniej jeden nieodwiedzony sąsiad:
     • Wybierz losowo jednego z nieodwiedzonych sąsiadów.
     • Usuń ścianę pomiędzy bieżącą komórką a wybraną komórką sąsiadującą.
     • Przejdź do wybranego sąsiada i oznacz go jako odwiedzonego.
     • Umieść bieżącą komórkę na stosie.
   • Jeżeli nie ma żadnych nieodwiedzonych sąsiadów:
     • Cofnij się, usuwają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 rozwiązywacz labiryntu. Jeśli uruchomisz go na już wygenerowanym labiryncie i po prostu zatrzymasz, gdy osiągniesz ustalony punkt końcowy, stos będzie zawierał rozwiązanie labiryntu.

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