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

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

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

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

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

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

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

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

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

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

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

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

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

ნაბიჯი 3: შემთხვევითი გასეირნება მარყუჟის ამოშლით

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

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

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