Rastúci strom Algoritmus bludisko generátor

Algoritmus Rastúci strom je zaujímavý, pretože dokáže emulovať správanie niekoľkých iných algoritmov v závislosti od toho, ako sa počas generovania vyberie ďalšia bunka. Implementácia na tejto stránke používa prístup zameraný na šírku a podobný frontu.

Dokonalé bludisko je bludisko, v ktorom existuje presne jedna cesta z ktoréhokoľvek bodu bludiska do ktoréhokoľvek iného bodu. To znamená, že nemôžete skončiť v kruhu, ale často narazíte na slepé uličky, ktoré vás prinútia otočiť sa a vrátiť sa späť.

Tu vygenerované mapy bludiska obsahujú predvolenú verziu bez počiatočnej a cieľovej pozície, takže si ich môžete určiť sami: z ľubovoľného bodu bludiska do ľubovoľného iného bodu bude existovať riešenie. Ak sa chcete inšpirovať, môžete zapnúť navrhovanú počiatočnú a cieľovú pozíciu - a dokonca si pozrieť riešenie medzi nimi.

O algoritme rastúceho stromu

Algoritmus Rastúci strom je flexibilná a výkonná metóda na generovanie dokonalých bludísk. Algoritmus je zaujímavý, pretože dokáže emulovať správanie niekoľkých ďalších algoritmov na generovanie bludísk, ako je Primov algoritmus, rekurzívne spätné sledovanie a rekurzívne delenie, v závislosti od toho, ako vyberiete ďalšiu bunku na spracovanie.

Ako funguje algoritmus rastúceho stromu

Krok 1: Inicializácia

• Začnite s mriežkou nenavštívených buniek.
• Vyberte náhodnú počiatočnú bunku a pridajte ju do zoznamu.

Krok 2: Slučka generovania bludiska

• Pokiaľ zoznam buniek nie je prázdny: Vyberte bunku zo zoznamu na základe špecifickej stratégie (vysvetlenej nižšie). Vytvorte priechod z vybranej bunky k jednému z jej nenavštívených susedov (vybraných náhodne). Pridajte suseda do zoznamu, pretože je teraz súčasťou bludiska. Ak vybraná bunka nemá žiadnych nenavštívených susedov, odstráňte ju zo zoznamu.

Krok 3: Ukončenie

• Algoritmus končí, keď v zozname už nie sú žiadne bunky, čo znamená, že celé bludisko je vytesané.

Stratégie výberu buniek (flexibilita algoritmu)

Rozhodujúcou črtou algoritmu Growing Tree je spôsob, akým si vyberiete, ktorú bunku spracujete ďalej. Táto voľba dramaticky ovplyvňuje vzhľad bludiska:

Najnovšia bunka (správanie podobné zásobníku) – Rekurzívny Backtracker:

• Vždy vyberte naposledy pridanú bunku.
• Vytvára dlhé, kľukaté chodby s mnohými slepými uličkami (ako bludisko s prehľadávaním do hĺbky).
• Bludiská majú tendenciu mať dlhé chodby a sú ľahko riešiteľné.

Náhodná bunka (náhodný Primov algoritmus):

• Zakaždým vyberte zo zoznamu náhodnú bunku.
• Vytvára rovnomernejšie rozložené bludisko so zložitými, zamotanými cestami.
• Menej dlhých chodieb a viac rozvetvenia.

Najstaršia bunka (správanie podobné frontu):

• Vždy vyberte najstaršiu bunku v zozname.
• Generuje bludiská s rovnomernejším rozložením, podobne ako vzor vyhľadávania do šírky.
• Krátke, husto zarastené chodby s hustým prepojením.
• (Toto je verzia implementovaná tu)

Hybridné prístupy:

Kombinujte stratégie pre rôzne charakteristiky bludiska. Napríklad:

• 90 % najnovšie, 10 % náhodné: Vyzerá prevažne ako rekurzívne bludisko s návratom do pôvodného stavu, ale s občasnými vetvami, ktoré prerušujú dlhé chodby.
• 50 % najnovšie, 50 % najstaršie: Vyvažuje dlhé chodby hustým porastom.

Ďalšie čítanie

Ak sa vám tento príspevok páčil, možno sa vám budú páčiť aj tieto návrhy:

• Kruskalov generátor bludísk algoritmov
• Ellerov generátor bludísk algoritmov
• Generátor Bludiska Lov a Zabitie