Generator labirinta Wilsonovega algoritma
Objavljeno: 16. februar 2025 ob 7:33:57 pop. UTC
Generator labirintov z uporabo Wilsonovega algoritma za ustvarjanje popolnega labirinta. Ta algoritem ustvari vse možne labirinte dane velikosti z enako verjetnostjo, tako da lahko teoretično ustvari labirinte z več mešanimi postavitvami, a ker je več možnih labirintov s krajšimi kot daljšimi koridorji, jih boste pogosteje videli.Wilson's Algorithm Maze Generator
Wilsonov algoritem je metoda naključnega sprehajanja z izbrisanimi zankami, ki ustvari enotna vpeta drevesa za ustvarjanje labirinta. To pomeni, da je enako verjetno, da bodo ustvarjeni vsi možni labirinti dane velikosti, zaradi česar gre za nepristransko tehniko generiranja labirintov. Wilsonov algoritem lahko štejemo za izboljšano različico Aldous-Broderjevega algoritma, saj ustvarja labirinte z enakimi značilnostmi, vendar deluje veliko hitreje, zato se tukaj nisem trudil implementirati Aldous-Broderjevega algoritma.
Popoln labirint je labirint, v katerem obstaja natanko ena pot od katere koli točke v labirintu do katere koli druge točke. To pomeni, da se ne morete vrteti v krogu, vendar boste pogosto naleteli na slepe ulice, zaradi česar se boste morali obrniti in vrniti nazaj.
Tukaj ustvarjeni zemljevidi labirintov vključujejo privzeto različico brez začetnih in končnih položajev, tako da jih lahko določite sami: iz katere koli točke v labirintu do katere koli druge točke obstaja rešitev. Če želite navdih, lahko omogočite predlagana začetni in končni položaj - in si celo ogledate rešitev med njima.
O Wilsonovem algoritmu
Wilsonov algoritem za generiranje enotnih vpetih dreves z uporabo naključne stene, izbrisane z zanko, je ustvaril David Bruce Wilson.
Wilson je ta algoritem prvotno predstavil leta 1996 med raziskovanjem naključnih vpetih dreves in Markovljevih verig v teoriji verjetnosti. Čeprav je bilo njegovo delo predvsem na področju matematike in statistične fizike, je bil algoritem od takrat široko sprejet za ustvarjanje labirintov zaradi svoje sposobnosti ustvarjanja popolnoma enakomernih labirintov.
Kako deluje Wilsonov algoritem za ustvarjanje labirinta
Wilsonov algoritem zagotavlja, da je končni labirint popolnoma povezan brez kakršnih koli zank z iterativnim vrezovanjem poti iz neobiskanih celic z uporabo naključnih sprehodov.
1. korak: Inicializacija
- Začnite z mrežo, napolnjeno s stenami.
- Določite seznam vseh možnih prehodnih celic.
2. korak: Izberite naključno začetno celico
- Izberite poljubno celico in jo označite kot obiskano. To služi kot izhodišče labirinta med ustvarjanjem.
3. korak: Naključni sprehod z brisanjem zanke
- Izberite neobiskano celico in začnite naključni sprehod (premikanje v naključnih smereh).
- Če hoja doseže že obiskano celico, izbrišite vse zanke na poti.
- Ko se hoja poveže z obiskano regijo, označite vse celice na poti kot obiskane.
4. korak: Ponavljajte, dokler ne obiščete vseh celic :
- Nadaljujte z izbiranjem neobiskanih celic in izvajanjem naključnih sprehodov, dokler vsaka celica ni del labirinta.