Groeiende boom algoritme doolhofgenerator

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

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 doolhofgeneratie-algoritmen kan emuleren, zoals Prim's algoritme, recursieve backtracking en recursieve deling, afhankelijk van hoe u de volgende te verwerken cel selecteert.

Hoe het Growing Tree-algoritme werkt

Stap 1: Initialisatie

• Begin met een raster van cellen die u nog niet eerder hebt bezocht.
• Kies een willekeurige startcel en voeg deze toe aan een lijst.

Stap 2: Doolhofgeneratielus

• Zolang de cellenlijst 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 onbezochte buren (willekeurig gekozen).
  • Voeg de buur toe aan de lijst, aangezien deze nu deel uitmaakt van het doolhof.
  • Als de geselecteerde cel geen onbezochte buren heeft, verwijdert u deze uit de lijst.

Stap 3: Beëindiging

• Het algoritme is voltooid zodra er geen cellen meer in de lijst staan. Dit betekent dat het hele doolhof is opgedeeld.

Celselectiestrategieën (flexibiliteit van het algoritme)

Het bepalende kenmerk van het Growing Tree-algoritme is hoe u kiest welke cel u als volgende wilt verwerken. Deze keuze heeft een dramatische invloed op het uiterlijk van het doolhof:

Nieuwste cel (stapelachtig gedrag) – Recursieve backtracker:

• Selecteer altijd de cel die het laatst is toegevoegd.
• Creëert lange, kronkelige gangen met veel doodlopende wegen (zoals een diepte-eerst zoekdoolhof).
• Doolhoven hebben vaak lange gangen en zijn gemakkelijk op te lossen.

Willekeurige cel (gerandomiseerd Prim's algoritme):

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

Oudste cel (wachtrijachtig gedrag):

• Kies altijd de oudste cel in de lijst.
• Genereert doolhoven met een gelijkmatigere spreiding, zoals een zoekpatroon waarbij de breedte eerst wordt gebruikt.
• Korte, bossige gangen met dichte verbindingen.
• (Dit is de versie die hier is geïmplementeerd)

Hybride benaderingen:

Combineer strategieën voor verschillende doolhofkenmerken. Bijvoorbeeld:

• 90% nieuwste, 10% willekeurig: Lijkt vooral op een recursief backtracker-doolhof, maar met af en toe vertakkingen die lange gangen doorbreken.
• 50% nieuwste, 50% oudste: zorgt voor een evenwicht tussen lange gangen en een bossige groei.