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

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

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

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

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

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

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

ალგორითმი მოქმედებს დასტის დაფუძნებული სიღრმისეული პირველი საძიებო მიდგომის გამოყენებით. აქ არის ნაბიჯ ნაბიჯ ავარია:

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

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

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