पॉलीगॉन आधारित पथदर्शी

Question

मैंने जावा में एक मूल ग्रिड आधारित ए * पथदर्शीकरण लागू किया है। मैं एक नौवहन मेष/बहुभुज आधारित पाथफाइंडर करना चाहते हैं, लेकिन समस्या यह मेरे पास है यह है:

अगर मैं नारंगी मार्ग नहीं मिला तो मैं इसे पाने के लिए सीधा करने के लिए a funnel algorithm की तरह कुछ इस्तेमाल कर सकते हैं वांछित मार्ग (नीला)। हालांकि, यदि कार्यक्रम प्रत्येक मार्ग, लाल और नारंगी की लागत की गणना करता है, तो यह कहेंगे कि लाल एक सस्ता है। मैं अपने ए * एल्गोरिदम प्रोग्राम कैसे करूं और/या मेरे मैश बनाऊं ताकि ऐसा न हो।

Answer 1

अध्याय 15 Computational Geometry: Algorithms and Applications में वर्णन करता है और वास्तव में इस समस्या का हल: मुक्त अंतरिक्ष एक समलम्बाकार नक्शा द्वारा वर्णित किया जा सकता है, लेकिन नक्शे का उपयोग कर पाया रास्तों जरूरी कम से कम नहीं हैं। अनुशंसित प्रतिनिधित्व (लावेल के Planning Algorithms (Section 6.2.4) में भी चर्चा की गई) एक तथाकथित दृश्यता ग्राफ है, जिसमें किनारों के किनारों को जोड़ते हैं।

छद्म कोड और आंकड़े पुस्तक मुखपृष्ठ से उपलब्ध हैं और Google preview में अध्याय के कुछ भाग भी शामिल हैं।

Answer 2

आपको यह लिंक देखना चाहिए: http://alienryderflex.com/shortest_path/ यह बताता है कि पॉलीगॉन के अंदर सबसे कम पथ की गणना कैसे करें, एक बहुत स्पष्ट स्पष्टीकरण और कोड कार्यान्वयन।

Answer 3

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