Miklix

Algoritam rastućeg stabla Generator labirinta

Objavljeno: 16. veljače 2025. u 21:58:10 UTC
Zadnje ažuriranje: 6. ožujka 2025. u 10:00:28 UTC

Generator labirinta koji koristi algoritam rastućeg stabla za stvaranje savršenog labirinta. Ovaj algoritam nastoji generirati labirinte slične algoritmu Hunt and Kill, ali s donekle drugačijim tipičnim rješenjem.

Ova je stranica strojno prevedena s engleskog kako bi bila dostupna što većem broju ljudi. Nažalost, strojno prevođenje još nije usavršena tehnologija pa se mogu pojaviti pogreške. Ako želite, izvornu englesku verziju možete pogledati ovdje:

Growing Tree Algorithm Maze Generator

Algoritam rastućeg stabla je zanimljiv jer može oponašati ponašanje nekoliko drugih algoritama, ovisno o tome kako je sljedeća ćelija odabrana tijekom generiranja. Implementacija na ovoj stranici koristi pristup u širinu, nalik na red čekanja.

Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.

Ovdje generirane karte labirinta 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 labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.


Generirajte novi labirint








O algoritmu rastućeg stabla

Algoritam Growing Tree je fleksibilna i moćna metoda za stvaranje savršenih labirinta. Algoritam je zanimljiv jer može oponašati ponašanje nekoliko drugih algoritama za generiranje labirinta, kao što je Primov algoritam, rekurzivno praćenje unatrag i rekurzivno dijeljenje, ovisno o tome kako odaberete sljedeću ćeliju za obradu.

Kako radi algoritam rastućeg stabla

Korak 1: Inicijalizacija

  • Započnite s mrežom neposjećenih ćelija.
  • Odaberite nasumično početnu ćeliju i dodajte je na popis.

Korak 2: Petlja generiranja labirinta

  • Iako popis ćelija nije prazan:
    • Odaberite ćeliju s popisa na temelju određene strategije (objašnjeno u nastavku).
    • Urežite prolaz od odabrane ćelije do jednog od njenih neposjećenih susjeda (nasumično odabranih).
    • Dodajte susjeda na popis jer je sada dio labirinta.
    • Ako odabrana ćelija nema neposjećenih susjeda, uklonite je s popisa.

Korak 3: Raskid

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

Strategije odabira ćelija (fleksibilnost algoritma)

Definirajuća značajka algoritma rastućeg stabla je način na koji birate koju ćete ćeliju sljedeću obraditi. Ovaj izbor dramatično utječe na izgled labirinta:

Najnovija ćelija (ponašanje poput niza) – rekurzivno praćenje unatrag:

  • Uvijek odaberite posljednju dodanu ćeliju.
  • Stvara duge, vijugave hodnike s mnogo slijepih ulica (poput labirinta za pretragu u dubinu).
  • Labirinti imaju duge prolaze i lako ih je riješiti.

Slučajna ćelija (randomizirani Primov algoritam):

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

Najstarija ćelija (ponašanje poput čekanja):

  • Uvijek odaberite najstariju ćeliju na popisu.
  • Generira labirinte s ujednačenijim širenjem, poput uzorka pretraživanja u širinu.
  • Kratki, žbunoviti prolazi s gustim spojevima.
  • (Ovo je verzija implementirana ovdje)

Hibridni pristupi:

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

  • 90% najnovije, 10% nasumično: uglavnom izgleda kao rekurzivni labirint za praćenje unazad, ali s povremenim granama koje prekidaju duge hodnike.
  • 50% najnoviji, 50% najstariji: Uravnotežuje duge hodnike s grmolikim rastom.

Podijeli na BlueskyPodijelite na FacebookuPodijelite na LinkedInuPodijelite na TumblrPodijeli na XPodijelite na LinkedInuPrikvači na Pinterest

Mikkel Bang Christensen

O autoru

Mikkel Bang Christensen
Mikkel je kreator i vlasnik miklix.com. Ima više od 20 godina iskustva kao profesionalni računalni programer/razvijač softvera i trenutno je zaposlen na puno radno vrijeme za veliku europsku IT korporaciju. Kada ne piše blog, svoje slobodno vrijeme provodi na široku lepezu interesa, hobija i aktivnosti, što se u određenoj mjeri može odraziti na različite teme obrađene na ovoj web stranici.