इस हफ्ते मैंने एक नए विषय पर काम करना शुरू कर दिया: काल कोठरी और गुफाओं की पीढ़ी। मैंने गुफाओं को और अधिक प्राकृतिक रूप देने के लिए गलियारों, और सेलुलर ऑटोमेटा उत्पन्न करने के लिए कमरे, भूलभुलैया पीढ़ी के एल्गोरिदम को उत्पन्न करने के लिए अंतरिक्ष विभाजन का उपयोग किया।

अंतरिक्ष विभाजन

कालकोठरी कमरे ( यादृच्छिक प्लेसमेंट , एजेंट-आधारित पीढ़ी , जुदाई स्टीयरिंग व्यवहार या एक भौतिक इंजन , आदि का उपयोग करके) उत्पन्न करने के कई तरीके हैं। लेकिन मेरा पसंदीदा तरीका अंतरिक्ष को विभाजित करना है, क्योंकि यह आसानी से नियंत्रित और विस्तारित होता है।

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

इस एल्गोरिथ्म की एकमात्र जटिलता जुदाई की स्थिति का विकल्प है। यदि हम अलगाव की स्थिति पर प्रतिबंध नहीं लगाते हैं, तो हमें अंतरिक्ष के अजीब विभाजन मिलेंगे:


इस व्यवहार से बचने के कई तरीके हैं। उनमें से एक जुदाई की स्थिति को दो पहलू अनुपातों तक सीमित करना है, उदाहरण के लिए, 30% से 70% या 40% से 60% तक की सीमा में। एक और तरीका समान वितरण के बजाय सामान्य या द्विपद का उपयोग करना है, जिससे पक्ष के केंद्र में अलगाव की संभावना बढ़ जाती है, और किनारों पर नहीं। ये तरीके समस्या को ठीक करते हैं, लेकिन यह समझना मुश्किल है कि पैरामीटर अंतिम परिणाम को कैसे प्रभावित करते हैं।

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


2.0 से 3.0 के अधिकतम अनुपात के साथ अच्छे परिणाम प्राप्त होते हैं:

रूम जनरेशन

अगले चरण कमरे के प्रत्येक कक्ष में पीढ़ी है। यहां कोई विशेष समस्याएं नहीं हैं, मैं सिर्फ सीमा निर्धारित करता हूं ताकि कमरे बहुत छोटे न हों और सेल की दीवारों के बहुत करीब न हों।

यहाँ परिणाम हैं:

रिब चयन

द्विआधारी विभाजन कालकोठरी जनरेटर में, विभाजित चरण में उपयोग किए जाने वाले द्विआधारी वृक्ष को आमतौर पर गलियारे उत्पन्न करने के लिए पुन: उपयोग किया जाता है। मैंने ऐसा नहीं किया, क्योंकि ऐसा दृष्टिकोण मुझे सीमित लगता है।

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


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

अभी के लिए, मैं बस किनारों का चयन करने के लिए Kruskal एल्गोरिथ्म और शहर के ब्लॉक की दूरी का उपयोग करता हूं। यहाँ परिणाम हैं:

कॉरिडोर जनरेशन

अगला कदम चयनित किनारों से गलियारे उत्पन्न करना है। यह संभवतः जनरेटर का सबसे पेचीदा हिस्सा है, क्योंकि मुझे सावधान रहने की जरूरत है ताकि कोई गलियारा दूसरे के साथ न रहे।

यहाँ परिणाम हैं:

गुफा पीढ़ी

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

वैसे भी, मैंने एक प्राकृतिक उपस्थिति बनाने के लिए सेलुलर ऑटोमेटा का उपयोग करने का फैसला किया, लेकिन नियंत्रित परिणाम प्राप्त करने के लिए उन पर प्रतिबंध लगाया। सिर्फ दो राज्यों के बजाय: मृत और जीवित, मैं चार का उपयोग करता हूं: बिल्कुल मृत, मृत, जीवित, निश्चित रूप से जीवित। "बिल्कुल सटीक" स्थिति प्रक्रिया में परिवर्तन नहीं कर सकती है, उनका उपयोग परिणामों को सीमित करने के लिए किया जाता है।

पिछले चरणों में उत्पन्न कमरे और गलियारे "बिल्कुल जीवित" कोशिकाओं से भरे हुए हैं। यही है, हमारे पास अभी भी सहायक कमरे हैं और हम गारंटी देते हैं कि वे एक-दूसरे से जुड़े होंगे। जिन किनारों का चयन नहीं किया गया है, वे "बिल्कुल मृत" कोशिकाओं से भरे हुए हैं ताकि कमरों के बीच कोई नया रास्ता न दिखाई दे। अंत में, कमरों और गलियारों के आसपास, हम बेतरतीब ढंग से कुछ कोशिकाओं को जीवित करते हैं। यहाँ प्रारंभिक विन्यास है:


फिर हम सेलुलर ऑटोमोबाटन शुरू करते हैं:



यहाँ कुछ और नमूना परिणाम दिए गए हैं:


बाद में मैं पहुंच योग्य भागों को हटाने के लिए एक भरण जोड़ूंगा।

एक दिलचस्प कालकोठरी जनरेटर बनाने के लिए एक लंबी यात्रा पर यह पहला कदम है। मैं परिणामों से प्रसन्न हूं। मुझे नियंत्रित और प्राकृतिक गुफाओं के निर्माण की विवश सेलुलर ऑटोमेटा पद्धति पर विशेष रूप से गर्व है। मुझे यह भी पसंद है कि प्रत्येक पीढ़ी का चरण दूसरों से अलग है और व्यक्तिगत रूप से संशोधित किया जा सकता है।

पृथक कोशिकाओं को हटा दें

तब मैंने दुर्गम कोशिकाओं को हटाने के लिए एक भरण लागू किया:

कमरों के बीच कई गलियारे

जनरेटर के मापदंडों के साथ प्रयोग करते हुए, मैंने पाया कि यदि आप कनेक्टिंग रूम के बीच थोड़ा शोर जोड़ते हैं, तो आपको दिलचस्प परिणाम मिलते हैं।

यहां कनेक्टिंग रूम में शोर लागू करने से पहले और तुरंत बाद परिणामों में अंतर है, पैरामीटर केवल एक इकाई द्वारा बदलता है:



यदि आप कमरे को थोड़ा बड़ा करते हैं, तो परिणाम और भी दिलचस्प होगा:


यह बहुत अच्छा है कि हमारे पास एक दुर्घटना है और सुंदर संरचनाएं उत्पन्न होती हैं, लेकिन एक ही समय में, ग्राफ की संरचना और कमरों के पदनाम संरक्षित होते हैं, जो उपयोगी होगा:

गुफाओं के लिए टाइल निर्माण

मैंने अपना अधिकांश समय टाइल बनाने में बिताया। यह बहुत मुश्किल नहीं है, लेकिन सही क्रियान्वयन के लिए इसमें थोड़ी मुश्किलें आती हैं।

यहाँ नमूना परिणाम हैं:


बड़ी बात यह है कि आप पत्थर की गुफा से रेत या बर्फ में आसानी से जा सकते हैं:


काल कोठरी उत्पन्न करने के अगले चरण दृश्यों और राक्षसों के जोड़ होंगे।