मैं एक आरटीएस गेम के लिए पथ खोज पर काम कर रहा हूं, जहां मैं गेम के ग्रिड से नेविगेशन जाल बना रहा हूं।छेद के साथ सबसे तेज़ त्रिकोण एल्गोरिदम?
मैंने मार्चिंग स्क्वायर के समान एक एल्गोरिदम लिखा है जो मानचित्र के चलने योग्य और अवांछनीय क्षेत्रों के बीच सीमाओं को बनाता है और सरल बनाता है। अब मेरे पास "जाल" है जो केवल किनारों से युक्त है। मुझे इस जाल को त्रिभुज करने की आवश्यकता है ताकि अंतिम त्रिभुज में शुरुआती किनारों को शामिल किया जा सके, और फिर मैं नेविगेशन जाल में छेद बनाने के लिए अवांछनीय क्षेत्रों को हटा सकता हूं। उदाहरण के लिए, मैं यह करने की जरूरत है ...
त्रिकोण नक्शे के चलने योग्य क्षेत्रों का प्रतिनिधित्व करते हैं। छेद पहाड़ों या इमारतों जैसे अनचाहे क्षेत्रों का प्रतिनिधित्व करते हैं। जाल को 2 डी माना जा सकता है, क्योंकि ऊंचाई अप्रासंगिक है। यह स्पष्ट रूप से एक बहुत ही सरल मामला है। गेम में नेविगेशन जाल में हजारों शिखर और कई छेद होंगे, लेकिन मैं गतिशील अद्यतन के लिए इसे छोटे हिस्सों में तोड़ सकता हूं।
मैंने डेलयूने त्रिभुज एल्गोरिदम को बाधित किया है, जो पहले अंक के डेलाउने त्रिभुज का निर्माण करता है, और फिर किसी भी त्रिकोण को हटा देता है जो बाधित किनारों को छेड़छाड़ करता है, फिर हटाए गए त्रिकोणों को फिर से त्रिकोणीय करता है।
यह मेरे उद्देश्यों के लिए थोड़ा अनावश्यक लगता है। मेरे जाल को डेलाउने होने की आवश्यकता नहीं है, और इसमें पूरी तरह से बाध्य किनारों की आवश्यकता होती है, इसलिए यदि संभव हो तो मैं अतिरिक्त त्रिकोणों को छोड़ना चाहता हूं। क्या इसके लिए एक बेहतर एल्गोरिदम है? मैंने देखा और देखा है, और केवल बाधित डेलयूने एल्गोरिदम खोजने में सक्षम है। या शायद मैं गलत हूं, और एक बाधित डेल्यूने एल्गोरिदम सबसे अच्छा होगा?
मैंने नेविगेशन जाल पथ खोज से पहले स्क्रैच किया है, लेकिन कभी भी नेविगेशन जाल उत्पन्न नहीं किया था। त्रिकोण एल्गोरिदम मेरे लिए नए हैं। कोई अंतर्दृष्टि?
चूंकि आपके पास त्रिकोणों पर विशेष अनुरोध नहीं हैं, इसलिए [बहुभुज त्रिभुज] (http://en.wikipedia.org/wiki/Polygon_triangulation) जैसे सरल दृष्टिकोण Delaunay से उपयोग करना बेहतर है। – Ante
मैंने कान-क्लिपिंग विधि को देखा, जो डेलाउने त्रिभुज से थोड़ी धीमी प्रतीत होती है, लेकिन मुझे लूपिंग ऑर्डर में अपने चरम को सॉर्ट करने की आवश्यकता होगी, है ना? –
अब मुझे एहसास है कि आपके पास केवल किनारों हैं। प्रत्येक मामले में आपको किनारों को जोड़ने और उन्मुख करने की आवश्यकता होगी, किसी भाग के लिए किसी अन्य भाग के अंदर खोजें (यह जानने के लिए कि यह एक छेद है या नहीं) और फिर छेद के साथ बहुभुज बहुभुज करें। छेद से बहुभुज सीमा या अन्य छेद तक 2 समान किनारों को जोड़कर छेद हटाया जा सकता है। कान क्लिपिंग सरल विधि है और अंतरिक्ष विभाजन (बीएसपी पेड़, चौकोर पेड़, ...) के साथ यह ओ (एन^2) से तेज है। – Ante