Rekurzívny Backtracker Maze Generator

Algoritmus rekurzívneho backtrackeru je skutočne všeobecným hĺbkovým vyhľadávaním. Keď sa používa na generovanie bludiska, mierne sa upravil tak, aby vybral cestu náhodne, zatiaľ čo ak by sa použil na skutočné účely vyhľadávania, zvyčajne by sa jednoducho hľadala každá úroveň v lineárnom poradí. Má tendenciu vytvárať bludiská s dlhými kľukatými chodbami a veľmi dlhým krútiacim sa 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.

Algoritmus rekurzívneho spätného sledovania je metóda hĺbkového vyhľadávania na generovanie dokonalých bludísk (bludisko bez slučiek a jedinou cestou medzi akýmikoľvek dvoma bodmi). Je to jednoduché, efektívne 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 pomocou LIFO frontu (tj zásobníka). V prípade veľmi veľkých bludísk je pravdepodobnejšie, že použitie rekurzie povedie k pretečeniu zásobníka hovorov v závislosti od programovacieho jazyka a dostupnej pamäte. Front LIFO možno jednoduchšie prispôsobiť na spracovanie veľkého množstva údajov, dokonca aj ponechanie frontu na disku alebo v databáze, ak je dostupná pamäť nedostatočná.

Ako to funguje

Algoritmus pracuje s použitím prístupu hĺbkového vyhľadávania založeného na zásobníku. Tu je podrobný rozpis:

1. Vyberte počiatočnú bunku a označte ju ako navštívenú.
2. Zatiaľ čo existujú nenavštívené bunky:
   • Pozrite sa na susedné cely, ktoré ešte neboli navštívené.
   • Ak existuje aspoň jeden nenavštívený sused:
     • Náhodne si vyberte jedného z nenavštevovaných susedov.
     • Odstráňte stenu medzi aktuálnou bunkou a zvoleným susedom.
     • Presuňte sa k vybranému susedovi a označte ho ako navštíveného.
     • Zatlačte aktuálnu bunku do zásobníka.
   • Ak neexistujú žiadni nenavštívení susedia:
     • Vráťte sa vytiahnutím poslednej bunky zo zásobníka.
3. Pokračujte v tomto procese, kým nebude zásobník prázdny.

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

V skutočnosti mám na tejto stránke v hre dve verzie tohto algoritmu: frontu 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 na šport, pretože som blázon, ktorý to považuje za zaujímavé, obe by mohla fungovať pre obe ;-)