Miklix

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.

Deze pagina is machinaal uit het Engels vertaald om hem voor zoveel mogelijk mensen toegankelijk te maken. Helaas is machinevertaling nog geen geperfectioneerde technologie, dus er kunnen fouten optreden. Als je dat liever hebt, kun je hier de originele Engelse versie bekijken:

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.


Nieuw doolhof genereren








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.

Delen op BlueskyDelen op FacebookDelen op LinkedInDelen op TumblrDelen op XDelen op LinkedInPin op Pinterest

Mikkel Bang Christensen

Over de auteur

Mikkel Bang Christensen
Mikkel is de bedenker en eigenaar van miklix.com. Hij heeft meer dan 20 jaar ervaring als professioneel computerprogrammeur/softwareontwikkelaar en werkt momenteel fulltime voor een groot Europees IT-bedrijf. Als hij niet blogt, besteedt hij zijn vrije tijd aan een breed scala aan interesses, hobby's en activiteiten, die tot op zekere hoogte weerspiegeld kunnen worden in de verscheidenheid aan onderwerpen op deze website.