पृथक गेम फ्रेम

Question

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

जबकि मेरा ए * संभवतः एक धुन को थोड़ा सा खर्च कर सकता है, मुझे यह भी पता है कि पथ को गति देने का एक और तरीका है कि कई गेम फ्रेमों पर पथदर्शी को विभाजित करें। यह पूरा करने के लिए एक अच्छी विधि क्या है?

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

अधिक जानकारी: यह एक रेक्टाइलिनर ग्रिड पर ए * है, और सी # और एक्सएनए फ्रेमवर्क का उपयोग करके प्रोग्राम किया गया है। मैं पथिंग की आवश्यकता में 50-75 इकाइयों तक संभावित रूप से होने की योजना बना रहा हूं।

धन्यवाद।

Answer 1

अनुमापकता

वहाँ इस स्थिति के लिए अनुकूलन करने के कई तरीके हैं। एक के लिए, आपको एकाधिक गेम फ्रेम में विभाजित नहीं होना पड़ सकता है। कुछ हद तक ऐसा लगता है कि स्केलेबिलिटी मुद्दा है। 100 इकाइयां कम से कम 100 गुना अधिक 1 इकाई से अधिक महंगी होती हैं।

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

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

बहु फ्रेम गणना

फ्रेम के बीच गणना विभाजित करने के लिए कोशिश कर रहा है के रूप में, वहाँ कुछ दृष्टिकोण मैं बंद हाथ के बारे में सोच सकते हैं।

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

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

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

पथों को हल करने के लिए एकल-थ्रेडेड, स्वैच्छिक दृष्टिकोण के साथ भी, यदि खेल स्थिति में परिवर्तन फ्रेम से फ्रेम के पथ की वैधता को प्रभावित करते हैं, तो आप फ्रेम पर वर्तमान समाधान को फिर से सत्यापित करने के लिए दौड़ने जा रहे हैं फ्रेम आधार के लिए।

उपयोग आंशिक समाधान

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

Answer 2

यदि आपकी इकाइयां एक ही गंतव्य के लिए सभी मार्ग हैं, तो यह उत्तर लागू हो सकता है, अन्यथा, यह केवल विचार के लिए भोजन होगा।

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

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

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