विल्सन का एल्गोरिदम भूलभुलैया जनरेटर

विल्सन का एल्गोरिथ्म एक लूप-इरेज़्ड रैंडम वॉक विधि है जो भूलभुलैया निर्माण के लिए समान फैले हुए पेड़ उत्पन्न करती है। इसका मतलब है कि किसी दिए गए आकार की सभी संभावित भूलभुलैयाएँ समान रूप से उत्पन्न होने की संभावना है, जो इसे एक निष्पक्ष भूलभुलैया निर्माण तकनीक बनाती है। विल्सन के एल्गोरिथ्म को एल्डस-ब्रोडर एल्गोरिथ्म का एक बेहतर संस्करण माना जा सकता है, क्योंकि यह समान विशेषताओं वाली भूलभुलैयाएँ उत्पन्न करता है, लेकिन यह बहुत तेज़ चलता है, इसलिए मैंने यहाँ एल्डस-ब्रोडर एल्गोरिथ्म को लागू करने की जहमत नहीं उठाई है।

एक आदर्श भूलभुलैया वह भूलभुलैया होती है जिसमें भूलभुलैया के किसी भी बिंदु से किसी अन्य बिंदु तक जाने के लिए बिल्कुल एक ही रास्ता होता है। इसका मतलब है कि आप चक्कर लगाते हुए नहीं रह सकते, लेकिन आप अक्सर ऐसे रास्ते पर आएँगे जहाँ आपको पीछे मुड़ना होगा और वापस लौटना होगा।

यहाँ बनाए गए भूलभुलैया मानचित्रों में बिना किसी आरंभ और समाप्ति स्थिति के एक डिफ़ॉल्ट संस्करण शामिल है, इसलिए आप उन्हें स्वयं तय कर सकते हैं: भूलभुलैया के किसी भी बिंदु से किसी भी अन्य बिंदु तक एक समाधान होगा। यदि आप प्रेरणा चाहते हैं, तो आप सुझाए गए आरंभ और समाप्ति स्थिति को सक्षम कर सकते हैं - और यहां तक ​​कि दोनों के बीच समाधान भी देख सकते हैं।

विल्सन के एल्गोरिदम के बारे में

लूप-इरेज़्ड रैंडम वॉल का उपयोग करके समान स्पैनिंग वृक्ष उत्पन्न करने के लिए विल्सन एल्गोरिदम डेविड ब्रूस विल्सन द्वारा बनाया गया था।

विल्सन ने मूल रूप से इस एल्गोरिथ्म को 1996 में संभाव्यता सिद्धांत में यादृच्छिक फैलाव वाले पेड़ों और मार्कोव श्रृंखलाओं पर शोध करते समय पेश किया था। हालाँकि उनका काम मुख्य रूप से गणित और सांख्यिकीय भौतिकी में था, लेकिन एल्गोरिथ्म को पूरी तरह से एकसमान भूलभुलैया बनाने की क्षमता के कारण भूलभुलैया निर्माण के लिए व्यापक रूप से अपनाया गया है।

विल्सन का एल्गोरिदम भूलभुलैया निर्माण के लिए कैसे काम करता है

विल्सन का एल्गोरिथ्म यह सुनिश्चित करता है कि अंतिम भूलभुलैया बिना किसी लूप के पूरी तरह से जुड़ी हुई है, इसके लिए यादृच्छिक चाल का उपयोग करते हुए अप्रयुक्त कोशिकाओं से पथों को पुनरावृत्त रूप से बनाया जाता है।

चरण 1: आरंभ करें

• दीवारों से भरे ग्रिड से शुरुआत करें।
• सभी संभावित मार्ग कोशिकाओं की एक सूची परिभाषित करें.

चरण 2: एक यादृच्छिक प्रारंभिक सेल चुनें

• कोई भी यादृच्छिक सेल चुनें और उसे विज़िट किए गए के रूप में चिह्नित करें। यह पीढ़ी के दौरान भूलभुलैया के शुरुआती बिंदु के रूप में कार्य करता है।

चरण 3: लूप-इरेज़िंग के साथ रैंडम वॉक

• किसी ऐसे सेल को चुनें जहां आप नहीं गए हैं और यादृच्छिक चलना शुरू करें (यादृच्छिक दिशाओं में चलते हुए)।
• यदि वॉक पहले से देखी गई सेल तक पहुंचता है, तो पथ में किसी भी लूप को मिटा दें।
• जब पथ भ्रमण किए गए क्षेत्र से जुड़ जाता है, तो पथ में सभी कक्षों को भ्रमण किए गए के रूप में चिह्नित करें।

चरण 4: सभी कक्षों पर जाने तक दोहराएं :

• अप्रयुक्त कक्षों का चयन करना तथा यादृच्छिक चालन करना तब तक जारी रखें जब तक कि प्रत्येक कक्ष भूलभुलैया का हिस्सा न बन जाए।