Generátor Bludiska Lov a Zabitie
Publikované: 16. februára 2025 o 20:56:50 UTC
Generátor bludiska pomocou algoritmu Hunt and Kill na vytvorenie dokonalého bludiska. Tento algoritmus je podobný Rekurzívnemu Backtrackeru, ale má tendenciu vytvárať bludisko s o niečo menej dlhými, kľukatými chodbami.Hunt and Kill Maze Generator
Algoritmus Hunt and Kill je skutočne upravenou verziou rekurzívneho backtrackera. Modifikácia pozostáva zo systematického skenovania (alebo „hľadania“) na novú bunku, aby pokračovala od chvíle, keď už nemôže ísť ďalej, na rozdiel od skutočného rekurzívneho vyhľadávania, ktoré sa vždy vráti do predchádzajúcej bunky v zásobníku.
Z tohto dôvodu môže byť tento algoritmus ľahko prispôsobený na generovanie bludísk s rôznym vzhľadom a pocitom, a to jednoduchým výberom častejšieho vstupu do režimu „poľovníctva“ alebo podľa špecifických pravidiel. Tu implementovaná verzia vstúpi do „loveckého“ režimu len vtedy, keď nemôže ísť ď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 lovu a zabíjania
Algoritmus Hunt and Kill je jednoduchá, ale účinná metóda na vytváranie bludísk. Je to trochu podobné hĺbkovému vyhľadávaniu (tj algoritmu Rekurzívny Backtracker), s výnimkou prípadu, keď nemôže ísť ďalej od aktuálnej pozície, systematicky skenuje (alebo „loví“) bludisko, aby našiel novú bunku, z ktorej by mohol pokračovať. Algoritmus pozostáva z dvoch hlavných fáz: chôdze a lovu.
Ako funguje algoritmus lovu a zabíjania pre generáciu bludiska
Krok 1: Začnite v náhodnej bunke
- 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števované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)
- Naskenujte 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.
- Pripojte túto bunku k navštívenému susedovi a pokračujte vo fáze chôdze.
- Opakujte, kým neprejdete všetky bunky.