प्रक्रियात्मक निर्माण पीढ़ी के लिए मार्कोव श्रृंखला

नोट: इस परियोजना का पूर्ण स्रोत कोड [ यहां ] पाया जा सकता है। चूंकि यह एक बड़ी परियोजना का हिस्सा है, मैं इस लेख को जारी किए जाने के समय, या /source/helpers/arraymath.h फ़ाइल के साथ-साथ /source/world/blueprint.cpp पर भी कमिट देखने की सलाह देता /source/world/blueprint.cpp ।

इस लेख में मैं 3D भवनों और अन्य प्रणालियों की प्रक्रियात्मक पीढ़ी के लिए मार्कोव श्रृंखला और सांख्यिकी का उपयोग करने के सिद्धांतों के बारे में विस्तार से बात करना चाहता हूं।

मैं सिस्टम की गणितीय नींवों को समझाऊंगा और स्पष्टीकरण को यथासंभव सामान्य बनाने का प्रयास करूंगा ताकि आप इस अवधारणा को अन्य स्थितियों में लागू कर सकें, उदाहरण के लिए, 2D डनजन्स उत्पन्न करने के लिए। स्पष्टीकरण छवियों और स्रोत कोड के साथ होगा।

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

परिणामों का उपयोग मेरे voxel इंजन में किया जाएगा ताकि टास्क बॉट बिल्डिंग, और फिर शहर बना सकें। लेख के अंत में एक उदाहरण है!


परिणामों के साथ कुछ उदाहरण।

मूल बातें

मार्कोव चेन

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

सिस्टम को राज्य स्थान से परिभाषित किया गया है, जो सभी संभव सिस्टम कॉन्फ़िगरेशन का स्थान है। यदि सिस्टम को सही ढंग से वर्णित किया गया है, तो हम राज्यों के बीच के बदलावों को असतत चरणों के रूप में भी वर्णित कर सकते हैं।

यह ध्यान दिया जाना चाहिए कि सिस्टम के एक राज्य से अक्सर कई संभावित असतत संक्रमण होते हैं, जिनमें से प्रत्येक सिस्टम की एक अलग स्थिति की ओर जाता है।

राज्य i से राज्य j में संक्रमण की संभावना बराबर है:

$$

$$P_ {ij}$$

मार्कोव प्रक्रिया इस राज्य स्थान का अध्ययन करने की प्रक्रिया है जिसकी मदद से इसे हस्तांतरित की गई संभावनाओं के आधार पर किया जाता है।

महत्वपूर्ण बात यह है कि मार्कोव के पास "कोई स्मृति नहीं है" प्रक्रिया है। इसका सीधा अर्थ है कि वर्तमान स्थिति से नए में संक्रमण की संभावनाएं केवल वर्तमान स्थिति पर निर्भर करती हैं और अब पहले देखी गई किसी भी अन्य शर्तों पर नहीं।

$$

$$P_ {ij} = P (i, j)$$

उदाहरण: पाठ पीढ़ी

एक प्रणाली बिट्स का एक क्रम है। राज्य स्थान बिट्स के सभी संभावित अनुक्रम हैं। एक असतत संक्रमण 0 से 1 या 1 से 0. से थोड़ा बदल जाएगा। यदि सिस्टम में एन बिट्स हैं, तो प्रत्येक राज्य से हमारे पास एक नए राज्य में संभव संक्रमण हैं। मार्कोव प्रक्रिया कुछ संभावनाओं का उपयोग करके बिट्स के मूल्यों को बदलकर राज्य के स्थान के अध्ययन में शामिल होगी।

उदाहरण: मौसम की भविष्यवाणी

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

मार्को चेन के लिए मोंटे कार्लो विधि

चूंकि राज्यों के बीच संक्रमण संभावनाओं द्वारा निर्धारित किए जाते हैं, इसलिए हम किसी भी राज्य में "स्थिर" होने की संभावना भी निर्धारित कर सकते हैं (या, यदि समय अनंत को जाता है, तो औसत समय जो हम एक विशेष स्थिति में होंगे)। यह राज्यों का आंतरिक वितरण है।

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

वे कहते हैं कि एक राज्य में होने की संभावना एक निश्चित लागत फ़ंक्शन के लिए आनुपातिक है * जो मौजूदा स्थिति का "अनुमान" देता है जिसमें सिस्टम स्थित है। यह माना जाता है कि यदि लागत कम है, तो इस राज्य में होने की संभावना अधिक है, और यह अनुपात नीरस है। लागत समारोह निम्नानुसार परिभाषित किया गया है:

$$

$$R (i)$$

नोट: यदि "आनुपातिक" शब्द का सही उपयोग किया जाता है, तो मुझे यकीन नहीं है, क्योंकि यह अनुपात जरूरी नहीं है कि रैखिक हो।

फिर राज्य वितरण से एक नमूना उच्च लागत के साथ कम लागत (या एक अच्छा "अनुमान") के साथ एक कॉन्फ़िगरेशन लौटाएगा!

यहां तक ​​कि एक बहुत बड़े राज्य के स्थान के साथ (संभवतः अनंत, लेकिन "अनगिनत अनंत"), सिस्टम की जटिलता की परवाह किए बिना, एमसीएमसी एल्गोरिदम कम लागत के साथ एक समाधान ढूंढ लेगा यदि हम इसे अभिसरण करने के लिए पर्याप्त समय देते हैं।

राज्य स्थान का ऐसा अध्ययन करना स्टोकेस्टिक अनुकूलन की एक मानक तकनीक है और इसमें मशीन सीखने जैसे क्षेत्रों में कई अनुप्रयोग हैं।

गिब्स वितरण

नोट: यदि यह खंड आपके लिए स्पष्ट नहीं है, तो आप इसे सुरक्षित रूप से छोड़ सकते हैं। आप सिस्टम के कार्यान्वयन का लाभ उठा सकते हैं।

जब हमने संभावित स्थिति के लिए लागत निर्धारित की है, तो हम इस स्थिति की संभावना कैसे निर्धारित करते हैं?

समाधान: गिब्स वितरण किसी दिए गए अवरोध के लिए अधिकतम एन्ट्रापी का वितरण है।

संक्षेप में, इसका मतलब है कि अगर हम सिस्टम की संभावनाओं पर कई अड़चनें लगाते हैं, तो गिब्स वितरण वितरण के आकार के बारे में "मान्यताओं की कम से कम मात्रा" पैदा करेगा।

नोट: गिब्स वितरण भी बाधाओं में भिन्नता के लिए कम से कम संवेदनशीलता के साथ वितरण है (कुल्बैक-लीब्लर डाइवर्जेंस मीट्रिक के अनुसार)।

राज्यों के वितरण पर हम जो एकमात्र प्रतिबंध लगाते हैं, वह लागत फ़ंक्शन है, इसलिए हम इसका उपयोग राज्यों के बीच संक्रमण की संभावना की गणना करने के लिए गिब्स वितरण में करते हैं:

$$

$$P_ {ij} = \ exp (- \ frac {R (j) -R (i)} {T}) * \ frac {1} {Z_i}$$

जहां Z राज्य i से संक्रमण के सेट का विभाजन कार्य है। यह एक सामान्यीकरण कारक है जो गारंटी देता है कि किसी भी राज्य से संक्रमण संभावनाओं का योग 1 है।

$$

$$Z_i = \ sum_j (P_ {ij})$$

ध्यान दें कि यदि हम तय करते हैं कि अगला राज्य समान राज्य होगा, तो सापेक्ष लागत शून्य है, अर्थात, सामान्य होने के बाद संभावना गैर-शून्य होगी (संकेतक के साथ वितरण के आकार के कारण)! इसका मतलब यह है कि कई संक्रमणों में अपरिवर्तित राज्यों की संभावना को शामिल करना आवश्यक है।

यह भी ध्यान देने योग्य है कि गिब्स वितरण "कम्प्यूटेशनल तापमान" टी द्वारा मानकीकृत है।

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

ध्यान दें कि जैसे ही तापमान अनंत हो जाता है, किसी भी व्यक्ति के संक्रमण की संभावना इस तरह से एकता में बदल जाती है कि जब राज्य से सभी संक्रमणों की संभावनाओं का सेट सामान्य हो जाता है, तो वे समान रूप से संभावित हो जाते हैं (या गिब्स वितरण सामान्य वितरण के करीब पहुंचते हैं), इस तथ्य के बावजूद कि उनकी लागत अधिक है!

जैसे-जैसे कम्प्यूटेशनल तापमान शून्य तक पहुंचता है, कम लागत वाले संक्रमण अधिक संभावना बन जाते हैं, अर्थात, पसंदीदा संक्रमण की संभावना बढ़ जाती है।

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

जब तापमान काफी कम हो जाता है, तो सभी संभावनाएं शून्य हो जाती हैं, बिना किसी संक्रमण की संभावना के अपवाद के साथ!

इसका कारण यह है कि केवल एक संक्रमण की अनुपस्थिति में एक शून्य लागत अंतर है, अर्थात, एक ही राज्य में होना तापमान पर निर्भर नहीं करता है। टी = 0 पर घातांक फ़ंक्शन के आकार के कारण, यह गैर-शून्य मान के साथ एकमात्र संभावना बन जाता है, अर्थात, सामान्य होने के बाद, यह एकता में बदल जाता है। नतीजतन, हमारी प्रणाली एक स्थिर बिंदु में परिवर्तित हो जाएगी और आगे ठंडा करना अब आवश्यक नहीं होगा। यह गिब्स वितरण का उपयोग करके संभाव्यता पीढ़ी का एक अभिन्न गुण है।

शीतलन दर को बदलकर प्रणाली के अभिसरण की प्रक्रिया को समायोजित किया जा सकता है!

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

नतीजतन, मार्कोव प्रक्रिया न केवल यादृच्छिक परिणाम उत्पन्न करती है, बल्कि "अच्छे" परिणाम उत्पन्न करने की कोशिश करती है, और उच्च संभावना के साथ यह सफल होगा!

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

नमूने की प्रक्रिया ही हमारे परिवर्तन के असतत सेट के बड़े पैमाने पर वितरण समारोह में उलटा परिवर्तन विधि का उपयोग करके किया जा सकता है। बाद में मैं दिखाऊंगा कि यह कैसे किया जाता है।

प्रक्रियात्मक पीढ़ी

यह प्रक्रिया प्रक्रियात्मक पीढ़ी के लिए कैसे उपयोगी है?

कुछ प्रणालियों में, एक साधारण एल्गोरिथ्म को परिभाषित करना अक्सर मुश्किल होता है जो अच्छे परिणाम उत्पन्न करता है, विशेष रूप से जटिल प्रणालियों के मामले में।

मनमाने ढंग से पीढ़ी के नियमों को स्थापित करना न केवल मुश्किल है, बल्कि केवल हमारी कल्पना और सीमा के मामलों के प्रसंस्करण द्वारा सीमित है।

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

निम्नलिखित आवश्यकताओं को प्रस्तुत किया गया है:

• सिस्टम एक असतत (संभवतः अनंत) राज्य कॉन्फ़िगरेशन में हो सकता है।
• हम राज्यों के बीच असतत बदलाव को परिभाषित कर सकते हैं।
• हम एक लागत फ़ंक्शन सेट कर सकते हैं जो सिस्टम की वर्तमान स्थिति का अनुमान लगाता है।

नीचे मैं कुछ अन्य उदाहरण दूंगा जिनमें, मेरी राय में, इस पद्धति को लागू किया जा सकता है।

कार्यान्वयन

छद्म कोड

हमारे कार्यान्वयन में, हम निम्नलिखित प्राप्त करना चाहते हैं:

• सिस्टम स्थिति सेट करें।
• अगले राज्य में सभी संभव बदलाव सेट करें।
• वर्तमान स्थिति की लागतों की गणना करें।
• सभी संभावित अगले राज्यों (या उनमें से एक सबसेट) की लागतों की गणना करें।
• गिब्स वितरण का उपयोग करके, संक्रमण की संभावना की गणना करें।
• संभावनाओं का उपयोग करके नमूना (नमूना) संक्रमण।
• एक नमूना संक्रमण करना।
• कम्प्यूटेशनल तापमान कम करें।
• जब तक आपको संतोषजनक परिणाम न मिलें तब तक चरणों को दोहराएं।

छद्म कोड के रूप में, MCMC एल्गोरिथ्म इस प्रकार है:

 // MCMC    T = 200; //     State s = initialState(); Transitions t[n] = {...} //n   thresh = 0.01; //  ( ) // ,      while(T > thresh){ //    curcost = costfunc(s); newcost[n] = {0}; // newcost   0 probability[n] = {0}; //     0 //  for(i = 0; i < n; i++){ newcost[i] = costfunc(doTransition(s, t[i])); probability[i] = exp(-(newcost[i] - curcost)/T); } //  probability /= sum(probability); //  sampled = sample_transition(t, probability); //  s = doTransition(s, sampled); //  T *= 0.975; } 

3D निर्माण पीढ़ी

राज्य अंतरिक्ष और संक्रमण

3 डी में इमारतें बनाने के लिए, मैं बाउंडिंग बॉक्स द्वारा निर्दिष्ट वॉल्यूम के साथ कई कमरे उत्पन्न करता हूं।

 struct Volume{ //   glm::vec3 a; glm::vec3 b; void translate(glm::vec3 shift); int getVol(); }; //   int Volume::getVol(){ return abs((bx-ax)*(by-ay)*(bz-az)); } //    void Volume::translate(glm::vec3 shift){ a += shift; b += shift; } 

यदि मैं एन कमरे उत्पन्न करता हूं, तो सिस्टम की स्थिति 3 डी अंतरिक्ष में बाउंडिंग बॉक्स का कॉन्फ़िगरेशन है।

यह ध्यान दिया जाना चाहिए कि इन संस्करणों के लिए संभावित कॉन्फ़िगरेशन अंतहीन हैं, लेकिन अनगिनत रूप से अनंत हैं (उन्हें अनंत समय में सूचीबद्ध किया जा सकता है)!

 //  (  !) std::vector<Volume> rooms; // N  for(int i = 0; i < n; i++){ //  Volume x; xa = glm::vec3(0); xb = glm::vec3(rand()%4+5); //   //  . rooms.push_back(x); } //... 

कई संभावित संक्रमण एक स्थान पर छह दिशाओं में से एक में एक स्थान पर कमरों की एक पारी होगी, जिसमें संक्रमण की अनुपस्थिति भी शामिल है:

 //... //   std::array<glm::vec3, 7> moves = { glm::vec3( 0, 0, 0), //   ! glm::vec3( 1, 0, 0), glm::vec3(-1, 0, 0), glm::vec3( 0, 1, 0), glm::vec3( 0,-1, 0), glm::vec3( 0, 0, 1), glm::vec3( 0, 0,-1), }; //... 

नोट: यह महत्वपूर्ण है कि हम सिस्टम को उसकी वर्तमान स्थिति में बने रहने में सक्षम बनाएं!

लागत समारोह

मैं चाहता था कि 3D स्पेस में वॉल्यूम "मैग्नेट" की तरह व्यवहार करें:

• यदि उनकी मात्राएं घटती हैं, तो यह बुरा है।
• यदि उनकी सतहों को छूते हैं, तो यह अच्छा है।
• यदि वे बिल्कुल भी स्पर्श नहीं करते हैं, तो यह बुरा है।
• यदि वे फर्श को छूते हैं, तो यह अच्छा है।

3 डी अंतरिक्ष में दो क्यूबॉइड्स के लिए, हम एक बाउंडिंग बॉक्स को आसानी से परिभाषित कर सकते हैं:

 Volume boundingBox(Volume v1, Volume v2){ //   Volume bb; //   bb.ax = (v1.ax < v2.ax)?v1.ax:v2.ax; bb.ay = (v1.ay < v2.ay)?v1.ay:v2.ay; bb.az = (v1.az < v2.az)?v1.az:v2.az; //   bb.bx = (v1.bx > v2.bx)?v1.bx:v2.bx; bb.by = (v1.by > v2.by)?v1.by:v2.by; bb.bz = (v1.bz > v2.bz)?v1.bz:v2.bz; return bb; } 

वॉल्यूम के बाउंडिंग बॉक्स का उपयोग करके, हम एक 3 डी वेक्टर की गणना कर सकते हैं जो मुझे दो संस्करणों के प्रतिच्छेदन के बारे में जानकारी देता है।

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

 //    3  glm::vec3 overlapVolumes(Volume v1, Volume v2){ //      Volume bb = boundingBox(v1, v2); //  glm::vec3 ext1 = glm::abs(v1.b - v1.a); // v1  3  glm::vec3 ext2 = glm::abs(v2.b - v2.a); // v2  3  glm::vec3 extbb = glm::abs(bb.b - bb.a); //   //  return ext1 + ext2 - extbb; } 

इस कोड का उपयोग मात्राओं की संख्या की गणना करने के लिए किया जाता है, जिसके लिए मैं एक भारित राशि बनाता हूं, जिसे अंततः लागत के रूप में उपयोग किया जाता है।

 int volumeCostFunction(std::vector<Volume> rooms){ // int metric[6] = { 0, //   0, //   0, //     0, //     0, // ,   0};//    int weight[6] = {2, 4, -5, -5, -5, 5}; //    for(unsigned int i = 0; i < rooms.size(); i++){ //     for(unsigned int j = 0; j < rooms.size(); j++){ //    ,  . if(i == j) continue; //    . glm::vec3 overlap = overlapVolumes(rooms[i], rooms[j]); //   glm::vec3 posOverlap = glm::clamp(overlap, glm::vec3(0), overlap); metric[0] += glm::abs(posOverlap.x*posOverlap.y*posOverlap.z); //   //   glm::vec3 negOverlap = glm::clamp(overlap, overlap, glm::vec3(0)); metric[1] += glm::abs(negOverlap.x*negOverlap.y*negOverlap.z); //   //   if(overlap.y == 0){ metric[2] += overlap.x*overlap.z; } //   (X) if(overlap.x == 0){ //      0,   , .. overlap.z = 0 metric[3] += overlap.z*overlap.y; } //   (Z) if(overlap.z == 0){ //      0,   , .. overlap.x = 0 metric[4] += overlap.x*overlap.y; } } //  ,   -   . if(rooms[i].ay == 0){ //  ,  ,    . metric[4] += rooms[i].ax*rooms[i].az; } //,     ! if(rooms[i].ay < 0){ //,        if(rooms[i].by < 0){ metric[5] += rooms[i].getVol(); } else{ metric[5] += abs(rooms[i].ay)*(rooms[i].bz-rooms[i].az)*(rooms[i].bx-rooms[i].ax); } } } // Metric * Weights return metric[0]*weight[0] + metric[1]*weight[1] + metric[2]*weight[2] + metric[3]*weight[3] + metric[4]*weight[4] + metric[5]*weight[5]; } 

नोट: "पॉजिटिव इंटरसेक्शन वॉल्यूम" का अर्थ है कि वॉल्यूम वास्तव में इंटरसेक्ट करते हैं। "नकारात्मक चौराहे की मात्रा" का अर्थ है कि वे बिल्कुल भी नहीं छूते हैं और 3 डी अंतरिक्ष में दो घनाभ के दो निकटतम बिंदुओं के बीच स्थित अंतरिक्ष में खंड द्वारा अंतर को परिभाषित किया गया है।

वज़न को इस तरह से चुना जाता है जैसे कि एक चीज़ को प्राथमिकता देना और दूसरों को ठीक करना। उदाहरण के लिए, यहां मैं फर्श के नीचे स्थित कमरों को गंभीर रूप से ठीक करता हूं, और उन लोगों की प्राथमिकता भी बढ़ाता हूं जिनकी सतह के क्षेत्र स्पर्श करते हैं (I से अधिक अंतर चौराहों को ठीक करते हैं)।

मैं सभी कमरों के लिए लागत पैदा करता हूं, उन कमरों की अनदेखी करता हूं जो खुद के साथ जोड़े जाते हैं।

कम लागत वाला समाधान खोजना

अभिसरण को छद्म कोड में वर्णित के रूप में किया जाता है। संक्रमण करते समय, मैं केवल एक समय में एक कमरा स्थानांतरित करता हूं। इसका मतलब यह है कि n कमरे और 7 संभावित संक्रमणों के साथ, मुझे 7 * n संभावनाओं की गणना करने की आवश्यकता है, और मैं उन सभी में से चयन करता हूं, केवल उस कमरे को स्थानांतरित करता हूं, जो शायद सबसे बेहतर है।

  //  float T = 250; while(T > 0.1){ //   std::vector<std::array<double, moves.size()>> probabilities; //   () int curEnergy = volumeCostFunction(rooms); //      ... for(int i = 0; i < n; i++){ //    std::array<double, moves.size()> probability; //      ,     for(unsigned int m = 0; m < moves.size(); m++){ //        . rooms[i].translate(moves[m]); //      ! probability[m] = exp(-(double)(volumeCostFunction(rooms) - curEnergy)/T); //   rooms[i].translate(-moves[m]); } //       probabilities.push_back(probability); } //  ( ) double Z = 0; for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ Z += probabilities[i][j]; } } //  for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ probabilities[i][j] /= Z; } } //    (CDF) ( ) std::vector<double> cdf; for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ if(cdf.empty()) cdf.push_back(probabilities[i][j]); else cdf.push_back(probabilities[i][j] + cdf.back()); } } //      std::random_device rd; std::mt19937 e2(rd()); std::uniform_real_distribution<> dist(0, 1); double uniform = dist(e2); int sampled_index = 0; //   CDF for(unsigned int i = 0; i < cdf.size(); i++){ //    ,   ... if(cdf[i] > uniform){ sampled_index = i; break; } } //     int _roomindex = sampled_index/moves.size(); int _moveindex = sampled_index%moves.size(); //  rooms[_roomindex].translate(moves[_moveindex]); // T T *= 0.99; // !!! } //!! //... 

नमूनाकरण सभी संभावित संक्रमणों के बड़े पैमाने पर वितरण समारोह में एक संचयी वितरण समारोह के गठन द्वारा किया जाता है; इस ऑपरेशन को "उलटा रूपांतर नमूनाकरण" कहा जाता है।

यह संक्रमण संभावनाओं का संचयी योग उत्पन्न करके पूरा किया जाता है, जो हमें संचयी वितरण फ़ंक्शन (CDF) प्रदान करता है। नमूने के लिए, हम 0 और 1 के बीच एक समान वितरण के साथ एक यादृच्छिक चर उत्पन्न करते हैं। चूंकि सीडीएफ का पहला तत्व शून्य है और अंतिम एक, हमें केवल "सीडीएफ सरणी के सूचकांक में समान वितरण के साथ हमारा नमूना चर" खोजने की आवश्यकता है, और यह होगा नमूना संक्रमण सूचकांक। यहाँ एक उदाहरण है:


एक सतत कार्य के बजाय असतत कदम हो सकते हैं। अधिक विवरण यहां पढ़ा जा सकता है ।

इसके अलावा, मेरे पास 3 डी स्पेस में रूम वॉल्यूम डेटा है!

मैं उन्हें ब्लूप्रिंट वर्ग का उपयोग करके एक "स्कीमा" उत्पन्न करने के लिए उपयोग करता हूं, ज्ञात थोक डेटा के लिए एक विषय लागू करता है। इसलिए घरों को उनका स्वरूप मिलता है। ब्लूप्रिंट क्लास का वर्णन पिछले लेख [ यहाँ ] ([ अनुवाद ] हैबे पर) में किया गया है। इन संस्करणों से एक घर की पूरी पीढ़ी के लिए, स्रोत कोड देखें।

परिणाम

इस तरह के एक सामान्यीकृत विधि के लिए परिणाम काफी अच्छे हैं। केवल एक चीज जो मुझे स्थापित करनी थी, वह लागत समारोह में सही प्राथमिकता और दंड भार थी।


इस एल्गोरिथ्म का उपयोग करते हुए निर्माण पीढ़ी के कुछ उदाहरण और उन पर लागू थीम।


साइड व्यू (अन्य इमारतें)।

अभिसरण स्वयं बहुत तेज़ है, विशेष रूप से कम संख्या में कमरे (3-5) के लिए, क्योंकि बाउंडिंग बॉक्स की गणना करना और लागत फ़ंक्शन का अनुमान लगाना बहुत सरल है।

वर्तमान संस्करण में, घरों में दरवाजे और खिड़कियां नहीं हैं, लेकिन यह एमसीएमसी एल्गोरिदम के लिए एक कार्य के बजाय 3 डी वॉल्यूम डेटा की व्याख्या करने का मामला है।

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

आमतौर पर दोष कमरे या भवन से अलग कमरों के रूप में दिखाई देते हैं। हवा में लटकना (ऊंची सीढ़ियों पर)।

एक्सटेंशन और अन्य सिस्टम

जाहिर है, 3 डी वॉल्यूम के साथ मेरी तकनीक केवल एक द्वारा कार्य के आयाम को कम करके 2 डी दुनिया में स्थानांतरित करना आसान है।

यही है, इसका उपयोग ऐसे कार्यों के लिए किया जा सकता है जैसे कि 2 डी गेम में प्रक्रियात्मक पीढ़ी के कमरे या कमरे एक शीर्ष दृश्य के साथ - एक दूसरे को कमरे संलग्न करना ऊपर वर्णित लागत फ़ंक्शन के समान उपयोग करता है।

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

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

अन्य संभावित अनुप्रयोग:

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

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

टास्क बॉट्स के लिए आवेदन

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

यहाँ एक वीडियो है कि कैसे बॉट इस एल्गोरिथम द्वारा निर्मित घर बनाता है:


( , ). . ( ) . , . , . - , , .