Ellerův algoritmus bludiště generátor

Ellerův algoritmus je algoritmus pro generování bludišť, který efektivně vytváří dokonalá bludiště (bludiště bez smyček a s jedinou cestou mezi libovolnými dvěma body) pomocí přístupu řádek po řádku. Vytváří bludiště podobně jako Kruskalův algoritmus, ale generuje pouze jeden řádek po druhém, bez nutnosti 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.

Tento algoritmus je pozoruhodný svým efektivním přístupem k generování bludišť řádek po řádku, což ho činí ideálním pro nekonečná bludiště nebo bludiště generovaná v reálném čase. Často se cituje v literatuře o procedurálním generování obsahu a generování bludišť, ale nepodařilo se mi najít primární zdroje s podrobnostmi o jeho původní publikaci.

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

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

Teoreticky se dá použít ke generování nekonečných bludišť, nicméně aby se zajistilo, že vygenerované bludiště je skutečně řešitelné, je nutné v určitém okamžiku přepnout na logiku „posledního řádku“, aby se bludiště dokončilo.

Krok 1: Inicializace prvního řádku

• 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ě sloučit sousední buňky nastavením stejného ID sady. Tím se zajistí, že budou existovat horizontální průchody.

Krok 3: Vytvořte vertikální spojení s dalším řádkem

• Pro každou sadu, která se v řádku objeví, musí být alespoň jedna buňka spojena směrem dolů (aby byla zajištěna konektivita).
• Každé sady náhodně vyberte jednu nebo více buněk, které se propojí s dalším řádkem.

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

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

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

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

Krok 6: Zpracování poslední řady

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

Další čtení

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

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