मैं एक साधारण टाइल-आधारित 2 डी गेम विकसित कर रहा हूं। मेरे पास एक स्तर है, जो वस्तुओं के साथ आबादी है जो टाइल्स और एक दूसरे के साथ बातचीत कर सकते हैं। टाइलमैप के साथ टकराव की जांच करना आसान है और यह रैखिक जटिलता वाले सभी वस्तुओं के लिए किया जा सकता है। लेकिन अब मुझे वस्तुओं के बीच टकराव का पता लगाना है और अब मुझे हर वस्तु को हर दूसरे वस्तु के खिलाफ जांचना है, जिसके परिणामस्वरूप वर्ग जटिलता है।टकराव का पता लगाने के लिए ओ (एन^2) जटिलता से बचें
मैं वर्ग जटिलता से बचने के लिए चाहते हैं। वस्तुओं के बीच टक्कर पहचान कॉल को कम करने के लिए कोई प्रसिद्ध तरीका है। क्या कोई डेटा-स्ट्रक्चर (जैसे बसपा पेड़ हो सकता है), जिन्हें आसानी से बनाए रखा जाता है और एक समय में कई टकरावों को अस्वीकार करने की अनुमति देता है।
उदाहरण के लिए, स्तर में वस्तुओं की कुल संख्या लगभग 500 है, के बारे में उनमें से 50 एक समय में स्क्रीन पर देखा जाता है ...
धन्यवाद!
क्या आप सभी के लिए टकराव का पता लगाना चाहते हैं या सिर्फ दृश्य वस्तुओं के लिए? –
एचएम। अभी तक यकीन नहीं। मुझे लगता है कि मैं स्क्रीन – SadSido
के बाहर ऑब्जेक्ट्स के साथ टकरावों को अनदेखा कर सकता हूं, उस स्थिति में आप केवल दृश्यमान वस्तुएं एकत्र कर सकते हैं और उन पर टकराव का पता लगा सकते हैं। अभी भी ओ (एन^2) समय जटिलता। –