विल्सन अल्गोरिदम मेझ जनरेटर

विल्सनचा अल्गोरिथम हा एक लूप-इरेज्ड रँडम वॉक मेथड आहे जो मेझ निर्मितीसाठी एकसमान स्पॅनिंग ट्रीज तयार करतो. याचा अर्थ असा की दिलेल्या आकाराचे सर्व संभाव्य मेझ तयार होण्याची शक्यता समान आहे, ज्यामुळे ते एक निष्पक्ष मेझ जनरेशन तंत्र बनते. विल्सनचा अल्गोरिथम हा अल्डोस-ब्रोडर अल्गोरिथमची सुधारित आवृत्ती मानला जाऊ शकतो, कारण तो समान वैशिष्ट्यांसह मेझ तयार करतो, परंतु तो खूप जलद चालतो, म्हणून मी येथे अल्डोस-ब्रोडर अल्गोरिथम लागू करण्याची तसदी घेतली नाही.

परिपूर्ण भूलभुलैया म्हणजे असा भूलभुलैया ज्यामध्ये भूलभुलैयामधील कोणत्याही बिंदूपासून दुसऱ्या बिंदूपर्यंत एकच मार्ग असतो. याचा अर्थ असा की तुम्ही वर्तुळात फिरू शकत नाही, परंतु तुम्हाला अनेकदा अडचणी येतील, ज्यामुळे तुम्हाला मागे वळून परत जावे लागेल.

येथे तयार केलेल्या भूलभुलैया नकाशांमध्ये कोणत्याही सुरुवातीच्या आणि शेवटच्या स्थानांशिवाय डीफॉल्ट आवृत्ती समाविष्ट आहे, म्हणून तुम्ही ते स्वतः ठरवू शकता: भूलभुलैयामधील कोणत्याही बिंदूपासून इतर कोणत्याही बिंदूपर्यंत एक उपाय असेल. जर तुम्हाला प्रेरणा हवी असेल, तर तुम्ही सुचविलेले प्रारंभ आणि शेवटचे स्थान सक्षम करू शकता - आणि दोघांमधील उपाय देखील पाहू शकता.

विल्सनच्या अल्गोरिथम बद्दल

लूप-इरेज्ड रँडम वॉल वापरून एकसमान स्पॅनिंग ट्रीज तयार करण्यासाठी विल्सनचा अल्गोरिथम डेव्हिड ब्रूस विल्सन यांनी तयार केला होता.

विल्सनने मूळतः १९९६ मध्ये संभाव्यता सिद्धांतातील यादृच्छिक स्पॅनिंग ट्रीज आणि मार्कोव्ह चेनचा अभ्यास करताना हे अल्गोरिथम सादर केले. जरी त्यांचे काम प्रामुख्याने गणित आणि सांख्यिकीय भौतिकशास्त्रात असले तरी, पूर्णपणे एकसमान भूलभुलैया तयार करण्याच्या क्षमतेमुळे भूलभुलैया निर्मितीसाठी अल्गोरिथमचा मोठ्या प्रमाणावर वापर केला जात आहे.

भूलभुलैया निर्मितीसाठी विल्सनचे अल्गोरिथम कसे कार्य करते

विल्सनचा अल्गोरिथम यादृच्छिक चालण्याचा वापर करून न भेट दिलेल्या पेशींमधून पुनरावृत्ती मार्ग कोरून अंतिम भूलभुलैया कोणत्याही लूपशिवाय पूर्णपणे जोडलेला आहे याची खात्री करतो.

पायरी १: सुरू करा

• भिंतींनी भरलेल्या ग्रिडने सुरुवात करा.
• सर्व शक्य पॅसेज सेल्सची यादी परिभाषित करा.

पायरी २: एक रँडम स्टार्टिंग सेल निवडा

• कोणताही यादृच्छिक सेल निवडा आणि तो भेट दिलेला म्हणून चिन्हांकित करा. हे पिढी दरम्यान चक्रव्यूहाचा प्रारंभ बिंदू म्हणून काम करते.

पायरी ३: लूप-इरेजिंगसह रँडम वॉक

• भेट न मिळालेला एक कक्ष निवडा आणि यादृच्छिक चालणे सुरू करा (यादृच्छिक दिशेने हालचाल करा).
• जर चालणे आधीच भेट दिलेल्या सेलपर्यंत पोहोचले तर, मार्गातील सर्व लूप पुसून टाका.
• एकदा वॉक भेट दिलेल्या प्रदेशाशी जोडला गेला की, मार्गातील सर्व सेल भेट दिलेल्या म्हणून चिन्हांकित करा.

पायरी ४: सर्व सेल्सना भेट देईपर्यंत पुनरावृत्ती करा:

• प्रत्येक पेशी चक्रव्यूहाचा भाग होईपर्यंत न भेट दिलेल्या पेशी निवडणे आणि यादृच्छिक चालणे सुरू ठेवा.

पुढील वाचन

जर तुम्हाला ही पोस्ट आवडली असेल, तर तुम्हाला हे सूचना देखील आवडतील:

• शिकार करा आणि मारून टाका चक्रव्यूह जनरेटर
• क्रुस्कलचा अल्गोरिथम मेझ जनरेटर
• वाढते वृक्ष अल्गोरिदम चक्रव्यूह जनरेटर