Generator voor jacht- en doodsdoolhoven
Gepubliceerd: 16 februari 2025 om 20:55:16 UTC
Maze generator die het Hunt and Kill-algoritme gebruikt om een perfect doolhof te creëren. Dit algoritme lijkt op de Recursive Backtracker, maar genereert doorgaans doolhoven met iets minder lange, kronkelende gangen.Hunt and Kill Maze Generator
Het Hunt and Kill-algoritme is eigenlijk een aangepaste versie van de Recursive Backtracker. De aanpassing bestaat uit het systematisch scannen (of "hunten") van een nieuwe cel om door te gaan vanaf het moment dat het niet verder kan, in tegenstelling tot een echte recursieve zoekopdracht, die altijd teruggaat naar de vorige cel op de stapel.
Hierdoor kan dit algoritme eenvoudig worden aangepast om doolhoven te genereren met een andere look en feel, door er gewoon voor te kiezen om vaker of volgens specifieke regels de "hunting"-modus in te gaan. De versie die hier is geïmplementeerd, gaat alleen de "hunting"-modus in als het niet verder van de huidige cel kan komen.
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 Hunt and Kill-algoritme
Het Hunt and Kill-algoritme is een eenvoudige maar effectieve methode om doolhoven te genereren. Het lijkt enigszins op een depth-first search (d.w.z. het Recursive Backtracker-algoritme), behalve dat het, wanneer het niet verder van de huidige positie kan komen, systematisch scant (of "jaagt") over het doolhof om een nieuwe cel te vinden om vanaf verder 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, onbekende buur.
- Ga naar de aangrenzende cel, markeer deze als bezocht en maak een pad tussen de vorige en de nieuwe cel.
- Herhaal dit totdat er geen buren meer zijn die u niet bezoekt.
Stap 3: Jachtfase (terugvolgen via scannen)
- Bekijk het raster rij voor rij (of kolom voor kolom).
- Zoek de eerste onbezochte cel met minstens één bezochte buur.
- Verbind die cel met een bezochte buur om de wandelfase te hervatten.
- Herhaal dit totdat alle cellen bezocht zijn.