👨🏼‍💼 🧚🏿 🐶 ग्राफ नोड डंगऑन जेनरेटर 🤵🏼 🎅🏻 ✍🏽

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

परिचय

एल्गोरिथ्म एक स्नातक की डिग्री काम के हिस्से के रूप में लिखा गया था और मा एट अल (2014) के एक लेख पर आधारित है। कार्य का उद्देश्य एल्गोरिथ्म में तेजी लाने और नए कार्यों के साथ पूरक करना था। मैं परिणाम से काफी खुश हूं, क्योंकि हमने गेम के निष्पादन के दौरान इसका उपयोग करने के लिए एल्गोरिथ्म को काफी तेज कर दिया था। स्नातक के काम को पूरा करने के बाद, हमने इसे एक लेख में बदलने और गेम-ऑन 2018 सम्मेलन में भेजने का फैसला किया।

एल्गोरिथ्म

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

(ए)

(बी)

(सी)

(डी)

आंकड़े (सी) और (डी) इनपुट ग्राफ (ए) और बिल्डिंग ब्लॉक्स (बी) से उत्पन्न आरेख दिखाते हैं।

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

इनपुट ग्राफ के उदाहरण मुख्य पथ को लाल रंग में दिखाया गया है, सहायक मार्ग नीले हैं, छोटा रास्ता नारंगी है।

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

अलग-अलग कमरों के लिए अलग-अलग आकार

मैंने स्तर के अंत में बॉस के कमरे का उल्लेख किया। हम नहीं चाहते कि बॉस का कमरा किसी अन्य साधारण कमरे की तरह दिखे, है ना? एल्गोरिथ्म आपको प्रत्येक कमरे के लिए फॉर्म सेट करने की अनुमति देता है। उदाहरण के लिए, हम स्तर और एक बॉस के कमरे की शुरुआत में एक कमरा बना सकते हैं, जिसमें कमरे के आकार के अपने सेट और अन्य सभी कमरों के लिए एक सामान्य सेट होना चाहिए।

इनपुट ग्राफ से उत्पन्न दो सर्किट, जिसमें कमरों का एक विशेष रूप कमरा नंबर 8 के साथ जुड़ा हुआ है।

स्पष्ट रूप से संकेत दिया दरवाजे की स्थिति

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

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

(ए)

(बी)

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

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

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

(ए)

(बी)

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

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

उदाहरण

बिल्डिंग ब्लॉक के विभिन्न सेटों और गलियारों के साथ उत्पन्न कई योजनाएं चालू हुईं।

गलियारों के निर्माण खंडों के अलग-अलग सेट से उत्पन्न कई योजनाएँ।

पोस्ट के दूसरे भाग में मैं एल्गोरिथ्म के आंतरिक संचालन के बारे में बात करूंगा।

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

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

एकता प्लगइन का स्क्रीनशॉट (परियोजना विकास के तहत है)

भाग 2. एल्गोरिथ्म का कार्यान्वयन

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

प्रेरणा

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

यह कैसे काम करता है

एल्गोरिथ्म का उद्देश्य ग्राफ़ में प्रत्येक नोड के लिए कमरे के आकार और स्थिति को निर्दिष्ट करना है ताकि कोई दो कमरे न हों, और पड़ोसी कमरे दरवाजे से जुड़े हों।

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

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

कॉन्फ़िगरेशन रिक्त स्थान

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

(ए)

(बी)

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

निम्नलिखित एल्गोरिथ्म का उपयोग एक निश्चित और एक मुक्त ब्लॉकों के कॉन्फ़िगरेशन स्थान की गणना करने के लिए किया जाता है। हम चलती ब्लॉक पर एक संदर्भ बिंदु का चयन करते हैं और सभी स्थानों पर विचार करते हैं

m a t h b b R^{2}

$\ mathbb {R} ^ 2$ , ऐसा तब होता है जब बहुभुज को स्थानांतरित करते समय ताकि इसका संदर्भ बिंदु इस स्थान पर स्थित हो, दोनों चल और निश्चित ब्लॉक एक दूसरे को स्पर्श करते हैं, लेकिन अंतर नहीं करते हैं। इस तरह के सभी बिंदुओं का सेट दो ब्लॉक (चित्रा (ए) ऊपर) का कॉन्फ़िगरेशन स्थान बनाता है। दो या दो से अधिक स्थिर ब्लॉकों के सापेक्ष चलती ब्लॉक के कॉन्फ़िगरेशन का स्थान प्राप्त करने के लिए, व्यक्तिगत कॉन्फ़िगरेशन रिक्त स्थान के चौराहे की गणना की जाती है (चित्रा (बी) ऊपर)।

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

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

वृद्धिशील योजना

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

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

Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; }

छद्म कोड सही योजना खोजने के लिए एक वृद्धिशील दृष्टिकोण दिखा रहा है।

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

(ए) इनपुट ग्राफ

(b) आंशिक आरेख

(d) पूर्ण रूपरेखा

(() पूरी रूपरेखा

वृद्धिशील योजना। आंकड़े (बी) और (सी) पहले सर्किट की योजना के बाद दो आंशिक आरेख दिखाते हैं। चित्रा (डी) एक दूसरे सर्किट द्वारा विस्तार (बी) के बाद पूरा सर्किट दिखाता है। चित्रा (ई) एक दूसरे सर्किट द्वारा विस्तार (सी) के बाद पूरा सर्किट दिखाता है।

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

(ए)

(बी)

जंजीरों में विघटन। चित्रा (बी) एक उदाहरण दिखाता है कि सर्किट पर आंकड़ा (ए) कैसे बिछाया जाए। प्रत्येक रंग एक अलग श्रृंखला का प्रतिनिधित्व करता है। संख्याएं उस क्रम को इंगित करती हैं जिसमें श्रृंखलाएं बनाई जाती हैं।

(d) पूर्ण रूपरेखा

(ए) इनपुट ग्राफ

(b) खराब आंशिक ग्राफ

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

नकली annealing

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

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

E = e^{f r a c A_{o} m e g a} e^{f r a c D_{o} m e g a} - 1

$E = e ^ {\ frac {A} {\ _ omega}} e ^ {\ frac {D} {\ _ omega}} - 1$

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

_{ओ} म े ग ा

$\ _ ओमेगा$ इस संभावना को प्रभावित करता है कि सिम्युलेटेड एनेलिंग को सबसे खराब कॉन्फ़िगरेशन में जाने की अनुमति है; इस पैरामीटर की गणना भवन ब्लॉकों के औसत क्षेत्र से की जाती है।

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

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

 List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if (/*       */) { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if (/* newLayout ,  currentLayout */) { currentLayout = newLayout; } else if (/* ,   ,    newLayout */) { currentLayout = newLayout; } } /*      */ } return generatedLayouts; }

यह annealing का अनुकरण करके एक अलग सर्किट सर्किट बनाने के लिए जिम्मेदार विधि का छद्म कोड है।

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

बोनस वीडियो

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

डाउनलोड करने योग्य सामग्री

.NET पर एल्गोरिथ्म का कार्यान्वयन मेरे जीथूब में पाया जा सकता है। रिपॉजिटरी में .NET DLL और WinForms GUI एप्लिकेशन है, जिसे YAML कॉन्फ़िगरेशन फ़ाइलों द्वारा नियंत्रित किया जाता है।

ग्राफ नोड डंगऑन जेनरेटर