Generator algorytmu rosnącego drzewa
Opublikowano: 16 lutego 2025 21:36:59 UTC
Ostatnia aktualizacja: 6 marca 2025 09:56:19 UTC
Growing Tree Algorithm Maze Generator
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ą.