Miklix

Algoritem rastočega drevesa Generator labirinta

Objavljeno: 16. februar 2025 ob 9:37:08 pop. UTC
Nazadnje posodobljeno: 6. marec 2025 ob 9:56:59 dop. UTC

Generator labirintov z uporabo algoritma Rastoče drevo za ustvarjanje popolnega labirinta. Ta algoritem ponavadi ustvari labirinte, podobne algoritmu Hunt and Kill, vendar z nekoliko drugačno tipično rešitvijo.

Ta stran je bila strojno prevedena iz angleščine, da bi bila dostopna čim večjemu številu ljudi. Žal strojno prevajanje še ni popolna tehnologija, zato lahko pride do napak. Če želite, si lahko izvirno angleško različico ogledate tukaj:

Growing Tree Algorithm Maze Generator

Algoritem Rastoče drevo je zanimiv, ker lahko posnema vedenje več drugih algoritmov, odvisno od tega, kako je med generiranjem izbrana naslednja celica. Izvedba na tej strani uporablja pristop v širino, podoben čakalni vrsti.

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.


Ustvarjanje novega labirinta








O algoritmu rastočega drevesa

Algoritem Rastoče drevo je prilagodljiva in zmogljiva metoda za ustvarjanje popolnih labirintov. Algoritem je zanimiv, ker lahko posnema vedenje več drugih algoritmov za ustvarjanje labirintov, kot so Primov algoritem, rekurzivno sledenje nazaj in rekurzivno deljenje, odvisno od tega, kako izberete naslednjo celico za obdelavo.

Kako deluje algoritem rastočega drevesa

1. korak: Inicializacija

  • Začnite z mrežo neobiskanih celic.
  • Izberite naključno začetno celico in jo dodajte na seznam.

2. korak: Zanka ustvarjanja labirinta

  • Čeprav seznam celic ni prazen:
    • Izberite celico s seznama glede na določeno strategijo (razloženo spodaj).
    • Izrežite prehod od izbrane celice do ene od njenih neobiskanih sosedov (izbranih naključno).
    • Dodajte soseda na seznam, saj je zdaj del labirinta.
    • Če izbrana celica nima neobiskanih sosedov, jo odstranite s seznama.

3. korak: Prekinitev

  • Algoritem se konča, ko na seznamu ni več celic, kar pomeni, da je celoten labirint izrezljan.

Strategije izbire celic (prilagodljivost algoritma)

Odločilna značilnost algoritma Rastoče drevo je, kako izberete, katero celico boste obdelali naslednjo. Ta izbira dramatično vpliva na videz labirinta:

Najnovejša celica (Vedenje, podobno skladu) – Rekurzivno povratno sledenje:

  • Vedno izberite nazadnje dodano celico.
  • Ustvari dolge, zavite hodnike s številnimi slepimi ulicami (kot labirint za iskanje v globino).
  • Labirinti imajo ponavadi dolge prehode in jih je enostavno rešiti.

Naključna celica (naključni Primov algoritem):

  • Vsakič izberite naključno celico s seznama.
  • Ustvari bolj enakomerno porazdeljen labirint s kompleksnimi, zapletenimi potmi.
  • Manj dolgih hodnikov in več razvejanosti.

Najstarejša celica (vedenje, podobno čakalni vrsti):

  • Vedno izberite najstarejšo celico na seznamu.
  • Ustvari labirinte z bolj enotno širino, kot vzorec iskanja v širino.
  • Kratki, grmičasti prehodi z gostimi povezavami.
  • (To je različica, implementirana tukaj)

Hibridni pristopi:

Združite strategije za različne značilnosti labirinta. Na primer:

  • 90 % najnovejših, 10 % naključnih: večinoma je videti kot rekurzivni labirint za sledenje nazaj, vendar z občasnimi vejami, ki prekinjajo dolge hodnike.
  • 50 % najnovejših, 50 % najstarejših: uravnava dolge hodnike z grmičevjem.

Delite na BlueskyDelite na FacebookuDelite na LinkedInuDelite na TumblrDelite na XDelite na LinkedInuPripni na Pinterest

Mikkel Bang Christensen

O avtorju

Mikkel Bang Christensen
Mikkel je avtor in lastnik spletne strani miklix.com. Ima več kot 20 let izkušenj kot profesionalni računalniški programer/razvijalec programske opreme in je trenutno za polni delovni čas zaposlen v veliki evropski IT korporaciji. Kadar ne piše bloga, svoj prosti čas posveča številnim interesom, hobijem in dejavnostim, kar se do neke mere odraža v raznolikosti tem na tem spletnem mestu.