Generator Labirinta Algoritma Eller

Ellerov algoritam je algoritam za generiranje lavirinata koji efikasno proizvodi savršene lavirinte (labirinte bez petlji i s jednom putanjom između bilo koje dvije tačke) koristeći pristup red po red. Proizvodi lavirinte slično Kruskalovom algoritmu, ali to čini generiranjem samo jednog reda u isto vrijeme, bez potrebe za pohranjivanjem cijelog lavirinta u memoriju. To ga čini korisnim za generiranje vrlo velikih lavirinata na vrlo ograničenim sistemima i za generiranje proceduralnog sadržaja.

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.

O Ellerovom algoritmu

Ellerov algoritam je predstavio David Eller.

Algoritam je poznat po svom efikasnom pristupu generisanju lavirina red po red, što ga čini idealnim za beskonačne lavirinte ili lavirinte generisane u realnom vremenu. Često se citira u literaturi o generisanju proceduralnog sadržaja i generisanju lavirina, ali nisam uspio pronaći primarne izvore koji detaljno opisuju njegovu originalnu publikaciju.

Kako Ellerov algoritam funkcioniše za generisanje lavirinta

Ellerov algoritam obrađuje red po red, održavajući i mijenjajući skupove povezanih ćelija. Osigurava povezanost izbjegavajući petlje i efikasno proširuje labirint prema dolje.

Teoretski se može koristiti za generiranje beskonačnih labirinta, međutim, kako bi se osiguralo da je generirani labirint zapravo rješiv, potrebno je u nekom trenutku preći na logiku "završnog reda" kako bi se labirint završio.

Korak 1: Inicijalizacija prvog reda

• Dodijelite svakoj ćeliji u redu jedinstveni ID skupa.

Korak 2: Spojite nekoliko susjednih ćelija horizontalno

• Nasumično spojite susjedne ćelije postavljanjem istog ID-a skupa. Ovo osigurava da postoje horizontalni prolazi.

Korak 3: Kreirajte vertikalne veze sa sljedećim redom

• Za svaki skup koji se pojavljuje u redu, barem jedna ćelija mora biti povezana prema dolje (kako bi se osigurala povezanost).
• Nasumično odaberite jednu ili više ćelija iz svakog skupa kako biste ih povezali sa sljedećim redom.

Korak 4: Pređite na sljedeći red

• Prenesite vertikalne veze dalje dodjeljivanjem istog ID-a skupa odgovarajućim ćelijama ispod.
• Dodijelite nove ID-ove skupova svim nedodijeljenim ćelijama.

Korak 5: Ponovite korake 2-4 dok ne dođete do posljednjeg reda

• Nastavite obradu red po red.

Korak 6: Obradite posljednji red

• Osigurajte da sve ćelije u posljednjem redu pripadaju istom skupu spajanjem svih preostalih odvojenih skupova.

Dodatno čitanje

Ako vam se svidio ovaj post, možda će vam se svidjeti i ovi prijedlozi:

• Rekurzivni Backtracker Maze Generator
• Generator labirinta za lov i ubijanje
• Generator labirinta algoritama za uzgoj drveća