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. Implementacija na tej strani uporablja pristop, ki odloča v širino in je 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 generiranja labirinta

• Dokler seznam celic ni prazen: Izberite celico s seznama na podlagi določene strategije (pojasnjeno spodaj). Izrežite prehod iz izbrane celice do enega 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 (fleksibilnost algoritma)

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

Najnovejša celica (vedenje, podobno skladu) – Rekurzivni povratni sledilnik:

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

Naključna celica (randomiziran Primov algoritem):

• Vsakič izberi naključno celico s seznama.
• Ustvari bolj enakomerno porazdeljen labirint s kompleksnimi, prepletenimi potmi.
• Manj dolgih hodnikov in več razvejanih.

Najstarejša celica (obnašanje podobno čakalni vrsti):

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

Hibridni pristopi:

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

• 90 % najnovejših, 10 % naključnih: Izgleda večinoma kot rekurzivni labirint povratnega sledenja, vendar z občasnimi vejami, ki prekinjajo dolge hodnike.
• 50 % najnovejših, 50 % najstarejših: Uravnoteži dolge hodnike z bujno rastjo.

Nadaljnje branje

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

• Rekurzivni Backtracker Maze Generator
• Generator labirinta Wilsonovega algoritma
• Generator labirinta Ellerjevega algoritma