3 डी अंतरिक्ष में एक रास्ता खोजने के लिए एक एकता संपत्ति विकसित करने का अनुभव

सुंदर एल्गोरिदम टीम में आपका स्वागत है!

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

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

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


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

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

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


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

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

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


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


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

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


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


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


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


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

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

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

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

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

हमें उम्मीद है कि यह सामग्री किसी को अपने प्रोजेक्ट को फिनिश लाइन पर लाने में मदद करेगी।