ნადირობა და მოკვლა მეზის გენერატორი

Hunt and Kill ალგორითმი ნამდვილად არის Recursive Backtracker- ის შეცვლილი ვერსია. მოდიფიკაცია შედგება სისტემატურად სკანირებისგან (ან "ნადირობა") ახალი უჯრედის გასაგრძელებლად, როდესაც ის ვერ წავა უფრო შორს, განსხვავებით ნამდვილი რეკურსიული ძიებისგან, რომელიც ყოველთვის დაბრუნდება წინა უჯრედში დასტის შესახებ.

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

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

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

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

Hunt and Kill ალგორითმი არის მარტივი, მაგრამ ეფექტური მეთოდი ლაბირინთების წარმოქმნისთვის. ეს გარკვეულწილად ჰგავს სიღრმისეული პირველი ძიების (ე.ი. Recursive Backtracker ალგორითმი), გარდა იმ შემთხვევისა, როდესაც ის ვერ წავა უფრო შორს მიმდინარე პოზიციიდან, ის სისტემატურად სკანირებს (ან "ნადირობას") ლაბირინთზე, რათა იპოვოს ახალი უჯრედი გასაგრძელებლად. ალგორითმი შედგება ორი ძირითადი ფაზისგან: სიარული და ნადირობა.

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

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

• იპოვნეთ შემთხვევითი უჯრედი ქსელში და მონიშნეთ როგორც ეწვია.

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

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

ნაბიჯი 3: ნადირობის ფაზა (Backtracking მეშვეობით სკანირება)

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