हम लहर फ़ंक्शन पतन एल्गोरिथ्म से निपटते हैं

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

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


README में मैक्सिम ने WFC के काम के बारे में संक्षेप में बताया, लेकिन मुझे ऐसा लगता है कि इस मुद्दे को बहुत ही बुनियादी बातों से अधिक विस्तृत प्रकटीकरण की आवश्यकता है। चूंकि एल्गोरिथ्म बाधाओं में प्रोग्रामिंग से संबंधित है , इसलिए अधिकांश लेख बाधाओं में प्रोग्रामिंग की अवधारणा को समझाने के लिए समर्पित है , और अंत में हम डब्ल्यूएफसी में लौट आएंगे ।

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

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

मिनी सुडोकू

एक निराशाजनक कार्य के रूप में, मैंने एक मिनी सुडोकू लिया । यह एक पहेली है जो कुछ कोशिकाओं में संख्याओं के साथ 4 × 4 ग्रिड की तरह दिखता है।


लक्ष्य प्रत्येक खाली कक्ष को नियमों के अनुसार 1 से 4 तक की संख्या के साथ भरना है:

• 1 से 4 तक की प्रत्येक संख्या एक पंक्ति में प्रत्येक पंक्ति में मौजूद होनी चाहिए।
• 1 से 4 तक की प्रत्येक संख्या को एक प्रति में प्रत्येक कॉलम में मौजूद होना चाहिए।
• 1 से 4 तक की प्रत्येक संख्या को एक प्रतिलिपि में प्रत्येक 2 × 2 कोने के वर्ग में मौजूद होना चाहिए।

इन नियमों के अनुसार, समाधान इस प्रकार होगा:


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

शर्तों का विवरण

आमतौर पर, प्रतिबंधों में एक प्रोग्रामिंग भाषा का उपयोग इसके लिए किया जाता है। ऐसी कई भाषाएं हैं, और कार्रवाई के उनके सिद्धांत समान हैं।

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

फिर प्रत्येक चर के लिए हम एक डोमेन परिभाषित करते हैं : संभावित मूल्यों का एक सेट। हमारे सुडोकू में, प्रत्येक खाली सेल के लिए, डोमेन {1, 2, 3, 4} होगा। और एक सेल के लिए जिसमें 1 पहले से ही दर्ज है, डोमेन {1} होगा।

अंत में, हम बाधाओं को निर्धारित करते हैं: हमारे चरों को बाध्य करने वाले नियम। अधिकांश प्रोग्रामिंग भाषाओं में, पहले से ही प्रतिबंधों के साथ एक फ़ंक्शन है all_distinct(..)जो अद्वितीय मूल्यों को पारित करने की आवश्यकता है। इसलिए सुडोकू नियमों को 12 बाधाओं में अनुवादित किया जा सकता है all_distinct- प्रत्येक पंक्ति और स्तंभ के लिए, साथ ही 2 × 2 कोने के वर्गों के लिए। हमें इस समस्या को हल करने के लिए केवल एक प्रकार की बाधा की आवश्यकता है, हालांकि, समस्या को पूरा करने के लिए समस्या का समाधान आमतौर पर आपकी समस्या का वर्णन करने के लिए विभिन्न प्रकार की बाधाओं के एक बड़े पुस्तकालय के साथ आता है।

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

बाधा संतुष्टि समस्याओं को हल करने के लिए एल्गोरिदम

कई अलग-अलग समाधान तकनीकें हैं। लेकिन मैं उनमें से सबसे सरल पर विचार करूंगा कि आप उनके काम के सिद्धांत को प्रदर्शित करें। प्रत्येक सेल के लिए डोमेन यहां दिखाए गए हैं:


चर डोमेन में ये सभी संभावित मान हैं।

अब पहली सीमा लें। इसके लिए आवश्यक है कि शीर्ष पंक्ति के सभी मान अद्वितीय हों। एक सेल में, मान 4 पहले से ही अंकित है, इसलिए, श्रृंखला के अन्य कक्षों में यह मान नहीं हो सकता है । हम इसे इन सेल के डोमेन से हटा देते हैं।


इस प्रक्रिया को सभी 12 प्रतिबंधों के साथ दोहराएं। इसे प्रतिबंधों का प्रसार कहा जाता है , क्योंकि प्रतिबंधों के माध्यम से एक चर से दूसरे में जानकारी वितरित की जाती है।


और देखो, हमारे पास चर हैं, जिन डोमेन में एक मान बाकी है। ये इन चरों के लिए सही समाधान होना चाहिए ।


ऐसा लगता है कि हम प्रतिबंधों के वितरण से और भी अधिक लाभ प्राप्त कर सकते हैं: नई लाल इकाइयों से संकेत मिलता है कि हमारे पास एक ही डोमेन के साथ और भी अधिक चर होंगे, और यह वितरण में भी योगदान देगा। पहेली हल होने तक प्रक्रिया को दोहराएं।

हम कार्य को जटिल करते हैं

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


यदि हम उपरोक्त तकनीक को लागू करने का प्रयास करते हैं, तो हम फंस जाएंगे:


अब सभी प्रतिबंध आम हैं, लेकिन अभी भी अपरिभाषित चर हैं।

एक व्यक्ति यह तय करेगा, लेकिन एक कंप्यूटर एल्गोरिथ्म करने में सक्षम नहीं होगा। लोगों के लिए नियमावली कहती है कि अब हमें अधिक से अधिक जटिल तार्किक निष्कर्षों की तलाश करने की जरूरत है। लेकिन हमें ऐसा करने के लिए एक कंप्यूटर एल्गोरिथ्म की आवश्यकता नहीं है, क्योंकि यह मुश्किल है, लेकिन हमें एक सार्वभौमिक एल्गोरिथ्म की आवश्यकता है जो प्रतिबंधों के किसी भी सेट के साथ काम कर सकता है, और न कि केवल सुडोकू नियमों के अनुसार।

इसलिए, कंप्यूटर सबसे बेवकूफ काम करते हैं : वे मान लेते हैं । सबसे पहले, हम पहेली की वर्तमान स्थिति को रिकॉर्ड करते हैं। फिर हम एक मनमाना चर चुनते हैं और इसे संभव मानों में से एक में सेट करते हैं। मान लें कि हम केंद्रीय सेल को 1 मान देते हैं।

अब हम प्रतिबंधों को थोड़ा और फैला सकते हैं। यहां केंद्र स्तंभ के लिए मुझे क्या मिला है:


नीले मूल्य अनुमान के बाद हमने जो निष्कर्ष दिए हैं। जैसा कि आप देख सकते हैं, कुछ हुआ। हम कुछ और चर डालते हैं, लेकिन मध्य ऊपरी सेल पर एक नज़र डालते हैं। यह खाली है: इसके डोमेन में प्रतिबंधों को संतुष्ट करने वाले कोई संभावित मूल्य नहीं हैं (5 नहीं हो सकते, क्योंकि यह मान पहले से ही 3 × 3 वर्ग में मौजूद है, और अन्य सभी संख्याएं पहले से ही इस कॉलम में हैं)।

अगर हमें एक खाली डोमेन वाला वैरिएबल मिलता है, तो इसका मतलब है कि हम इसे कोई मान नहीं दे सकते। यही है, पहेली को हल नहीं किया जा सकता है। यह पता चला है कि हमारी धारणा गलत थी ।

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


बहुत सारे काम किए गए हैं, लेकिन वे आगे बढ़ गए हैं। हालांकि, केंद्रीय सेल से 1 को बाहर करने के बाद भी, हम अभी भी एक मृत केंद्र में हैं। यह फिर से और फिर से एक धारणा बनाने का समय है।

यहां बहुत सारे एल्गोरिदम क्रियाएं नहीं हैं। हर बार जब हम प्रतिबंध वितरित नहीं कर सकते, हम एक धारणा बनाते हैं और आगे बढ़ते हैं। और जब से आप एक विरोधाभास का सामना करने से पहले कई बार फंस सकते हैं, तो आप कई बचाए गए राज्यों और मान्यताओं को जमा करेंगे।

वापसी के साथ प्रत्येक पुनरावृत्ति के साथ, आप कम से कम एक चर द्वारा डोमेन को कम करते हैं, ताकि कई रोलबैक के बावजूद, एल्गोरिथ्म अंततः काम पूरा करेगा।

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

हम लहर फ़ंक्शन के पतन पर लौटते हैं

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

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

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

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

नोट : मेरी शर्तें मैक्सिम की शर्तों से भिन्न हैं। वह डोमेन के एरे को एक लहर कहता है, और एक यादृच्छिक टाइल चुनना एक अवलोकन है। यही है, एक सादृश्य क्वांटम यांत्रिकी के साथ तैयार किया गया है। लेकिन तुलना सतही है, इसलिए हम इसे अनदेखा करेंगे।

उपरोक्त सिद्धांतों में कई जोड़ हैं जो एल्गोरिथ्म में अनुग्रह और प्रदर्शन को जोड़ते हैं। लेकिन चलो पहले वर्णित चरणों को देखें।

उदाहरण

मान लें कि हमें चार प्रकार की टाइलों के साथ 3 बाय 3 ग्रिड भरने की आवश्यकता है:


सीमाएं हैं: आसन्न टाइल्स के रंग एक दूसरे से मेल खाना चाहिए।

जैसा कि सुडोकू उदाहरण में, मैं मोनोक्रोम छवियों वाले डोमेन की सामग्री को चित्रित करूंगा। जब डोमेन में केवल एक तत्व बचा है, तो मैं इसे आकार में बढ़ाऊंगा और इसे रंग में दिखाऊंगा।

सबसे पहले, प्रत्येक सेल में, किसी भी प्रकार की टाइलें स्थित हो सकती हैं:


मुख्य WFC लूप चलाएँ। बेतरतीब ढंग से एक सेल का चयन करें, उदाहरण के लिए, ऊपरी बाएं। अब डोमेन में एक टाइल चुनें और अन्य सभी को हटा दें।


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


क्या हम सिकुड़े हुए डोमेन को देखते हुए अन्य टाइलों को अपडेट कर सकते हैं? हाँ! यद्यपि हम पहली टाइल की पसंद के बारे में निश्चित नहीं हैं, हम देखते हैं कि शेष विकल्प दाईं ओर ले जाते हैं। यही है, ऊपरी दाहिने कोने में कुछ प्रकार की टाइलें नहीं डाली जा सकती हैं। नीचे बाएँ कोने के साथ एक ही बात।


हम अब प्रतिबंधों को वितरित नहीं कर सकते हैं, इसलिए हम मुख्य चक्र को दोहराते हैं: सेल चयन, टाइल चयन और वितरण। इस बार हम ऊपरी मध्य सेल लेते हैं:


एक और चक्र: बाएं मध्य कोशिका को लें। केंद्रीय सेल के लिए प्रतिबंधों के प्रसार के बाद, एक संभव मूल्य बना हुआ है।


सामान्य तौर पर, आप विचार को समझते हैं। आप बाकी कोशिकाओं को स्वयं भर सकते हैं।

आप एक साथ प्रयोग करना चाहते हैं और अधिक जटिल इंटरैक्टिव उदाहरण , मेरा सुझाव है कि यह एक ।

सबसे छोटी एन्ट्रापी

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

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

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

$$

$$entropy = — \sum p_{i}log(p_{i})$$

यह डोमेन में टाइल्स का एक योग है जहां $$$p_{i}$- इस टाइल के लिए संभावना।

कुशल कंप्यूटिंग

यद्यपि मैं विवरण में नहीं जाना चाहता, हालांकि, दो अनुकूलन हैं जो मुझे गति को इतना बढ़ाने की अनुमति देते हैं कि उन्हें अनदेखा नहीं किया जा सकता है।

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

इसके अलावा, आसन्न बाधा की जांच करने के लिए, हमें इस प्रश्न का उत्तर देने की आवश्यकता है: "सेल ए के डोमेन में टाइलों को देखते हुए, सेल बी के डोमेन में क्या टाइल संभव हैं यदि कोशिकाएं आसन्न हैं?"

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

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

एल्गोरिथ्म एक्सटेंशन

क्योंकि WFC विवश समस्याओं की अधिक सामान्य समझ पर आधारित है, इसलिए उपयोग की जाने वाली बाधाओं को बदलकर एल्गोरिथ्म का विस्तार करने के कई तरीके हैं।

स्पष्ट परिवर्तनों में से एक यह है कि कोई भी हमें वर्ग कोशिकाओं का उपयोग करने के लिए मजबूर नहीं करता है। डब्ल्यूएफसी हेक्सागोनल कोशिकाओं पर, तीन आयामों या इससे भी अधिक असामान्य सतहों पर महान काम करता है ।




आप अतिरिक्त प्रतिबंध लगा सकते हैं: कुछ टाइल्स को ठीक कर सकते हैं, या कई कोशिकाओं से "मॉड्यूल" बना सकते हैं।

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

में एक अन्य लेख, मैं कैसे आप WFC से सबसे अच्छा परिणाम प्राप्त कर सकते के बारे में बात की थी।

WFC को ओवरलैप करना

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

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


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

आगे क्या होगा?

प्रतिबंधों के साथ समस्याओं का समाधान कंप्यूटर विज्ञान का एक बड़ा और सक्रिय रूप से विकसित क्षेत्र है, और मैंने केवल इस पर छुआ है। WFC - विवश समस्याओं के समाधान के लिए किसी अन्य प्रक्रियात्मक पीढ़ी के एल्गोरिथ्म की तरह - अभी भी नया है। मैं हाल ही के उपयोग के मामलों का अंदाजा लगाने के लिए r / processuralgeneration , #wavefunctioncollapse , @exutumno और @osksta पढ़ने की सलाह देता हूं ।

आप डब्ल्यूएफसी के बारे में मेरा लेख भी पढ़ सकते हैं , मेरे ओपनसोर्स लाइब्रेरी या यूनिटी टूल के साथ प्रयोग कर सकते हैं । प्रक्रियात्मक पीढ़ी पर मेरे अन्य लेखों के बारे में मत भूलना ।