StarCraft और StarCraft 2 में मार्ग खोज एल्गोरिदम की तुलना

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



स्टारक्राफ्ट 2 पाथफाइंडिंग के यांत्रिकी का अनुवाद

मार्ग खोज

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



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



BroodWar में रास्ते खोजना थोड़ा अलग तरह से काम करता है। एक आइसोमेट्रिक मानचित्र पर, एक इकाई केवल 8 दिशाओं में आगे बढ़ सकती है, और आपको एल्गोरिथ्म पर बहुत अधिक प्रोसेसर समय खर्च नहीं करना चाहिए। इसलिए, इस स्थिति में मार्ग खोज एल्गोरिथ्म ए * एल्गोरिथ्म (ए-स्टार - वेव एल्गोरिथ्म ) पर आधारित हो सकता है और, इकाइयों की आवाजाही को देखते हुए, मुझे लगता है कि यह धारणा सच्चाई के बहुत करीब है।





BroodWar में ए-स्टार एल्गोरिथ्म का अनुप्रयोग





इस स्थिति में खिलाड़ी क्या देखता है



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





यदि वे 180 डिग्री घुमाए जाते हैं, तो मुतालिस अलग-अलग संदर्भ बिंदु चुनते हैं





बड़ी संख्या में मुख्य बिंदुओं को सेट करके ब्रोडवर्ड एल्गोरिथ्म का अनुकरण करने का प्रयास



अंतर यह है कि ब्रूडवेयर में इकाइयां, ए * एल्गोरिदम, समान कुंजी बिंदुओं के अनुसार, चरण दर चरण चलती हैं। और StarCraft 2 में, प्रत्येक इकाई के लिए एक अलग मार्ग की गणना की जाती है और न्यूनतम संख्या का उपयोग किया जाता है।

टक्कर संरक्षण

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



StarCraft 2 में, इकाइयां टकराव से बचती हैं और मार्ग बदलकर बाधाओं से बचती हैं। यह मानना ​​तर्कसंगत है कि प्रत्येक इकाई में एक टक्कर सेंसर होता है, जो सही समय पर बाधा को बायपास करने के लिए संकेत देगा। यह इकाइयों को एक साथ विलय करने की अनुमति देता है या इसके विपरीत एक नया पथ या गति की हानि की गणना के बिना अलग करने के लिए। सबसे खराब स्थिति में, इकाइयां टकराव की त्रिज्या को अनदेखा कर सकती हैं, जिससे चिकनी आंदोलन और बेहतर समग्र आंदोलन दक्षता प्रदान की जा सकती है।





OpenSteer : बाधाओं से बचने के लिए एक खुला स्रोत पुस्तकालय





BroodWar का Zerg तय करता है कि पहले कौन दौड़ता है। और StarCraft 2 में, ज़गुर पहले से प्रकट होना शुरू हो जाता है।



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





फ्लैश बनाम एफर्ट (OSL 3rd फाइनल गेम)। फ्लैश की मरीन काफी अलग हैं। इसलिए, फ्लैंक से चलने वाले ज़र्गलिंग ने उन्हें मार दिया। यह फ़्लैश एक जीत की लागत

निष्कर्ष

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



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



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



नोट: लेख SC2 की आधिकारिक रिलीज से पहले लिखा गया था