2010-08-21 13 views
6

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

सबकुछ बेकार ढंग से काम करता प्रतीत होता है लेकिन ऐसा लगता है कि दृष्टि गणना की रेखा एक बाधा है। यह आसान है: यदि एक दुश्मन इकाई मेरी इकाई की किसी भी लॉस रेंज से करीब है तो यह दिखाई देगी।

वर्तमान में मैं एक काफी अनुभवहीन एल्गोरिथ्म का उपयोग करें: हर दुश्मन इकाइयों के लिए मैं यह देखना होगा कि मेरी इकाइयों के किसी भी उसे देखते हैं। यह हे है (एन^2)

तो अगर वहाँ 8 खिलाड़ी हैं और वे 3000 इकाइयों प्रत्येक कि सबसे खराब स्थिति में खिलाड़ी प्रति 3000 * 21000 = 63,000,000 परीक्षण का मतलब होगा की है। जो काफी धीमा है।

अधिक विवरण: यह एक बेवकूफ सरल 2 डी अंतरिक्ष RTS है: कोई ग्रिड, इकाइयों एक सीधे लाइनों के साथ हर जगह आगे बढ़ रहे हैं और वहाँ कोई टकराव तो वे एक-दूसरे के माध्यम से स्थानांतरित कर सकते हैं है। तो सैकड़ों इकाइयां भी एक ही स्थान पर हो सकती हैं।

मैं इस एलओएस एल्गोरिदम को किसी भी तरह तेज़ करना चाहता हूं। कोई विचार?

संपादित करें:

तो अतिरिक्त विवरण:

  • मैं मतलब एक खिलाड़ी भी 3000 इकाइयों हो सकता है।
  • मेरी इकाइयों में रडार हैं ताकि वे सभी दिशाओं की दिशा में समान रूप से हों।
+1

मैं भी http://gamedev.stackexchange.com/ पर इस पूछ की सलाह देते हैं, अगर खेल प्रोग्रामिंग रत्न पुस्तकों में से एक में इस बारे में एक लेख (पहले तीन में से एक, मुझे लगता है।) था आप पहले से नहीं हैं – cHao

+0

3000/8 = 375, एससी 2 में आपके पास अधिकतम 200 भोजन हो सकता है, जो 375 इकाइयों को ठीक से मैक्रो कर पाएगा! :) –

+0

ओहके, आरटीएस = वास्तविक समय रणनीति! – Lazer

उत्तर

7

spatial data structure का उपयोग कुशलता से स्थान के आधार पर इकाइयों को देखने के लिए करें।

ही, यदि आप केवल परवाह है कि क्या एक इकाई दिखाई दे रहा है, लेकिन नहीं है जो इकाई यह देखा, तो आप

for each unit 
    mark the regions this unit sees in your spatial data structure 

करते हैं और हो सकता है:

isVisible(unit) = isVisible(region(unit)) 

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

आपको Muki Haklay's demonstration of spatial indexes उपयोगी भी मिल सकता है।

3

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

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

तो, अगर यह सच है, तो आप दो समूहों में अपने सभी टुकड़ों को विभाजित करना चाहते हैं।

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

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

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

+0

मेरी इकाइयों की दृष्टि दिशात्मक नहीं है उनके पास 'रडार' हैं ताकि वे सभी दिशाओं को समान रूप से देख सकें। अगर एक इकाई बहुत करीब आती है तो वे इसे देखेंगे। – Calmarius

+0

हालांकि अच्छा जवाब है। – Calmarius

+0

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

4

मैं इसे एक ग्रिड के साथ करूँगा। मुझे लगता है कि वाणिज्यिक आरटीएस गेम समस्या का समाधान कैसे करते हैं।

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

अब जब भी एक इकाई एक और करने के लिए दृश्यता की एक क्षेत्र से चला जाता है, एक की जांच करते हैं:

  • एक देखा क्षेत्र के लिए एक अदृश्य से चला गया - खिलाड़ी की दृश्यता पर नजर के लिए इकाई जोड़ें।
  • किसी अदृश्य क्षेत्र से देखा गया - प्लेयर के दृश्यता ट्रैकर से इकाई को हटा दें।
  • अन्य दो मामलों में कोई दृश्यता परिवर्तन नहीं हुआ।

यह तेज़ है लेकिन कुछ स्मृति लेता है। हालांकि, बिटरएरे और पॉइंटर्स के लिस्ट के साथ, स्मृति उपयोग इतना बुरा नहीं होना चाहिए।

+0

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

संबंधित मुद्दे