Ellerov generátor bludísk algoritmov

Ellerov algoritmus je algoritmus generovania bludiska, ktorý efektívne vytvára dokonalé bludisko (bludisko bez slučiek a jedinou cestou medzi akýmikoľvek dvoma bodmi) pomocou prístupu riadok po riadku. Vytvára bludisko podobné Kruskalovmu algoritmu, ale robí to tak, že generuje iba jeden riadok naraz, bez potreby ukladania celého bludiska do pamäte. Vďaka tomu je užitočný na generovanie veľmi veľkých bludísk na veľmi obmedzených systémoch a na generovanie procedurálneho obsahu.

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.

O Ellerovom algoritme

Ellerov algoritmus predstavil David Eller.

Algoritmus sa vyznačuje efektívnym prístupom ku generovaniu bludiska riadok po riadku, vďaka čomu je ideálny pre nekonečné bludisko alebo bludisko generované v reálnom čase. Bežne sa cituje v literatúre o generovaní procedurálneho obsahu a bludisku, ale nepodarilo sa mi nájsť primárne zdroje podrobne popisujúce jeho pôvodnú publikáciu.

Ako funguje Ellerov algoritmus pri vytváraní bludiska

Ellerov algoritmus spracováva jeden riadok po druhom, pričom udržiava a upravuje sady spojených buniek. Zabezpečuje konektivitu a zároveň sa vyhýba slučkám a efektívne rozširuje bludisko smerom nadol.

Teoreticky sa dá použiť na generovanie nekonečných bludísk, ale aby sa zabezpečilo, že vygenerované bludisko je skutočne riešiteľné, je potrebné v určitom bode prepnúť na logiku „posledného radu“, aby sa bludisko dokončilo.

Krok 1: Inicializujte prvý riadok

• Priraďte každej bunke v riadku jedinečné ID sady.

Krok 2: Vodorovne pripojte niekoľko susedných buniek

• Náhodne zlúčte susedné bunky tak, že im nastavíte rovnaké ID sady. To zaisťuje, že existujú vodorovné priechody.

Krok 3: Vytvorte vertikálne pripojenia k ďalšiemu riadku

• Pre každú množinu, ktorá sa zobrazí v riadku, sa musí aspoň jedna bunka pripojiť smerom nadol (aby sa zabezpečila konektivita).
• Náhodne vyberte jednu alebo viac buniek z každej sady, aby ste sa pripojili k ďalšiemu riadku.

Krok 4: Prejdite na ďalší riadok

• Vertikálne pripojenia preneste ďalej priradením rovnakého ID sady zodpovedajúcim bunkám nižšie.
• Priraďte nové ID sady všetkým nepriradeným bunkám.

Krok 5: Opakujte kroky 2–4, kým sa nedosiahne posledný riadok

• Pokračujte v spracovaní riadok po riadku.

Krok 6: Spracujte posledný riadok

• Uistite sa, že všetky bunky v poslednom riadku patria do rovnakej množiny zlúčením zostávajúcich samostatných množín.