Mazes पैदा करने के लिए एलर की एल्गोरिथ्म

यह एक एलर के एल्गोरिथम लेख का एक विषय अनुवाद है। यह प्रोग्रामेटिकली लेबिरिंथ उत्पन्न करने के तरीके के बारे में बात करता है। आगे का कथन लेखक का है।

  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
 | __ | __ __ __ | __ |  __ |  |  |  |  |
 | __ | __ | __ |  __ __ |  __ __ |  |
 |  |  |  |  |  | __ | __ |  |  |  |
 | __ | __ |  |  |  __ |  __ | __ |  __ | __ |  | __ |
 |  __ |  |  | __ __ __ |  |  | __ |  |  |  |
 |  |  |  |  | __ |  | __ |  |  __ | __ __ |  |  |
 |  | __ __ __ __ __ __ |  |  __ |  |  |
 |  |  |  |  |  __ |  |  __ |  |  | __ |  |  |
 |  |  |  | __ |  |  |  |  |  | __ __ |
 |  |  | __ | __ | __ __ |  |  |  |  |  __ |  |
 | __ __ |  |  |  | __ | __ |  __ |  |  __ __ |
 |  __ |  |  __ | __ | __ | __ |  | __ __ |
 |  |  |  |  |  | __ |  |  __ __ |  __ |
 |  __ |  | __ __ | __ |  __ |  |  |  |  |  |
 |  __ __ |  __ | __ |  | __ |  |  | __ |  |
 | __ __ __ | __ | __ | __ __ __ __ __ | __ | __ | __ | __ __ __ | 

एलर का एल्गोरिथ्म आपको लेबिरिंथ बनाने की अनुमति देता है जिनके पास दो बिंदुओं के बीच केवल एक ही रास्ता है। एल्गोरिथ्म अपने आप में बहुत तेज़ है और अन्य लोकप्रिय एल्गोरिदम (जैसे प्राइम और क्रुस्ल) की तुलना में मेमोरी का अधिक कुशलता से उपयोग करता है, जिसमें लाइनों की संख्या के अनुपात में मेमोरी की आवश्यकता होती है। यह आपको सीमित मेमोरी साइज़ के साथ बड़े mazes बनाने की अनुमति देता है।



इंटरनेट पर एलर एल्गोरिथ्म के बारे में बहुत कम जानकारी है। सबसे अच्छा स्रोत जो मुझे मिल सकता है ( वाल्टर पुलन वेबसाइट) में वर्णन के साथ सिर्फ एक पैराग्राफ है जो उपयोगी है, लेकिन एल्गोरिथ्म को लागू करने के लिए पर्याप्त नहीं है। इसके अलावा, प्रोग्रामर के लिए गणित और भौतिकी की पुस्तक में वर्णित एल्गोरिदम सबसे अधिक संभावना नहीं है। मैंने लापता हिस्सों पर विचार किया और मुझे यकीन है कि जिस एल्गोरिथ्म का मैंने वर्णन किया है वह वास्तव में एलर का एल्गोरिथ्म है। आप इसके बारे में अधिक जानकारी भूलभुलैया पीढ़ी: एलर के एल्गोरिथम लेख में भी पा सकते हैं।

एल्गोरिथम विवरण

नोट: हम मानते हैं कि बाईं सेल में बाईं ओर एक बॉर्डर है और दाईं ओर सबसे दाईं ओर।

1. पहली पंक्ति बनाएँ। कोई भी सेल किसी भी सेट का हिस्सा नहीं होगा।
2. कोशिकाओं को असाइन करें जो आपके अनन्य सेट में सेट नहीं हैं।
3. दाएं बॉर्डर बनाएं, बाएं से दाएं जा रहा है:
   1. अनियमित रूप से सीमा जोड़ने या न करने का निर्णय लें
      1. यदि वर्तमान सेल और दाईं ओर सेल एक ही सेट से संबंधित हैं, तो उनके बीच एक सीमा बनाएं (छोरों को रोकने के लिए)
      2. यदि आप एक सीमा नहीं जोड़ने का निर्णय लेते हैं, तो उन दो सेटों को मिलाएं जिनमें वर्तमान सेल और दाईं ओर सेल स्थित हैं।
4. नीचे से दाएं से बाएं की ओर बॉर्डर बनाएं:
   • अनियमित रूप से सीमा जोड़ने या न करने का निर्णय लें। सुनिश्चित करें कि प्रत्येक सेट में कम सीमा के बिना कम से कम एक सेल है (अलग क्षेत्रों को रोकने के लिए)
     1. यदि इसके सेट में केवल एक सेल है, तो नीचे से एक बॉर्डर न बनाएं
     2. यदि सेल निचली सीमा के बिना अपने सेट में एक है, तो एक निचली सीमा न बनाएं
5. तय करें कि क्या आप लाइनों को जोड़ना जारी रखेंगे या यदि आप भूलभुलैया खत्म करना चाहते हैं
   1. यदि आप दूसरी पंक्ति जोड़ना चाहते हैं, तो:
      1. वर्तमान लाइन प्रिंट करें
      2. सभी सही सीमाओं को हटा दें
      3. उनके सेट से निचली सीमा वाले सेल निकालें
      4. सभी निचले सीमा को हटा दें
      5. चरण 2 से जारी रखें।
   2. यदि आप भूलभुलैया खत्म करने का निर्णय लेते हैं, तो:
      1. प्रत्येक सेल में एक निचला बॉर्डर जोड़ें
      2. बाएं से दाएं चलना:
         1. यदि वर्तमान सेल और दाईं ओर स्थित सेल अलग सेट के सदस्य हैं, तो:
            1. सही बॉर्डर निकालें
            2. वर्तमान सेल और सेल के सेट को दाईं ओर मिलाएं
            3. समाप्ति रेखा प्रिंट करें

उदाहरण

इस उदाहरण में, हम एक सरल भूलभुलैया बनाएंगे। हम इसे लाइन से लाइन बनाना शुरू करेंगे, ऊपर से नीचे की ओर, बाएं से दाएं की ओर। पंक्ति में प्रत्येक कक्ष सेट का होगा। हम उनकी संख्या के अनुसार सेट के नंबरों को नीचे रखकर और सेल में इन नंबरों को लिखकर इसकी कल्पना करते हैं। प्रत्येक सेल में दाईं ओर और / या नीचे एक बॉर्डर हो सकता है। हम मानते हैं कि बहुत पहले के बाईं ओर और पंक्ति में बहुत अंतिम सेल के दाईं ओर सीमाएं हैं।

चरण 1: पहली पंक्ति बनाएं

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  | 

चरण 2: सेट से संबंधित सभी कोशिकाओं को हमारे नए सेट से न जोड़ें

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 2 3 4 5 6 7 8 | 

चरण 3: दाईं ओर बॉर्डर बनाएं

  ___ ___ ___ ___ ___ ___ ___ ___
	 | (१ २) ३ ४ ५ ६ | 3 | 

यदि हम सीमा नहीं बनाने का निर्णय लेते हैं, तो हम सेट को एकजुट करते हैं

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  १ (१ ३) ४ ५ ६ | 4 | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  १ १ (१ | ४) ५ ६ | 4 | 

  ... 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 1 1 |  4 4 |  6 6 6 | 

स्टेप 4: बॉटम बॉर्डर बनाएं

सुनिश्चित करें कि कोशिकाओं के प्रत्येक सेट में कम सीमा के बिना कम से कम एक सेल है। यदि यह शर्त पूरी नहीं होती है, तो हम अलग-थलग क्षेत्रों का निर्माण करेंगे।

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ | 

चरण 5 ए: एक नई लाइन बनाना

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |  <- इस लाइन को प्रिंट करें
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |  <- हमारी पिछली पंक्ति चालू हो गई 

सही सीमाओं को हटाएं

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |
	 |  1 _1_ _1_ 4 _4_ 6 6 _6_ | 

यदि कक्ष की निचली सीमा है, तो इसे सेट से हटा दें:

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |
	 |  1 ___ ___ 4 ___ 6 6 ___ | 

निचली सीमा को हटा दें

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |
	 |  १ ४ ६ ६ | 

चरण 2 से जारी है:

चरण 2: उन कोशिकाओं को संलग्न करें जो उनके अनूठे सेटों से संबंधित नहीं हैं

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ | 
	 |  1 2 3 4 5 6 6 7 | 

चरण 3: दाईं ओर सीमाएँ जोड़ें

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 | (१ | २) ३ ४ ५ ६ ६) |  <- सीमा गयी 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 | (2 3) 4 5 6 6 7 |  <- कोई सीमा नहीं जोड़ी गई; 2 और 3 के सेट को मिलाएं 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  २ (२ ४) ५ ६ ६ 5 |  <- कोई सीमा नहीं जोड़ी गई; 2 और 4 के सेटों को मिलाएं 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  २ २ (२ | ५) ६ ६ 5 |  <- सीमा गयी 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  २ २ २ | (५ | ६) ६ 5 |  <- सीमा गयी 

अगले दो सेल एक ही सेट के सदस्य हैं, इसलिए हमें एक सीमा जोड़ना होगा। यदि हम नहीं जोड़ते हैं, तो इससे हमारे चक्रव्यूह में चक्र आएंगे

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 | (6 | 6) 7 |  <- एक सीमा जोड़ना होगा 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 |  6 | (6 7) |  <- कोई सीमा नहीं जोड़ी गई; गठबंधन सेट 6 और 7 

चरण 4: निचली सीमा

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 |  6 |  6 6 | 

याद रखें, सेट से कम से कम एक सेल की सीमा कम नहीं होनी चाहिए

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 _2_ _2_ |  5 | _6_ |  6 _6_ | 

आप जितनी चाहें उतनी लाइनें जोड़ सकते हैं

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | _1_ 1 |  ३ ३ |  7 _7_ _7_ |  8 | 

चरण 5 बी: भूलभुलैया को खत्म करना

अंतिम पंक्ति सामान्य लोगों से अलग होती है 1) प्रत्येक सेल में एक निचला बॉर्डर 2 होता है) प्रत्येक सेल एक सेट से संबंधित होना चाहिए।

एक सेट में कोशिकाओं को संलग्न करना बहुत सरल है, आपको केवल उन कोशिकाओं के बीच की सीमाओं को हटाने की आवश्यकता है जो अलग-अलग सेटों के सदस्य हैं जब तक कि वे एक ही सेट से संबंधित न हों। उस सीमा को न हटाएं जो दो कोशिकाओं को अलग करती है जो पहले से एक ही सेट से संबंधित हैं।

हम एक नियमित पंक्ति बनाकर और प्रत्येक सेल में एक निचला बॉर्डर जोड़कर शुरू करते हैं।

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ _1_ | _3_ | _3_ | _7_ _7_ | | _8_ _8_ | 

हम भूलभुलैया समाप्त करते हैं, विभिन्न सेटों से संबंधित कोशिकाओं के बीच की सीमाओं को नष्ट करते हैं और उन्हें एक में जोड़ते हैं।

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ (1_ | _3) | _3_ | _7_ _7_ | | _8_ _8_ | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | _ _ |  |  ___ ___ |  |
	 | _1_ _1_ _1_ | (1_ | _7) _7_ | _8_ _8_ | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ _1_ _1_ | _1_ _1_ (1_ | _8) _8_ | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ _1_ _1_ | _1_ _1_ _1_ _1_ _1_ | 

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