Rekurzivní Backtracker Maze Generator

Algoritmus rekurzivního zpětného sledování je ve skutečnosti obecným účelem prohledávání do hloubky. Při použití pro generování bludiště se mírně upravil tak, aby cestu vybral náhodně, zatímco při použití pro skutečné účely hledání by člověk typicky prohledával každou úroveň v lineárním pořadí. Má tendenci vytvářet bludiště s dlouhými, klikatými chodbami a velmi dlouhým, kroucený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.

Algoritmus rekurzivního zpětného sledování je metoda prohledávání do hloubky pro generování dokonalých bludišť (bludiště bez smyček a jedinou cestou mezi libovolnými dvěma body). Je to 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án pomocí rekurze. Často se implementuje v iterativním přístupu pomocí 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 snadněji přizpůsobit pro zpracování velkého množství dat, a to i ponechat frontu na disku nebo v databázi, pokud není k dispozici dostatek paměti.

Jak to funguje

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

1. Vyberte počáteční buňku a označte ji jako navštívenou.
2. Zatímco existují nenavštívené buňky:
   • Podívejte se na sousední cely, které ještě nebyly navštíveny.
   • Pokud existuje alespoň jeden nenavštívený soused:
     • Náhodně si vyberte jednoho z nenavštěvovaných sousedů.
     • Odstraňte zeď mezi aktuální buňkou a vybraným sousedem.
     • Přesuňte se k vybranému sousedovi a označte jej jako navštíveného.
     • Posuňte aktuální buňku do zásobníku.
   • Pokud neexistují žádní nenavštívení sousedé:
     • Zpět vytažením poslední buňky ze zásobníku.
3. Pokračujte v tomto procesu, dokud není zásobník prázdný.

Zajímavým faktem o tomto algoritmu je, že funguje jak jako generátor bludiště, tak jako luštitel. Pokud jej spustíte na již vygenerovaném bludišti a zastavíte se, když dosáhnete určeného koncového bodu, zásobník bude obsahovat řešení bludiště.

Ve skutečnosti mám na tomto webu ve hře dvě verze tohoto algoritmu: frontu LIFO pro generování bludišť na této stránce a rekurzi založenou na řešení bludišť, také bludišť generovaných jinými algoritmy (tak se tvoří mapy s řešeními). Mít dvě různé verze je jen pro sport, protože jsem blázen, který to považuje za zajímavé, každá by mohla fungovat pro obě ;-)