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

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

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

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

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

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

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

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

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

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

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

• მიანიჭეთ თითოეული უჯრედი ზედიზედ უნიკალურ კომპლექტს.

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

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

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

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

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

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

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

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

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

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