Miklix

Generator labirinta algoritama za uzgoj drveća

Objavljeno: 16. februar 2025. u 21:58:05 UTC
Posljednje ažurirano: 6. mart 2025. u 10:00:06 UTC

Generator labirinta koristi algoritam Growing Tree za stvaranje savršenog labirinta. Ovaj algoritam ima tendenciju da generira labirinte slične algoritmu Hunt and Kill, ali sa nešto drugačijim tipičnim rješenjem.

Ova stranica je mašinski prevedena sa engleskog kako bi bila dostupna što većem broju ljudi. Nažalost, mašinsko prevođenje još nije usavršena tehnologija, pa može doći do grešaka. Ako želite, možete pogledati originalnu englesku verziju ovdje:

Growing Tree Algorithm Maze Generator

Algoritam Growing Tree je zanimljiv, jer može oponašati ponašanje nekoliko drugih algoritama, ovisno o tome kako je sljedeća ćelija odabrana tokom generacije. Implementacija na ovoj stranici koristi pristup nalik na širinu, poput reda.

Savršen labirint je labirint u kojem postoji tačno jedan put od bilo koje tačke u labirintu do bilo koje druge tačke. To znači da ne možete završiti u krugu, ali ćete često nailaziti na slijepe ulice, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta koje se ovdje generiraju uključuju zadanu verziju bez ikakvih početnih i završnih pozicija, tako da ih možete sami odlučiti: postojat će rješenje od bilo koje točke u lavirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženi početni i ciljni položaj - pa čak i vidjeti rješenje između njih.


Stvorite novi labirint








O algoritmu uzgoja stabla

Algoritam Growing Tree je fleksibilan i moćan metod za generisanje savršenih labirinta. Algoritam je zanimljiv jer može oponašati ponašanje nekoliko drugih algoritama za generiranje labirinta, kao što su Primov algoritam, rekurzivno vraćanje unazad i rekurzivna podjela, u zavisnosti od toga kako odaberete sljedeću ćeliju za obradu.

Kako radi algoritam rastućeg stabla

Korak 1: Inicijalizacija

  • Počni sa mrežom neposjećenih ćelija.
  • Odaberite nasumičnu početnu ćeliju i dodajte je na listu.

Korak 2: Petlja stvaranja labirinta

  • Dok lista ćelija nije prazna:
    • Izaberite ćeliju sa liste na osnovu specifične strategije (objašnjeno u nastavku).
    • Izrežite prolaz iz odabrane ćelije do jednog od njenih neposjećenih susjeda (odabranih nasumično).
    • Dodajte susjeda na popis jer je sada dio labirinta.
    • Ako odabrana ćelija nema neposjećenih susjeda, uklonite je sa liste.

Korak 3: Raskid

  • Algoritam završava kada nema više ćelija na listi, što znači da je cijeli labirint isklesan.

Strategije odabira ćelija (fleksibilnost algoritma)

Definirajuća karakteristika algoritma Growing Tree je kako birate koju ćeliju ćete obraditi sljedeću. Ovaj izbor dramatično utiče na izgled labirinta:

Newest Cell (Stack-like Behavior) – Rekurzivni Backtracker:

  • Uvijek odaberite posljednju dodanu ćeliju.
  • Stvara dugačke, zavojite hodnike s mnogo slijepih ulica (poput labirinta za pretraživanje dubine).
  • Labirinti imaju tendenciju da imaju duge prolaze i lako ih je riješiti.

Slučajna ćelija (Randomizirani Primov algoritam):

  • Svaki put izaberi nasumičnu ćeliju sa liste.
  • Stvara ravnomjernije raspoređen labirint sa složenim, zamršenim stazama.
  • Manje dugih hodnika i više grananja.

Najstarija ćelija (ponašanje poput reda):

  • Uvijek odaberite najstariju ćeliju na listi.
  • Generira labirinte sa ujednačenijim širenjem, kao širina prvog obrasca pretraživanja.
  • Kratki, žbunasti prolazi sa gustim vezama.
  • (Ovo je verzija implementirana ovdje)

Hibridni pristupi:

Kombinirajte strategije za različite karakteristike labirinta. Na primjer:

  • 90% najnoviji, 10% nasumično: Izgleda uglavnom kao rekurzivni labirint backtrackera, ali s povremenim granama koje razbijaju dugačke hodnike.
  • 50% najnoviji, 50% najstariji: Uravnotežuje duge hodnike sa grmolikim rastom.

Podijelite na BlueskyPodijelite na FacebookuPodijelite na LinkedIn-uPodijelite na Tumblr-uPodijeli na XPodijelite na LinkedIn-uPrikači na Pinterest

Mikkel Bang Christensen

O autoru

Mikkel Bang Christensen
Mikkel je kreator i vlasnik miklix.com. Ima preko 20 godina iskustva kao profesionalni kompjuterski programer/programer softvera i trenutno je zaposlen sa punim radnim vremenom u velikoj evropskoj IT korporaciji. Kada ne piše blog, svoje slobodno vrijeme provodi na širokom spektru interesovanja, hobija i aktivnosti, što se u određenoj mjeri može odraziti na različite teme koje se obrađuju na ovoj web stranici.