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

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

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

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

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

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

როგორ მუშაობს მზარდი ხის ალგორითმი

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

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

ნაბიჯი 2: Maze თაობის მარყუჟი

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

ნაბიჯი 3: შეწყვეტა

• ალგორითმი მთავრდება, როდესაც სიაში აღარ არის უჯრედები, რაც იმას ნიშნავს, რომ მთელი ლაბირინთი მოჩუქურთმებულია.

უჯრედების შერჩევის სტრატეგიები (ალგორითმის მოქნილობა)

მზარდი ხის ალგორითმის განმსაზღვრელი თვისებაა ის, თუ როგორ აირჩევთ რომელი უჯრედის დამუშავებას შემდეგ. ეს არჩევანი მკვეთრად მოქმედებს ლაბირინთის გარეგნობაზე:

უახლესი უჯრედი (Stack-ის მსგავსი ქცევა) – რეკურსიული Backtracker:

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

შემთხვევითი უჯრედი (რანდომიზებული პრიმის ალგორითმი):

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

უძველესი უჯრედი (რიგის მსგავსი ქცევა):

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

ჰიბრიდული მიდგომები:

შეუთავსეთ სტრატეგიები მრავალფეროვანი ლაბირინთის მახასიათებლებისთვის. მაგალითად:

• 90% უახლესი, 10% შემთხვევითი: ძირითადად ჰგავს რეკურსიულ უკანა ლაბირინთს, მაგრამ ზოგჯერ ფილიალებით, რომლებიც გრძელი დერეფნების დაშლას იწვევენ.
• 50% უახლესი, 50% უძველესი: აბალანსებს ხანგრძლივი დერეფნების ერთად bushy ზრდა.