Jahtaa ja Tappaa Labyrintin Generaattori
Julkaistu: 16. helmikuuta 2025 klo 20.53.51 UTC
Labyrinttigeneraattori, joka käyttää Hunt and Kill -algoritmia täydellisen sokkelon luomiseen. Tämä algoritmi on samanlainen kuin Recursive Backtracker, mutta sillä on taipumus luoda sokkeloita, joissa on hieman vähemmän pitkiä, mutkaisia käytäviä.Hunt and Kill Maze Generator
Hunt and Kill -algoritmi on todella muokattu versio Recursive Backtrackerista. Muokkaus koostuu uuden solun systemaattisesta skannaamisesta (tai "metsästämisestä"), jotta se voi jatkaa siitä hetkestä lähtien, kun se ei voi mennä pidemmälle, toisin kuin todellinen rekursiivinen haku, joka palaa aina pinon edelliseen soluun.
Tämän vuoksi tämä algoritmi voidaan helposti mukauttaa luomaan eri näköisiä ja tuntuvia sokkeloita, vain valitsemalla "metsästys"-tilaan siirtyminen useammin tai tiettyjen sääntöjen mukaan. Tässä toteutettu versio siirtyy "metsästys"-tilaan vain, kun se ei voi mennä kauemmaksi nykyisestä solusta.
Täydellinen sokkelo on sokkelo, jossa on täsmälleen yksi reitti mistä tahansa sokkelon pisteestä mihin tahansa toiseen pisteeseen. Tämä tarkoittaa, että et voi päätyä kiertämään ympyrää, mutta joudut usein umpikujaan, jolloin sinun on pakko kääntyä ympäri ja palata takaisin.
Tässä luotuihin sokkelokarttoihin sisältyy oletusversio, jossa ei ole alku- ja loppupisteitä, joten voit päättää ne itse: mistä tahansa sokkelon pisteestä mihin tahansa muuhun pisteeseen on olemassa ratkaisu. Jos haluat inspiraatiota, voit ottaa käyttöön ehdotetun alku- ja maalipaikan - ja jopa nähdä ratkaisun näiden kahden välissä.
Tietoja Hunt and Kill -algoritmista
Hunt and Kill -algoritmi on yksinkertainen mutta tehokas menetelmä sokkeloiden luomiseen. Se on jossain määrin samanlainen kuin syvyyshaku (eli Recursive Backtracker-algoritmi), paitsi silloin, kun se ei voi mennä kauemmaksi nykyisestä sijainnista, se skannaa (tai "metsästä") systemaattisesti sokkelon yli löytääkseen uuden solun, josta jatkaa. Algoritmi koostuu kahdesta päävaiheesta: kävelystä ja metsästyksestä.
Kuinka metsästää ja tappaa -algoritmi toimii sokkelosukupolvessa
Vaihe 1: Aloita satunnaisesta solusta
- Etsi satunnainen solu ruudukosta ja merkitse se käydyksi.
Vaihe 2: Kävelyvaihe (satunnainen kävely)
- Valitse satunnainen vierailematon naapuri.
- Siirry kyseiseen naapuriin, merkitse se vierailluksi ja luo polku edellisen ja uuden solun välille.
- Toista, kunnes vierailemattomia naapureita ei ole jäljellä.
Vaihe 3: Metsästysvaihe (takaisinseuranta skannauksen kautta)
- Skannaa ruudukko rivi riviltä (tai sarake sarakkeelta).
- Etsi ensimmäinen vierailematon solu, jossa on vähintään yksi vierailtu naapuri.
- Jatka kävelyvaihetta yhdistämällä tämä solu vierailevaan naapuriin.
- Toista, kunnes kaikki solut on käyty.