Rastúci strom Algoritmus bludisko generátor

Algoritmus Growing Tree je zaujímavý, pretože dokáže napodobniť správanie niekoľkých ďalší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 podobný šírke 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 Growing Tree je flexibilná a výkonná metóda na vytváranie dokonalých bludísk. Algoritmus je zaujímavý, pretože dokáže napodobniť správanie niekoľkých ďalších algoritmov vytvárania 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

• Zatiaľ čo zoznam buniek nie je prázdny:
  • Vyberte bunku zo zoznamu na základe špecifickej stratégie (vysvetlené nižšie).
  • Vyrežte 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 vybratá bunka nemá nenavštívených susedov, odstráňte ju zo zoznamu.

Krok 3: Ukončenie

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

Stratégie výberu buniek (flexibilita algoritmu)

Definujúcou vlastnosťou algoritmu rastúceho stromu je spôsob výberu bunky, ktorá sa má spracovať ako ďalšia. Táto voľba dramaticky ovplyvňuje vzhľad bludiska:

Najnovšia bunka (správanie podobné stohovaniu) – rekurzívny backtracker:

• Vždy vyberte naposledy pridanú bunku.
• Vytvára dlhé, kľukaté chodby s mnohými slepými uličkami (ako hĺbkové prehľadávacie bludisko).
• Bludisko máva dlhé pasáže a je ľahké ich vyriešiť.

Random Cell (Randomized Prim's Algorithm):

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

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

• Vždy vyberte najstaršiu bunku v zozname.
• Vytvára bludiská s rovnomernejším rozložením, ako je vzor vyhľadávania do šírky.
• Krátke krovinaté 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ších, 10 % náhodných: Vyzerá väčšinou ako bludisko rekurzívneho spätného sledovania, ale s občasnými vetvami, ktoré prerušujú dlhé chodby.
• 50 % najnovšie, 50 % najstaršie: Vyrovnáva dlhé chodby hustým porastom.