Jahtaa ja Tappaa Labyrintin Generaattori

Metsästys- ja tappamisalgoritmi on itse asiassa muunneltu versio rekursiivisesta paluuseuranta-algoritmista. Muokkaus perustuu systemaattiseen uuden solun etsimiseen (tai "metsästämiseen"), josta jatkaa, kun se ei enää voi jatkaa, toisin kuin todellisessa rekursiivisessa haussa, jossa palataan aina pinon edelliseen soluun.

Tästä johtuen tätä algoritmia voidaan helposti mukauttaa luomaan eri näköisiä ja tuntuisia sokkeloita vain valitsemalla "metsästys"-tilaan useammin tai tiettyjen sääntöjen mukaisesti. Tässä toteutettu versio siirtyy "metsästys"-tilaan vain, kun se ei voi mennä pidemmälle 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 metsästys- ja tappoalgoritmista

Metsästys- ja tapa-algoritmi on yksinkertainen mutta tehokas menetelmä sokkeloiden luomiseen. Se on jossain määrin samanlainen kuin syvyyshaku (eli rekursiivinen paluuhakualgoritmi), paitsi että kun se ei voi mennä pidemmälle 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ä.

Miten metsästys- ja tappoalgoritmi toimii sokkeloiden luomisessa

Vaihe 1: Aloita satunnaisesta solusta

• Etsi ruudukosta satunnainen solu ja merkitse se käydyksi.

Vaihe 2: Kävelyvaihe (satunnainen kävely)

• Valitse satunnainen naapuri, jonka luona et ole käynyt.
• Siirry naapurisolun luo, merkitse se vierailluksi ja piirrä polku edellisen ja uuden solun välille.
• Toista, kunnes ei ole enää yhtään vierailematonta naapuria.

Vaihe 3: Metsästysvaihe (takaisinseuranta skannauksen avulla)

• Skannaa ruudukko rivi riviltä (tai sarake sarakkeelta).
• Etsi ensimmäinen vierailematon solu, jolla on ainakin yksi naapuri, jossa on vierailtu.
• Yhdistä kyseinen solu vierailtuun naapuriin jatkaaksesi kävelyvaihetta.
• Toista, kunnes kaikki solut on käyty läpi.

Lisälukemista

Jos pidit tästä postauksesta, saatat pitää myös näistä ehdotuksista:

• Kruskalin algoritmi sokkelogeneraattori
• Ellerin algoritmin sokkelogeneraattori
• Wilsonin algoritmin sokkelogeneraattori