Rekurzivní Backtracker Maze Generator

Rekurzivní algoritmus backtracker je ve skutečnosti univerzální prohledávání do hloubky. Při použití pro generování bludišť je mírně upraven tak, aby vybíral cestu náhodně, zatímco při použití pro skutečné prohledávání by se obvykle prohledávala každá úroveň v lineárním pořadí. Má tendenci vytvářet bludiště s dlouhými, klikatými chodbami a velmi dlouhým, klikatým řešením.

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.

Rekurzivní algoritmus backtrackeru je metoda prohledávání do hloubky pro generování dokonalých bludišť (bludišť bez smyček a s jedinou cestou mezi libovolnými dvěma body). Je jednoduchá, efektivní a vytváří vizuálně přitažlivá bludiště s dlouhými, klikatými chodbami.

Navzdory svému názvu nemusí být nutně implementována pomocí rekurze. Často se implementuje iterativním přístupem s použitím fronty LIFO (tj. zásobníku). U velmi velkých bludišť je pravděpodobnější, že použití rekurze povede k přetečení zásobníku volání, v závislosti na programovacím jazyce a dostupné paměti. Frontu LIFO lze snáze přizpůsobit pro zpracování velkého množství dat, a to i v případě, že není k dispozici dostatek paměti, a dokonce ji uchovat na disku nebo v databázi.

Jak to funguje

Algoritmus pracuje s využitím přístupu prohledávání do hloubky založeného na zásobníku. Zde je podrobný popis:

1. Vyberte počáteční buňku a označte ji jako navštívenou.
2. Dokud existují nenavštívené buňky: Podívejte se na sousední buňky, které dosud nebyly navštíveny. Pokud existuje alespoň jeden nenavštívený soused: Náhodně vyberte jednoho z nenavštívených sousedů. Odstraňte zeď mezi aktuální buňkou a vybraným sousedem. Přejděte k vybranému sousedovi a označte ho jako navštíveného. Vložte aktuální buňku na zásobník. Pokud neexistují žádní nenavštívení sousedé: Vraťte se zpět odebráním poslední buňky ze zásobníku.
3. V tomto postupu pokračujte, dokud se zásobník nevyprázdní.

Zajímavostí tohoto algoritmu je, že funguje jak jako generátor bludišť, tak i jako jeho řešitel. Pokud jej spustíte na již vygenerovaném bludišti a zastavíte ho v okamžiku dosažení určeného koncového bodu, zásobník bude obsahovat řešení bludiště.

Na tomto webu mám ve skutečnosti dvě verze tohoto algoritmu: verzi založenou na frontě LIFO pro generování bludišť na této stránce a verzi založenou na rekurzi pro řešení bludišť, a také bludišť generovaných jinými algoritmy (tak se vytvářejí mapy s řešeními). Dvě různé verze jsou jen pro sport, protože jsem nerd, kterého to zajímá, každá by mohla fungovat pro obě ;-)

Další čtení

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

• Generátor lovu a zabíjení bludiště
• Kruskalův Algorithm Maze Generator
• Ellerův algoritmus bludiště generátor