फैक्टरियो में नया पथ खोजक एल्गोरिथ्म

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

रास्ता खोजो

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

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


इस वीडियो में एल्गोरिथ्म धीमा है ताकि आप बेहतर तरीके से देख सकें कि यह कैसे काम करता है।

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

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

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


यह वीडियो वास्तविकता में एल्गोरिथ्म की गति को दर्शाता है; वह धीमा नहीं है।

ब्लॉक की कमी

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

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

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

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


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

पदानुक्रमित पथ खोज

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

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

इसका समाधान यह है कि सरलीकरण का उपयोग वास्तविक खोज के लिए "अनुशंसा" के रूप में किया जाए। विशेष रूप से, हम इसका उपयोग हेयुरिस्टिक खोज फ़ंक्शन का एक स्मार्ट संस्करण बनाने के लिए करेंगे।

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

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

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

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


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

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