आस-पास की ऑब्जेक्ट्स एल्गोरिदम

Question

मैं ऐसे गेम पर काम कर रहा हूं जहां स्थान पर वास्तव में एक ऑब्जेक्ट मौजूद हो सकता है (x, y) जहां x और yints हैं। उदाहरण के लिए, (0, 0) पर कोई ऑब्जेक्ट मौजूद हो सकता है या ऐसा नहीं हो सकता है, लेकिन एक साथ कई ऑब्जेक्ट मौजूद होने के लिए यह संभव नहीं है।

मैं यह तय करने की कोशिश कर रहा हूं कि कौन सी एसटीएल कंटेनर समस्या के लिए उपयोग करने के लिए और इस समस्या को हल करने का सबसे अच्छा तरीका है।

असल में, मैं किसी ऑब्जेक्ट और उसके (x, y) स्थान से शुरू करता हूं। लक्ष्य सबसे लंबा निर्धारित करना है, उस वस्तु के आस-पास की वस्तुओं के आधार पर सबसे बड़ा संभव आयताकार। आयत वर्तमान वस्तु के ऊपर और नीचे सभी वस्तुओं का उपयोग करके बनाया जाना चाहिए। यही है, यह सबसे लंबा होना चाहिए कि यह संभवतः प्रारंभिक ऑब्जेक्ट स्थिति पर आधारित हो सकता है।

उदाहरण के लिए, निम्नलिखित मेरी वस्तु ग्रिड का प्रतिनिधित्व करता है और मैं स्थान (3, 4) पर हरे रंग वस्तु के साथ शुरू कर रहा हूँ:

फिर, आयत मैं देख रहा हूँ गुलाबी वर्गों के प्रतिनिधित्व की जाएगी नीचे:

तो,, मैं (3, 4) पर वस्तु के साथ शुरू संभालने उदाहरण की तरह चलता रहा होगा यह जांचने की आवश्यकता है कि क्या वस्तुओं (2, 4), (4, 4), (3, 3), और (3, 5) पर मौजूद हैं या नहीं। यदि किसी भी स्थान पर कोई ऑब्जेक्ट मौजूद है, तो मुझे ऑब्जेक्ट के लिए सबसे बड़ा संभव आयताकार खोजने की प्रक्रिया को दोहराना होगा।

ये वस्तुएं दुर्लभ हैं और गेम की दुनिया भारी है। यह पूरी दुनिया की दुनिया के लिए केवल new 2 डी सरणी के लिए व्यावहारिक प्रतीत नहीं होता है क्योंकि अधिकांश तत्व खाली होंगे। हालांकि, मुझे किसी भी स्थिति में किसी ऑब्जेक्ट की जांच करने के लिए किसी भी स्थिति में अनुक्रमित करने की आवश्यकता है।

इसके बजाय, मैं का उपयोग कर के बारे में सोचा एक std::map तो जैसे:

std::map< std::pair<int, int>, ObjectData> m_objects; 

फिर, जैसा कि मैं आसपास के वस्तुओं जाँच कर रहा हूँ, मैं अपने पाश में map::find() इस्तेमाल कर सकते हैं, पता चल सके कि आसपास के वस्तुओं मौजूद हैं:

if(m_objects.find(std::pair<3, 4>) != m_objects.end()) 
{ 
    //An object exists at (3, 4). 
    //Add it to the list of surrounding objects. 
} 

यदि मैं ऐसा करने का निर्णय लेता हूं तो मैं संभावित रूप से map::find() पर बहुत सी कॉल कर सकता हूं, लेकिन नक्शा पूरी दुनिया की 2 डी सरणी में new से बहुत कम स्मृति लेगा।

क्या किसी को भी एक साधारण एल्गोरिदम पर कोई सलाह है जिसे मैं ढूंढने के लिए उपयोग कर सकता हूं? क्या मुझे std::map का उपयोग करना जारी रखना चाहिए या इस तरह की समस्या के लिए कोई बेहतर कंटेनर है?

Answer 1

यदि संभव हो तो हैशपैप का उपयोग करना एक सुधार होगा। यह आपको ओ (1) की अपेक्षित समय जटिलता के साथ कम से कम अपनी संभावित व्यापक खोजों की अनुमति देगा।

यहां एक धागा है (Mapping two integers to one, in a unique and deterministic way) जो कि दो पूर्णांक को एकसाथ कैसे है इसके बारे में कुछ विस्तार में जाता है।

यदि आपका कंपाइलर सी ++ 11 का समर्थन करता है, तो आप std :: unordered_map का उपयोग कर सकते हैं।यदि नहीं, तो बूस्ट मूल रूप से वही बात है: http://www.boost.org/doc/libs/1_38_0/doc/html/boost/unordered_map.html

Answer 2

आप एक स्थानिक डेटा संरचना पर विचार करना चाहेंगे। यदि डेटा 'स्पैस' है, जैसा कि आप कहते हैं, तो क्वाड्री पड़ोस की खोज करने से आपको बहुत सारी प्रोसेसिंग पावर मिल सकती है। मैं व्यक्तिगत रूप से आर-पेड़ का उपयोग करता हूं, लेकिन यह सबसे अधिक संभावना है क्योंकि मेरे पास एक आर-पेड़ लाइब्रेरी है जिसे मैंने लिखा है और आसानी से आयात कर सकता है।

उदाहरण के लिए, मान लें कि आपके पास 10,000 तत्वों के साथ 1000x1000 ग्रिड है। इस पल के लिए मानते हुए, एक समान रूप से यादृच्छिक वितरण, हम (घनत्व के आधार पर) कहेंगे, उससे कहीं अधिक नहीं। । । या तो आयाम में छूने वाली तीन से पांच वस्तुओं की एक श्रृंखला (इस घनत्व पर, तीन लंबवत उन्मुख वस्तुओं की एक श्रृंखला समय के 0.01% संभावना के साथ होगी)। मान लीजिए कि विचाराधीन वस्तु (x,y) पर स्थित है। (x-5,y-5) से शुरू होने वाली एक विंडो खोज और (x+5,y+5) पर जाने से आपको रैखिक खोज करने के लिए 121 121 तत्वों की एक सूची मिल जाएगी। यदि आपका रेक्ट-पिकिंग एल्गोरिदम नोटिस करता है कि एक लंबा आयताकार बनाना संभव होगा (यानी यदि 11x11 बाउंडिंग बॉक्स के किनारों पर विचार करने वाला एक रेक्ट स्पर्श करता है), तो मूल की एक दिशा में 5x5 क्षेत्र के लिए विंडो खोज दोहराएं। आवश्यकतानुसार दोहराएं।

यह निश्चित रूप से केवल तभी काम करता है जब आपके पास अत्यधिक स्पैस डेटा होता है। आर-पेड़ को अनुकूलित करने के लायक हो सकता है जैसे पत्तियां एक assoc हैं। डेटा संरचना (यानी Int -> Int -> Object), लेकिन उस बिंदु पर केवल एक समाधान खोजने के लिए सबसे अच्छा है जो घनत्व डेटा पर काम करता है।

मैं इस पर अधिक सोच रहा हूं; कहीं कहीं कहीं अधिक सरल समाधान की संभावना है।

आर पेड़ पर कुछ संदर्भों:

• The original paper, मूल एल्गोरिदम के लिए।
• The Wikipedia page, जो इस विषय पर कुछ सभ्य अवलोकन है।
• The R-tree portal, आर-पेड़ से संबंधित डेटासेट और एल्गोरिदम के लिए।

यदि मैं कभी इसे थोड़ा साफ करने के लिए घूमता हूं तो मैं इसे अपने स्वयं के आर-पेड़ कार्यान्वयन (सार्वजनिक डोमेन) के लिंक के साथ संपादित कर दूंगा।

Answer 3

प्रत्येक ग्रिड स्थान पर आपको कितना डेटा स्टोर करने की आवश्यकता है? यदि आप केवल झंडे की तलाश में हैं जो पड़ोसियों को इंगित करता है कि आपके पास कम से कम दो "कम तकनीक" समाधान हैं

ए) यदि आपका ग्रिड स्पैस है, तो प्रत्येक वर्ग एक पड़ोसी सूची कैसे रखता है? तो प्रत्येक वर्ग जानता है कि पड़ोसी वर्गों पर कब्जा कर लिया गया है। स्क्वायर पर कब्जा या खाली होने पर सूचियों को बनाए रखने के लिए आपके पास कुछ काम होगा। लेकिन पड़ोसी सूचियों का मतलब है कि आपको

बी पर ग्रिड मानचित्र की आवश्यकता नहीं है b) यदि ग्रिड नक्शा स्थान वास्तव में केवल अंक हैं, तो प्रति बिट 1 बिट का उपयोग करें। परिणाम मानचित्र 8x8 = 64 गुना छोटा होगा जो प्रत्येक ग्रिड बिंदु के लिए बाइट्स का उपयोग करता है। बिट ऑपरेशन तेजी से हल्का कर रहे हैं। एक 10,000x10,000 नक्शा 100,000,000 बिट्स या 12.5 एमबी (लगभग)

Answer 4

यह संदिग्ध रूप से होमवर्क समस्या की तरह लगता है (क्योंकि यह अजीब स्थिति है "आयत वर्तमान वस्तु के ऊपर और नीचे सभी वस्तुओं का उपयोग करके बनाई जानी चाहिए "यह समाधान तुच्छ बनाता है)। लेकिन मैं इसे एक शॉट दे दूंगा। मैं सुविधा के लिए "ऑब्जेक्ट" के बजाय "पिक्सेल" शब्द का उपयोग करने जा रहा हूं।

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

संगत आकारों को संग्रहित करने का एक विशिष्ट नुकसान यह है कि यदि आपकी पिक्सेल-ऑब्जेक्ट्स चारों ओर घूम रहे हैं (उदाहरण के लिए यदि वे एक रोग्वेलिक गेम में राक्षसों का प्रतिनिधित्व करते हैं), तो मुझे यकीन नहीं है कि संघ-खोज डेटा संरचना वृद्धिशील अपडेट का समर्थन करती है। आपको प्रत्येक "फ्रेम" पर यूनियन-खोज चलाने पड़ सकते हैं, जो बहुत खराब होगा।

वैसे भी ... चलो बस कहना है कि आप std::unordered_map<std::pair<int,int>, ObjectData*> का उपयोग कर रहे हैं, क्योंकि यह मेरे लिए बहुत उचित लगता है। (आप निश्चित रूप से संकेत दिए गए अपने नक्शे में, वास्तविक वस्तुओं, संग्रहीत करना चाहिए लगभग नहीं है क्योंकि चारों ओर को कॉपी उन सभी वस्तुओं को संकेत को कॉपी की तुलना में बहुत धीमी होने जा रहा है।)

typedef std::pair<int, int> Pt; 
typedef std::pair<Pt, Pt> Rectangle; 
std::unordered_map<Pt, ObjectData *> myObjects; 

/* This helper function checks a whole vertical stripe of pixels. */ 
static bool all_pixels_exist(int x, int min_y, int max_y) 
{ 
    assert(min_y <= max_y); 
    for (int y = min_y; y <= max_y; ++y) { 
     if (myObjects.find(Pt(x, y)) == myObjects.end()) 
      return false; 
    } 
    return true; 
} 

Rectangle find_tallest_rectangle(int x, int y) 
{ 
    assert(myObjects.find(Pt(x,y)) != myObjects.end()); 
    int top = y; 
    int bottom = y; 
    while (myObjects.find(Pt(x, top-1) != myObjects.end()) --top; 
    while (myObjects.find(Pt(x, bottom+1) != myObjects.end()) ++bottom; 
    // We've now identified the first vertical stripe of pixels. 
    // The next step is to "paint-roller" that stripe to the left as far as possible... 
    int left = x; 
    while (all_pixels_exist(left-1, top, bottom)) --left; 
    // ...and to the right. 
    int right = x; 
    while (all_pixels_exist(right+1, top, bottom)) ++right; 
    return Rectangle(Pt(top, left), Pt(bottom, right)); 
}