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 tego, jak następna komórka jest wybierana podczas generowania. Implementacja na tej stronie wykorzystuje podejście typu wideth-first, podobne do kolejki.

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. Algorytm jest interesujący, ponieważ może emulować zachowanie kilku innych algorytmów generowania labiryntów, takich jak algorytm Prima, rekurencyjne cofanie się i rekurencyjne dzielenie, w zależności od tego, jak wybierzesz następną komórkę 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

• Jeśli lista komórek nie jest pusta:
  • Wybierz komórkę z listy na podstawie określonej strategii (wyjaśnionej poniżej).
  • Wytycz przejście z wybranej komórki do jednej z jej nieodwiedzonych sąsiadek (wybranych losowo).
  • Dodaj sąsiada do listy, ponieważ teraz jest on częścią labiryntu.
  • Jeśli wybrana komórka nie ma żadnych 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 wyboru komórek (elastyczność algorytmu)

Cechą charakterystyczną algorytmu Growing Tree jest to, w jaki sposób wybierasz, którą komórkę przetworzyć jako następną. Ten wybór dramatycznie wpływa na wygląd labiryntu:

Najnowsza komórka (zachowanie podobne do stosu) – rekurencyjny backtracker:

• Zawsze wybieraj ostatnio dodaną komórkę.
• Tworzy długie, kręte korytarze z wieloma ślepymi zaułkami (jak w labiryncie 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'sa):

• 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 podobne do kolejki):

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

Podejścia hybrydowe:

Połą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 rozgałęzieniami, które rozbijają długie korytarze.
• 50% najnowsze, 50% najstarsze: równoważy długie korytarze bujną roślinnością.