Wilson's algoritme doolhofgenerator

Het algoritme van Wilson is een lus-verwijderde random walk-methode die uniforme opspannende bomen genereert voor het creëren van doolhoven. Dit betekent dat alle mogelijke doolhoven van een bepaalde grootte een gelijke kans hebben om gegenereerd te worden, waardoor het een onbevooroordeelde techniek voor het genereren van doolhoven is. Het algoritme van Wilson kan worden beschouwd als een verbeterde versie van het Aldous-Broder-algoritme, omdat het doolhoven genereert met identieke kenmerken, maar het werkt veel sneller. Daarom heb ik het Aldous-Broder-algoritme hier niet geïmplementeerd.

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 Wilsons algoritme

Het algoritme van Wilson voor het genereren van uniforme opspannende bomen met behulp van een lusverwijderde willekeurige muur is ontwikkeld door David Bruce Wilson.

Wilson introduceerde dit algoritme oorspronkelijk in 1996 tijdens zijn onderzoek naar willekeurige opspannende bomen en Markovketens in de kansrekening. Hoewel zijn werk zich voornamelijk richtte op wiskunde en statistische fysica, is het algoritme sindsdien op grote schaal toegepast voor het genereren van doolhoven vanwege het vermogen om perfect uniforme doolhoven te produceren.

Hoe het algoritme van Wilson werkt voor het genereren van doolhoven.

Het algoritme van Wilson zorgt ervoor dat het uiteindelijke doolhof volledig verbonden is zonder lussen door iteratief paden te creëren vanuit nog niet bezochte cellen met behulp van willekeurige wandelingen.

Stap 1: Initialiseren

• Begin met een raster gevuld met muren.
• Definieer een lijst van alle mogelijke doorgangscellen.

Stap 2: Kies een willekeurige startcel

• Kies een willekeurige cel en markeer deze als bezocht. Dit dient als startpunt van het doolhof tijdens het genereren.

Stap 3: Willekeurige wandeling met lusverwijdering

• Kies een nog niet bezochte cel en begin een willekeurige wandeling (bewegen in willekeurige richtingen).
• Als de route een reeds bezochte cel bereikt, verwijder dan alle lussen in het pad.
• Zodra de wandeling aansluit op het bezochte gebied, markeer dan alle cellen op het pad als bezocht.

Stap 4: Herhaal dit totdat alle cellen bezocht zijn:

• Ga door met het selecteren van nog niet bezochte cellen en het uitvoeren van willekeurige wandelingen totdat elke cel deel uitmaakt van het doolhof.

Verder lezen

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

• Groeiende boom algoritme doolhofgenerator
• Ellers algoritme doolhofgenerator
• Recursieve Backtracker Doolhof Generator