Miklix

Generator algorytmu rosnącego drzewa

Opublikowano: 16 lutego 2025 21:36:59 UTC
Ostatnia aktualizacja: 6 marca 2025 09:56:19 UTC

Generator labiryntu wykorzystujący algorytm Growing Tree do tworzenia idealnego labiryntu. Ten algorytm ma tendencję do generowania labiryntów podobnych do algorytmu Hunt and Kill, ale z nieco innym typowym rozwiązaniem.

Ta strona została przetłumaczona maszynowo z języka angielskiego, aby była dostępna dla jak największej liczby osób. Niestety, tłumaczenie maszynowe nie jest jeszcze dopracowaną technologią, więc mogą wystąpić błędy. Jeśli wolisz, możesz wyświetlić oryginalną angielską wersję tutaj:

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.


Generowanie nowego labiryntu








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ą.

Udostępnij na BlueskyUdostępnij na FacebookuUdostępnij na LinkedInUdostępnij na TumblrUdostępnij na XUdostępnij na LinkedInPrzypnij na Pintereście

Mikkel Bang Christensen

O autorze

Mikkel Bang Christensen
Mikkel jest twórcą i właścicielem miklix.com. Ma ponad 20-letnie doświadczenie jako profesjonalny programista komputerowy / programista oprogramowania i jest obecnie zatrudniony na pełny etat w dużej europejskiej korporacji IT. Kiedy nie bloguje, poświęca swój wolny czas na szeroki wachlarz zainteresowań, hobby i aktywności, co może w pewnym stopniu znaleźć odzwierciedlenie w różnorodności tematów poruszanych na tej stronie.