რეკურსიული Backtracker Maze გენერატორი

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

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

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

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

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

როგორ მუშაობს

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

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

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

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

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

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

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