छद्म सूची याद किए बिना छद्म-यादृच्छिक क्रम में एक सूची में इटरेटिंग

Question

a game में, हम इकाइयों का चयन करने के लिए 'colour picking' नामक तकनीक का उपयोग करते हैं।

इसका मतलब है कि प्रत्येक दृश्य इकाई को एक अद्वितीय रंग दिया जाता है।

यहाँ एक दृश्य रंग पिकिंग के लिए तैयार की एक उदाहरण है:

कुछ उपयोगकर्ताओं को 16-बिट प्रदर्शित करता है हो सकता है के रूप में, इन रंगों रेंज 0..64K में हो सकता है।

हालांकि, अगर हम इकाइयों को वृद्धिशील रंग देते हैं उदा। यूनिट 0 0 है, यूनिट एन एन है तो मनुष्यों को डिबग करने के लिए रंग बहुत कठिन होते हैं। इकाइयां लगभग अलग-अलग हैं।

हम इकाइयों को अद्वितीय और विशिष्ट रंग देना चाहते हैं।

हम वर्तमान में टकराव की जांच के लिए प्रयुक्त रंगों को संग्रहीत करने के लिए एक बाइनरी पेड़ (सी ++ map) का उपयोग करके एक निश्चित चरण में वृद्धि कर रहे हैं। यह कम अंत हार्डवेयर पर एक प्रदर्शन समस्या है। यहां तक ​​कि यदि यह हैश तालिका थी और string का उपयोग करने से बचा, तो गेम फ्रेम में अस्थायी स्मृति आवंटन को फेंक दिया जाना चाहिए। इसलिए कोड को अनुकूलित करने के बजाय इसे अनुकूलित करने के बजाय, मैं यह जानना चाहता हूं कि इतिहास को पूरी तरह से बनाए रखने से बचने के तरीके हैं या नहीं।

क्या 0.संख्याओं पर पुनरावृत्ति करने का कोई तरीका है। एक बड़े चरण या यादृच्छिक रूप से 64.6 संभावित मानों का उपयोग किया जाता है, और टकराव से बचने के लिए पहले से आवंटित रंगों के इतिहास का उपयोग करने से बचते हैं?

^{(यह एक से अधिक 64K स्क्रीन पर दिखाई इकाइयों हम उस मामले को संभालने के लिए की जरूरत नहीं है कि देखते हैं कि इतना संभावना नहीं है!)}

Answer 1

मेरे कोशिश:

1. उठाओ अपने वांछित सीमा के पास एक prime number (64,007 यहाँ एक अच्छे उम्मीदवार है)।
2. इस संख्या के primitive roots modulo p खोजें।

3. एक "मध्यम श्रेणी" आदिम रूट चुनें (43067 एक अच्छा उम्मीदवार है)।

   class Sequence 
   { 
   public: 
       uint32_t get() const {return state;} 
       void advance() { state = (state * k)%p;} 
       void reset() { state = k; } 
   private: 
       uint32_t state = 43067; 
       const uint32_t k = 43067; 
       const uint32_t p = 64007; 
   }; 
   

इस चक्र) रेंज [1, 64,007 ठीक एक बार में सभी नंबरों को, एक छद्म यादृच्छिक फैशन में।

Answer 2

आप बस step_size ले सकता से विभाजित कुल उपलब्ध रंग होने के लिए कुल इकाइयां, और उसके बाद प्रत्येक इकाई के रंग के रूप में (unit_index * step_size) का उपयोग करें?

Answer 3

सबसे पहले, रंगीन राज्यों को स्टोर करने के लिए बाइनरी का उपयोग करें (1-प्रयुक्त, 0-अप्रयुक्त)। 2^16 = 65536 (राज्यों)। यदि हम एक रंग के लिए 1 बिट का उपयोग करते हैं, तो 65536/8 = 8192 बाइट की आवश्यकता होती है।
अगला प्रश्न यह है कि इन बाइट्स को कैसे प्रबंधित करें। मैं एक पेड़ संरचना का सुझाव देता हूं: इन 8192 बाइट्स पर, एक और (8192/8 =) 1024 बाइट्स की आवश्यकता होती है, इन ऊपरी बाइट्स में प्रत्येक बिट 8192 बाइट्स में एक बाइट का प्रतिनिधित्व करता है, यदि निम्न बाइट्स में से कोई सभी 1 है, इसका ऊपरी बिट है 1.
यह नियम ऊपरी और ऊपरी विस्तारित कर सकता है: 8192 -> 1024 -> 128 ... आखिरकार, 1 बाइट (हालांकि पूरी तरह से उपयोग नहीं किया जाता है)।
इस संरचना का उपयोग करने के लिए, आप रूट बाइट से कई बार 0.77 में यादृच्छिक संख्या उत्पन्न कर सकते हैं, यदि इसका बिट 1 है, तो पुनः प्रयास करें; यदि इसका 0, निचला बाइट तक नीचे है, तो निम्न कार्य बाइट तक पहुंचने तक इन क्रियाओं को दोहराएं।
इसके अतिरिक्त, आप इस पेड़ को एक सरणी में बना सकते हैं: बस हेपसोर्ट में ढेर की तरह। (कुछ खाली इकाइयों के साथ)।

ऐपेंड: एक int16 को एक बार एक बाइट से नीचे एक रंग की आवश्यकता होती है, आपको तीन-बिट बाइनरी संख्या मिलती है, उन्हें बाएं से दाएं रंग संख्या में जोड़ दें: int16। (रूट बाइट केवल 2 राज्यों का प्रतिनिधित्व करता है, और केवल 1-बिट बाइनरी संख्या उत्पन्न करता है, इसका फॉर्म 111111 है?

Answer 4

मुझे वास्तव में समस्या दिखाई नहीं दे रही है। जैसा कि मैंने टिप्पणियों में लिखा था, आपको केवल 128K की आवश्यकता है एक क्रमपरिवर्तन स्टोर करें [0 ..64 के), और आपको मुख्य लूप के अंदर किसी भी आवंटन की आवश्यकता नहीं है।

class ColorPicker { 
    std::array<uint16_t, 65536> colors; 
    uint16_t idx; 

    public: 
    ColorPicker() : idx(0) 
    { 
     std::iota(colors.begin(), colors.end(), 0); 
     std::random_shuffle(colors.begin(), colors.end()); 
    } 

    uint16_t next_color() 
    { 
     return colors[idx++]; 
    } 
}; 

आप केवल इन संरचनाओं में से एक की जरूरत है: यहाँ सी ++ 11 में स्टेटफुल रंग की दुकान है (पुराने सी ++, एक vector या new[] उपयोग करें)। अब, जब भी आप एक नई इकाई बनाते हैं, तो पर ColorPicker पर कॉल करें और इसे इकाई पर एक विशेषता के रूप में संग्रहीत करें।

यह समाधान रंगों के बावजूद चक्र होगा। यदि यह वांछित नहीं है, तो प्रत्येक बार जब सूचकांक शून्य पर घूमता है तो random_shuffle करें।

Answer 5

ऐसा लगता है कि यह महत्वपूर्ण है कि एक दूसरे के करीब इकाइयों के बीच का अंतर काफी अधिक है, यानी मैं इकाइयों की निकटता को ध्यान में रखने के लिए कुछ तरीके से आने का प्रयास करूंगा।

उदाहरण के लिए, आप इकाइयों के एक्स/वाई निर्देशांक को ध्यान में रख सकते हैं जैसे समन्वय जो एक-दूसरे के करीब होते हैं, उच्च विपरीत वाले रंग प्राप्त करते हैं, कम विपरीत केवल उन इकाइयों के लिए उपयोग किया जाता है जो पर्याप्त रूप से दूर हैं।

एक पहला शॉट 256 रंगों का एक सरल सरणी a होना चाहिए, जैसे a[n] और a[n+1] के बीच एक बड़ा अंतर है। इसके बाद आप सरणी में इंडेक्स के रूप में अपने एक्स और/या वाई समन्वय मॉड्यूलो 256 का उपयोग कर इकाइयों का रंग चुन सकते हैं। इस तरह, आपको उन इकाइयों के लिए रंगों का पुन: उपयोग किया जाएगा जो कम से कम 256 पिक्सेल (या जो भी मीट्रिक आप उपयोग कर सकते हैं) अलग हैं, लेकिन इकाइयों के लिए अलग-अलग रंग जो एक दूसरे के बहुत करीब हैं।