Rostoucí strom Algoritmus bludiště generátor

Algoritmus Rostoucí strom je zajímavý, protože dokáže emulovat chování několika dalších algoritmů v závislosti na tom, jak je během generování vybrána další buňka. Implementace na této stránce používá přístup zaměřující se do šířky a podobný 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 Rostoucí strom je flexibilní a výkonná metoda pro generování dokonalých bludišť. Algoritmus je zajímavý, protože dokáže emulovat chování několika dalších algoritmů pro generování bludišť, 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 s 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ě

• Pokud seznam buněk není prázdný: Vyberte buňku ze seznamu na základě specifické strategie (vysvětleno níže). Vytvoř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 končí, když v seznamu již nejsou žádné další buňky, což znamená, že celé bludiště bylo vytesáno.

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

Charakteristickým rysem algoritmu Growing Tree je způsob, jakým si vyberete, kterou buňku zpracovat dále. Tato volba dramaticky ovlivňuje vzhled bludiště:

Nejnovější buňka (chování podobné zásobníku) – Rekurzivní Backtracker:

• Vždy vyberte naposledy přidanou buňku.
• Vytváří dlouhé, klikaté chodby s mnoha slepými uličkami (jako bludiště prohledávající hloubku).
• Bludiště mívají dlouhé chodby a snadno se řeší.

Náhodná buňka (randomizovaný Primův algoritmus):

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

Nejstarší buňka (chování podobné frontě):

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

Hybridní přístupy:

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

• 90 % nejnovější, 10 % náhodné: Vypadá většinou jako rekurzivní bludiště typu „backtracker“, ale s občasnými větvemi, které přerušují dlouhé chodby.
• 50 % nejnovějších, 50 % nejstarších: Vyvažuje dlouhé chodby keřovitým porostem.

Další čtení

Pokud se vám tento příspěvek líbil, mohly by se vám líbit i tyto návrhy:

• Rekurzivní Backtracker Maze Generator
• Kruskalův Algorithm Maze Generator
• Ellerův algoritmus bludiště generátor