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

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

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

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

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

Hunt and Kill ალგორითმის შესახებ

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

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

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

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

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

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

ნაბიჯი 3: ძიების ფაზა (უკან დაბრუნება სკანირების გზით)

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

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

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

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