Generator labirinta Wilsonovega algoritma

Wilsonov algoritem je metoda naključnega sprehoda z izbrisano zanko, ki generira enakomerna vpeta drevesa za ustvarjanje labirintov. To pomeni, da je enako verjetno, da bodo generirani 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 generira labirinte z enakimi značilnostmi, vendar deluje veliko hitreje, zato se tukaj nisem ukvarjal z implementacijo 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 enakomernih razteznih dreves z uporabo naključne stene z izbrisom zanke je ustvaril David Bruce Wilson.

Wilson je ta algoritem prvotno predstavil leta 1996 med raziskovanjem naključnih razteznih dreves in markovskih verig v teoriji verjetnosti. Čeprav je bilo njegovo delo predvsem na področju matematike in statistične fizike, je algoritem od takrat široko sprejet za generiranje labirintov zaradi svoje sposobnosti ustvarjanja popolnoma enakomernih labirintov.

Kako Wilsonov algoritem deluje za generiranje labirinta

Wilsonov algoritem zagotavlja, da je končni labirint popolnoma povezan brez zank z iterativnim rezljanjem 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 celic prehoda.

2. korak: Izberite naključno začetno celico

• Izberite katero koli naključno celico in jo označite kot obiskano. To služi kot izhodišče labirinta med generiranjem.

3. korak: Naključni sprehod z brisanjem zanke

• Izberi neobiskano celico in začni naključni sprehod (premikaj se v naključne smeri).
• Če sprehod doseže že obiskano celico, izbrišite vse zanke na poti.
• Ko se sprehod poveže z obiskano regijo, označi 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.

Nadaljnje branje

Če vam je bila ta objava všeč, vam bodo morda všeč tudi ti predlogi:

• Generator labirinta Ellerjevega algoritma
• Algoritem rastočega drevesa Generator labirinta
• Generator labirinta Kruskalovega algoritma