Groeiende boom algoritme doolhofgenerator

Het Growing Tree-algoritme is interessant omdat het het gedrag van verschillende andere algoritmen kan nabootsen, afhankelijk van hoe de volgende cel tijdens de generatie wordt gekozen. De implementatie op deze pagina maakt gebruik van een breedte-eerst-zoekalgoritme met een wachtrij-achtige aanpak.

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 Growing Tree-algoritme

Het Growing Tree-algoritme is een flexibele en krachtige methode voor het genereren van perfecte doolhoven. Het algoritme is interessant omdat het het gedrag van verschillende andere doolhofgeneratiealgoritmen kan nabootsen, zoals het algoritme van Prim, recursieve backtracking en recursieve deling, afhankelijk van hoe je de volgende cel selecteert om te verwerken.

Hoe het Growing Tree-algoritme werkt

Stap 1: Initialisatie

• Begin met een raster van nog niet bezochte cellen.
• Kies een willekeurige startcel en voeg deze toe aan een lijst.

Stap 2: Generatielus voor het doolhof

• Zolang de lijst met cellen niet leeg is: selecteer een cel uit de lijst op basis van een specifieke strategie (hieronder uitgelegd). Maak een doorgang van de geselecteerde cel naar een van de nog niet bezochte buurcellen (willekeurig gekozen). Voeg de buurcel toe aan de lijst, aangezien deze nu deel uitmaakt van het doolhof. Als de geselecteerde cel geen nog niet bezochte buurcellen heeft, verwijder deze dan uit de lijst.

Stap 3: Beëindiging

• Het algoritme stopt wanneer er geen cellen meer in de lijst staan, wat betekent dat het hele doolhof is uitgehouwen.

Celselectiestrategieën (flexibiliteit van het algoritme)

Het bepalende kenmerk van het Growing Tree-algoritme is de manier waarop je kiest welke cel je vervolgens verwerkt. Deze keuze heeft een dramatisch effect op het uiterlijk van het doolhof:

Nieuwste cel (stapelachtig gedrag) – Recursieve backtracker:

• Selecteer altijd de laatst toegevoegde cel.
• Dit levert lange, kronkelende gangen op met veel doodlopende wegen (zoals een doolhof in een dieptezoekalgoritme).
• Doolhoven hebben doorgaans lange gangen en zijn makkelijk op te lossen.

Willekeurige cel (gerandomiseerd Prim's algoritme):

• Kies telkens een willekeurige cel uit de lijst.
• Creëert een gelijkmatiger verdeeld doolhof met complexe, verstrengelde paden.
• Minder lange gangen en meer vertakkingen.

Oudste cel (wachtrijachtig gedrag):

• Kies altijd de oudste cel in de lijst.
• Genereert doolhoven met een meer gelijkmatige spreiding, zoals bij een breedte-eerst zoekpatroon.
• Korte, begroeide gangen met veel verbindingen.
• (Dit is de versie die hier is geïmplementeerd)

Hybride benaderingen:

Combineer strategieën voor uiteenlopende doolhofkenmerken. Bijvoorbeeld:

• 90% nieuwste, 10% willekeurig: Het lijkt grotendeels op een recursief doolhof met teruggaande bewegingen, maar met af en toe vertakkingen die de lange gangen onderbreken.
• 50% nieuwste, 50% oudste: zorgt voor een evenwicht tussen lange gangen en weelderige begroeiing.

Verder lezen

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

• Generator voor jacht- en doodsdoolhoven
• Ellers algoritme doolhofgenerator
• Wilson's algoritme doolhofgenerator