ელერის ალგორითმის ლაბირინთის გენერატორი

ელერის ალგორითმი არის ლაბირინთის გენერირების ალგორითმი, რომელიც ეფექტურად ქმნის იდეალურ ლაბირინთებს (ლაბირინთები ციკლების გარეშე და ერთი ბილიკით ნებისმიერ ორ წერტილს შორის) რიგით-რიგით მიდგომის გამოყენებით. ის ქმნის კრუსკალის ალგორითმის მსგავს ლაბირინთებს, მაგრამ ამას აკეთებს ერთდროულად მხოლოდ ერთი რიგის გენერირებით, მთელი ლაბირინთის მეხსიერებაში შენახვის საჭიროების გარეშე. ეს მას სასარგებლოს ხდის ძალიან შეზღუდულ სისტემებზე ძალიან დიდი ლაბირინთების გენერირებისთვის და პროცედურული შინაარსის გენერირებისთვის.

სრულყოფილი ლაბირინთი არის ლაბირინთი, რომელშიც არის ზუსტად ერთი გზა ლაბირინთის ნებისმიერი წერტილიდან ნებისმიერ სხვა წერტილამდე. ეს ნიშნავს, რომ თქვენ არ შეგიძლიათ ბოლომდე იაროთ წრეებში, მაგრამ ხშირად შეხვდებით ჩიხებს, რომლებიც გაიძულებენ შეტრიალდეთ და უკან დაბრუნდეთ.

აქ გენერირებული ლაბირინთის რუქები მოიცავს ნაგულისხმევ ვერსიას ყოველგვარი საწყისი და დასრულების პოზიციების გარეშე, ასე რომ თქვენ შეგიძლიათ თავად გადაწყვიტოთ ისინი: იქნება გამოსავალი ლაბირინთის ნებისმიერი წერტილიდან ნებისმიერ სხვა წერტილამდე. თუ გსურთ შთაგონება, შეგიძლიათ ჩართოთ შემოთავაზებული საწყისი და დასრულების პოზიცია - და კიდევ ნახოთ გამოსავალი ამ ორს შორის.

ელერის ალგორითმის შესახებ

ელერის ალგორითმი დევიდ ელერმა შემოიღო.

ალგორითმი გამოირჩევა ლაბირინთების გენერირების ეფექტური, რიგითი მიდგომით, რაც მას იდეალურს ხდის უსასრულო ლაბირინთებისთვის ან რეალურ დროში გენერირებული ლაბირინთებისთვის. ის ხშირად მოიხსენიება პროცედურული შინაარსის გენერირებისა და ლაბირინთების გენერირების ლიტერატურაში, თუმცა ვერ ვიპოვე მისი ორიგინალური გამოცემის დეტალური აღწერის პირველადი წყაროები.

როგორ მუშაობს ელერის ალგორითმი ლაბირინთის გენერირებისთვის

ელერის ალგორითმი ერთდროულად ამუშავებს ერთ რიგს, ინარჩუნებს და ცვლის დაკავშირებული უჯრედების ნაკრებებს. ის უზრუნველყოფს კავშირს მარყუჟების თავიდან აცილების პარალელურად და ეფექტურად აფართოებს ლაბირინთს ქვემოთ.

თეორიულად, მისი გამოყენება შესაძლებელია უსასრულო ლაბირინთების გენერირებისთვის, თუმცა, იმისათვის, რომ უზრუნველყოთ გენერირებული ლაბირინთის რეალურად ამოხსნა, აუცილებელია გარკვეულ მომენტში „ბოლო რიგის“ ლოგიკაზე გადასვლა ლაბირინთის დასასრულებლად.

ნაბიჯი 1: პირველი რიგის ინიციალიზაცია

• მწკრივის თითოეულ უჯრედს მიანიჭეთ უნიკალური ნაკრების ID.

ნაბიჯი 2: რამდენიმე მიმდებარე უჯრედის ჰორიზონტალურად შეერთება

• შემთხვევით გააერთიანეთ მიმდებარე უჯრედები ერთი და იგივე ნაკრების ID-ზე დაყენებით. ეს უზრუნველყოფს ჰორიზონტალური გადასასვლელების არსებობას.

ნაბიჯი 3: შექმენით ვერტიკალური კავშირები შემდეგ რიგთან

• რიგში გამოჩენილი თითოეული ნაკრებისთვის, სულ მცირე ერთი უჯრედი უნდა დაუკავშირდეს ქვემოთ (დაკავშირების უზრუნველსაყოფად).
• შემთხვევით აირჩიეთ ერთი ან მეტი უჯრედი თითოეული ნაკრებიდან შემდეგ რიგთან დასაკავშირებლად.

ნაბიჯი 4: გადადით შემდეგ რიგში

• ვერტიკალური კავშირების გადატანა შესაძლებელია ქვემოთ მოცემული შესაბამისი უჯრედებისთვის იგივე ნაკრების ID-ის მინიჭებით.
• მიანიჭეთ ახალი ნაკრების ID-ები ნებისმიერ გამოუყოფელ უჯრედს.

ნაბიჯი 5: გაიმეორეთ ნაბიჯები 2–4 ბოლო რიგამდე მიღწევამდე

• განაგრძეთ დამუშავება რიგის მიხედვით.

ნაბიჯი 6: საბოლოო რიგის დამუშავება

• დარწმუნდით, რომ ბოლო რიგის ყველა უჯრედი ერთსა და იმავე კომპლექტს მიეკუთვნება დარჩენილი ცალკეული კომპლექტების გაერთიანებით.

დამატებითი საკითხავი

თუ ეს პოსტი მოგეწონათ, შეიძლება ეს რჩევებიც მოგეწონოთ:

• მზარდი ხის ალგორითმის ლაბირინთის გენერატორი
• კრუსკალის ალგორითმის ლაბირინთში გენერატორი
• ნადირობა და მოკვლა მეზის გენერატორი