Rekurzívny Backtracker Maze Generator

Rekurzívny algoritmus spätného sledovania je v skutočnosti univerzálne vyhľadávanie do hĺbky. Pri použití na generovanie bludiska sa mierne upravuje tak, aby sa cesta vyberala náhodne, zatiaľ čo pri použití na skutočné vyhľadávacie účely by sa zvyčajne prehľadávala každá úroveň v lineárnom poradí. Má tendenciu vytvárať bludiská s dlhými, kľukatými chodbami a veľmi dlhým, kľukatým riešením.

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.

Rekurzívny algoritmus spätného sledovania je metóda vyhľadávania do hĺbky na generovanie dokonalých bludísk (bludísk bez slučiek a s jednou cestou medzi ľubovoľnými dvoma bodmi). Je jednoduchá, efektívna a vytvára vizuálne príťažlivé bludiská s dlhými, kľukatými chodbami.

Napriek svojmu názvu nemusí byť nevyhnutne implementovaná pomocou rekurzie. Často sa implementuje iteratívnym prístupom s použitím frontu LIFO (t. j. zásobníka). Pri veľmi veľkých bludiskách je pravdepodobnejšie, že použitie rekurzie povedie k pretečeniu zásobníka volaní v závislosti od programovacieho jazyka a dostupnej pamäte. Front LIFO sa dá ľahšie prispôsobiť na spracovanie veľkého množstva údajov, dokonca aj na uchovávanie frontu na disku alebo v databáze, ak nie je k dispozícii dostatok pamäte.

Ako to funguje

Algoritmus funguje na princípe prehľadávania do hĺbky, ktorý je založený na zásobníkoch. Tu je podrobný popis:

1. Vyberte počiatočnú bunku a označte ju ako navštívenú.
2. Pokiaľ existujú nenavštívené bunky: Pozrite sa na susedné bunky, ktoré ešte neboli navštívené. Ak existuje aspoň jeden nenavštívený sused: Náhodne vyberte jedného z nenavštívených susedov. Odstráňte stenu medzi aktuálnou bunkou a vybraným susedom. Presuňte sa k vybranému susedovi a označte ho ako navštíveného. Vložte aktuálnu bunku na zásobník. Ak neexistujú žiadni nenavštívení susedia: Vráťte sa späť odstránením poslednej bunky zo zásobníka.
3. Pokračujte v tomto procese, kým sa zásobník nevyprázdni.

Zaujímavosťou tohto algoritmu je, že funguje ako generátor bludiska aj ako riešiteľ bludiska. Ak ho spustíte na už vygenerovanom bludisku a zastavíte ho, keď dosiahnete určený koncový bod, zásobník bude obsahovať riešenie bludiska.

Na tejto stránke mám v skutočnosti dve verzie tohto algoritmu: verziu založenú na fronte LIFO na generovanie bludísk na tejto stránke a verziu založenú na rekurzii na riešenie bludísk, tiež bludísk generovaných inými algoritmami (takto sa vytvárajú mapy s riešeniami). Mať dve rôzne verzie je len pre šport, pretože som nerd, ktorého to zaujíma, ktorákoľvek by mohla fungovať pre obe ;-)

Ďalšie čítanie

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

• Wilsonov generátor bludísk algoritmov
• Kruskalov generátor bludísk algoritmov
• Ellerov generátor bludísk algoritmov