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

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

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

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

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

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

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

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

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

ნაბიჯი 2: ლაბირინთის გენერაციის ციკლი

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

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

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

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

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

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

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

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

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

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

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

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

ლაბირინთის სხვადასხვა მახასიათებლებისთვის სტრატეგიების შერწყმა. მაგალითად:

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

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

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

• უილსონის ალგორითმის ლაბირინთის გენერატორი
• რეკურსიული Backtracker Maze გენერატორი
• კრუსკალის ალგორითმის ლაბირინთში გენერატორი