Ellerov algoritam Lavirint generator

Ellerov algoritam je algoritam za generisanje lavirinta koji efikasno proizvodi savršene lavirinte (lavirint bez petlji i jednu stazu između bilo koje dve tačke) koristeći pristup red-po-red. Proizvodi lavirinte slične Kruskalovom algoritmu, ali to čini generisanjem samo jednog reda u isto vreme, bez potrebe za čuvanjem celog lavirinta u memoriju. To ga čini korisnim za generisanje veoma velikih lavirinta na veoma ograničenim sistemima i za proceduralno generisanje sadržaja.

Savršen lavirint je lavirint u kojem postoji tačno jedan put od bilo koje tačke u lavirintu do bilo koje druge tačke. To znači da ne možete završiti u krugovima, ali ćete često naići na ćorsokak, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta generisane ovde uključuju podrazumevanu verziju bez ikakvih početnih i završnih pozicija, tako da možete sami da odlučite o njima: biće rešenje od bilo koje tačke u lavirintu do bilo koje druge tačke. Ako želite inspiraciju, možete da omogućite predloženu početnu i završnu poziciju - pa čak i da vidite rešenje između ova dva.

O Eller's algoritmu

Eller's algoritam je uveo David Eller.

Algoritam je poznat po efikasnom pristupu generisanju lavirinta, rad po redovima, što ga čini idealnim za beskonačne lavirinte ili lavirinte generisane u realnom vremenu. Često se pominje u literaturi o proceduralnom generisanju sadržaja i generisanju lavirinata, ali nisam mogao da pronađem primarne izvore koji detaljno opisuju njegovu originalnu publikaciju.

Kako Eller's algoritam funkcioniše za generisanje lavirinata

Eller's algoritam obrađuje po jedan red u isto vreme, održavajući i modifikujući skupove povezanih ćelija. On obezbeđuje povezanost dok izbegava petlje i efikasno proširuje lavirint prema dole.

Teorijski, može se koristiti za generisanje beskonačnih lavirinata, međutim, kako bi se osiguralo da generisani lavirint bude zapravo rešiv, potrebno je preći na logiku "poslednjeg reda" u nekom trenutku kako bi se završio lavirint.

Korak 1: Inicijalizujte prvi red

• Dodelite svakoj ćeliji u redu jedinstveni ID skupa.

Korak 2: Povežite neke susedne ćelije horizontalno

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

Korak 3: Kreirajte vertikalne veze sa sledećim redom

• Za svaki skup koji se pojavljuje u redu, barem jedna ćelija mora se povezati prema dole (kako bi se osigurala povezanost).
• Nasumično izaberite jednu ili više ćelija iz svakog skupa da se povežu sa sledećim redom.

Korak 4: Pređite na sledeći red

• Prenesite vertikalne veze dodeljujući isti ID skupa odgovarajućim ćelijama ispod.
• Dodelite nove ID-eve skupa svim ne dodeljenim ćelijama.

Korak 5: Ponovite korake 2–4 dok ne stignete do poslednjeg reda

• Nastavite sa obradom red po red.

Korak 6: Obradite poslednji red

• Osigurajte da sve ćelije u poslednjem redu pripadaju istom skupu spajajući sve preostale odvojene skupove.