बहु-कहानी 3 डी डंगऑन की प्रक्रियात्मक पीढ़ी

हाल ही में, मैंने कई रॉगुलाइक खेले, इसलिए मैंने अपने स्वयं के प्रक्रियात्मक कालकोठरी जनरेटर को लिखने की कोशिश करने का फैसला किया। इस समस्या को हल करने के कई तरीके हैं, और मैंने यहां वर्णित लेखक TinyKeep के एल्गोरिथ्म को चुना है । मैंने इस एल्गोरिथ्म का विस्तार किया है ताकि यह 3 डी में काम करे और मल्टी-स्टोरी डंगऑन बना सके।

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

दो आयाम

पहले मुझे दो आयामों के लिए एक एल्गोरिथ्म लिखने की आवश्यकता है। सामान्य तौर पर, यह TinyKeep एल्गोरिथ्म के समान काम करता है, लेकिन अधिक दिलचस्प स्तर बनाने के लिए मतभेद है।

इस उदाहरण के लिए दृश्य को डंगऑन 2 डी कहा जाता है। इसके लिए कोड Scripts2D फ़ोल्डर में है।

एल्गोरिथ्म

दुनिया एक आयताकार ग्रिड में विभाजित है। मुझे लगता है कि 1 इकाई गलियारे को इंगित करने के लिए पर्याप्त होगी। एक पूर्ण गेम में, एकता की 1 इकाई, उदाहरण के लिए, 5 मीटर के अनुरूप हो सकती है। ग्रिड के लिए, मैंने 30 × 30 का आकार चुना।

1. हम कमरों को मनमाने ढंग से व्यवस्थित करते हैं, लेकिन ताकि वे एक-दूसरे को ओवरलैप न करें। स्थान मायने नहीं रखता है, इसलिए इस उदाहरण में मैं उन्हें एक यादृच्छिक स्थान और आकार देता हूं। इसके अलावा, प्रत्येक तरफ, मैंने एक बफर को 1 यूनिट चौड़ा (ताकि कमरे एक दूसरे को स्पर्श न करें) जोड़ा, लेकिन यह एल्गोरिथ्म के काम करने के लिए आवश्यक नहीं है।


लाल आयताकार कमरे हैं

कमरों के लिए एक Delaunay त्रिभुज ग्राफ बनाएँ। मैंने इसके लिए Bower-Watson एल्गोरिथम का उपयोग किया। कई भाषाओं में इस एल्गोरिथ्म के कई कार्यान्वयन हैं, मैंने एक को चुना जो सी # को पोर्ट करना आसान होगा।


Delaunay त्रिकोण

3. त्रिकोणासन से न्यूनतम फैले हुए वृक्ष (MST) बनाएं। मैंने इसके लिए प्राइम एल्गोरिथ्म का उपयोग किया।


एमएसटी गलियारे

4. हम गलियारों की एक सूची बनाते हैं, मंच से पेड़ के प्रत्येक किनारे से शुरू करते हैं। 3. पेड़ में सभी कमरे होते हैं, इसलिए प्रत्येक कमरे के लिए पथ मौजूद होने की गारंटी है। त्रिकोणीयकरण से सूची में किनारों को बेतरतीब ढंग से जोड़ें। इसलिए हम गलियारों में कई छोरों का निर्माण करेंगे। मेरे कोड में, मैंने प्रत्येक किनारे को 12.5% ​​तक जोड़ने की संभावना का उपयोग किया।


एमएसटी में कई किनारों को जोड़ने के बाद गलियारे। ध्यान दें कि लूप दिखाई दिए हैं।

5. सूची में प्रत्येक गलियारे के लिए, गलियारे की शुरुआत से अंत तक के मार्ग खोजने के लिए ए * एल्गोरिथ्म का उपयोग करें। एक रास्ता खोजने के बाद, यह दुनिया की स्थिति को बदल देता है ताकि भविष्य के गलियारे हमेशा मौजूदा वाले को बायपास कर सकें।

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


नीली आयतें गलियारे हैं

यहाँ एक एल्गोरिथ्म के कुछ उदाहरण दिए गए हैं जो वास्तविक ग्राफ़िकल संसाधनों का उपयोग करते हैं (संसाधन और उनके प्लेसमेंट के लिए कोड भंडार में नहीं हैं):

तीन आयाम

एक काम कर रहे 2 डी कालकोठरी जनरेटर बनाया, मैं इसे 3 डी में स्थानांतरित करना शुरू कर दिया। उपयोग किए गए सभी एल्गोरिदम में 3 डी संस्करण हैं, इसलिए यह सरल, सही होना चाहिए?

एल्गोरिथ्म

ग्रिड का आकार अब 30x5x30 है।

1. पहला परिवर्तन 3 डी में कमरों की पीढ़ी थी। यह परिवर्तन तुच्छ है।


कृपया ध्यान दें कि कमरे कई मंजिल ऊंचे हो सकते हैं।

2. फिर हम इन कमरों के Delaunay 3D-triangulation, या बल्कि Delaunay tetrahyard खोजें। "3 डी Delaunay triangulation" या "Delaunay tetrahedralization" शब्दों के बारे में जानकारी के लिए खोज करने के बाद, मुझे कई शोध लेख मिले, लेकिन एक भी कोड नमूना नहीं मिला।

3 डी सीजीएएल त्रिभुज के कार्यान्वयन के लिए मुझे सबसे ज्यादा जरूरत थी, लेकिन इसके साथ दो समस्याएं थीं। सबसे पहले, यह मॉड्यूल केवल GPL लाइसेंस के तहत उपलब्ध था। दूसरा - कोड इतना अधिक टेम्प्लेट और अस्पष्ट था कि मैं यह नहीं पता लगा सका कि एल्गोरिथ्म कहां लागू किया गया था।

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

यह नया संस्करण Scripts3D/Delaunay3D.cs में स्थित है, Scripts3D/Delaunay3D.cs किसी को MIT लाइसेंस के साथ आसानी से समझे जाने वाले कोड की आवश्यकता होती है।


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

3 और 4. पूरी तरह से तुच्छ परिवर्तनों के साथ चरण 2 से किनारों को प्राइम एल्गोरिथ्म में पारित किया जा सकता है।


3 डी-एमएसटी गलियारे


कई पसलियों के साथ गलियारे फिर से जुड़ गए

5. 3 डी एल्गोरिदम ए * में लागू होने पर कठिनाइयां शुरू होती हैं। 2 डी संस्करण बहुत सरल है, यह ए * का एक मानक कार्यान्वयन है। इसे 3 डी में स्थानांतरित करने के लिए, मुझे अलग-अलग मंजिलों पर ऊपर और नीचे जाने और कमरों को जोड़ने के लिए पथ खोज एल्गोरिथ्म की क्षमता को जोड़ने की आवश्यकता है। मैंने फर्श को ऊर्ध्वाधर सीढ़ियों से नहीं, बल्कि सीढ़ियों की उड़ानों से जोड़ने का फैसला किया।

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


साइड व्यू। आप पक्षों पर नोड बना सकते हैं, लेकिन शीर्ष पर नोड नहीं।

सीढ़ी के लिए पथ खोज एल्गोरिथ्म बनाने के लिए, मुझे इसके आकार का चयन करने की आवश्यकता है। 1: 1 की लंबाई के लिए ऊंचाई का अनुपात बहुत अधिक कठोर होगा, इसलिए मैंने 1: 2 का अनुपात चुना। माप की प्रत्येक ऊर्ध्वाधर इकाई के लिए, सीढ़ी दो क्षैतिज इकाइयों को स्थानांतरित करती है। इसके अलावा, चरित्र को रखने के लिए सीढ़ी के ऊपर जगह होनी चाहिए, यानी सीढ़ी के ऊपर दो सेल भी खुले होने चाहिए। सामान्य तौर पर, एक सीढ़ी में चार कोशिकाएँ होती हैं:


सीढ़ी और इसके ऊपर खाली जगह

सीढ़ियों के ऊपर और नीचे एक गलियारा भी होना चाहिए। पथ खोज एल्गोरिथ्म को पक्ष या विपरीत दिशा से सीढ़ियों तक आने में सक्षम नहीं होना चाहिए। यह अव्यवहारिक और अजीब होगा यदि सीढ़ी गलियारे में दुर्घटनाग्रस्त हो जाती है, जैसा कि नीचे दिखाया गया है।



यही है, अंत में, सीढ़ियों का प्रारूप नीचे की छवि की तरह दिखना चाहिए। एल्गोरिथ्म को खोजने वाले मार्ग को दो नीले वर्गों में गलियारों के अस्तित्व को सुनिश्चित करना चाहिए।


सीढ़ी एक ठोस नीले वर्ग से शुरू होती है और एक मंजिल तक जाती है।

पथ खोज एल्गोरिदम को एक चरण में शुरू से अंत बिंदु तक जाना चाहिए। इसका मतलब है कि इसे 3 इकाइयों को क्षैतिज और 1 इकाई को ऊपर या नीचे स्थानांतरित किया जाना चाहिए। एल्गोरिदम ए * को एक नोड से अगले तक प्रत्येक चरण पर जाने के लिए डिज़ाइन किया गया है। सीढ़ियों को बनाने के लिए, मुझे सीढ़ियों की चार कोशिकाओं को "कूदना" पड़ता है।

कठिनाई यह है कि किसी भी तरह मुझे सीढ़ियों के चारों ओर जाने के लिए एल्गोरिदम प्राप्त करने की आवश्यकता है जो इसे बनाता है। मैं उन्हें बंद सेट ए * में नहीं जोड़ सकता, क्योंकि तब इन कोशिकाओं के माध्यम से एक और दिशा से दूसरी दिशा में जाने में सक्षम नहीं होगा। लेकिन मैं उन्हें या तो नहीं छोड़ सकता, क्योंकि तब पथ खोज एल्गोरिथ्म नए बनाए गए सीढ़ी के साथ आगे बढ़ने में सक्षम होगा, जो ऊपर दिखाए गए अवांछनीय स्थितियों का निर्माण करेगा।

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

ऊपर वर्णित व्यवहार केवल उसी पथ फ़ंक्शन कॉल के भीतर कुछ संभावित पथों के लिए आवश्यक है। सभी गलियारों को उत्पन्न करने के लिए, अभी भी मार्ग खोजने के लिए कई चुनौतियां हैं। बाद में पुनरावृत्तियों पहले की तरह मौजूदा सीढ़ियों को बायपास करेगी।

इस स्तर पर एल्गोरिथ्म अब पूरी तरह से ए * नहीं है। सिर्फ सीढ़ियों के हिसाब से इसमें कई विशेष मामले हैं। प्रत्येक चरण में पूरे पिछले पथ को सत्यापित करने की आवश्यकता एक महंगी प्रक्रिया है। एक भोली कार्यान्वयन ने शुरुआत से पहले सभी नोड्स का पालन किया, उन्हें एक लिंक्ड सूची के रूप में पढ़ा। फिर प्रत्येक पड़ोसी नोड के लिए पथ की जांच करने के लिए O (N) समय लगेगा।

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

जैसा कि यह हो सकता है, समग्र जटिलता लगभग ओ (एन ^ 2) होगी, हालांकि मुझे नहीं पता कि यह कैसे सही ढंग से विश्लेषण करना है। यह संशोधन कालकोठरी पीढ़ी के एल्गोरिथ्म का मुख्य "अड़चन" है।

इन सभी परिवर्तनों को करने के बाद, परिणाम इस प्रकार था:


हरी आयतें सीढ़ियाँ हैं


जेनरेटर पथ सरल हो सकते हैं ...


... या जटिल

यहाँ एक 3 डी कालकोठरी वास्तविक ग्राफिक संसाधनों के साथ कैसा दिखता है:


कई मंजिलों के साथ कालकोठरी


कालकोठरी पीढ़ी एल्गोरिदम दिलचस्प उद्भव व्यवहार बनाने में सक्षम है।


दो सीढ़ियाँ एक डबल-चौड़ी सीढ़ी बनाती हैं


ट्रिपल चौड़ाई सीढ़ी की व्याख्या करना कठिन है


दो मंजिलों के नीचे जाने वाला मार्ग बीच में एक मंच के साथ दो सीढ़ियां बना सकता है


जब कई रास्ते एक-दूसरे के बगल से गुजरते हैं, तो गलियारे काफी बड़े हो सकते हैं


दो सीढ़ियाँ एक मंजिल पर उतरती हैं

निष्कर्ष

परियोजना का सबसे कठिन हिस्सा 3 डी संस्करण के लिए आवश्यक एल्गोरिदम का निर्माण था। मुझे डिलायने के 3 डी ट्राइंगुलेशन का एक भी कार्यान्वयन नहीं मिला, इसलिए मुझे इसे स्वयं करना पड़ा। पथ खोज एल्गोरिथ्म की आवश्यकताएं बहुत विशिष्ट थीं, इसलिए मैंने इसे स्वयं भी किया।

लेकिन काम इसके लायक था। इस एल्गोरिथ्म द्वारा बनाए गए काल कोठरी दिलचस्प हैं और एक अच्छे खेल की नींव बन सकती हैं।