Algoritem rastočega drevesa Generator labirinta

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.

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.