मैं एक भूलभुलैया पीढ़ी एल्गोरिदम की तलाश में हूं जो किसी भी मृत सिरे के साथ मैज उत्पन्न कर सकता है लेकिन केवल एक शुरुआत और अंत है।कोई मृत अंत के साथ भूलभुलैया पीढ़ी के लिए एल्गोरिदम?
http://www.astrolog.org/labyrnth/maze/unicursl.gif
मैं कहां मिल या इस तरह के एक उलझन पीढ़ी एल्गोरिथ्म निर्माण के बारे में जाते हो से छवि: इस तरह?
ऐसा लगता है कि आप एक छद्म यादृच्छिक अंतरिक्ष पूरक वक्र (उदाहरण के लिए, Context-based Space Filling Curves -EUROGRAPHICS ’2000 (पीडीएफ प्रारूप, 1.1 एमबी) देखें)
एक एक Space-filling curve नजर डालें।
मुझे संदेह है कि आप इनमें से किसी एक के निर्माण के लिए कुछ यादृच्छिकता लागू कर सकते हैं जो आप चाहते हैं।
अंतरिक्ष भरने वाले वक्र शांत हैं, लेकिन उस पेपर के उन लोगों के पास मृत सिरों हैं, और मुझे यकीन नहीं है कि आप उनसे कैसे छुटकारा पा सकते हैं। –
@j_random_hacker: मुझे लगता है कि विचार यह है कि अंतरिक्ष-भरने घटता में "दीवारें" एक लंबी रेखा है; इसलिए यदि आप काले और गोरे को उलट देते हैं तो आपके पास एक मृत अंतराल के साथ एक समाधान भूलभुलैया होनी चाहिए। –
@ ली: अच्छा बिंदु। –
मैं के माध्यम से, बस एक विचार यह सोचा भी नहीं:
दीवार की नई बिट्स के लिए 'मनमानी' चयन प्रक्रिया बाहरी दीवार के लिए लंबवत सीधे वर्गों को 'बढ़ने' की कोशिश कर सकती है, फिर भी जहां भी संभव हो वहां भरने के लिए कुछ चरण स्विच पर स्विच शुरू हो सकता है।
शायद इसे पीछे हटने की क्षमता की आवश्यकता होगी।
शायद यह बहुत कुशल नहीं है।
मुझे लगता है कि यह मृत अंत में अच्छी तरह से परिणाम हो सकता है। – phimuemue
@phimuemue: एक मृत अंत का तात्पर्य है कि ऐसे ब्लॉक हैं जिन्हें दीवार के बिना कोई समाधान नहीं होने के कारण दीवार में बदल दिया जा सकता है (यानी शुरुआत से अंत तक एल्गोरिदम खोजने में पथ विफल)। जब तक समाधान को अवरुद्ध किए बिना दीवार ब्लॉक जोड़ना संभव हो, तब दीवार जोड़ें। –
मैं पूरी तरह से काला (पूर्ण) वर्ग से शुरू करने के लिए उत्सुक हूं और पथ खोदने की कोशिश करता हूं। खुदाई के दौरान आप आसानी से सुनिश्चित करते हैं कि कोई मृत-अंत नहीं है, बस चलते रहें। बैकट्रैकिंग, गहराई पहले खोज एल्गोरिदम का प्रयोग करें। एक "यादृच्छिक चलना" करें - प्रत्येक चरण में, यादृच्छिक रूप से निर्णय लें कि दिशा रखना या इसे बदलना है या नहीं। मृत अंत की स्थिति की जांच करें - यदि आप अटक जाते हैं, तो आप या तो कह सकते हैं "ठीक है, मैं कर चुका हूं, मैं खत्म में हूं", या, अगर आप भूलभुलैया को अभी तक पर्याप्त रूप से खोद नहीं पाते हैं, तो बैकट्रैक। हमेशा याद रखें कि आपने पहले क्या किया है और यादृच्छिक रूप से कुछ अन्य क्रियाओं को आजमाएं। संभवतः कुछ दिशाओं को पसंद करने के लिए कुछ ह्युरिस्टिक का उपयोग करें, जैसे कि कहें, दीवार को चकमा देने से पहले हमेशा कुछ खाली जगह रखें, दीवारों के चारों ओर घूमने के लिए पहले प्रयास करें। इस तरह आप वांछित समाधान ढूंढ सकते हैं जो सभी वर्गों को और अधिक तेज़ी से भर देता है।
उदाहरण में आप देते हैं कि शुरुआत से ही एक वास्तविक मार्ग है। यदि वह सब कुछ है जो आप चाहते हैं, तो मुझे लगता है कि आप यादृच्छिक सैर का उपयोग कर सकते हैं!
अवधारणा सरल है: भूलभुलैया की बाहरी सीमाओं, एक प्रारंभ बिंदु, और एक अंत बिंदु, प्रारंभ बिंदु से अंततः यादृच्छिक चलने के लिए एक समारोह लिखें जो अंततः अंत बिंदु पर समाप्त होता है। शर्तों यह होगी कि हमारा "यादृच्छिक वॉकर" केवल पिछले वर्ग से ऊपर, नीचे, दाएं या बाएं स्थानांतरित हो सकता है, और पहले के ट्रैवर्स वाले वर्ग (यह दीवारों को बनाता है) के एक वर्ग के भीतर नहीं आ सकता है।
जैसा कि मैंने इसे देखा, यहां दो एल्गोरिदमिक चुनौतियां हैं। पहला यह पता लगा रहा है कि हम पहले ट्रैवर्स स्क्वायर (टकराव) के एक वर्ग के भीतर हैं या नहीं। शायद हम ट्रैवर्स वाले वर्गों (उनके निर्देशांक) और भूलभुलैया सीमाओं की एक सूची बनाए रख सकते हैं, और प्रत्येक नए वर्ग के लिए सूची में प्रत्येक वर्ग से दूरी का मूल्यांकन किया जा सकता है। हालांकि यह बहुत कुशल नहीं लगता है।
दूसरी चुनौती वास्तव में हमारे यादृच्छिक चलने के साथ अंत बिंदु तक पहुंच रही है।यदि पहले ट्रैवर्स वाले वर्गों के साथ टकराव कोई मुद्दा नहीं था, तो हम अंततः अपने अंतिम बिंदु तक पहुंचने के लिए बाध्य होंगे, लेकिन उनके साथ हमें समस्या है कि हम अंत बिंदु से खुद को बंद कर सकते हैं। इससे बचने का तरीका लूप्स के प्रवेश की जांच करना और टालना है। अगर हम ट्रैवर्स पथ और/या भूलभुलैया सीमाओं द्वारा गठित लूप में प्रवेश करने से बचते हैं, तो हम अंत बिंदु के लिए एक संभावित मार्ग बनाए रखते हैं। जहां तक वास्तव में यह पता लग रहा है कि हम एक लूप में हैं ... मेह वह कठिन है।
यदि आपके पास पहले से ही एक भूलभुलैया-हल करने वाला एल्गोरिदम है, तो आप इसे तब भी चला सकते हैं जब आपके संभावित वर्ग से अंत बिंदु तक कोई पथ मौजूद हो या नहीं। जब आप इसे चलाते हैं, तो ऐसा लगता है कि पहले से चलने वाले सभी वर्ग दीवारों के साथ-साथ उनकी सीमाएं भी हैं।
जब 'चलना' एक स्टैक में प्रत्येक चरण पर किए गए परिवर्तनों को बनाए रखें, तो इस तरह आप आगे बढ़कर एक्स कदम देख सकते हैं और फिर प्रत्येक चरण में जैसे कि आप कोई और कदम नहीं उठा सकते (एक कोने या सर्पिल में चला गया चलने की तरह) स्टैक को तब तक पॉप करें जब तक आपके पास एए व्यवहार्य चलने वाला पथ न हो और स्टैक खाली होने तक वहां से चलना जारी रखें (यानी आप हर तरह से ढेर को पॉप करते हैं क्योंकि प्रत्येक पिछले चरण में कोई व्यवहार्य पड़ोसी नहीं था)। फिर भूलभुलैया डेटा संरचना में परिवर्तन लागू करें।
मैं इस समय इस पर काम कर रहा हूं ... किनारे से शुरू हो रहा हूं, मैं एक वर्ग सरणी में यादृच्छिक चल रहा हूं, जब मैं उनके माध्यम से गुजरता हूं तो पथ लंबाई के साथ कोशिकाओं को चिह्नित करता हूं।
जब आप अटक जाते हैं (और आप करेंगे), एक टी-जंक्शन बनाएं जो आपके आस-पास के सबसे हालिया पथ के साथ एक लूप बना रहा हो (लेकिन नीचे देखें)। मैं फिर टी-जंक्शन के दूसरी तरफ मौजूदा रास्ते के साथ ट्रैक करता हूं और वहां लूप तोड़ता हूं। यह लटकती पूंछ फिर यादृच्छिक चलने के अपने नए 'सिर' बनाती है (पथ स्रोत से अपने पथ की लंबाई को फिर से समझना याद रखें), और आप आगे बढ़ सकते हैं।
प्रयोगों से पता चलता है कि ऐसा करके यह (या अभी तक नहीं देखा गया है) नई पूंछ बनाने के एक लूप में आया है, जब तक कि आपकी नई 'पूंछ' फंस गई हो, आप बस नहीं मस्तिष्क से उस सेल के साथ एक लिंक फिर से बनाएं जिसे आपने अभी हाल ही में तोड़ दिया है - उस मामले में दूसरा सबसे हालिया चुनें।
समाप्त मामला है जब आप एक बढ़त तत्व पर 'अटक' हो जाता है, और आप सरणी भर दिया (अपने पथ की लंबाई सरणी के क्षेत्र के रूप में एक ही है) - आपका काम हो गया। आपका प्रारंभ बिंदु आपके अंतिम बिंदु की ओर जाता है।
इस के साथ दो संभावित अक्षमताएं और संभावित हिचकी लगती हैं (मैं इस समय एल्गोरिदम के साथ खेल रहा हूं) - कभी-कभी आप कोने में चलेंगे और जारी रखने का एकमात्र तरीका लूप को दोबारा बनाना है जो आपने अभी टूटा है उसके साथ लिंक करें। फिर अनुक्रम बैक-ट्रैक उन सभी लूपों के माध्यम से जिन्हें आपने पहले उस बिंदु पर बनाया था जिस पर आप मूल रूप से फंस गए थे। यदि कि कहीं और नहीं जा सकते (यह दूसरे कोने है) तो आप सिर्फ दो के बीच उछाल होगा। इसके आस-पास के तरीके हैं, लेकिन इसका मतलब है कि कुछ प्रकार की लूप कोशिकाओं की सूची रखना, केवल तभी इसे साफ़ करना जब आप वास्तव में कुछ नया रास्ता डालते हैं।
अन्यकि इसे छोड़ने का खतरा लगता है एक अजीब वर्ग रिक्त है, खासकर जब आपके सरणी अजीब-दर-अजीब है। मैं पूरी तरह से जांच की है नहीं क्यों यह मामला है, और जब ऐसा होता है कि पिछले कोने समस्या विशेष रूप से प्रचलित लगता है यह है।कार्य जारी है ...
अहह - मुझे एक यूनिकर्सल भूलभुलैया उत्पन्न करने का एक आसान तरीका मिला है। – Nick
आह - मैं एक unicursal उलझन पैदा करने का एक बहुत आसान तरीका मिल गया है।
रिक्त ग्रिड से शुरू करें, और इसे छोटे 2x2 लूप से भरें। यदि ग्रिड अजीब है, तो आपको कुछ 2x3 लूपों में मिश्रण करने की आवश्यकता होगी, और यदि यह अजीब बात है, तो आपको एक सिंगल स्क्वायर फ्री छोड़ना होगा - मैं आम तौर पर एक कोने को खाली छोड़ देता हूं।
इसके बाद, मनमाने ढंग से छोरों एक साथ शामिल बड़ा छोरों के रूप में - तो (उदाहरण के लिए) 2 2x2 छोरों एक भी 4x2 पाश हो जाते हैं। ऐसा करने के लिए, सुनिश्चित करें कि आप अपने आप को लूप में शामिल नहीं करते हैं।
अंततः आप एकल लूप सभी कोशिकाओं छोरों के मूल खेत के कब्जे में अप का उपयोग करता है के साथ खत्म हो जाएगा। इस लूप को किसी भी स्थिति में तोड़ दें, और आपको एक यूनिकर्सल भूलभुलैया मिल गई है, जहां शुरुआत और अंत स्थान एक-दूसरे के बगल में हैं।
अब आप छोटे लूप बनाने और तोड़कर ग्रिड के चारों ओर अंत बिंदुओं को स्थानांतरित कर सकते हैं - अंत में भूलभुलैया में एक और बिंदु में हुक करें, और फिर अपने एकल टुकड़े को फिर से बनाने के लिए विपरीत तरफ टी-जंक्शन को तोड़ दें एक नए अंत स्थान के साथ स्ट्रिंग।
आप एक अजीब-दर-अजीब उलझन पर काम कर रहे हैं, यह पिछले तकनीक कीड़ा अपने सिरों में से एक के लिए खत्म हो रिक्त कोने में अपने भूलभुलैया पूरा करने के लिए इस्तेमाल करते हैं।
मुझे लगता है कि मैं एक और तरीका मिल गया है, हालांकि मैं अभी तक इसे बड़े पैमाने पर परीक्षण नहीं किया गया है।
https://twitter.com/tdhooper/status/340853820584230915/photo/1
देखें बाएं से दाएं:
एक गैर unicursal भूलभुलैया के रूप में यहाँ https://en.wikipedia.org/wiki/File:Prim_Maze.svg वर्णित उत्पन्न करें, मुझे लगता है कि इस रस्मी एल्गोरिथ्म
है बाहर निकलने के ऊपर सील
भूलभुलैया में हर बिंदु पर जाने वाला पथ बनाएं (यानी इसे हल करने का प्रयास करें)
इस पथ मेक एक दीवार
यह काम करता है: http://www.stainlessvision.com/lab/maze-generator/unicursal.html यहाँ कोड: https: // GitHub।com/tdhooper/यादृच्छिक भूलभुलैया-जनरेटर –
वहाँ किसी भी प्रतिबंध है, उदा है कोई 2x2 काला वर्ग? –
@ ली रयान: नहीं। हालांकि जवाबों के बीच इस तरह के एल्गोरिदम होना अच्छा लगेगा। – Fejuto
संबंधित: http://stackoverflow.com/questions/2641964/algorithm-to-generate-a-segment-maze – nico