घूमते हुए राक्षस: नक्शे पर समस्याओं से कैसे छुटकारा पाएं

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

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

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

दीवार में चलने वाला

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

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

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

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

बिंगो! "Walk_monster.cpp" की तुलना में कोड फ़ाइल का बेहतर नाम खोजना मुश्किल है। और मुझे लगभग यकीन था कि अब से कोड समस्याओं के बिना बनाया जाएगा।

मुद्दे पर आंदोलन

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

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

लेकिन वास्तव में, हमने डेटा का परीक्षण किया, न कि कोड का। यह बहुत संभावना है कि गति कोड में कीड़े होंगे जो उच्च गुणवत्ता वाले डेटा के साथ भी खराब व्यवहार का कारण बनेंगे।

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

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

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

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

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

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

तेजी से तलाश रैंडम पेड़

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

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

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

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

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


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


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

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

इसलिए मुझे जल्दी से एहसास हुआ कि मुझे एक एल्गोरिथ्म की तलाश करने की ज़रूरत है जो प्रभावी रूप से कम-आयामी स्थानों को पूरी तरह से कवर करे।

3 डी बाढ़ भरना

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

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

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

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

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

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

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


एक काफी सरल प्रयोग के लिए बुरा नहीं है। लेकिन एल्गोरिथ्म मुझे "सीमा प्रतिध्वनि" कहता है। यह प्रभाव मानचित्र के अध्ययन के दौरान निम्नलिखित स्क्रीनशॉट में देखा जा सकता है:


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

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

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

स्थानीय दिशात्मक नमूनाकरण

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

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

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

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

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


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


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

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

किनारों का रुधिर सत्यापन

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

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

यहां तक ​​कि यह सरल योजना बहुत ही उच्च गुणवत्ता वाले, घने नमूने के साथ सीमा के बिना अनावश्यक रूप से पड़ोसी खुले क्षेत्रों में नमूना बनाती है। यहाँ कई सीमाओं वाला एक क्षेत्र है, लेकिन किनारों की जाँच के बिना:


और यहाँ किनारों की जाँच के साथ एक ही क्षेत्र है:


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

त्वरित जीत

यहां तक ​​कि विकास में केवल थोड़ा समय लगाने और काफी सरल कोड बनाने के बावजूद, मैंने यह हासिल किया है कि वॉक मॉन्स्टर पहले से ही काफी उपयुक्त आउटपुट तैयार कर रहा है जो गेम में वास्तविक समस्याओं का पता लगा सकता है। यहाँ उन समस्याओं के उदाहरण हैं जो मुझे एल्गोरिथम के विकास के दौरान मिलीं:


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


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



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

प्रश्न खोलें

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

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

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

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

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

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