Miklix

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.

Táto stránka bola strojovo preložená z angličtiny, aby bola prístupná čo najväčšiemu počtu ľudí. Žiaľ, strojový preklad ešte nie je dokonalá technológia, takže sa môžu vyskytnúť chyby. Ak chcete, môžete si pozrieť pôvodnú anglickú verziu tu:

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.


Generovanie nového bludiska








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.

Zdieľať na BlueskyZdieľať na FacebookuZdieľať na LinkedInZdieľať na TumblrZdieľať na XZdieľať na LinkedInPripnúť na Pintereste

Mikkel Bang Christensen

O autorovi

Mikkel Bang Christensen
Mikkel je tvorcom a majiteľom miklix.com. Má viac ako 20 rokov skúseností ako profesionálny počítačový programátor/vývojár softvéru a v súčasnosti pracuje na plný úväzok pre veľkú európsku IT korporáciu. Keď práve nepíše blog, venuje svoj voľný čas širokej škále záujmov, koníčkov a aktivít, čo sa môže do istej miery odrážať v rôznorodosti tém na tejto webovej lokalite.