Wilson's algoritme doolhofgenerator

Wilson's algoritme is een loop-erased random walk methode die uniforme spanning trees genereert voor het maken van doolhoven. Dit betekent dat alle mogelijke doolhoven van een bepaalde grootte even waarschijnlijk gegenereerd worden, wat het een onbevooroordeelde doolhofgeneratietechniek maakt. Wilson's algoritme kan worden beschouwd als een verbeterde versie van het Aldous-Broder-algoritme, omdat het doolhoven genereert met identieke kenmerken, maar het werkt veel sneller, dus ik heb hier niet de moeite genomen om het Aldous-Broder-algoritme te implementeren.

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 algoritme van Wilson

Wilsons algoritme voor het genereren van uniforme overspannende bomen met behulp van een lus-gewiste willekeurige wand is ontwikkeld door David Bruce Wilson.

Wilson introduceerde dit algoritme oorspronkelijk in 1996 toen hij onderzoek deed naar willekeurige spanningsbomen en Markov-ketens in de kansrekening. Hoewel zijn werk voornamelijk in de wiskunde en statistische fysica lag, is het algoritme sindsdien breed 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 is verbonden zonder lussen, door iteratief paden te creëren uit 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 de generatie.

Stap 3: Willekeurige wandeling met lus-wissen

• Kies een cel die je nog niet hebt bezocht en begin aan een willekeurige wandeling (je beweegt in willekeurige richtingen).
• Als u tijdens de wandeling een cel bereikt die u al bezocht hebt, wist u alle lussen in het pad.
• Zodra de wandeling aansluit op het bezochte gebied, markeert u alle cellen in het pad als bezocht.

Stap 4: Herhaal dit totdat alle cellen zijn bezocht :

• Blijf onbezochte cellen selecteren en voer willekeurige wandelingen uit totdat elke cel deel uitmaakt van het doolhof.