बड़ी संख्या में अंतःक्रियात्मक कणों की मॉडलिंग करना

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

सरलता के लिए, हम 2 डी मामले पर विचार करेंगे, कण गोल हैं, कणों की त्रिज्या सभी के लिए समान है।

सामग्री

1. एल्गोरिथ्म अवलोकन
1.1। पूर्ण खोज
1.2। स्वीप और प्रून
1.3। नियमित नेटवर्क
2. कुछ अनुकूलन
2.1। स्वीप और प्रून
2.2। नियमित नेटवर्क
3. निष्पादन की गति की तुलना
4. आवेदन (कार्यक्रम और स्रोत कोड)
5. निष्कर्ष

1. एल्गोरिथ्म अवलोकन

1.1। पूर्ण खोज

यह सबसे आसान और एक ही समय में सभी संभव तरीकों में सबसे धीमा है। कणों के सभी संभावित जोड़े के बीच एक जांच है।

void Update() { for (int i = 0; i < NUM_P; ++i) { for (int j = i + 1; j < NUM_P; ++j) { Collision(&_particles[i], &_particles[j]); } } } 

कठिनाई: O (n ^ 2)

पेशेवरों:
* समझने और लागू करने में बहुत आसान
* विभिन्न कण आकारों के प्रति संवेदनशील नहीं
विपक्ष:
* सब से मंद

1.2। स्वीप और प्रून

इस एल्गोरिथ्म का सार यह है कि पहले हम ओएक्स अक्ष के साथ अपनी बाईं सीमा द्वारा सभी कणों को सॉर्ट करते हैं, और फिर हम प्रत्येक कण को ​​केवल उन लोगों के साथ जांचते हैं जिनकी बाईं सीमा वर्तमान कण की सही सीमा से कम है।

मैं चित्रों में एल्गोरिथ्म के संचालन का वर्णन करने का प्रयास करूंगा।
प्रारंभिक स्थिति:

जैसा कि आप देख सकते हैं, कणों का आदेश नहीं दिया गया है।
कण की बाईं सीमा (X स्थिति कण त्रिज्या घटाकर) को छाँटने के बाद, हमें निम्न चित्र मिलता है:

अब आप हलचल शुरू कर सकते हैं। हम प्रत्येक कण को ​​एक दूसरे कण के साथ जांचते हैं जब तक कि पहले कण की सही सीमा दूसरे कण की बाईं सीमा से बड़ी हो।

एक उदाहरण पर विचार करें।
0 कण 1 और 2 के साथ टकराव की जाँच करेगा:

2 और 3 के साथ 1।
2 केवल 3 के साथ।
3 4, 5 और 6 के साथ टकराव की जाँच करेगा:

मुझे लगता है कि बात स्पष्ट है।

इस एल्गोरिथ्म का मेरा कार्यान्वयन:

 void Update() { qsort(_sap_particles, NUM_P, sizeof(Particle *), CompareParticles); for (int i = 0; i < NUM_P; ++i) { for (int j = i + 1; j < NUM_P && _sap_particles[i]->pos.x + RADIUS_P > _sap_particles[j]->pos.x - RADIUS_P; ++j) { Collision(_sap_particles[i], _sap_particles[j]); } } } 

यह ध्यान देने योग्य है कि यह एल्गोरिथ्म उन मामलों में सबसे प्रभावी है जहां समय के प्रत्येक क्षण के लिए कण आंदोलन छोटा है, क्योंकि छंटाई मुख्य भार को संभालती है, और यह तेज हो जाएगा यदि कण पहले से ही आंशिक रूप से छंटे हुए हैं।

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

कठिनाई: ओ (एन ^ 2) - सबसे खराब स्थिति में, ओ (एन * लॉग (एन)) - औसत मामले में

पेशेवरों:
* लागू करने के लिए आसान है
* विभिन्न कण आकारों के प्रति संवेदनशील नहीं
* अच्छा प्रदर्शन
विपक्ष:
* एल्गोरिथ्म को समझने में थोड़ा समय लगता है

1.3। नियमित नेटवर्क

जैसा कि आप शायद नाम से अनुमान लगाते हैं, एल्गोरिथ्म का सार यह है कि पूरे स्थान को छोटे वर्गों के एक समान नेटवर्क में विभाजित किया गया है, जिसका आकार कण के व्यास के बराबर है। इस नेटवर्क का प्रत्येक वर्ग (सेल) एक सरणी है।
उदाहरण के लिए, यह इस तरह दिख सकता है:

  const int _GRID_WIDTH = (int)(WIDTH / (RADIUS_P * 2.0f)); const int _GRID_HEIGHT = (int)(HEIGHT / (RADIUS_P * 2.0f)); std::vector<Particle *> _grid[_GRID_WIDTH][_GRID_HEIGHT]; 

मुख्य लूप के प्रत्येक पुनरावृत्ति पर, यह नेटवर्क साफ़ हो जाता है और फिर से भर जाता है। भरने एल्गोरिथ्म अत्यंत सरल है: कण सेल सूचकांक कण व्यास द्वारा दोनों निर्देशांक को विभाजित करके और आंशिक भाग को त्यागकर गणना की जाती है। एक उदाहरण:

  int x = (int)(_particles[i].pos.x / (RADIUS_P * 2.0f)); int y = (int)(_particles[i].pos.y / (RADIUS_P * 2.0f)); 

इस प्रकार, प्रत्येक कण के लिए, सूचकांक की गणना करना और इसे इस सूचकांक के साथ सेल में जोड़ना आवश्यक है (एक तत्व को सरणी में जोड़ें)।
अब यह केवल प्रत्येक कोशिका के माध्यम से जाने और उसके आसपास के 8 कोशिकाओं के सभी कणों के साथ अपने सभी कणों की जांच करने के लिए बनी हुई है, जबकि अपने आप को जांचना नहीं भूलती है।

इसे इस तरह किया जा सकता है:

  void Update() { for (int i = 0; i < _GRID_WIDTH; ++i) { for (int j = 0; j < _GRID_HEIGHT; ++j) { _grid[i][j].clear(); } } for (int i = 0; i < MAX_P; ++i) { int x = (int)(_particles[i].pos.x / (RADIUS_P * 2.0f)); int y = (int)(_particles[i].pos.y / (RADIUS_P * 2.0f)); _grid[x][y].push_back(&_particles[i]); } //        } 

कठिनाई: O (n)

पेशेवरों:
* सब से तेज
* लागू करने के लिए आसान है
विपक्ष:
* अतिरिक्त मेमोरी की आवश्यकता
* विभिन्न कण आकार के लिए संवेदनशील (संशोधन आवश्यक)

2. कुछ अनुकूलन

2.1। स्वीप और प्रून

कणों को सॉर्ट करने के लिए किस अक्ष को चुनकर इस एल्गोरिथ्म को थोड़ा बेहतर किया जा सकता है। इष्टतम अक्ष वह है जिसके साथ कणों की सबसे बड़ी संख्या स्थित है।

इष्टतम ओए अक्ष:

इष्टतम OX अक्ष:

2.2। नियमित नेटवर्क

अनुकूलन नंबर 1:
हम नेटवर्क के अधिक कुशल प्रतिनिधित्व का उपयोग करते हैं:

  const int _MAX_CELL_SIZE = 4; const int _GRID_WIDTH = (int)(WIDTH / (RADIUS_P * 2.0f)); const int _GRID_HEIGHT = (int)(HEIGHT / (RADIUS_P * 2.0f)); int _cell_size[_GRID_WIDTH * _GRID_HEIGHT]; Particle *_grid[_GRID_WIDTH * _GRID_HEIGHT * _MAX_CELL_SIZE]; 

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

अनुकूलन №2
मुख्य लूप के प्रत्येक पुनरावृत्ति पर ग्रिड सरणी को पूरी तरह से साफ़ करने के बजाय, हम केवल उसमें परिवर्तन करेंगे जो घटित हुए हैं।
हम नेटवर्क में प्रत्येक सेल के सभी कणों के माध्यम से चलते हैं, नए कण सूचकांक की गणना करते हैं, और यदि यह वर्तमान के बराबर नहीं है, तो हम कण को ​​वर्तमान सेल से हटाते हैं और इसे नए सेल में मुक्त स्थान में जोड़ते हैं।
निष्कासन उसी स्थान पर दर्ज करने से होता है जो एक ही कोशिका से अंतिम कण होता है।
यहाँ मेरा कोड है जो इसे लागू करता है:

  for (int i = 0; i < _GRID_WIDTH * _GRID_HEIGHT; ++i) { for (int j = 0; j < _cell_size[i]; ++j) { int x = (int)(_grid[i * _MAX_CELL_SIZE + j]->pos.x / (RADIUS_P * 2.0)); int y = (int)(_grid[i * _MAX_CELL_SIZE + j]->pos.y / (RADIUS_P * 2.0)); if (x < 0) { x = 0; } if (y < 0) { y = 0; } if (x >= _GRID_WIDTH) { x = _GRID_WIDTH - 1; } if (y >= _GRID_HEIGHT) { y = _GRID_HEIGHT - 1; } //            if (x * _GRID_HEIGHT + y != i && _cell_size[x * _GRID_HEIGHT + y] < _MAX_CELL_SIZE) { _grid[(x * _GRID_HEIGHT + y) * _MAX_CELL_SIZE + _cell_size[x * _GRID_HEIGHT + y]++] = _grid[i * _MAX_CELL_SIZE + j]; //           _grid[i * _MAX_CELL_SIZE + j] = _grid[i * _MAX_CELL_SIZE + --_cell_size[i]]; } } } 

अनुकूलन संख्या 3
हम पड़ोसी 8 कोशिकाओं के साथ सत्यापन का उपयोग करते हैं। यह बेमानी है, यह केवल 4 पड़ोसी कोशिकाओं की जांच करने के लिए पर्याप्त है।
उदाहरण के लिए, इस तरह:

शेष कोशिकाओं के साथ, चेक या तो पहले या बाद में पास होगा:


अनुकूलन №4
आप मेमोरी में डेटा की स्थानीयता बढ़ाकर एल्गोरिथ्म को थोड़ा गति दे सकते हैं। यह प्रोसेसर कैश से डेटा पढ़ने के लिए अधिक बार, और रैम तक कम पहुंच की अनुमति देगा। लेकिन मुख्य लूप के प्रत्येक पुनरावृत्ति पर ऐसा न करें, क्योंकि यह सभी प्रदर्शन को मार देगा, हालांकि, आप इस ऑपरेशन को कर सकते हैं, उदाहरण के लिए, एक बार एक सेकंड, या हर कुछ सेकंड में अगर दृश्य थोड़ा बदलता है।
आप नेटवर्क पर उनके स्थान के अनुसार, मुख्य सरणी में कणों के क्रम को बदलकर स्थानीयता बढ़ा सकते हैं।
यानी पहले 4 कण 0 कोशिकाओं से होंगे, अगले 4 1 से और इतने पर।

3. निष्पादन की गति की तुलना

कण संख्या	ब्रूटफोर्स (एमएस)	स्वीप और प्र्यून (एमएस)	नियमित नेटवर्क (एमएस)
1000	4	1	1
2000	14	1	1
5000	89	4	2
10000	355	10	4
20000	1438	28	7
30000	3200	55	11
100000	12737	140	23

जैसा कि आप तालिका से देख सकते हैं, एल्गोरिदम का रनिंग समय उनकी जटिलता से मेल खाता है, नियमित नेटवर्क लगभग रैखिक रूप से बढ़ता है :)।

4. आवेदन (कार्यक्रम और स्रोत कोड)

http://rghost.ru/35826275

संग्रह में कोडब्लॉक में लिखा गया एक प्रोजेक्ट है, साथ ही लिनक्स के लिए बायनेरिज़ भी है, लेकिन चूंकि एक खिड़की और प्रदर्शन ग्राफिक्स बनाने के लिए, मैंने क्लैनलिब लाइब्रेरी का उपयोग किया, फिर परियोजना को विंडोज के तहत समस्याओं के बिना संकलित किया जाना चाहिए।

कार्यक्रम में प्रबंधन:
नंबर 1 - ब्रूटफोर्स
नंबर 2 - स्वीप और प्रून
नंबर 3 - विनियामक नेटवर्क
बाईं माउस बटन - चलती "धक्का"।

5. निष्कर्ष

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