Generator voor jacht- en doodsdoolhoven

Het Hunt and Kill-algoritme is in feite een aangepaste versie van de recursieve backtracker. De aanpassing bestaat uit het systematisch scannen (of "jagen") naar een nieuwe cel om vanaf te gaan wanneer het niet verder kan, in tegenstelling tot een echte recursieve zoektocht, die altijd terugkeert naar de vorige cel op de stapel.

Hierdoor kan dit algoritme eenvoudig worden aangepast om doolhoven met een andere uitstraling te genereren, door bijvoorbeeld vaker of volgens specifieke regels de "jachtmodus" in te schakelen. De hier geïmplementeerde versie schakelt alleen over naar de "jachtmodus" wanneer het niet verder kan vanuit de huidige cel.

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.

Over het jacht- en kill-algoritme

Het Hunt and Kill-algoritme is een eenvoudige maar effectieve methode voor het genereren van doolhoven. Het lijkt enigszins op een dieptezoekalgoritme (oftewel het recursieve backtracker-algoritme), met dit verschil dat wanneer het niet verder kan vanaf de huidige positie, het systematisch het doolhof afspeurt (of "jaagt") om een nieuwe cel te vinden om vanuit te gaan. Het algoritme bestaat uit twee hoofdfasen: lopen en jagen.

Hoe het Hunt and Kill-algoritme werkt voor het genereren van doolhoven.

Stap 1: Begin bij een willekeurige cel.

• Zoek een willekeurige cel in het raster en markeer deze als bezocht.

Stap 2: Loopfase (willekeurige wandeling)

• Kies een willekeurige buur die je nog niet hebt bezocht.
• Ga naar die aangrenzende cel, markeer deze als bezocht en maak een pad tussen de vorige en de nieuwe cel.
• Herhaal dit totdat er geen buren meer over zijn die nog niet bezocht zijn.

Stap 3: Jachtfase (Terugvolgen via scannen)

• Scan het raster rij voor rij (of kolom voor kolom).
• Zoek de eerste nog niet bezochte cel die minstens één bezochte buurcel heeft.
• Verbind die cel met een bezochte buur om de wandelfase te hervatten.
• Herhaal dit totdat alle cellen bezocht zijn.

Verder lezen

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

• Wilson's algoritme doolhofgenerator
• Groeiende boom algoritme doolhofgenerator
• Ellers algoritme doolhofgenerator