Generátor Bludiska Lov a Zabitie

Algoritmus Hunt and Kill je v skutočnosti upravenou verziou rekurzívneho Backtrackeru. Modifikácia spočíva v systematickom skenovaní (alebo „hľadaní“) novej bunky, od ktorej sa dá pokračovať, na rozdiel od skutočného rekurzívneho vyhľadávania, ktoré sa vždy vráti k predchádzajúcej bunke na zásobníku.

Vďaka tomu sa tento algoritmus dá ľahko prispôsobiť na generovanie bludísk s rôznym vzhľadom a dojmom, a to len výberom častejšieho vstupu do režimu „lovu“ alebo podľa špecifických pravidiel. Verzia implementovaná v tomto dokumente vstupuje do režimu „lovu“ iba vtedy, keď sa nemôže dostať ďalej od aktuálnej bunky.

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 algoritme Hunt and Kill

Algoritmus Hunt and Kill je jednoduchá, ale účinná metóda generovania bludísk. Je do istej miery podobný prehľadávaniu do hĺbky (t. j. algoritmu Recursive Backtracker), až na to, že keď sa nemôže dostať ďalej od aktuálnej pozície, systematicky prehľadáva (alebo „loví“) bludisko, aby našiel novú bunku, z ktorej môže pokračovať. Algoritmus pozostáva z dvoch hlavných fáz: chôdze a lovu.

Ako funguje algoritmus Hunt and Kill pre generovanie bludiska

Krok 1: Začnite s náhodnou bunkou

• Nájdite náhodnú bunku v mriežke a označte ju ako navštívenú.

Krok 2: Fáza chôdze (náhodná chôdza)

• Vyberte si náhodného nenavštíveného suseda.
• Presuňte sa k tomuto susedovi, označte ho ako navštívený a vytvorte cestu medzi predchádzajúcou a novou bunkou.
• Opakujte, kým nezostanú žiadni nenavštívení susedia.

Krok 3: Fáza lovu (Spätné sledovanie prostredníctvom skenovania)

• Prehľadajte mriežku riadok po riadku (alebo stĺpec po stĺpci).
• Nájdite prvú nenavštívenú bunku, ktorá má aspoň jedného navštíveného suseda.
• Pre obnovenie fázy chôdze pripojte túto bunku k navštívenému susedovi.
• Opakujte, kým nenavštívite všetky bunky.

Ďalšie čítanie

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

• Rekurzívny Backtracker Maze Generator
• Ellerov generátor bludísk algoritmov
• Wilsonov generátor bludísk algoritmov