बाधा आधारित टाइल प्लेसमेंट एल्गोरिथ्म

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

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

टाइल सेट

जेनरेट वर्ल्ड्स में, प्रत्येक दुनिया को टाइल (टाइलसेट) के एक सेट से इकट्ठा किया जाता है। संक्षेप में, टाइलें सिर्फ छोटे स्वर मॉडल हैं। एक उदाहरण से शुरू करते हैं। नीचे की छवि 9 टाइलों से बनी है। जैसा कि आप देख सकते हैं, प्रत्येक टाइल में वेक्सल्स होते हैं जो रंगीन क्यूब्स के रूप में दिखाई देते हैं।


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


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

हम टाइल्स को आपस में जोड़ते हैं

4 टाइलों वाली टाइल पर एक नज़र डालें:


ये टाइलें ऊपर दिखाए गए तीन आयामी टाइलों के समान हैं।

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

ऊपर प्रस्तुत 4 टाइलों के एक अनुमेय संयोजन में, सीमाओं के साथ प्रकाश कोशिकाओं को केवल प्रकाश कोशिकाओं को छूना चाहिए, और एक अंधेरे सेल को केवल अंधेरे कोशिकाओं को छूना चाहिए। उदाहरण के लिए:


सही और गलत कनेक्शन के उदाहरण।

दाईं ओर का उदाहरण अस्वीकार्य है, क्योंकि टाइल के किनारे के किनारे, प्रकाश वर्ग अंधेरे वर्ग को छूता है। इस टाइलसेट के लिए उत्पन्न दो वैध संयोजन नीचे दिखाए गए हैं:


सामान्य मामले में, वैध टाइल संयोजन बनाना कोई तुच्छ कार्य नहीं है। उदाहरण के लिए, निम्नलिखित सरल "लालची" रणनीति पर विचार करें: हम एक खाली ग्रिड से शुरू करते हैं। प्रत्येक पुनरावृत्ति में, हम टाइल को किसी बिंदु पर रखते हैं, एक टाइल का चयन करते हैं जो पहले से रखी गई टाइलों को ध्यान में रखते हुए स्वीकार्य है। नीचे दिए गए चित्र ऐसी रणनीति की समस्याओं को दर्शाते हैं।


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

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


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

फास्ट कैशिंग प्लेसमेंट सूचना कैशिंग के लिए धन्यवाद

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

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


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

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

3 डी में सिस्टम का विस्तार करना

जेनरेट वर्ल्ड्स एल्गोरिथ्म स्वाभाविक रूप से तीसरे आयाम वाले दुनिया में फैलता है। आम चेहरों के साथ 4 पड़ोसी टाइलों के साथ 2 डी टाइलों के रंग के मिलान के बजाय, अब हमारे पास 3 डी टाइलें हैं जो 6 पड़ोसियों के साथ अपने पड़ोसियों के साथ रंग में मेल खाना चाहिए। निम्नलिखित 3 डी टाइलों पर विचार करें:


3 डी में इन टाइलों की विधानसभा निम्नानुसार है:


इस मामले में, स्वीकार्य पड़ोस दो आयामी नहीं हैं, लेकिन तीन आयामी ग्रिड हैं, और एल्गोरिथ्म उन्हें इसी तरह के 2 डी मामले में उत्पन्न करता है।

परिणाम गैलरी

इस विवरण के कार्यान्वयन के साथ-साथ संक्षिप्त विवरण के साथ उत्पन्न दुनिया को दिखाया गया है।


बाहर निकलने के साथ कमरा दिखाने वाले जनरेट वर्ल्ड से स्क्रीनशॉट। छत पर सीमायें टाइल्स की सीमाओं के साथ मेल खाती हैं।


एक अन्य टूल से एक स्क्रीनशॉट जो मैं पैदा करता हूं वह जेनरेट वर्ल्ड्स एल्गोरिदम का भी उपयोग करता है; विभिन्न प्रकार के कमरे और गलियारे दिखाए जाते हैं।


पिछले एक के समान एक दुनिया, लेकिन अब एक सुंदर सममितीय दृश्य में


दुनिया, जिसका निर्माण मैं दांते के नर्क के नौवें चक्र से प्रेरित था: पापी जो बर्फ में जमे हुए थे। MagicaVoxel में प्रस्तुत किया गया।


दुनिया, जिसका निर्माण मैं दांते के नरक के दूसरे दौर से प्रेरित था: परिदृश्य, जो जलती हुई बारिश से सिंचित है, जो पुल को पार करता है। MagicaVoxel में प्रस्तुत किया गया।


झरने और नदियों के साथ घास के प्लेटफार्मों की दुनिया। MagicaVoxel में प्रस्तुत किया गया।


इमारतों और दीवारों के साथ एक मध्ययुगीन शहर की लैंडस्केपिंग। MagicaVoxel में प्रस्तुत किया गया।