Recursieve Backtracker Doolhof Generator

Het recursieve backtracker-algoritme is eigenlijk een algemene diepte-eerst-zoekopdracht. Wanneer het wordt gebruikt voor het genereren van doolhoven, wordt het lichtjes aangepast om het pad willekeurig te kiezen, terwijl men bij daadwerkelijke zoekdoeleinden doorgaans elk niveau in lineaire volgorde zou doorzoeken. Het produceert meestal doolhoven met lange, kronkelende gangen en een zeer lange, draaiende oplossing.

Een perfect doolhof is een doolhof waarin er precies één pad is van elk punt in het doolhof naar elk ander punt. Dat betekent dat je geen rondjes kunt lopen, maar dat je vaak op doodlopende paden stuit, waardoor je gedwongen wordt om te keren en terug te gaan.

De doolhofkaarten die hier worden gegenereerd bevatten een standaardversie zonder start- en eindposities, zodat je die zelf kunt bepalen: er is een oplossing van elk punt in het doolhof naar elk ander punt. Als je inspiratie wilt, kun je een voorgestelde start- en eindpositie inschakelen - en zelfs de oplossing tussen die twee bekijken.

Het recursive backtracker-algoritme is een depth-first zoekmethode voor het genereren van perfecte doolhoven (doolhoven zonder lussen en met één pad tussen twee willekeurige punten). Het is eenvoudig, efficiënt en produceert visueel aantrekkelijke doolhoven met lange, kronkelende gangen.

Ondanks de naam hoeft het niet per se te worden geïmplementeerd met behulp van recursie. Het wordt vaak geïmplementeerd in een iteratieve benadering met behulp van een LIFO-wachtrij (d.w.z. een stapel). Voor zeer grote doolhoven is het gebruik van recursie waarschijnlijker om te resulteren in een overloop van de aanroepstapel, afhankelijk van de programmeertaal en het beschikbare geheugen. Een LIFO-wachtrij kan gemakkelijker worden aangepast om grote hoeveelheden gegevens te verwerken, zelfs door de wachtrij op schijf of in een database te houden als het beschikbare geheugen onvoldoende is.

Hoe het werkt

Het algoritme werkt met een stack-based depth-first search-aanpak. Hier is de stapsgewijze uitsplitsing:

1. Kies een startcel en markeer deze als bezocht.
2. Hoewel er nog onbezochte cellen zijn:
   • Kijk eens naar de aangrenzende cellen die nog niet bezocht zijn.
   • Als er minstens één onbezochte buur is:
     • Kies willekeurig een van de buren die je niet kent.
     • Verwijder de muur tussen de huidige cel en de gekozen buurcel.
     • Ga naar de gekozen buur en markeer deze als bezocht.
     • Duw de huidige cel op de stapel.
   • Als er geen onbezochte buren zijn:
     • Ga terug door de laatste cel van de stapel te verwijderen.
3. Herhaal dit proces totdat de stapel leeg is.

Een interessant feit over dit algoritme is dat het zowel als een doolhofgenerator als een doolhofoplosser werkt. Als je het uitvoert op een reeds gegenereerd doolhof en gewoon stopt wanneer je het vastgestelde eindpunt bereikt, zal de stack de oplossing voor het doolhof bevatten.

Ik heb eigenlijk twee versies van dit algoritme in het spel op deze site: een LIFO-queue-based versie voor het genereren van doolhoven op deze pagina en een recursie-based versie voor het oplossen van doolhoven, ook doolhoven gegenereerd door andere algoritmes (zo worden de kaarten met de oplossingen gemaakt). Twee verschillende versies hebben is alleen voor de sport omdat ik een nerd ben die het interessant vindt, beide hadden voor beide kunnen werken ;-)