Generator Labirinta Algoritma Eller

Ellerov algoritam je algoritam za generiranje labirinta koji efikasno proizvodi savršene labirinte (labirinte bez petlji i jednom putanjom između bilo koje dvije tačke) koristeći pristup red-po-red. Proizvodi labirinte slične Kruskalovom algoritmu, ali to čini generiranjem samo jednog po jednog reda, bez potrebe za pohranjivanjem cijelog labirinta u memoriju. To ga čini korisnim za generiranje vrlo velikih labirinta na vrlo ograničenim sistemima i za proceduralno generiranje 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 značajan po svom efikasnom pristupu generiranju labirinta, što ga čini idealnim za beskonačne labirinte ili labirinte generirane u realnom vremenu. Obično se citira u proceduralnom stvaranju sadržaja i literaturi o stvaranju labirinta, ali nisam bio u mogućnosti pronaći primarne izvore koji detaljno opisuju njegovo originalno objavljivanje.

Kako Ellerov algoritam radi za stvaranje labirinta

Ellerov algoritam obrađuje jedan po jedan red, održavajući i modificirajući skupove povezanih ćelija. Osigurava povezanost uz izbjegavanje petlji 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 prebaciti se na logiku "posljednjeg reda" u nekom trenutku da bi se labirint završio.

Korak 1: Inicijalizirajte prvi red

• Dodijelite svakoj ćeliji u redu jedinstveni ID skupa.

Korak 2: Spojite neke susjedne ćelije horizontalno

• Nasumično spojite susjedne ćelije tako što ćete ih postaviti na isti ID skupa. To osigurava da postoje horizontalni prolazi.

Korak 3: Kreirajte vertikalne veze sa sljedećim redom

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

Korak 4: Prelazak na sljedeći red

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

Korak 5: Ponavljajte korake 2-4 dok se ne dođe do posljednjeg reda

• Nastavite s obradom red po red.

Korak 6: Obrada posljednjeg reda

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