Miklix

Groeiende boom algoritme doolhofgenerator

Gepubliceerd: 16 februari 2025 om 21:36:57 UTC
Laatst bijgewerkt: 6 maart 2025 om 09:56:15 UTC

Maze generator die het Growing Tree-algoritme gebruikt om een perfect doolhof te creëren. Dit algoritme genereert doolhoven die lijken op het Hunt and Kill-algoritme, maar met een ietwat andere typische oplossing.

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:

Growing Tree Algorithm Maze Generator

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.


Nieuw doolhof genereren








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.

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.