Ellerov generátor bludísk algoritmov

Ellerov algoritmus je algoritmus generovania bludísk, ktorý efektívne vytvára dokonalé bludiská (bludiská bez slučiek a s jednou cestou medzi ľubovoľnými dvoma bodmi) pomocou prístupu riadok po riadku. Vytvára bludiská podobné Kruskalovmu algoritmu, ale robí to generovaním iba jedného riadku naraz, bez nutnosti ukladať celé bludisko 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.

Tento algoritmus je pozoruhodný svojím efektívnym prístupom k generovaniu bludiska riadok po riadku, vďaka čomu je ideálny pre nekonečné bludiská alebo bludiská generované v reálnom čase. Bežne sa cituje v literatúre o generovaní procedurálneho obsahu a generovaní bludiska, ale nenašiel som primárne zdroje s podrobnosťami o jeho pôvodnej publikácii.

Ako funguje Ellerov algoritmus pre generovanie bludiska

Ellerov algoritmus spracováva jeden riadok po druhom, pričom udržiava a upravuje sady prepojených buniek. Zaisťuje prepojenie, pričom 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, avšak aby sa zabezpečilo, že vygenerované bludisko je skutočne riešiteľné, je potrebné v určitom bode prepnúť na logiku „posledného riadku“, aby sa bludisko dokončilo.

Krok 1: Inicializácia prvého riadku

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

Krok 2: Horizontálne spojenie susedných buniek

• Náhodne zlúčte susedné bunky nastavením rovnakého ID sady. Tým sa zabezpečí, že budú existovať horizontálne priechody.

Krok 3: Vytvorenie vertikálnych spojení s ďalším riadkom

• Pre každú množinu, ktorá sa objaví v riadku, musí byť aspoň jedna bunka spojená smerom nadol (aby sa zabezpečila konektivita).
• Každej sady náhodne vyberte jednu alebo viac buniek, ktoré sa pripoja k ďalšiemu riadku.

Krok 4: Prejdite na ďalší riadok

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

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

• Pokračujte v spracovaní riadok po riadku.

Krok 6: Spracovanie posledného riadku

• Zlúčením všetkých zostávajúcich samostatných množín zabezpečte, aby všetky bunky v poslednom riadku patrili do rovnakej množiny.

Ďalšie čítanie

Ak sa vám tento príspevok páčil, možno sa vám budú páčiť aj tieto návrhy:

• Kruskalov generátor bludísk algoritmov
• Rastúci strom Algoritmus bludisko generátor
• Wilsonov generátor bludísk algoritmov