Recursieve Backtracker Doolhof Generator

Het recursieve backtracker-algoritme is in feite een algemene dieptezoekalgoritme. Bij gebruik voor het genereren van doolhoven wordt het enigszins aangepast om het pad willekeurig te kiezen, terwijl bij daadwerkelijke zoekdoeleinden doorgaans elk niveau lineair wordt doorzocht. Het algoritme produceert vaak doolhoven met lange, kronkelende gangen en een zeer lange, ingewikkelde 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 recursieve backtracker-algoritme is een dieptezoekmethode voor het genereren van perfecte doolhoven (doolhoven zonder lussen en met slechts éé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 met recursie te worden geïmplementeerd. Het wordt vaak geïmplementeerd met een iteratieve aanpak met behulp van een LIFO-wachtrij (oftewel een stapel). Bij zeer grote doolhoven is de kans op een aanroepstackoverloop groter bij gebruik van recursie, afhankelijk van de programmeertaal en het beschikbare geheugen. Een LIFO-wachtrij kan gemakkelijker worden aangepast aan het verwerken van grote hoeveelheden data, zelfs als de wachtrij op schijf of in een database wordt bewaard als het beschikbare geheugen ontoereikend is.

Hoe het werkt

Het algoritme werkt met een op stapels gebaseerde dieptezoekmethode. Hier volgt een stapsgewijze uitleg:

1. Kies een startcel en markeer deze als bezocht.
2. Als er nog niet bezochte cellen zijn: Bekijk de aangrenzende cellen die nog niet bezocht zijn. Als er minstens één niet-bezochte buurcel is: Kies willekeurig een van de niet-bezochte buurcellen. Verwijder de muur tussen de huidige cel en de gekozen buurcel. Ga naar de gekozen buurcel en markeer deze als bezocht. Plaats de huidige cel op de stapel. Als er geen niet-bezochte buurcellen zijn: Ga terug door de laatste cel van de stapel te verwijderen.
3. Ga zo door totdat de stapel leeg is.

Een interessant feit over dit algoritme is dat het zowel als doolhofgenerator als als doolhofoplosser werkt. Als je het uitvoert op een reeds gegenereerd doolhof en stopt zodra je het afgesproken eindpunt bereikt, bevat de stack de oplossing van het doolhof.

Ik gebruik op deze site eigenlijk twee versies van dit algoritme: een LIFO-versie voor het genereren van doolhoven op deze pagina en een recursieversie voor het oplossen van doolhoven, inclusief doolhoven die door andere algoritmen zijn gegenereerd (zo worden de kaarten met de oplossingen gemaakt). Het gebruik van twee verschillende versies is puur voor de lol, omdat ik een nerd ben die het interessant vindt; beide versies hadden prima gewerkt ;-)

Verder lezen

Als je dit bericht leuk vond, vind je deze suggesties misschien ook interessant:

• Groeiende boom algoritme doolhofgenerator
• Ellers algoritme doolhofgenerator
• Generator voor jacht- en doodsdoolhoven