Rekursiivinen Backtracker Maze Generator

Rekursiivinen backtracker-algoritmi on todella yleiskäyttöinen syvyyshaku. Kun sitä käytettiin sokkelon luomiseen, se muuttui hieman valitsemaan polku satunnaisesti, kun taas jos sitä käytetään varsinaisiin hakutarkoituksiin, tyypillisesti etsitään jokaista tasoa lineaarisessa järjestyksessä. Sillä on taipumus tuottaa sokkeloita, joissa on pitkät, mutkittelevat käytävät ja erittäin pitkä, kiertyvä 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 backtracker-algoritmi on syvyys-ensimmäinen hakumenetelmä täydellisten sokkeloiden luomiseen (sokkeloita, joissa ei ole silmukoita ja yksi polku minkä tahansa kahden pisteen välillä). Se on yksinkertainen, tehokas ja tuottaa visuaalisesti houkuttelevia sokkeloita pitkillä, mutkaisilla käytävillä.

Nimestään huolimatta sitä ei välttämättä tarvitse toteuttaa rekursiolla. Se toteutetaan usein iteratiivisesti LIFO-jonon (eli pinon) avulla. Erittäin suurissa sokkeloissa rekursion käyttö johtaa todennäköisemmin puhelupinon ylivuotoon ohjelmointikielestä ja käytettävissä olevasta muistista riippuen. LIFO-jono voidaan helpommin mukauttaa käsittelemään suuria tietomääriä, jopa pitämään jono levyllä tai tietokannassa, jos käytettävissä oleva muisti ei riitä.

Miten se toimii

Algoritmi toimii pinopohjaisella syvyys-ensin hakumenetelmällä. Tässä on vaiheittainen erittely:

1. Valitse aloitussolu ja merkitse se käydyksi.
2. Vaikka vierailemattomia soluja on:
   • Katso viereisiä soluja, joissa ei ole vielä vieraillut.
   • Jos vähintään yksi vierailematon naapuri on olemassa:
     • Valitse satunnaisesti yksi vierailemattomista naapureista.
     • Poista seinä nykyisen solun ja valitun naapurin välistä.
     • Siirry valitun naapurin luo ja merkitse se käydyksi.
     • Työnnä nykyinen solu pinoon.
   • Jos vierailemattomia naapureita ei ole:
     • Palaa taaksepäin avaamalla pinon viimeinen solu.
3. Jatka tätä prosessia, kunnes pino on tyhjä.

Mielenkiintoinen tosiasia tästä algoritmista on, että se toimii sekä sokkelogeneraattorina että sokkelon ratkaisijana. Jos käytät sitä jo luodussa sokkelossa ja pysähdyt vain osuessasi päätepisteeseen, pino sisältää ratkaisun sokkeloon.

Itse asiassa minulla on tällä sivustolla pelissä kaksi versiota tästä algoritmista: LIFO-pohjainen sokkeloiden luomiseen tällä sivulla ja rekursiopohjainen sokkeloiden ratkaisemiseen, myös muiden algoritmien luomia sokkeloita (näin tehdään ratkaisut sisältävät kartat). Kaksi eri versiota on vain urheilua varten, koska olen nörtti, joka pitää sen mielenkiintoisena, kumpi tahansa olisi voinut toimia molemmissa ;-)