एक अच्छा 2 डी ग्रिड-आधारित पथ-खोज एल्गोरिदम क्या है?

Question

मैं वर्तमान में HTML5 < कैनवास > तत्व का उपयोग कर जावास्क्रिप्ट में एक 2 डी गेम लिख रहा हूं। यह बहुत अच्छी तरह से आ रहा है, लेकिन मैं एक समस्या में भाग गया है।

मेरे खेल के लिए स्तर का डिज़ाइन ग्रिड – में विभिन्न स्थानों पर कब्जा करने वाली विभिन्न बाधाओं के साथ एक ग्रिड (इसलिए एक सेल से उत्तर/दक्षिण/पूर्व/पश्चिम सेल में जाने वाली पथ लागत 1 है) एक भूलभुलैया की तरह, लेकिन बहुत अधिक विग्गल रूम के साथ। प्रत्येक व्यक्तिगत स्तर 400 × 200 कोशिकाओं के क्रम में है।

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

Answer 1

ए * एक बहुत आम 2 डी पथदर्शी एल्गोरिदम है। यदि पथदर्शी अपरिचित है, तो यह आपके सिर को लपेटने में थोड़ा समय लग सकता है, लेकिन यह बहुत जटिल नहीं है। आप किसी और के उदाहरण कोड को देख सकते हैं जिसे आपके इरादे से अधिक जटिल एप्लिकेशन के लिए विकसित किया गया है। a good tutorial for understanding the algorithm here है।

Answer 2

इसे देखें https://github.com/qiao/PathFinding.js इसमें बहुत सारे डेमो और पथ खोजने वाले अल्गोथम्स हैं।

Answer 3

EasyStar.js एक अच्छी लग रही लाइब्रेरी है जो आप जो करना चाहते हैं वह प्रतीत होता है। मैंने इसे स्वयं नहीं उपयोग किया है, लेकिन प्रोजेक्ट के जिथब पेज पर प्रलेखन बहुत अच्छा दिखता है, और शायद यह है कि मैं आपकी स्थिति में क्या चुनूँगा।