Generator algorytmu rosnącego drzewa

Algorytm Growing Tree jest interesujący, ponieważ może emulować zachowanie kilku innych algorytmów, w zależności od sposobu wyboru kolejnej komórki podczas generacji. Implementacja przedstawiona na tej stronie wykorzystuje podejście oparte na kolejce i podejściu „najpierw wszerz”.

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 rosnącego drzewa

Algorytm Growing Tree to elastyczna i wydajna metoda generowania idealnych labiryntów. Jest on interesujący, ponieważ może emulować działanie kilku innych algorytmów generowania labiryntów, takich jak algorytm Prima, rekurencyjne cofanie się i rekurencyjne dzielenie, w zależności od sposobu wyboru kolejnej komórki do przetworzenia.

Jak działa algorytm rosnącego drzewa

Krok 1: Inicjalizacja

• Zacznij od siatki nieodwiedzanych komórek.
• Wybierz losową komórkę początkową i dodaj ją do listy.

Krok 2: Pętla generowania labiryntu

• Dopóki lista komórek nie jest pusta:Wybierz komórkę z listy na podstawie określonej strategii (wyjaśnionej poniżej).Wytnij przejście z wybranej komórki do jednego z jej nieodwiedzonych sąsiadów (wybranego losowo).Dodaj sąsiada do listy, ponieważ stanie się on częścią labiryntu.Jeśli wybrana komórka nie ma nieodwiedzonych sąsiadów, usuń ją z listy.

Krok 3: Zakończenie

• Algorytm kończy się, gdy na liście nie ma już żadnych komórek, co oznacza, że cały labirynt został utworzony.

Strategie selekcji komórek (elastyczność algorytmu)

Cechą charakterystyczną algorytmu Growing Tree jest wybór komórki do przetworzenia w następnej kolejności. Ten wybór ma ogromny wpływ na wygląd labiryntu:

Najnowsza komórka (zachowanie przypominające stos) – rekurencyjny backtracker:

• Zawsze wybieraj ostatnio dodaną komórkę.
• Tworzy długie, kręte korytarze z wieloma ślepymi zaułkami (jak labirynt w trakcie poszukiwań w głąb).
• Labirynty z reguły mają długie przejścia i są łatwe do rozwiązania.

Losowa komórka (randomizowany algorytm Prim'a):

• Za każdym razem wybierz losową komórkę z listy.
• Tworzy bardziej równomiernie rozłożony labirynt ze skomplikowanymi, splątanymi ścieżkami.
• Mniej długich korytarzy i więcej rozgałęzień.

Najstarsza komórka (zachowanie przypominające kolejkę):

• Zawsze wybieraj najstarszą komórkę na liście.
• Generuje labirynty o bardziej równomiernym rozłożeniu, przypominające wzorzec przeszukiwania wszerz.
• Krótkie, krzaczaste przejścia z gęstymi połączeniami.
• (To jest wersja zaimplementowana tutaj)

Podejścia hybrydowe:

Łącz strategie dla zróżnicowanych cech labiryntu. Na przykład:

• 90% najnowsze, 10% losowe: Wygląda głównie jak rekurencyjny labirynt typu backtracker, ale z okazjonalnymi odgałęzieniami, które rozbijają długie korytarze.
• 50% najnowsze, 50% najstarsze: równoważy długie korytarze krzaczastą roślinnością.

Dalsza lektura

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

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