डिजस्ट्रा का एल्गोरिदम प्रारंभिक स्थिति से पहुंचने वाले ग्राफ में सभी नोड्स के सबसे छोटे पथ की गणना करता है। आपके औसत आधुनिक खेल के लिए, यह अनावश्यक और अविश्वसनीय रूप से महंगा दोनों होगा।
आप 2 डी और 3 डी के बीच एक अंतर बनाते हैं, लेकिन यह ध्यान देने योग्य है कि किसी भी ग्राफ-आधारित एल्गोरिदम के लिए, आपकी खोज स्थान के आयामों की संख्या में कोई फर्क नहीं पड़ता है। जिस वेब पेज से आपने लिंक किया है वह मार्ग बिंदु ग्राफ और नेविगेशन मेस पर चर्चा करता है; दोनों ग्राफ-आधारित हैं और सिद्धांतों में किसी भी आयाम में काम कर सकते हैं। यद्यपि वहां कोई "विशिष्ट स्क्वायर रिक्त स्थान" नहीं है, वहां एआई स्थानांतरित हो सकते हैं और जो गेम डिजाइनरों द्वारा ध्यान से रखा गया है उस स्थान पर "स्लॉट" अलग करें।
निष्कर्ष निकालना, ए * वास्तव में 2 डी गेम में जितना अधिक 3 डी गेम में उपयोग करने के लिए एल्गोरिदम है। चलो देखते हैं कि ए * कैसे काम करता है:
- शुरुआत में, आप अपनी वर्तमान स्थिति के समन्वय और अपनी लक्षित स्थिति को जानते हैं। आप अपने गंतव्य के लिए दूरी का आशावादी अनुमान बनाते हैं, उदाहरण के लिए प्रारंभ स्थिति और लक्ष्य के बीच सीधे लाइन की लंबाई।
- ग्राफ में आसन्न नोड्स पर विचार करें। यदि उनमें से एक आपका लक्ष्य है (या इसमें नेविगेशन जाल के मामले में यह शामिल है), तो आप कर चुके हैं।
- प्रत्येक आसन्न नोड के लिए (एक नेविगेशन जाल के मामले में, इस हो सकता है बहुभुज या मध्य के कुछ अन्य प्रकार की geometric center), अनुमान लगाने के दो उपायों के राशि के रूप में वहाँ के साथ यात्रा के लिए जुड़े लागत: जिस मार्ग से आप यात्रा कर चुके थे, उसकी लंबाई दूर है, और दूरी का एक और आशावादी अनुमान जो अभी भी को कवर करना होगा।
- पिछले विकल्पों से अपने विकल्पों को अपने अनुमानित लागत द्वारा अपने सभी विकल्पों के साथ क्रमबद्ध करें, और सबसे कम अनुमानित लागत वाले विकल्प को चुनें। चरण 2 से दोहराएं।
कुछ विवरण हैं जिन पर मैंने चर्चा नहीं की है, लेकिन यह देखने के लिए पर्याप्त होना चाहिए कि ए * मूल रूप से आपकी जगह के आयामों की संख्या से स्वतंत्र कैसे है। आपको यह भी देखने में सक्षम होना चाहिए कि यह निरंतर रिक्त स्थान के लिए क्यों काम करता है।
कुछ निकट से संबंधित एल्गोरिदम हैं जो मानक ए * खोज में कुछ समस्याओं से निपटते हैं।उदाहरण के लिए रिकर्सिव सर्वश्रेष्ठ-प्रथम खोज (आरबीएफएस) और सरलीकृत मेमोरी-बाध्य ए * (एसएमए *) को कम स्मृति की आवश्यकता होती है, जबकि वास्तविक समय ए * (एलआरटीए *) सीखने से एजेंट को पूर्ण पथ की गणना करने से पहले स्थानांतरित करने की अनुमति मिलती है। मुझे नहीं पता कि इन एल्गोरिदम वास्तव में वर्तमान खेलों में उपयोग किए जाते हैं या नहीं।
कोनों के गोलाकार के लिए, यह दूरी रेखाओं (जहां कोनों को गोलाकार आर्क द्वारा प्रतिस्थापित किया जाता है) के साथ किया जा सकता है, या किसी भी प्रकार के spline पूर्ण-पथ चिकनाई के लिए फ़ंक्शन के साथ किया जा सकता है।
इसके अलावा, एल्गोरिदम संभव है कि खोज स्थान पर एक ढाल पर भरोसा करें (जहां अंतरिक्ष में प्रत्येक बिंदु एक मान के साथ जुड़ा हुआ है), ग्राफ के बजाए। ये शायद अधिकांश खेलों में लागू नहीं होते हैं क्योंकि वे अधिक समय और स्मृति लेते हैं, लेकिन किसी भी तरह से जानना दिलचस्प हो सकता है। उदाहरणों में विभिन्न hill-climbing algorithms (जो डिफ़ॉल्ट रूप से रीयल-टाइम हैं) और potential field विधियां शामिल हैं।
प्रक्रियात्मक रूप से एक सतत स्थान से ग्राफ प्राप्त करने के तरीके भी मौजूद हैं, उदाहरण के लिए cell decomposition, Voronoi skeletonization और probabilistic roadmap skeletonization। पूर्व नेविगेशन जाल के साथ कुछ संगत उत्पादन करेगा (हालांकि इसे हाथ से तैयार किए गए नेविगेशन जाल के रूप में समान रूप से कुशल बनाना मुश्किल हो सकता है) जबकि बाद के दो उपज के परिणाम जो वेपॉइंट ग्राफ की तरह अधिक होंगे। इनमें से सभी, साथ ही साथ संभावित क्षेत्र विधियों और ए * खोज, रोबोटिक्स के लिए प्रासंगिक हैं।
सूत्रों का कहना है:
यह [खेल विकास] (http के लिए एक अच्छा सवाल होगा: // gamedev। stackexchange.com) साइट। – Matthias