Rostoucí strom Algoritmus bludiště generátor

Algoritmus Growing Tree je zajímavý, protože dokáže emulovat chování několika dalších algoritmů v závislosti na tom, jak se při generování vybere další buňka. Implementace na této stránce používá přístup založený na šířce jako ve frontě.

Dokonalé bludiště je bludiště, ve kterém existuje přesně jedna cesta z kteréhokoli bodu bludiště do kteréhokoli jiného bodu. To znamená, že nemůžete skončit v kruhu, ale často narazíte na slepé uličky, které vás donutí se otočit a vrátit se zpět.

Zde vygenerované mapy bludiště obsahují výchozí verzi bez počátečních a cílových pozic, takže si je můžete určit sami: z jakéhokoli bodu v bludišti do jakéhokoli jiného bodu existuje řešení. Pokud se chcete inspirovat, můžete zapnout navrhovanou startovní a cílovou pozici - a dokonce si prohlédnout řešení mezi nimi.

O algoritmu rostoucího stromu

Algoritmus Growing Tree je flexibilní a výkonná metoda pro generování dokonalých bludišť. Algoritmus je zajímavý, protože může emulovat chování několika dalších algoritmů pro generování bludiště, jako je Primův algoritmus, rekurzivní zpětné sledování a rekurzivní dělení, v závislosti na tom, jak vyberete další buňku ke zpracování.

Jak funguje algoritmus rostoucího stromu

Krok 1: Inicializace

• Začněte mřížkou nenavštívených buněk.
• Vyberte náhodnou počáteční buňku a přidejte ji do seznamu.

Krok 2: Smyčka generování bludiště

• Zatímco seznam buněk není prázdný:
  • Vyberte buňku ze seznamu na základě konkrétní strategie (vysvětleno níže).
  • Vyřízněte průchod z vybrané buňky k jednomu z jejích nenavštívených sousedů (vybraných náhodně).
  • Přidejte souseda do seznamu, protože je nyní součástí bludiště.
  • Pokud vybraná buňka nemá žádné nenavštívené sousedy, odeberte ji ze seznamu.

Krok 3: Ukončení

• Algoritmus skončí, když v seznamu nejsou žádné další buňky, což znamená, že celé bludiště bylo vyřezáno.

Strategie výběru buněk (flexibilita algoritmu)

Charakteristickým rysem algoritmu Growing Tree je způsob, jakým si vyberete buňku, kterou chcete zpracovat jako další. Tato volba dramaticky ovlivní vzhled bludiště:

Nejnovější buňka (chování podobné stacku) – rekurzivní backtracker:

• Vždy vyberte naposledy přidanou buňku.
• Vytváří dlouhé, klikaté chodby s mnoha slepými uličkami (jako hloubkové hledací bludiště).
• Bludiště mívají dlouhé průchody a jsou snadno řešitelná.

Random Cell (Randomized Prim's Algorithm):

• Pokaždé vyberte ze seznamu náhodnou buňku.
• Vytváří rovnoměrněji rozmístěné bludiště se složitými, spletitými cestami.
• Méně dlouhých chodeb a více větvení.

Nejstarší buňka (chování jako ve frontě):

• Vždy vyberte nejstarší buňku v seznamu.
• Generuje bludiště s rovnoměrnějším rozložením, jako je vyhledávací vzor na šířku.
• Krátké, křovinaté chodby s hustým napojením.
• (Toto je verze implementovaná zde)

Hybridní přístupy:

Kombinujte strategie pro různé charakteristiky bludiště. Například:

• 90 % nejnovějších, 10 % náhodných: Vypadá většinou jako bludiště rekurzivního zpětného sledování, ale s občasnými větvemi, které rozbíjejí dlouhé chodby.
• 50 % nejnovější, 50 % nejstarší: Vyrovnává dlouhé chodby keřovitým porostem.