लेबिरिंथ: वर्गीकरण, पीढ़ी, समाधान की खोज

यह क्लासिक पोस्ट mazes के माध्यम से बनाने और जाने के सबसे लोकप्रिय तरीकों का विवरण देता है। लेख को चार भागों में विभाजित किया गया है: वर्गीकरण, पीढ़ी एल्गोरिदम, लेबिरिंथ को हल करने के लिए एल्गोरिदम और लेबिरिंथ के साथ अन्य संचालन।

भूलभुलैया वर्गीकरण

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

• 
  
  द्वि-आयामी : अधिकांश लेबिरिंथ, कागज और वास्तविक दोनों, इस आयाम हैं, अर्थात्, हम हमेशा भूलभुलैया को कागज की शीट पर प्रदर्शित कर सकते हैं और भूलभुलैया के किसी भी अन्य गलियारों को पार किए बिना इसके साथ आगे बढ़ सकते हैं।
• त्रि-आयामी : तीन-आयामी भूलभुलैया के कई स्तर हैं; इसमें (कम से कम ऑर्थोगोनल संस्करण में), चार कार्डिनल दिशाओं के अलावा, मार्ग नीचे और ऊपर जा सकते हैं। 3 डी भूलभुलैया को अक्सर ऊपर और नीचे सीढ़ियों के साथ 2 डी स्तरों की एक सरणी के रूप में कल्पना की जाती है।
• 
  
  उच्च आयाम : आप चार आयामी mazes और भी अधिक बहुआयामी बना सकते हैं। कभी-कभी उन्हें चौथे आयाम के माध्यम से "पोर्टल्स" के साथ 3 डी भूलभुलैया के रूप में कल्पना की जाती है, उदाहरण के लिए, "अतीत" और "भविष्य" के पोर्टल्स।
• 
  
  इंटरव्यूइंग : इंटरविविंग के साथ लेबिरिंथ - ये अनिवार्य रूप से दो आयामी (या 2.5-आयामी) लेबिरिंथ हैं, जिसमें, हालांकि, मार्ग एक दूसरे को ओवरलैप कर सकते हैं। प्रदर्शित करते समय, यह आमतौर पर काफी स्पष्ट होता है कि मृत छोर कहाँ हैं और एक मार्ग दूसरे से ऊपर कैसे है। वास्तविक दुनिया से लेबिरिंथ, जिसमें भूलभुलैया के एक हिस्से को दूसरे के साथ जोड़ने वाले पुल हैं, आंशिक रूप से इंटरलेसिंग हैं।

उच्च रक्तचाप: उच्च रक्तचाप के अनुसार वर्गीकरण एक भूलभुलैया के माध्यम से आगे बढ़ने वाली वस्तु के आयाम से मेल खाती है, न कि भूलभुलैया। निम्न प्रकार उपलब्ध हैं:

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

टोपोलॉजी: टोपोलॉजी वर्ग भूलभुलैया अंतरिक्ष की ज्यामिति का वर्णन करता है जिसमें यह एक पूरे के रूप में मौजूद है। निम्न प्रकार उपलब्ध हैं:

• 
  
  सामान्य : यह यूक्लिडियन अंतरिक्ष में मानक भूलभुलैया है।
• 
  
  प्लैनेयर : शब्द "प्लानर" किसी भी असामान्य टोपोलॉजी के साथ किसी भी भूलभुलैया का वर्णन करता है। आमतौर पर इसका मतलब है कि भूलभुलैया के किनारों को दिलचस्प तरीके से जोड़ा जाता है। उदाहरण: एक घन की सतह पर लेबिरिंथ, एक मोबियस स्ट्रिप की सतह पर लेबिरिंथ और एक टोरस पर उन लोगों के बराबर लेबिरिंथ, जहां बाएं और दाएं, ऊपरी और निचले पक्ष जोड़े में जुड़े हुए हैं।

टेसेलेशन: व्यक्तिगत कोशिकाओं की ज्यामिति का एक वर्गीकरण जो भूलभुलैया बनाता है। मौजूदा प्रकार:

• 
  
  ऑर्थोगोनल : यह एक मानक आयताकार ग्रिड है जिसमें कोशिकाओं को समकोण पर प्रतिच्छेद करने वाले मार्ग होते हैं। टेसेलेशन के संदर्भ में, उन्हें गामा लेबिरिंथ भी कहा जा सकता है।
• 
  
  डेल्टा : डेल्टा लेबिरिंथ से जुड़े त्रिकोण शामिल हैं, और प्रत्येक सेल में इससे जुड़े तीन मार्ग हो सकते हैं।
• 
  
  सिग्मा : सिग्मा लेबिरिंथ जुड़े हुए हेक्सागोन से बने होते हैं; प्रत्येक सेल में छह पास हो सकते हैं।
• 
  
  थीटा : थीटा लेबिरिंथ में मार्ग के संकेंद्रित वृत्त होते हैं, जिसमें शुरुआत या अंत केंद्र में होता है और दूसरा बाहरी किनारे पर। सेल में आमतौर पर चार संभावित कनेक्शन पथ होते हैं, लेकिन मार्ग के बाहरी रिंगों में कोशिकाओं की अधिक संख्या के कारण अधिक हो सकते हैं।
• 
  
  एप्सिलॉन : एप्सिलॉन लेबिरिंथ से जुड़े ऑक्टागोन या वर्ग होते हैं, उनमें से प्रत्येक कोशिका में आठ या चार पास हो सकते हैं।
• 
  
  ज़ेटा : ज़ेटा भूलभुलैया एक आयताकार ग्रिड पर स्थित है, केवल क्षैतिज और ऊर्ध्वाधर मार्ग के अलावा, विकर्ण मार्ग 45 डिग्री के कोण पर अनुमत हैं।
• 
  
  ओमेगा : ओमेगा शब्द का तात्पर्य निरंतर किसी भी गैर-ऑर्थोगोनल टेसेलेशन के साथ किसी भी भूलभुलैया से है। डेल्टा, सिग्मा, थीटा और ipsilon labyrinths इस प्रकार के हैं, कई अन्य योजनाओं की तरह, जिनके बारे में आप सोच सकते हैं, उदाहरण के लिए, एक भूलभुलैया जिसमें समकोण त्रिभुज के जोड़े होते हैं।
• 
  
  क्रैक : एक दरार भूलभुलैया निरंतर टेस्यूलेशन के बिना एक अनाकार भूलभुलैया है, जिसमें दीवारें और पैदल मार्ग यादृच्छिक कोणों पर स्थित हैं।
• 
  
  भग्न : एक भग्न भूलभुलैया एक भूलभुलैया है जो छोटे भूलभुलैया से बनी होती है। नेस्टेड कोशिकाओं से एक भिन्नात्मक भूलभुलैया प्रत्येक कोशिका में एक भूलभुलैया है जिसमें अन्य लेबिरिंथ रखे जाते हैं, और इस प्रक्रिया को कई बार दोहराया जा सकता है। एक असीम रूप से पुनरावर्ती भग्न भूलभुलैया एक सच्चा भग्न है जिसमें भूलभुलैया की सामग्री खुद को दोहराती है, एक अनिवार्य रूप से असीम रूप से बड़ी भूलभुलैया है।

रूटिंग: राउटिंग द्वारा वर्गीकरण संभवत : माज़ उत्पन्न करने में सबसे दिलचस्प पहलू है। से ऊपर वर्णित श्रेणियों में परिभाषित ज्यामिति के भीतर पास के प्रकार से जुड़ा हुआ है।

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

बनावट: बनावट वर्गीकरण विभिन्न मार्ग और ज्यामिति के साथ पास की शैली का वर्णन करता है। बनावट केवल ऐसे पैरामीटर नहीं हैं जिन्हें चालू या बंद किया जा सकता है। यहाँ चर के कुछ उदाहरण दिए गए हैं:

• 
  
  पूर्वाग्रह : विस्थापित मार्ग के साथ भूलभुलैया में, सीधे मार्ग दूसरों की तुलना में एक दिशा में अधिक जाते हैं। उदाहरण के लिए, उच्च क्षैतिज विस्थापन के साथ एक भूलभुलैया में, हमारे पास बाएं से दाएं लंबे मार्ग होंगे, और उन्हें जोड़ने वाले ऊपर से नीचे तक केवल छोटे मार्ग होंगे। इस तरह के चक्रव्यूह को "तंतुओं के पार" पारित करना अधिक कठिन होता है।
• 
  
  ओवरफ्लाइट : ओवरफ्लाइ मेट्रिक यह निर्धारित करता है कि मजबूर टर्न दिखने से पहले कितनी देर तक गलियारे लगेंगे। एक कम अवधि वाले भूलभुलैया में, तीन या चार कोशिकाओं की तुलना में लंबे समय तक कोई सीधा मार्ग नहीं होगा, और यह बहुत यादृच्छिक होगा। उच्च अवधि वाले एक भूलभुलैया में, भूलभुलैया में लंबे पास का एक बड़ा प्रतिशत होगा, जो इसे एक माइक्रोचिप की तरह दिखाई देगा।
• 
  
  अभिजात्यवाद: भूलभुलैया का " अभिजात्य " सूचक भूलभुलैया के आकार के सापेक्ष समाधान की लंबाई निर्धारित करता है। अभिजात वर्ग के लेबिरिंथ का आमतौर पर एक छोटा, प्रत्यक्ष समाधान होता है, जबकि गैर-अभिजात वर्ग के लेबिरिंथ में, समाधान भूलभुलैया के क्षेत्र के एक बड़े हिस्से पर गुजरता है। एक उच्च-गुणवत्ता वाले कुलीन भूलभुलैया एक गैर-कुलीन भूलभुलैया की तुलना में बहुत अधिक जटिल हो सकते हैं।
• 
  
  समरूपता : एक सममित भूलभुलैया में सममित मार्ग होते हैं, उदाहरण के लिए, केंद्र के सापेक्ष रोटेशन की समरूपता में, या क्षैतिज या ऊर्ध्वाधर अक्षों के साथ परिलक्षित होता है। भूलभुलैया आंशिक रूप से या पूरी तरह से सममित हो सकती है, और पैटर्न को किसी भी समय दोहरा सकती है।
• 
  
  समरूपता: एक समरूप एल्गोरिथ्म समान संभाव्यता के साथ सभी संभव mazes उत्पन्न करता है। एक भूलभुलैया को एक सजातीय बनावट कहा जा सकता है अगर यह एक सजातीय एल्गोरिथ्म द्वारा उत्पन्न एक विशिष्ट भूलभुलैया जैसा दिखता है। एक विषम एल्गोरिथ्म सैद्धांतिक रूप से किसी भी स्थान में सभी संभावित mazes उत्पन्न कर सकता है, लेकिन समान संभावना के साथ नहीं। विषमता आगे भी बढ़ सकती है - ऐसे लेबिरिंथ हो सकते हैं जो एल्गोरिथ्म कभी उत्पन्न नहीं करेगा।
• नदी का प्रवाह: "प्रवाह" विशेषता का अर्थ है कि एक भूलभुलैया बनाने के दौरान, एल्गोरिथ्म पड़ोसी की कोशिकाओं (या दीवारों) को चालू एक को देखेगा और साफ करेगा, अर्थात, यह प्रवाहित होगा (शब्द "तरलता") पानी की तरह अभी भी अप्रकाशित भागों में। कम प्रवाह दर के साथ एक आदर्श भूलभुलैया में, आमतौर पर कई छोटे मृत छोर होंगे, और अधिक "द्रव" भूलभुलैया में कम मृत छोर होंगे, लेकिन वे लंबे समय तक रहेंगे।

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

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

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

• 
  
  अभिविन्यास : कुछ मार्गों पर आप केवल एक दिशा में आगे बढ़ सकते हैं। एक प्रोग्रामिंग दृष्टिकोण से, इस तरह के एक भूलभुलैया को सभी प्रकारों का वर्णन करने वाले एक अप्रत्यक्ष ग्राफ के विपरीत, एक निर्देशित ग्राफ द्वारा वर्णित किया जाएगा।
• 
  
  विभाजन : भूलभुलैया में विभिन्न वर्गों के अनुरूप अलग-अलग भाग हो सकते हैं।
• 
  
  अनंत लंबाई की भूलभुलैया: हम एक असीम रूप से लंबी भूलभुलैया (स्तंभों की एक परिमित संख्या और पंक्तियों की कोई भी संख्या) बना सकते हैं, लेकिन साथ ही साथ मेमोरी में भूलभुलैया के केवल एक हिस्से को स्टोर करते हैं, एक छोर से दूसरे छोर तक "स्क्रॉलिंग" करते हैं और अगली लाइनें बनाते समय नष्ट कर देते हैं। एक उदाहरण हंट एंड किल एल्गोरिथम का संशोधित संस्करण है। व्यक्ति फ्रेम से बना एक लंबी फिल्म के रूप में एक संभावित अंतहीन भूलभुलैया की कल्पना कर सकता है। एक समय में केवल दो लगातार फ्रेम मेमोरी में जमा होते हैं। हंट एंड किल एल्गोरिथ्म चलाते हैं, हालांकि यह एक पूर्वाग्रह बनाता है जो शीर्ष फ्रेम के लिए प्रवण होता है, इसलिए यह पहले समाप्त होता है। पूरा होने के बाद, फ़्रेम की आवश्यकता नहीं है, आप इसे प्रिंट कर सकते हैं या इसके साथ कुछ और कर सकते हैं। जैसा कि हो सकता है, इसे त्यागें, आंशिक रूप से निर्मित निचले फ्रेम को एक नया ऊपरी फ्रेम बनाएं और नए निचले फ्रेम को साफ करें। प्रक्रिया को तब तक दोहराएं जब तक हम रुकने का फैसला नहीं करते, और तब तक रुकें जब तक कि हंट एंड किल दोनों फ्रेम पूरा नहीं कर लेता। केवल सीमा यह है कि भूलभुलैया में दो फ्रेम से अधिक की लंबाई के लिए प्रवेश द्वार की ओर जाने वाली पथ शाखा कभी नहीं होगी। एक अंतहीन भूलभुलैया बनाने का सबसे आसान तरीका है एलर एल्गोरिथ्म या सिडविंदर एल्गोरिथ्म, क्योंकि वे पहले से ही एक समय में एक पंक्ति में लेबिरिंथ बनाते हैं, इसलिए आप उन्हें केवल भूलभुलैया में लाइनें जोड़ सकते हैं।
• 
  
  आभासी भग्न लेबिरिंथ: वर्चुअल एक भूलभुलैया है जिसमें एक ही समय में पूरे भूलभुलैया को मेमोरी में संग्रहीत नहीं किया जाता है। उदाहरण के लिए, यह आपके स्थान के पास 100x100 मार्ग का केवल एक सिमुलेशन में स्टोर कर सकता है जहां आप एक बड़े भूलभुलैया से गुजरते हैं। नेस्टेड फ्रैक्टल लेबिरिंथ के विस्तार का उपयोग विशाल आभासी लेबिरिंथ बनाने के लिए किया जा सकता है, उदाहरण के लिए, एक बिलियन प्रति बिलियन पास। यदि हम एक बिलियन प्रति बिलियन पास (मार्ग के बीच छह फीट की दूरी के साथ) की भूलभुलैया की एक वास्तविक प्रतिलिपि बनाते हैं, तो यह पृथ्वी की सतह को 6,000 से अधिक बार भर देगा! केवल 9 स्तरों के साथ 10 ⁹ से 10 ⁹ पास की भूलभुलैया, या एक संलग्न भूलभुलैया पर विचार करें। यदि हम अपने चारों ओर कम से कम 100x100 हिस्सा रखना चाहते हैं, तो यह हमारे लिए सबसे कम स्तर पर 100x100 का उप भूलभुलैया बनाने और सात 10x10 लेबिरिंथ बनाने के लिए पर्याप्त है, जिसमें यह जानने के लिए एम्बेडेड है कि दीवारें 100x100 भाग में हैं। (वास्तव में, चार समीपस्थ भागों का आकार 100x100 होना बेहतर है, यदि आप भाग के किनारे या कोने के पास एक वर्ग बनाते हैं, लेकिन एक ही अवधारणा यहां लागू होती है।) यह सुनिश्चित करने के लिए कि भूलभुलैया के आसपास स्थिर और अपरिवर्तित है, हमारे पास एक सूत्र है। प्रत्येक घोंसले के स्तर पर समन्वय के लिए एक यादृच्छिक बीज संख्या को परिभाषित करना। वर्चुअल फ्रैक्टल लेबिरिंथ मंडेलब्रोट फ्रैक्टल के समान हैं, जिनमें से यह वास्तव में मौजूद है, और हमें काफी उच्च आवर्धन पर एक निश्चित समन्वय की यात्रा करने की आवश्यकता है। ताकि यह दिखाई दे।

भूलभुलैया एल्गोरिदम

यहाँ ऊपर वर्णित लेबिरिंथ के विभिन्न वर्गों को बनाने के लिए सामान्यीकृत एल्गोरिदम की एक सूची दी गई है:

• 
  
  आदर्श : एक आदर्श आदर्श भूलभुलैया बनाने के लिए यह आमतौर पर "बढ़ने" के लिए आवश्यक है, छोरों और पृथक क्षेत्रों की अनुपस्थिति सुनिश्चित करना। हम बाहरी दीवार से शुरू करते हैं और बेतरतीब ढंग से दीवार के एक टुकड़े को जोड़ते हैं जो इसे छूता है। हम भूलभुलैया के लिए दीवार खंडों को बेतरतीब ढंग से जोड़ना जारी रखते हैं, लेकिन सुनिश्चित करें कि प्रत्येक नया खंड मौजूदा दीवार के एक छोर से छूता है, और इसका दूसरा छोर भूलभुलैया के अभी भी गैर-निर्मित हिस्से में है। यदि आप एक दीवार खंड जोड़ते हैं, जिसके दोनों छोर बाकी भूलभुलैया से अलग हो जाते हैं, तो यह एक असंबद्ध दीवार बना देगा जिसके चारों ओर एक लूप होगा, और यदि आप एक खंड जोड़ते हैं, तो दोनों छोर जो भूलभुलैया को स्पर्श करते हैं, यह एक अगम्य क्षेत्र बना देगा। यह दीवारों को जोड़ने की एक विधि है; यह कट आउट्स को काटने के लगभग समान है, जिसमें मार्ग के हिस्सों को काट दिया जाता है ताकि केवल एक छोर मौजूदा पास को छू सके।
• 
  
  : , , . : (1) , (2) , , -«», (3) , , , (4) , , (3) , , .
• 
  
  : — , , , , . U- , , , , . . , : , , , . , . , .
• 
  
  : , . , , . - , , , , .
• 3D : , , , . - .
• 
  
  : , , . ( ): , , , . , . , ; , . , , .
• 
  
  Crack : Crack- , , . , , , «» . , , . , - . , , ; . , .
• 
  
  : «» , , . , - : (1) , . (2) , , , , , (.. ). (3) , , . , .
• 
  
  : — 3D-, -, , . 3D- , , . , , . , . , ( ), , , .
• 
  
  Planair : Planair- , . — . , .
• 
  
  : , , , -, , , , . , . , , , , , .

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

• 
  
  पुनरावर्ती बैकट्रैकर : - recursive backtracker, , . , , . , , . , . , . , , , . , . Recursive backtracking , , , .
• 
  
  : , . , «» , , . , , ( ). , . , , . , - , , . , , . , . , - (union-find algorithm): , . . , - .
• 
  
  प्राइम का एल्गोरिथ्म (सच) : यह एल्गोरिदम विशिष्ट रूप से बेतरतीब किनारे के वज़न को संसाधित करके न्यूनतम फैले हुए पेड़ बनाता है। आवश्यक मेमोरी की मात्रा भूलभुलैया के आकार के लिए आनुपातिक है। हम किसी भी शीर्ष से शुरू करते हैं (समाप्त भूलभुलैया समान होगी, ऊपर से कोई फर्क नहीं पड़ता जो हम शुरू करते हैं)। हम सबसे छोटे वजन के साथ मार्ग के किनारे का चयन करते हैं जो भूलभुलैया को उस बिंदु से जोड़ता है जो पहले से ही इसमें नहीं है, और फिर इसे भूलभुलैया में संलग्न करें। भूलभुलैया तब पूरी हो जाती है जब प्रश्न में किनारों को नहीं छोड़ा जाता है। अगले किनारे का कुशलता से चयन करने के लिए, आपको एक प्राथमिकता कतार (आमतौर पर एक ढेर का उपयोग करके लागू) की आवश्यकता होती है जो सीमा के सभी किनारों को संग्रहीत करती है। हालाँकि, यह एल्गोरिथ्म धीमा है क्योंकि ढेर से आइटम का चयन करने में लॉग (n) समय लगता है। इसलिए, क्रैस्कल एल्गोरिदम को पसंद करना बेहतर है, जो न्यूनतम फैले हुए पेड़ भी बनाता है, क्योंकि यह तेज है और एक समान संरचना के साथ लेबिरिंथ बनाता है। वास्तव में, एक ही यादृच्छिक बीज के साथ, प्राइमा और क्रैस्कल एल्गोरिदम एक ही लेबिरिंथ बना सकते हैं।
• 
  
  प्राइम का एल्गोरिथम (सरलीकृत) : इस प्राइम का एल्गोरिथ्म एक न्यूनतम फैले हुए पेड़ बनाता है। इस तरह से सरलीकृत किया जाता है कि किनारों के सभी वजन समान होते हैं। यह भूलभुलैया के आकार के लिए आनुपातिक क्षमता की आवश्यकता है। हम एक यादृच्छिक चोटी से शुरू करते हैं। हम बेतरतीब ढंग से भूलभुलैया से जोड़ने वाले मार्ग के किनारे का चयन करते हैं जो अभी तक इसमें नहीं है, और फिर इसे भूलभुलैया के साथ संलग्न करें। भूलभुलैया तब पूरी हो जाती है जब प्रश्न में किनारों को नहीं छोड़ा जाता है। चूंकि किनारों को भारहीन किया जाता है और आदेश नहीं दिया जाता है, उन्हें एक साधारण सूची के रूप में संग्रहीत किया जा सकता है, अर्थात, सूची से तत्वों का चयन बहुत तेज होगा और निरंतर समय लगता है। इसलिए, यह रैंडम एज वेट के साथ ट्रू प्राइम एल्गोरिथम की तुलना में बहुत तेज है। निर्मित भूलभुलैया बनावट में कम प्रवाह दर और सही प्राइम विधि की तुलना में सरल समाधान होगा, क्योंकि यह शुरुआती बिंदु से समान रूप से फैलता है, जैसे कि गिरा हुआ सिरप, और उच्च वजन के साथ पसलियों के टुकड़े को बायपास नहीं करता है, जिसे बाद में ध्यान में रखा जाता है।
• 
  
  प्राइम के एल्गोरिथ्म (संशोधित) : इस प्राइम के एल्गोरिथ्म एक न्यूनतम फैले हुए पेड़ बनाता है, संशोधित किया गया है ताकि किनारों के सभी वजन समान हों। हालांकि, इसे इस तरह से लागू किया जाता है कि किनारों के बजाय यह कोशिकाओं पर दिखता है। मेमोरी की मात्रा भूलभुलैया के आकार के लिए आनुपातिक है। निर्माण की प्रक्रिया में, प्रत्येक कोशिका के तीन प्रकार हो सकते हैं: (1) "आंतरिक": कोशिका भूलभुलैया का हिस्सा है और पहले से ही इसमें कटा हुआ है, (2) "सीमा": कोशिका भूलभुलैया का हिस्सा नहीं है और इसमें अभी तक कटौती नहीं हुई है, लेकिन यह स्थित है सेल के बगल में जो पहले से ही "आंतरिक" है, और (3) "बाहरी": सेल अभी तक भूलभुलैया का हिस्सा नहीं है, और इसके पड़ोसियों में से कोई भी "आंतरिक" सेल नहीं है। हम एक सेल चुनकर शुरू करते हैं, इसे "आंतरिक" बनाते हैं, और इसके सभी पड़ोसियों के लिए हम टाइप करते हैं "सीमा"। हम बेतरतीब ढंग से "सीमा" सेल का चयन करते हैं और उसमें पड़ोसी "आंतरिक" कोशिकाओं में से एक मार्ग को काटते हैं। हम इस "सीमा" सेल की स्थिति को "आंतरिक" में बदलते हैं और अपने सभी पड़ोसियों के प्रकार को "बाहरी" से "सीमा" में बदलते हैं। भूलभुलैया तब पूरी होती है जब कोई "सीमा" कोशिकाएं नहीं बची होती हैं (अर्थात, कोई "बाहरी" कोशिकाएं नहीं बची हैं, जिसका अर्थ है कि हर कोई "आंतरिक" बन गया है)। यह एल्गोरिथ्म बहुत कम उपज सूचकांक के साथ लेबिरिंथ बनाता है, जिसमें कई छोटे गतिरोध और सीधे समाधान हैं। परिणामी भूलभुलैया बहुत ही सरल प्राइमा एल्गोरिथ्म के परिणाम के समान है, एक मामूली अंतर के साथ: फैले हुए पेड़ में voids केवल तभी भरे जाते हैं जब एक सीमा सेल को यादृच्छिक रूप से चुना जाता है, जिससे एक कोशिका के माध्यम से भरने की ट्रिपल संभावना के विपरीत होता है। इसके अलावा, एल्गोरिदम सरलीकृत प्राइम एल्गोरिथ्म की तुलना में बहुत तेज है, क्योंकि यह किनारों की सूची को संकलित करने और संसाधित करने की आवश्यकता नहीं है।
• 
  
  एल्डस-ब्रोड एल्गोरिथ्म: इस एल्गोरिथ्म में जो दिलचस्प है वह यह है कि यह सजातीय है, अर्थात यह किसी दिए गए आकार के सभी संभावित लेबिरिंथों के बराबर संभावना के साथ बनाता है। इसके अलावा, इसे अतिरिक्त मेमोरी या स्टैक की आवश्यकता नहीं है। हम एक बिंदु का चयन करते हैं और अनियमित रूप से पड़ोसी सेल में जाते हैं। यदि हम एक अनटूट सेल में आ गए हैं, तो पिछले सेल से उसमें जाने वाले मार्ग को काट दें। हम तब तक पड़ोसी कोशिकाओं में जाते रहते हैं, जब तक कि हम सभी कोशिकाओं के मार्ग नहीं काट देते। यह एल्गोरिथ्म कम प्रवाह दर के साथ लेबिरिंथ बनाता है, केवल क्रैस्कल एल्गोरिदम से थोड़ा अधिक है। (इसका मतलब है कि किसी दिए गए विनिमय के लिए, उच्च उपज के साथ कम उपज सूचकांक के साथ अधिक लेबिरिंथ हैं, क्योंकि औसत संभावना वाला भूलभुलैया समान रूप से कम है।) इस एल्गोरिथ्म के बारे में बुरी बात यह है कि यह बहुत धीमा है क्योंकि यह बाद के लिए एक बौद्धिक खोज नहीं करता है। कोशिकाओं, अर्थात्, वास्तव में पूरा होने की गारंटी नहीं है। हालांकि, इसकी सादगी के कारण, यह जल्दी से कई कोशिकाओं के माध्यम से जा सकता है, इसलिए यह तेजी से पूरा होता है जितना आप सोच सकते हैं। औसतन, मानक एल्गोरिदम की तुलना में इसे पूरा करने में सात गुना अधिक समय लगता है, हालांकि बुरे मामलों में यह बहुत लंबा हो सकता है अगर यादृच्छिक संख्या जनरेटर लगातार पिछले कुछ कोशिकाओं से बचता है। इसे दीवारों को जोड़ने के रूप में लागू किया जा सकता है, अगर सीमा की दीवार को एक ही शीर्ष माना जाता है, अर्थात्, उदाहरण के लिए, यदि चाल हमें सीमा की दीवार पर ले जाती है, तो हम सीमा के साथ एक यादृच्छिक बिंदु पर टेलीपोर्ट करते हैं, और उसके बाद ही आगे बढ़ना जारी रखते हैं। दीवारों को जोड़ने के मामले में, यह लगभग दो बार तेजी से काम करता है, क्योंकि सीमा की दीवार के साथ टेलीपोर्टेशन भूलभुलैया के दूर के हिस्सों तक तेजी से पहुंचने की अनुमति देता है।
• 
  
  विल्सन का एल्गोरिथ्म : यह एल्डस-ब्रोड एल्गोरिथ्म का एक उन्नत संस्करण है, यह बिल्कुल उसी बनावट के साथ लेबिरिंथ बनाता है (एल्गोरिदम सजातीय हैं, अर्थात, सभी संभावित लेबिरिंथ समान संभावना के साथ उत्पन्न होते हैं), लेकिन विल्सन एल्गोरिथ्म बहुत तेज है। यह मेमोरी को भूलभुलैया के आकार तक ले जाता है। हम एक बेतरतीब ढंग से चयनित प्रारंभिक भूलभुलैया सेल के साथ शुरू करते हैं। हम एक यादृच्छिक सेल का चयन करते हैं जो अभी तक भूलभुलैया का हिस्सा नहीं है और जब तक हम पहले से ही भूलभुलैया से संबंधित सेल नहीं पाते हैं, तब तक एक यादृच्छिक चलना करते हैं। जैसे ही हम भूलभुलैया के पहले से ही निर्मित भाग पर ठोकर खाते हैं, हम चयनित यादृच्छिक सेल पर लौट आते हैं और इन कोशिकाओं को भूलभुलैया में जोड़कर किए गए पूरे रास्ते को काट देते हैं। अधिक विशेष रूप से, जब हम रास्ते पर लौटते हैं, तो हम प्रत्येक सेल को उस दिशा में काटते हैं, जिसमें पिछली बार जब हम सेल छोड़ते हैं, तो रैंडम वॉक होता था। यह वापसी पथ के साथ छोरों की उपस्थिति से बचा जाता है, ताकि एक लंबा मार्ग भूलभुलैया में शामिल हो जाए। जब सभी कोशिकाएं इससे जुड़ी होती हैं तो भूलभुलैया पूरी हो जाती है। अल्गोरिद-ब्रोडर के रूप में एल्गोरिथ्म में समान गति की समस्याएं हैं, क्योंकि प्रारंभिक सेल के लिए पहला यादृच्छिक पथ खोजने में बहुत समय लग सकता है, लेकिन कई रास्तों को रखने के बाद, बाकी भूलभुलैया बहुत जल्दी कट जाती है। औसतन, यह एल्डस-ब्रोडर की तुलना में पांच गुना तेज है, और सर्वश्रेष्ठ एल्गोरिदम की तुलना में दो गुना कम है। यह ध्यान देने योग्य है कि दीवारों को जोड़ने के मामले में, यह दो बार तेजी से काम करता है, क्योंकि पूरी सीमा की दीवार शुरू में भूलभुलैया का हिस्सा है, इसलिए पहली दीवारें बहुत तेजी से जुड़ती हैं।
• 
  
  हंट एंड किल एल्गोरिथ्म : यह एल्गोरिथ्म सुविधाजनक है क्योंकि इसमें अतिरिक्त मेमोरी या स्टैक की आवश्यकता नहीं होती है, और इसलिए मेमोरी से बाहर भागने की असंभवता के कारण कमजोर कंप्यूटर पर विशाल मेज़ या लेबिरिंथ बनाने के लिए उपयुक्त है। चूंकि इसके कोई नियम नहीं हैं जिन्हें लगातार पालन करने की आवश्यकता होती है, इसलिए इसे उपयोग करने वाले विभिन्न बनावटों के साथ लेबिरिंथ को संशोधित करना और बनाना भी सबसे आसान है। यह लगभग एक पुनरावर्ती बैकट्रैक्टर के समान है, केवल वर्तमान स्थिति के पास कोई सेल नहीं बनाया गया है। हम "शिकार" मोड में प्रवेश करते हैं और व्यवस्थित रूप से भूलभुलैया को स्कैन करते हैं जब तक कि हम पहले से ही काटे गए सेल के बगल में संयुक्त राष्ट्र निर्मित सेल नहीं पाते। इस स्तर पर, हम फिर से इस नए स्थान में कटौती करना शुरू करते हैं। जब "शिकार" मोड में सभी कोशिकाओं को स्कैन किया जाता है तो भूलभुलैया पूरी हो जाती है। यह एल्गोरिथ्म एक उच्च प्रवाह दर के साथ लेबिरिंथ बनाने के लिए जाता है, लेकिन पुनरावर्ती बैकट्रैक जितना ऊंचा नहीं है। आप इसे कम प्रवाह दर के साथ लेबिरिंथ उत्पन्न करने के लिए मजबूर कर सकते हैं, अधिक बार "शिकार" मोड में प्रवेश कर सकते हैं। यह समय बीतने के कारण धीमी गति से चलता है, आखिरी कोशिकाओं का शिकार होता है, लेकिन क्रैस्कल एल्गोरिथम की तुलना में यह बहुत धीमा नहीं है। इसे दीवारों को जोड़ने के सिद्धांत के अनुसार लागू किया जा सकता है, यदि आप कभी-कभी पुनरावर्ती बैकट्रैक्टर में निहित समस्याओं से बचने के लिए यादृच्छिक रूप से टेलीपोर्ट करते हैं।
• 
  
  बढ़ते एल्गोरिथम
  ट्री (ग्रोइंग ट्री एल्गोरिथम) : यह एक सामान्यीकृत एल्गोरिथम है जो विभिन्न बनावट के साथ लेबिरिंथ बना सकता है। आवश्यक मेमोरी भूलभुलैया के आकार तक पहुंच सकती है। हर बार जब एक सेल काटा जाता है, तो हम इसे सूची में जोड़ते हैं। सूची से एक सेल का चयन करें और इसके बगल में संयुक्त राष्ट्र निर्मित सेल के लिए मार्ग काट दें। यदि वर्तमान के पास कोई संयुक्त राष्ट्र निर्मित सेल नहीं हैं, तो सूची से वर्तमान सेल को हटा दें। सूची में और कुछ नहीं होने पर भूलभुलैया पूरी हो जाती है। एल्गोरिथ्म के बारे में दिलचस्प बात यह है कि, आप सूची से सेल का चयन कैसे करते हैं, इसके आधार पर, आप कई अलग-अलग बनावट बना सकते हैं। उदाहरण के लिए, यदि आप हमेशा अंतिम जोड़े गए सेल का चयन करते हैं, तो यह एल्गोरिथ्म एक पुनरावर्ती बैकट्रैक में बदल जाता है। यदि आप हमेशा बेतरतीब ढंग से कोशिकाओं का चयन करते हैं, तो यह समान व्यवहार करता है, लेकिन प्राइम एल्गोरिथम के लिए नहीं। यदि आप हमेशा सूची में जोड़ी गई सबसे पुरानी कोशिकाओं का चयन करते हैं, तो हम सबसे संभावित उपज सूचकांक के साथ एक भूलभुलैया बनायेंगे, जो कि प्राइम एल्गोरिथ्म से भी कम है। यदि आप आमतौर पर बहुत अंतिम सेल चुनते हैं, लेकिन कभी-कभी एक यादृच्छिक सेल चुनते हैं, तो भूलभुलैया में एक उच्च प्रवाह दर होगी, लेकिन एक छोटा और प्रत्यक्ष समाधान। यदि सबसे हाल की कोशिकाओं में से एक को यादृच्छिक रूप से चुना गया है, तो भूलभुलैया में प्रवाह की दर कम होगी, लेकिन एक लंबा और घुमावदार समाधान।
• 
  
  बढ़ते वन एल्गोरिथ्म : यह पेड़ों और सेटों के आधार पर एक अधिक सामान्यीकृत एल्गोरिथ्म है। यह पेड़ के बढ़ते एल्गोरिथम का विस्तार है, जिसमें अनिवार्य रूप से एक साथ विस्तार करने वाले कई उदाहरण शामिल हैं। हम सभी कोशिकाओं के साथ शुरू करते हैं जो "नई" की सूची में क्रमिक रूप से क्रमबद्ध होते हैं; इसके अलावा, प्रत्येक सेल का अपना सेट होता है, जैसा कि क्रुक्ल एल्गोरिथम की शुरुआत में। सबसे पहले, "नए" की सूची से "सक्रिय" की सूची में ले जाकर एक या अधिक कोशिकाओं का चयन करें। "सक्रिय" सूची से एक सेल का चयन करें और "नई" सूची से अगले संयुक्त राष्ट्र निर्मित सेल के लिए मार्ग को काट दें, "सक्रिय" की सूची में एक नया सेल जोड़कर और दो कोशिकाओं के सेट को मिलाएं। यदि भूलभुलैया के मौजूदा हिस्से में कटौती करने का प्रयास किया जाता है, तो इसे सक्षम करें यदि कोशिकाएं अलग-अलग सेट में हैं और कोशिकाओं को जोड़ती हैं, जैसा कि क्रैस्कल एल्गोरिथम में किया गया है। यदि वर्तमान सेल के पास कोई "नई" कोशिकाएं नहीं हैं, तो वर्तमान सेल को "समाप्त" लोगों की सूची में ले जाएं। "सक्रिय" की सूची खाली हो जाने पर भूलभुलैया पूरी हो जाती है। अंत में, हम सभी शेष सेटों को जोड़ते हैं, जैसा कि क्रुस्क्ल एल्गोरिथम में है। समय-समय पर, आप "सक्रिय" की सूची में "नए" की सूची से एक या अधिक कोशिकाओं को स्थानांतरित करके नए पेड़ बना सकते हैं, जैसा कि शुरुआत में किया गया था। मूल पेड़ों की संख्या और नव निर्मित पेड़ों के शेयरों को नियंत्रित करके, आप कई अद्वितीय बनावट उत्पन्न कर सकते हैं जो पेड़ के बढ़ते एल्गोरिदम के पहले से ही लचीले मापदंडों के साथ संयोजन करते हैं।
• 
  
  एलर का एल्गोरिथ्म : यह एक विशेष एल्गोरिथ्म है, क्योंकि यह न केवल हर किसी की तुलना में तेज़ है, बल्कि इसमें कोई स्पष्ट पूर्वाग्रह या कमियां भी नहीं हैं; इसके अलावा, जब इसे बनाया जाता है, तो मेमोरी का उपयोग सबसे कुशलता से किया जाता है। इसकी आवश्यकता भी नहीं है कि संपूर्ण भूलभुलैया मेमोरी में है, यह लाइन के आकार के लिए आनुपातिक मात्रा का उपयोग करता है। यह लाइन द्वारा एक भूलभुलैया रेखा बनाता है, स्ट्रिंग की पीढ़ी पूरी होने के बाद, एल्गोरिथ्म अब इसे ध्यान में नहीं रखता है। एक पंक्ति में प्रत्येक सेल एक सेट में निहित है; दो कोशिकाएँ एक ही सेट से संबंधित होती हैं यदि उनके बीच पहले से निर्मित भूलभुलैया के बीच एक रास्ता है। यह जानकारी आपको लूप या अलग-थलग क्षेत्रों को बनाए बिना वर्तमान लाइन में मार्ग काटने की अनुमति देती है। वास्तव में, यह क्रैस्कल एल्गोरिदम से काफी मिलता-जुलता है, केवल यहां एक समय में एक लाइन बनाई जाती है, जबकि क्रैस्कल पूरे भूलभुलैया के माध्यम से दिखता है। एक पंक्ति बनाने में दो भाग होते हैं: पंक्ति के भीतर आसन्न कोशिकाओं को बेतरतीब ढंग से कनेक्ट करें, अर्थात। हम क्षैतिज मार्ग काट देते हैं, फिर कोशिकाओं को वर्तमान और अगली पंक्ति के बीच में जोड़ते हैं, अर्थात। ऊर्ध्वाधर मार्ग काट दिया। क्षैतिज मार्गों को काटते समय, हम उन कोशिकाओं को नहीं जोड़ते हैं जो पहले से ही एक ही सेट में हैं (क्योंकि एक लूप अन्यथा बनाया जाएगा), और ऊर्ध्वाधर मार्ग काटते समय हमें एक सेल कनेक्ट करना होगा यदि इसका एक इकाई आकार है (क्योंकि यदि आप इसे छोड़ देते हैं, तो यह एक अलग क्षेत्र बना देगा)। क्षैतिज मार्ग काटते समय, यदि हम एक ही सेट में होते हैं, तो हम कोशिकाओं को जोड़ते हैं (क्योंकि अब उनके बीच एक रास्ता है), और जब हम सेल से नहीं जुड़ते हैं तो ऊर्ध्वाधर मार्ग काटते हैं, हम इसे एक अलग सेट में डालते हैं (क्योंकि अब इसे बाकी भूलभुलैया से अलग कर दिया जाता है। )। निर्माण इस तथ्य से शुरू होता है कि पहली पंक्ति में कोशिकाओं को जोड़ने से पहले, प्रत्येक कोशिका का अपना सेट होता है। कोशिकाओं को अंतिम पंक्ति में जुड़ा होने के बाद निर्माण पूरा हो गया है। पूरा करने का एक विशेष नियम है: पूरा होने के समय तक, प्रत्येक सेल को अलग-अलग क्षेत्रों से बचने के लिए एक ही सेट में होना चाहिए। (आखिरी पंक्ति पड़ोसी कोशिकाओं के प्रत्येक जोड़े के संयोजन द्वारा बनाई गई है जो अभी तक एक ही सेट में नहीं हैं।) कोशिकाओं के चक्रीय दोगुनी लिंक वाली सूची का उपयोग करके सेट को लागू करना सबसे अच्छा है (जो सिर्फ एक सरणी हो सकता है जो एक ही सेट के दोनों तरफ कोशिकाओं के जोड़े को कोशिकाओं को बांधता है)। निरंतर समय के लिए एक सेट में पड़ोसी कोशिकाओं की उपस्थिति का सम्मिलन, विलोपन और सत्यापन करें। इस एल्गोरिथ्म के साथ समस्या भूलभुलैया के विभिन्न किनारों के प्रसंस्करण में असंतुलन है; बनावट में दाग से बचने के लिए, आपको कनेक्टिंग कोशिकाओं को सही अनुपात में कनेक्ट और छोड़ना होगा।
• 
  
  पुनरावर्ती विभाजन: यह एल्गोरिथ्म कुछ हद तक पुनरावर्ती बैकट्रैकिंग के समान है, क्योंकि वे दोनों ढेर का उपयोग करते हैं, केवल यह गलियारे के साथ नहीं, बल्कि दीवारों के साथ काम करता है। हम एक यादृच्छिक क्षैतिज या ऊर्ध्वाधर दीवार बनाकर शुरू करते हैं जो एक यादृच्छिक क्षेत्र को एक यादृच्छिक पंक्ति या स्तंभ में अंतरित करती है, और यादृच्छिक रूप से रिक्त स्थानों को अपने साथ रखती है। फिर हम विभाजित दीवार द्वारा उत्पन्न दो उप-भागों के लिए प्रक्रिया को पुन: दोहराते हैं। सर्वोत्तम परिणामों के लिए, आपको क्षेत्र के अनुपात के आधार पर क्षैतिज या ऊर्ध्वाधर की पसंद में एक विचलन जोड़ने की आवश्यकता है, उदाहरण के लिए, एक क्षेत्र जिसकी चौड़ाई दो बार है ऊंचाई को अधिक बार ऊर्ध्वाधर दीवारों से विभाजित किया जाना चाहिए। यह दिशाओं में विचलन के बिना सबसे तेज एल्गोरिथ्म है, और अक्सर यह बाइनरी पेड़ों पर आधारित मेज़ों के साथ प्रतिस्पर्धा भी कर सकता है, क्योंकि यह एक ही समय में कई सेल बनाता है, हालांकि इसमें भूलभुलैया के इंटीरियर को पार करने वाली लंबी दीवारों के रूप में एक स्पष्ट खामी है। यह एल्गोरिथ्म एक प्रकार का एम्बेडेड फ्रैब्रल लेबिरिंथ है, लेकिन प्रत्येक सेल के अंदर एक ही आकार के लेबिरिंथ के साथ एक निश्चित आकार की कोशिकाओं के लगातार लेबिरिंथ बनाने के बजाय, यह किसी दिए गए क्षेत्र को यादृच्छिक आकार: 1x2 या 2x1 के भूलभुलैया में विभाजित करता है। रिकर्सिव डिवीजन का उपयोग पासआउट्स को काटने के लिए नहीं किया जा सकता है, क्योंकि इससे एक स्पष्ट समाधान का निर्माण होता है जो या तो बाहरी किनारे पर चलता है, या अन्यथा सीधे अंदर को काटता है।
• 
  
  बाइनरी पेड़ों पर आधारित लेबिरिंथ : वास्तव में, ये सबसे सरल और सबसे तेज़ संभव एल्गोरिदम हैं, हालांकि, निर्मित लेबिरिंथ में बहुत उच्च पूर्वाग्रह के साथ एक बनावट है। प्रत्येक सेल के लिए, हम या तो ऊपर या बाईं ओर एक मार्ग काटते हैं, लेकिन दोनों दिशाओं में कभी नहीं। दीवारों के अतिरिक्त के साथ संस्करण में, प्रत्येक शीर्ष के लिए एक दीवार खंड जोड़ा जाता है जो नीचे या दाईं ओर जाता है, लेकिन दोनों दिशाओं में नहीं। प्रत्येक कोशिका अन्य सभी कोशिकाओं से स्वतंत्र है, क्योंकि हमें इसे बनाते समय कुछ अन्य कोशिकाओं की स्थिति की जांच करने की आवश्यकता नहीं है। इसलिए, यह स्मृति के बिना लेबिरिंथ उत्पन्न करने के लिए एक वास्तविक एल्गोरिदम है, जो निर्मित लेबिरिंथ के आकार द्वारा सीमित नहीं है। वास्तव में, यह एक द्विआधारी पेड़ है, अगर हम ऊपरी बाएं कोने को एक जड़ मानते हैं, और प्रत्येक नोड या सेल में एक अद्वितीय मूल नोड है, जो ऊपर या इसके बाईं ओर एक सेल है। बाइनरी पेड़ों पर आधारित लेबिरिंथ मानक आदर्श लेबिरिंथ से अलग हैं, क्योंकि सेल प्रकार के आधे से अधिक प्रकार उनमें मौजूद नहीं हो सकते हैं। उदाहरण के लिए, उनमें कभी भी चौराहे नहीं होंगे, और सभी मृत छोरों के ऊपर या बाईं ओर मार्ग होते हैं, और कभी भी नीचे या दाईं ओर नहीं जाते हैं। लेबिरिंथ के पास ऊपरी बाएं से निचले दाएं तिरछे मार्ग से जाने वाले मार्ग होते हैं, और निचले दाएं से ऊपरी बाएं से स्थानांतरित करना बहुत आसान है। आप हमेशा ऊपर या बाईं ओर जा सकते हैं, लेकिन दोनों दिशाओं में एक साथ कभी नहीं, इसलिए आप बाधाओं का सामना किए बिना, हमेशा निर्धारित रूप से तिरछे और बाईं ओर जा सकते हैं। आपके पास नीचे और दाईं ओर जाकर मृत सिरों को चुनने और गिरने का अवसर होगा। , , , .
• 
  
  Sidewinder: , . : , , . , , , , , . , ( , ). , sidewinder . , sidewinder . , sidewinder , , . sidewinder , « ». , sidewinder — , , , , . sidewinder , , , .

	%			?	?			%
	0					N^2	379	100.0
Recursive Backtracker	10					N^2	27	19.0
Hunt and Kill	11 (21)					0	100 (143)	9.5 (3.9)
	23					N*	10	7.2
	25					0*	10	2.0
Sidewinder	27					0*	12	2.6
	28					N*	20	4.2 (3.2)
	29					N^2	48 (25)	4.5
-	29					0	279 (208)	4.5
	30					N^2	33	4.1
()	30					N^2	160	4.1
()	32					N^2	59	2.3
()	36 (31)					N^2	30	2.3
	49 (39)					N^2	48	11.0
	49 (39)					N^2	76	11.0

यह तालिका ऊपर वर्णित आदर्श लेबिरिंथ बनाने के लिए एल्गोरिदम की विशेषताओं को सारांशित करती है। तुलना के लिए, एक एकल-मार्ग भूलभुलैया एल्गोरिथ्म जोड़ा गया है (सैद्धांतिक रूप से, एकल-मार्ग भूलभुलैया आदर्श हैं)। कॉलम स्पष्टीकरण:

• : , , , 2D-. . , , , . 10% ( ) 49% ( ). Recursive Backtracker 1%. 66%: .
• : : , , . , , , , . , , .
• : , . . , , . Recursive Backtracker , , , . , , . , Hunt and Kill , , .
• : , . , . Sidewinder , . , . Hunt and Kill , , , .
• : . «» , . «» , , . «» , , . , .
• : , . , , (N), (N^2). , ( ). , , . Sidewinder , . , .
• : , , , . , ( 10), . 100x100 Daedalus. , , , .
• : , , . , 100x100 . . «» . , . , . , , , .

माज़ को हल करने के कई तरीके हैं, और उनमें से प्रत्येक की अपनी विशेषताएं हैं। यहाँ विशिष्ट एल्गोरिदम की एक सूची दी गई है:

• 
  
  दीवारों के साथ (दीवार अनुयायी) : . («»), . ( ). , ( ) . , . , , . , , , . 3D- , 3D- 2D-, .. , -, -, .
• 
  
  : , «» , . 2D- , , .. . , , . . , , . , , . , , . , , — -1, — 1. , , .. 360 , «». , «», , , , , . , , . , — , .
• 
  
  : (Chain algorithm) , ( ) . , , . , . , , . , . ( ) , . . , , . «» , . , , , . , . , .
• 
  
  Recursive backtracker: , . , . : ( ), «», , , «», , . , , «»; «» . (backtracking) , , . , . , , .
• 
  
  (Trémaux's algorithm): . recursive backtracker : , . , . , , . , , , . ( , .) , (.. ), , , , (.. , ). , , , , , . , . , , .
• 
  
  (Dead end filler) : . , . , , . , . , , . , , .
• 
  
  Cul-de-sac filler : , , . dead end filler, , . ( — , , ) , . dead end filler. , , , , . , , , dead end filler.
• 
  
  Blind alley filler : , , . , . — , , . , , cul-de-sac filler, . . , , , , . , , , ( ). , , . , cul-de-sac filler - , collision solver , - .
• 
  
  Blind alley sealer : blind alley filler , , . . . , , blind alley filler, . . , , , , . , , . , . , , . , , .
• 
  
  (Shortest path finder): , , . , , . collision solver, , , «» , ( ), «» , , . «», , . , - , . , , , A* , .
• 
  
  (Shortest paths finder) : , . , , , , , , , - , . , , , «» , , , . , , , , . , .
• Collision solver: "amoeba" solver. . , . «» , ( ). « » ( ), , . «», , , , . ( , «», . , , , .) , shortest paths finder, ( ) ( ).
• Random mouse: , , .. , . 180 , . , , . , , .

		?		?	?	?	?
Random Mouse	1			/
Wall Follower	1			/
	1			/
	1		+
Recursive Backtracker	1
ट्रेमो एलगोरिदम	1	हां	तुम हो	अंदर / पर	नहीं	नहीं	हां
मृत अंत भराव	सभी +	नहीं	भूलभुलैया	ऊपर	नहीं	हां	हां
कुल-डे-थैली भराव	सभी +	नहीं	भूलभुलैया	ऊपर	नहीं	हां	हां
अंधा गली मुहर	सभी +	हां	भूलभुलैया	नहीं	नहीं	नहीं	हां
अंधा गली भराव	सब	हां	भूलभुलैया	ऊपर	नहीं	हां	नहीं
टकराव सॉल्वर	सब से छोटा	हां	आप +	नहीं	नहीं	नहीं	हां
सबसे छोटे रास्तों की खोज करें	सब से छोटा	हां	आप +	नहीं	हां	नहीं	हां
सबसे छोटा रास्ता खोजें	1 सबसे छोटा	हां	आप +	नहीं	हां	नहीं	हां

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

• समाधान: एल्गोरिथम और एल्गोरिथ्म की क्रियाओं के समाधानों का वर्णन करता है, अगर कई हैं। एल्गोरिथ्म एक समाधान चुन सकता है या कई छोड़ सकता है। इसके अतिरिक्त, समाधान कोई भी पथ या सबसे छोटा रास्ता हो सकता है। डेड एंड फिलर और पुल-डे-सैल फिलर (साथ ही इसके अनुपयोगी क्षेत्रों को संसाधित करते समय अंधा गली सीलर) सभी समाधान छोड़ते हैं, हालांकि, वे ऐसे मार्ग भी छोड़ सकते हैं जो किसी भी समाधान पथ में नहीं हैं, इसलिए मैंने उन्हें "ऑल +" चिह्नित किया। "।
• वारंटी: क्या एल्गोरिथ्म कम से कम एक समाधान खोजने की गारंटी है? यादृच्छिक माउस के लिए, "नहीं" इंगित किया गया है, क्योंकि इसके पूरा होने की गारंटी नहीं है, और दीवार अनुयायी और कॉलेज के एल्गोरिथ्म के लिए, "नहीं" इंगित किया गया है, क्योंकि वे एक समाधान खोजने में सक्षम नहीं होंगे यदि लक्ष्य द्वीप के अंदर है। "डेड" को डेड एंड फिलर और पुल-डे-सैक फिलर के लिए इंगित किया जाता है, क्योंकि विकर मेज़ में उन्हें समाधान नहीं मिल सकता है।
• प्राथमिकता: भूलभुलैया को सुलझाने के लिए दो प्रकार के एल्गोरिदम हैं: "आप" (भूलभुलैया में स्थित) को प्राथमिकता देना या भूलभुलैया को प्राथमिकता देना। यदि प्राथमिकता आपको दी गई है, तो हमारे पास एक बिंदु है ("आप" तालिका में इंगित किया गया है) या कई बिंदु ("आप +") और एल्गोरिथ्म उन्हें भूलभुलैया के शुरू से अंत तक खींचने की कोशिश करता है। यदि भूलभुलैया को प्राथमिकता दी जाती है, तो हम भूलभुलैया की पूरी जांच करते हैं और बेकार मार्ग को छोड़ देते हैं।
• आदमी के लिए उपलब्ध: आदमी भूलभुलैया को हल करने के लिए एल्गोरिथ्म का उपयोग कर सकता है, या तो असली भूलभुलैया में या ऊपर से नक्शा देख रहा है। "आप" को प्राथमिकता देने वाले कुछ एल्गोरिदम को भूलभुलैया (या इसके ऊपर) के अंदर एक व्यक्ति के रूप में लागू किया जा सकता है, और कुछ जो भूलभुलैया को प्राथमिकता देते हैं, उन्हें एक व्यक्ति के रूप में लागू किया जा सकता है, लेकिन केवल भूलभुलैया के ऊपर। अन्य एल्गोरिदम बहुत जटिल हैं और उनका विश्वसनीय कार्यान्वयन केवल एक कंप्यूटर में संभव है।
• स्वतंत्र पास: एल्गोरिथ्म कहीं भी निष्पादित कर सकता है। कुछ एल्गोरिदम के लिए आवश्यक है कि लेबिरिंथ के पास स्पष्ट मार्ग हों या ग्राफ़ की शब्दावली में बोलना हो, व्यक्तिगत कोने के बीच स्पष्ट किनारों या कंप्यूटर पर लागू होने पर एक पिक्सेल का मार्ग। दीवार अनुयायी, प्रतिज्ञा एल्गोरिथ्म, और सर्किट एल्गोरिथ्म को केवल आपके एक तरफ दीवार की आवश्यकता होती है। पुनरावर्ती बैकट्रैक्टर और सबसे छोटा पथ (रों) खोजक खुले स्थानों के माध्यम से अपना मार्ग बनाते हैं।
• कोई मेमोरी की आवश्यकता नहीं: क्या एल्गोरिथ्म को लागू करने के लिए आपको अतिरिक्त मेमोरी या स्टैक की आवश्यकता है। प्रभावी एल्गोरिदम को केवल भूलभुलैया के बिटमैप की आवश्यकता होती है और उन्हें हल करने की प्रक्रिया में भूलभुलैया में मार्कर को जोड़ने की आवश्यकता नहीं होती है।
• उपवास: क्या निर्णय प्रक्रिया को तेज माना जाता है। सबसे कुशल एल्गोरिदम भूलभुलैया के प्रत्येक सेल को केवल एक बार देखने के लिए पर्याप्त हैं, या वे इसके कुछ हिस्सों को पूरी तरह से छोड़ सकते हैं। रनटाइम भूलभुलैया के आकार के लिए आनुपातिक होना चाहिए, या ओ (एन ^ 2), जहां एन पक्ष के साथ कोशिकाओं की संख्या है। रैंडम माउस धीमा है क्योंकि इसके पूरा होने की गारंटी नहीं है, और अंधा गली भराव संभावित रूप से प्रत्येक कांटा से भूलभुलैया को हल करता है।

लेबिरिंथ के साथ अन्य ऑपरेशन

Mazes बनाने और हल करने के अलावा, आप उनके साथ अन्य कार्य कर सकते हैं:

• 
  
  भरें: यह एक "त्वरित और गंदा" है, लेकिन फिर भी उपयोगी फ़ंक्शन जिसे फिल या फ्लडफ़िल ग्राफिक लाइब्रेरी प्रक्रिया के लिए एक कॉल के साथ लागू किया जा सकता है। हम शुरुआत में फ़्लडफ़िल का प्रदर्शन करते हैं, और यदि अंत में बाढ़ नहीं हुई है, तो भूलभुलैया का कोई समाधान नहीं है। लेबिरिंथ में, प्रवेश और निकास जो किनारों पर हैं, हम एक दीवार के फ्लडफ़िल का प्रदर्शन करते हैं, और शेष किनारों के समाधान को चिह्नित करते हैं। मेज़ों में जहां शुरुआत और अंत अंदर होते हैं, हम बाउंडिंग वॉल के फ्लडफ़िल को निष्पादित करते हैं, और यदि निकास दीवार को हटाया नहीं गया है, तो इस भूलभुलैया को दीवारों के साथ पालन करके हल नहीं किया जा सकता है। भूलभुलैया और अन्य कार्यों को बनाने के कई तरीके कुछ बिंदुओं पर भूलभुलैया के "भरने" का उपयोग करते हैं।
• 
  
  अलगाव पदच्युत: भूलभुलैया को बदलें ताकि इसमें ऐसे अंश न हों जो शेष चक्रव्यूह से नहीं निकल सकते। इस तरह के हिस्सों को बाकी भूलभुलैया के साथ जोड़ने वाली दीवारों को हटाकर इसे बाहर किया जाता है। हम भूलभुलैया की एक प्रति के साथ शुरू करते हैं, फिर शुरुआत के पास मार्ग को भरें। हम भूलभुलैया को स्कैन करते हैं (अधिमानतः यादृच्छिक क्रम में, लेकिन सभी संभावित कोशिकाओं की यात्रा के साथ) भरे हुए सेल से सटे गैर-भरे हुए कोशिकाओं की उपस्थिति के लिए। हम मूल भूलभुलैया में इस बिंदु पर दीवार खंड को हटाते हैं, इस नए बिंदु पर भूलभुलैया भरते हैं और तब तक दोहराते हैं जब तक कि सभी भाग भरे नहीं जाते। इस फ़ंक्शन का उपयोग बुने हुए और पैटर्न वाले लेबिरिंथ बनाने के लिए किया जाता है।
• 
  
  लूप हटाने: भूलभुलैया को बदल दें ताकि कोई लूप न हो और दीवारें इसमें किसी भी चीज से न जुड़ी हों, और भूलभुलैया के प्रत्येक हिस्से को किसी भी बिंदु से केवल एक ही रास्ते से पहुँचा जा सकता है। इस फ़ंक्शन का कार्यान्वयन लगभग अलग-थलग क्षेत्रों को हटाने के समान है, केवल हम दीवारों को मार्ग के रूप में, और इसके विपरीत समझते हैं। हम भूलभुलैया की एक प्रति से शुरू करते हैं, फिर बाहरी दीवारों को भरते हैं। हम भूलभुलैया को स्कैन करते हैं (अधिमानतः यादृच्छिक क्रम में, लेकिन सभी संभव दीवार में सबसे ऊपर की यात्रा के साथ) भरे हुए लोगों के बगल में गैर-भरी हुई दीवारों की उपस्थिति के लिए। इस स्तर पर दीवारों के दो हिस्सों को मूल भूलभुलैया से जोड़ने वाले एक दीवार खंड को जोड़ें, इस नए बिंदु पर भूलभुलैया भरें और सभी भागों के भरने तक दोहराएं। इस फ़ंक्शन का उपयोग टेम्प्लेट माज़ बनाने के लिए किया जाता है और विकर मेज़ को आदर्श लोगों में परिवर्तित करने के लिए उपयोग किया जा सकता है, जो फिर भी मूल लोगों के समान रहते हैं।
• 
  
  अड़चनों के लिए खोजें : मार्ग या चौराहे बिंदुओं के चक्रव्यूह में खोजें जिसके माध्यम से इस भूलभुलैया के सभी समाधान पास होते हैं। ऐसा करने के लिए, बाएं हाथ की विधि के साथ दीवारों का अनुसरण करना शुरू करें बाएं समाधान प्राप्त करने के लिए, और सही समाधान प्राप्त करने के लिए दाहिने हाथ की विधि के साथ दीवारों के साथ पालन करना शुरू करें। वे स्थान जहां दो समाधान आम हैं, वे अड़चनें हैं। हालांकि, यह तकनीक केवल लेबिरिंथ के लिए काम करती है, जिसे दीवारों के साथ पालन करके सफलतापूर्वक हल किया जा सकता है। अन्य लेबिरिंथ में, अड़चनों को खोजने के लिए, आपको किसी भी समाधान को खोजने की आवश्यकता है, साथ ही साथ अंधा गली मुहर चलाने के लिए (यह भूलभुलैया को अयोग्य बना सकता है यदि यह भूलभुलैया के अंदर प्रवेश या निकास को एक बड़ा मृत अंत मानता है)। बंद मार्ग से गुजरने वाले समाधान पथ के कुछ हिस्सों में अड़चनें हैं।

एल्गोरिदम कार्यान्वयन

• डेडलस : ऊपर वर्णित mazes बनाने और हल करने के लिए सभी एल्गोरिदम, डेडलस में कार्यान्वित किए जाते हैं, एक मुफ्त और विंडोज प्रोग्राम डाउनलोड करने के लिए उपलब्ध है। Daedalus के साथ पूरा एक पूर्ण स्रोत कोड है।