Rekursiivinen Backtracker Maze Generator

Rekursiivinen takaisinseuranta-algoritmi on itse asiassa yleiskäyttöinen syvyyshaku. Sokkeloiden luomiseen sitä on hieman muokattu siten, että polku valitaan satunnaisesti, kun taas varsinaiseen hakuun sitä käytetään tyypillisesti vain tasojen etsimiseen lineaarisessa järjestyksessä. Se tuottaa yleensä sokkeloita, joissa on pitkiä, mutkittelevia käytäviä ja erittäin pitkä, kiemurteleva ratkaisu.

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ä.

Rekursiivinen takaisinseuranta-algoritmi on syvyyshakumenetelmä täydellisten sokkeloiden (sokkeloiden, joissa ei ole silmukoita ja joiden välillä on vain yksi polku) luomiseksi. Se on yksinkertainen, tehokas ja tuottaa visuaalisesti houkuttelevia sokkeloita pitkillä, mutkittelevilla käytävillä.

Nimestään huolimatta sitä ei välttämättä tarvitse toteuttaa rekursiolla. Se toteutetaan usein iteratiivisella lähestymistavalla käyttäen LIFO-jonoa (eli pinoa). Hyvin suurissa sokkeloissa rekursion käyttö johtaa todennäköisemmin kutsupinon ylivuotoon ohjelmointikielestä ja käytettävissä olevasta muistista riippuen. LIFO-jonoa voidaan helpommin mukauttaa suurten tietomäärien käsittelyyn, ja jono voidaan jopa pitää levyllä tai tietokannassa, jos käytettävissä oleva muisti ei riitä.

Miten se toimii

Algoritmi toimii pinopohjaisella syvyyshakumenetelmällä. Tässä on vaiheittainen erittely:

1. Valitse aloitussolu ja merkitse se käydyksi.
2. Kun soluja on vielä vierailematta: Katso naapurisoluja, joissa ei ole vielä käyty. Jos on olemassa ainakin yksi vierailematon naapuri: Valitse satunnaisesti yksi vierailemattomista naapureista. Poista seinä nykyisen solun ja valitun naapurin väliltä. Siirry valittuun naapuriin ja merkitse se käydyksi. Työnnä nykyinen solu pinoon. Jos vierailemattomia naapureita ei ole: Palaa taaksepäin poistamalla viimeinen solu pinosta.
3. Jatka tätä prosessia, kunnes pino on tyhjä.

Mielenkiintoinen seikka tässä algoritmissa on, että se toimii sekä sokkelogeneraattorina että sokkelonratkaisijana. Jos suoritat sen jo luodussa sokkelossa ja pysähdyt vain, kun saavutat päätepisteen, pino sisältää sokkelon ratkaisun.

Minulla on itse asiassa kaksi versiota tästä algoritmista tällä sivustolla: LIFO-jonoon perustuva sokkeloiden luomiseen tällä sivulla ja rekursioon perustuva sokkeloiden ratkaisemiseen, myös muiden algoritmien luomien sokkeloiden ratkaisemiseen (näin ratkaisukartat tehdään). Kahden eri version olemassaolo on vain urheilua varten, koska olen nörtti, joka pitää sitä mielenkiintoisena, kumpi tahansa olisi voinut toimia molemmissa ;-)

Lisälukemista

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

• Kasvavan puun algoritmin sokkelogeneraattori
• Kruskalin algoritmi sokkelogeneraattori
• Wilsonin algoritmin sokkelogeneraattori