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

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

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

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

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

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

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

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

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

ნაბიჯი 1: ინიციალიზაცია

• დაიწყეთ კედლებით სავსე ბადით.
• განსაზღვრეთ ყველა შესაძლო გადასასვლელი უჯრის სია.

ნაბიჯი 2: აირჩიეთ შემთხვევითი საწყისი უჯრა

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

ნაბიჯი 3: შემთხვევითი სიარული ციკლის წაშლით

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

ნაბიჯი 4: გაიმეორეთ მანამ, სანამ ყველა უჯრედი არ მოინახულება:

• განაგრძეთ დაუთვალიერებელი უჯრედების შერჩევა და შემთხვევითი გასეირნების შესრულება მანამ, სანამ ყველა უჯრედი ლაბირინთის ნაწილი არ გახდება.

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

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

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