Wilson se algoritme doolhof kragopwekker
Gepubliseer: 16 Februarie 2025 om 19:36:31 UTC
Doolhofgenerator met behulp van Wilson se algoritme om 'n perfekte doolhof te skep. Hierdie algoritme genereer alle moontlike doolhowe van 'n gegewe grootte met dieselfde waarskynlikheid, so dit kan in teorie doolhowe van baie gemengde uitlegte genereer, maar aangesien daar meer moontlike doolhowe met korter gange as langer is, sal jy dit meer gereeld sien.Wilson's Algorithm Maze Generator
Wilson se algoritme is 'n lus-uitgevee ewekansige loopmetode wat eenvormige bome genereer vir doolhofskepping. Dit beteken dat alle moontlike doolhowe van 'n gegewe grootte ewe waarskynlik gegenereer sal word, wat dit 'n onbevooroordeelde doolhofgenereringstegniek maak. Wilson se algoritme kan beskou word as 'n verbeterde weergawe van die Aldous-Broder-algoritme, aangesien dit doolhowe met identiese eienskappe genereer, maar dit loop baie vinniger, so ek het nie die moeite gedoen om die Aldous-Broder-algoritme hier te implementeer nie.
'n Volmaakte doolhof is 'n doolhof waarin daar presies een pad van enige punt in die doolhof na enige ander punt is. Dit beteken dat jy nie uiteindelik in sirkels kan rondloop nie, maar jy sal dikwels doodloopstrate teëkom, wat jou dwing om om te draai en terug te gaan.
Die doolhofkaarte wat hier gegenereer word, bevat 'n verstekweergawe sonder enige begin- en eindposisies, so jy kan dit self besluit: daar sal 'n oplossing wees van enige punt in die doolhof na enige ander punt. As jy inspirasie wil hê, kan jy 'n voorgestelde begin- en eindposisie aktiveer - en selfs die oplossing tussen die twee sien.
Oor Wilson se algoritme
Wilson se algoritme vir die generering van eenvormige bome met behulp van 'n lus-uitgeveede ewekansige muur is geskep deur David Bruce Wilson.
Wilson het hierdie algoritme oorspronklik in 1996 bekendgestel terwyl hy ewekansige bome en Markov-kettings in waarskynlikheidsteorie ondersoek het. Alhoewel sy werk hoofsaaklik in wiskunde en statistiese fisika was, is die algoritme sedertdien wyd aangeneem vir doolhofgenerering vanweë sy vermoë om perfek eenvormige doolhowe te produseer.
Hoe Wilson se algoritme werk vir doolhofgenerering
Wilson se algoritme verseker dat die finale doolhof ten volle verbind is sonder enige lusse deur iteratief paaie uit onbesoekte selle te kerf met behulp van ewekansige staptogte.
Stap 1: Inisialiseer
- Begin met 'n rooster gevul met mure.
- Definieer 'n lys van alle moontlike deurgangselle.
Stap 2: Kies 'n ewekansige beginsel
- Kies enige ewekansige sel en merk dit as besoek. Dit dien as die beginpunt van die doolhof tydens opwekking.
Stap 3: Willekeurige stap met lus-uitvee
- Kies 'n onbesoekte sel en begin 'n ewekansige stap (beweeg in ewekansige rigtings).
- As die stap 'n reeds besoekte sel bereik, vee enige lusse in die paadjie uit.
- Sodra die stap by die besoekte streek aansluit, merk al die selle in die pad as besoek.
Stap 4: Herhaal totdat alle selle besoek is:
- Gaan voort om onbesoekte selle te kies en ewekansige staptogte uit te voer totdat elke sel deel van die doolhof is.