भग्न परिदृश्य के निर्माण के लिए हीरा-वर्ग एल्गोरिथ्म

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



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



अंदर आपको कई योजनाएं और सुंदर चित्र मिलेंगे, काफी कुछ अक्षर और एल्गोरिथ्म के एक उदाहरण कार्यान्वयन के लिए एक लिंक।

सामान्य कार्ययोजना

आमतौर पर लैंडस्केप पीढ़ी का क्या मतलब है? अगर हम कंप्यूटर गेम के लिए एक स्तर के निर्माण (लगभग वास्तविक समय में) के बारे में बात करते हैं - जैसे कि, वास्तव में, Minecraft, तो इस प्रक्रिया में निम्नलिखित बिंदु शामिल हैं:

1. एक ऊंचाई का नक्शा बनाएं । प्रारंभ में, हमारे पास एक सपाट द्वि-आयामी ग्रिड है और हम इसके प्रत्येक सेल को एक निश्चित ऊंचाई प्रदान करते हैं। कैसे? इस पर बाद में चर्चा की जाएगी। वैसे, ग्रिड को आयताकार होना जरूरी नहीं है - उदाहरण के लिए, त्रिभुज से बने ग्रिड के लिए एक समान एल्गोरिथ्म यहां वर्णित है । हालांकि, ज्यादातर मामलों में, वर्ग पिक्सेल कोशिकाओं से मिलकर एक ग्रिड अधिक सुविधाजनक है। ऊंचाई के नक्शे के साथ, पानी से ढंके क्षेत्रों को भी परिभाषित किया जाता है - कम से कम समुद्र और महासागर (एक नियम के रूप में, वे कोशिकाएं जो एक निश्चित स्तर से नीचे झूठ बोलती हैं) पानी बन जाती हैं।
2. बायोम वितरण । यहां आपको भूगोल में कुछ ज्ञान की आवश्यकता होगी (हालांकि, एक परिदृश्य बनाने की पूरी प्रक्रिया के लिए यह आवश्यक है)। यह निर्धारित करने के लिए कि टुंड्रा कहाँ होना चाहिए, रेगिस्तान कहाँ है, और जहाँ वर्षावन है, पहले से निर्मित ऊँचाई का नक्शा और, उदाहरण के लिए, पानी के स्थानों से दूरी या कुछ पूर्व निर्धारित बिंदुओं (भूमध्य रेखा / ध्रुवों) में मदद मिलेगी। बदले में, बायोम कई अन्य मापदंडों को निर्धारित करेंगे - उदाहरण के लिए, घास कवर, चट्टानी क्षेत्रों की संख्या, पौधे, नदियों और झीलों की संख्या, आदि।
3. हमने पृथ्वी, महासागर और समुद्र भी बनाए, भौगोलिक क्षेत्र वितरित किए। क्या भूल गए? चलो नदी , बिल्कुल! पानी के अलावा, जो पहाड़ों से निकलकर समुद्र में उतरेगा या झीलों में बनेगा, पृथ्वी की सतह पर उनके प्रभाव का अनुकरण किया जाना चाहिए - रिवरबेड का गठन किया जाना चाहिए और झीलों और अन्य जल के किनारों पर समुद्र तटों के साथ धारा के साथ रेत और नरम मिट्टी का परिवहन किया जाना चाहिए। दुर्भाग्य से, इस प्रक्रिया, जिसे पानी का क्षरण कहा जाता है, अन्य प्रकार के कटाव की तरह , मुझे इस लेख के दायरे से बाहर जाना होगा। फिर भी, संदर्भ की सूची में इस विषय पर बहुत अच्छी सामग्री के लिए कुछ लिंक हैं।
4. अतिरिक्त कार्रवाई । वास्तव में, परिदृश्य पहले से ही बनाया गया है, लेकिन अभी भी कई चीजें हैं जो इस पर सुधार की जा सकती हैं - उदाहरण के लिए, Minecraft में, भूमिगत स्थान पूरी तरह से प्राकृतिक गुफाओं से भरा हुआ है, और सतह पर कई पेड़ उगते हैं। इसके अलावा, निश्चित रूप से, बायोम के आधार पर, वनस्पतियों और जीवों में विविधता लाने के लिए संभव है - यदि लक्ष्य वास्तविक प्रकृति में क्या हो रहा है जितना संभव हो उतना करीब हो।

अंत में, उत्पन्न परिदृश्य को केवल खींचना होगा। यहां मैं केवल एक विवरण पर ध्यान देना चाहता हूं - जबकि तीन-आयामी मानचित्र के पारंपरिक दृश्य के मामले में उपर्युक्त त्रिकोणीय ग्रिड उपयोगी होगा, वर्ग कोशिकाओं के लिए voxels का उपयोग बहुत उपयोगी हो सकता है। हालाँकि, यह पूरी तरह से अलग कहानी है।

ऊंचाई का नक्शा बनाने के तरीके

तो, आइए एक परिदृश्य बनाने में सबसे महत्वपूर्ण चरण पर नज़र डालें - यह निर्धारित करते हुए कि पृथ्वी की सतह पर प्रत्येक बिंदु किस ऊंचाई पर है। सबसे आम विचार दोनों निर्देशांक पर जाने और नक्शा बनाने के लिए है [x] [y] = यादृच्छिक () - काफी पर्याप्त है, यह स्वीकार्य परिणाम नहीं देगा, इसलिए आपको कुछ अधिक चालाक का उपयोग करने की आवश्यकता है।

पहाड़ियों को "मैन्युअल रूप से" बनाएं

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

वोरोनोई आरेख पर आधारित परिदृश्य

वास्तव में, हाल ही में, जब तक अगला दृष्टिकोण मेरे लिए पूरी तरह से अज्ञात नहीं था और मुझे बहुत आश्चर्य हुआ कि यह बहुत प्रभावशाली परिणाम देने में सक्षम था।



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



यदि पिछला पैराग्राफ आपके लिए स्पष्ट नहीं है - यह डरावना नहीं है, तो इसका सार ऐसे ग्रिड के बारे में बनाने के लिए आता है जैसा कि दाईं ओर की आकृति में है। इसकी मुख्य संपत्ति इसकी अनियमितता है। यह इसके आधार पर निर्मित परिदृश्य को "वर्ग" नहीं लगने देता है।



आगे की क्रियाएं तुच्छ हैं - हम बेतरतीब ढंग से पानी से भरे होने वाले बहुभुजों का चयन करते हैं, और शेष बहुभुजों से संबंधित बिंदुओं की ऊँचाई को समुद्र-ओकीना के लिए सबसे कम दूरी के बराबर बनाते हैं। यह एक ही शोर (खुद को ऊंचाई और बहुभुज की सीमाओं तक) को जोड़ने के लिए बनी हुई है - और हमें एक बहुत अच्छा द्वीप (या मुख्य भूमि, पैमाने पर निर्भर करता है) मिलेगा।



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

डायमंड-स्क्वायर एल्गोरिदम

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



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



तथ्य यह है कि यह एल्गोरिथ्म फ्रैक्टल्स से संबंधित है इसका पुनरावर्ती व्यवहार है। प्रारंभ में, हम किसी भी तरह से खंड के सिरों पर ऊँचाई निर्धारित करते हैं और इसे बीच में एक बिंदु के साथ दो उप-खंडों में विभाजित करते हैं। हम इस बिंदु को एक यादृच्छिक मूल्य से स्थानांतरित करते हैं और विभाजन को प्राप्त करते हैं और प्राप्त उप-खंडों में से प्रत्येक के लिए स्थानांतरित करते हैं। और इसी तरह - जब तक खंड एक पिक्सेल लंबे नहीं हो जाते। यह संपूर्ण एल्गोरिथ्म है (दाईं ओर आकृति देखें)। आह, हाँ - एक महत्वपूर्ण टिप्पणी: यादृच्छिक विस्थापन उन खंडों की लंबाई के लिए आनुपातिक होना चाहिए, जिन पर विभाजन किए जाएंगे। उदाहरण के लिए, हम लंबाई l के एक खंड को विभाजित करते हैं - फिर इसके बीच में बिंदु की ऊंचाई होनी चाहिए

h = ( h _L + h _R ) / 2 + यादृच्छिक (- R * l , R * l )

( h _L और h _R खंड के बाएँ और दाएँ छोर पर ऊँचाई हैं, और निरंतर R परिणामी पॉलीलाइन के "खुरदरापन" को निर्धारित करता है और इस एल्गोरिथम में मुख्य पैरामीटर है)।



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

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



यह अभी तक हीरा-वर्ग नहीं है - इस एल्गोरिथ्म, एक नियम के रूप में, इसे मिडपॉइंट विस्थापन एल्गोरिदम भी कहा जाता है, और इस तथ्य के बावजूद कि यह अपेक्षाकृत स्वीकार्य परिणाम देता है, आप परिणामी तस्वीर में इसकी "सीधी" प्रकृति को आसानी से देख सकते हैं।



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



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



उपयोग करने की आवश्यकता के अलावा, मान लें, गहराई में चलने के बजाय चौड़ाई में चलना, एक और सूक्ष्मता है - परिदृश्य के किनारों पर स्थिति। तथ्य यह है कि हीरे के चरण में, एल्गोरिथ्म उन बिंदुओं की ऊंचाई का उपयोग करता है जो वर्तमान वर्ग के बाहर हैं और, संभवतः, पूरा नक्शा। कैसे हो? दो विकल्प हैं (हालांकि आप अपने खुद के साथ आ सकते हैं, निश्चित रूप से): या तो इन ऊंचाइयों को 0 (या 1, या किसी अन्य स्थिरांक के बराबर मानें; इस तरह, पानी के नीचे हमारे परिदृश्य के किनारों को डुबोने के लिए सुविधाजनक है), या कल्पना करें कि हमारा विमान मुड़ा हुआ है। torus (toroidal planet, hmm ...) और मैप की लेफ्ट बॉर्डर के बायीं ओर 64 पिक्सल्स में पड़ी एक पॉइंट की ऊँचाई का पता लगाने की कोशिश करते हुए, हम राईट बॉर्डर से 64 पॉइंट दूर एक पॉइंट की ऊँचाई का पता लगाते हैं। इसे बहुत ही सरलता से लागू किया जाता है (जैसा कि, हालाँकि, पहला विकल्प) - हमें मानचित्र के आकार के बराबर निर्देशांक मोड्यूल लेने में मदद मिलेगी।



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

बड़े मानचित्रों के लिए डायमंड-स्क्वायर एल्गोरिदम का संशोधन

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



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



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







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

function val(x, y, v) { if (typeof(v) != 'undefined') data[x + '_' + y] = Math.max(0.0, Math.min(1.0, v)); else { if (x <= 0 || x >= size || y <= 0 || y >= size) return 0.0; if (data[x + '_' + y] == null) { //       . base = 1; while (((x & base) == 0) && ((y & base) == 0)) base <<= 1; if (((x & base) != 0) && ((y & base) != 0)) squareStep(x, y, base); else diamondStep(x, y, base); } return data[x + '_' + y]; } } function displace(v, blockSize, x, y) { return (v + (randFromPair(x, y, seed) - 0.5) * blockSize * 2 / size * roughness); } function squareStep(x, y, blockSize) { if (data[x + '_' + y] == null) { val(x, y, displace((val(x - blockSize, y - blockSize) + val(x + blockSize, y - blockSize) + val(x - blockSize, y + blockSize) + val(x + blockSize, y + blockSize)) / 4, blockSize, x, y)); } } function diamondStep(x, y, blockSize) { if (data[x + '_' + y] == null) { val(x, y, displace((val(x - blockSize, y) + val(x + blockSize, y) + val(x, y - blockSize) + val(x, y + blockSize)) / 4, blockSize, x, y)); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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



जैसा कि पहले ही उल्लेख किया गया है, एल्गोरिथ्म में कई जादू लाइनें हैं - यहां वे हैं:

 base = 1; while (((x & base) == 0) && ((y & base) == 0)) base <<= 1; if (((x & base) != 0) && ((y & base) != 0)) squareStep(x, y, base); else diamondStep(x, y, base);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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



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



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

 function randFromPair(x, y) { for (var i = 0; i < 80; i++) { var xm7 = x % 7; var xm13 = x % 13; var xm1301081 = x % 1301081; var ym8461 = y % 8461; var ym105467 = y % 105467; var ym105943 = y % 105943; y = x + seed; x += (xm7 + xm13 + xm1301081 + ym8461 + ym105467 + ym105943); } return (xm7 + xm13 + xm1301081 + ym8461 + ym105467 + ym105943) / 1520972.0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

इसके अलावा, इस समारोह में आसानी से एक "वैश्विक अनाज" पेश करना संभव था, जो पूरे परिदृश्य को निर्धारित करता है, और अवशेषों को लेने के कारण, इसका रिटर्न मान काफी हद तक समान रूप से वितरित किया जाता है [0, 1)। हालाँकि, मुझे यकीन है कि आप तेजी से सुरुचिपूर्ण समाधान के साथ आ सकते हैं - आप इस लेख में "होमवर्क" पर विचार कर सकते हैं :)



जैसा कि सभी ने शायद अनुमान लगाया था, मैंने जावास्क्रिप्ट में कार्यान्वयन लिखा है, जो मूल्यों और स्रोत कोड दोनों के साथ प्रयोग करना समान रूप से आसान बनाता है। पृष्ठ स्वयं http://denull.ru/terrain.htm पर उपलब्ध है, और सभी कोड http://denull.ru/terrain.js फ़ाइल में स्थित है। इसे देखने के लिए, आपको एक ब्राउज़र की आवश्यकता होती है जो html5 का समर्थन करता है (ईमानदार होने के लिए, मैंने इसे केवल Google Chrome में परीक्षण किया है), चूंकि प्रतिपादन कैनवास पर जाता है (और, यह ध्यान दिया जाना चाहिए, प्रतिपादन खुद भी कुछ समय लेता है)।

संबंधित सामग्री

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