Ellerův algoritmus bludiště generátor

Ellerův algoritmus je algoritmus generování bludiště, který efektivně vytváří dokonalá bludiště (bludiště bez smyček a jedinou cestou mezi libovolnými dvěma body) pomocí přístupu po řádcích. Vytváří bludiště podobná Kruskalově algoritmu, ale dělá to tak, že generuje pouze jeden řádek najednou, aniž by bylo nutné ukládat celé bludiště do paměti. Díky tomu je užitečný pro generování velmi velkých bludišť na velmi omezených systémech a pro generování procedurálního obsahu.

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.

O Ellerově algoritmu

Ellerův algoritmus představil David Eller.

Algoritmus je pozoruhodný svým efektivním přístupem ke generování bludišť po řádcích, takže je ideální pro nekonečná bludiště nebo bludiště generovaná v reálném čase. Běžně se cituje v literatuře pro generování procedurálního obsahu a generování bludišť, ale nepodařilo se mi najít primární zdroje podrobně popisující jeho původní publikaci.

Jak Ellerův algoritmus funguje pro generování bludišť

Ellerův algoritmus zpracovává jeden řádek po druhém, udržuje a upravuje sady spojených buněk. Zajišťuje konektivitu a zároveň se vyhýbá smyčkám a efektivně rozšiřuje bludiště směrem dolů.

Teoreticky může být použit ke generování nekonečných bludišť, nicméně aby bylo zajištěno, že generované bludiště je skutečně řešitelné, je nutné v určitém okamžiku přepnout na logiku „poslední řady“, aby bylo bludiště dokončeno.

Krok 1: Inicializujte první řádek

• Přiřaďte každé buňce v řádku jedinečné ID sady.

Krok 2: Spojte několik sousedních buněk vodorovně

• Náhodně slučujte sousední buňky tak, že jim nastavíte stejné ID sady. Tím je zajištěno, že existují vodorovné průchody.

Krok 3: Vytvořte vertikální připojení k dalšímu řádku

• Pro každou sadu, která se objeví v řádku, se musí alespoň jedna buňka připojit směrem dolů (aby byla zajištěna konektivita).
• Náhodně vyberte jednu nebo více buněk z každé sady pro připojení k dalšímu řádku.

Krok 4: Přejděte na další řádek

• Vertikální připojení přeneste dále přiřazením stejného ID sady odpovídajícím buňkám níže.
• Přiřaďte nová ID sady všem nepřiřazeným buňkám.

Krok 5: Opakujte kroky 2–4, dokud nedosáhnete posledního řádku

• Pokračujte ve zpracování řádek po řádku.

Krok 6: Zpracujte poslední řádek

• Ujistěte se, že všechny buňky v posledním řádku patří do stejné sady sloučením zbývajících samostatných sad.