круг круг столкновение низкие ресурсы

Question

Я хочу протестировать 1000 кругов, сталкивающихся @ 60 FPS на машине с низким ресурсом, Iphone (ну, это никоим образом не низкий ресурс). Я понимаю, что это не тривиальная проблема. Я смотрел на это со многих точек зрения и чувствую, что у меня нет хакеров, чтобы понять это, на самом деле я чувствую, что кто-то может сразу ответить PFFFFFFF 1000, что новобранец. Именно ответ, на который я молюсь, на самом деле!

Надеюсь, я найду такой ответ высокого калибра, такой как это для этой простой проблемы.

Например, это было довольно блестяще, я даже никогда не слышал термин B.A.M.S раньше.
https://stackoverflow.com/a/1049285/310678
и что-то, о чем я ничего не знал.


Легко, когда вы говорите 20 30 50 100 200, но 1000 2000 5000 10000 20000!
Пожалуйста, помогите мне пойти на высокий балл.

Answer 1

1. Используйте quadtree, чтобы разделить пространство и значительно сократить количество сравнений. Here is a nice tutorial.
2. Проверка столкновения между двумя кругами довольно быстро. Круг с радиусом r1 и центром в (x1, y1) сталкивается с другим кругом с радиусом r2 и центром в (x2, y2) тогда и только тогда, когда:
   euclideanDistance(x1, y1, x2, y2) <= r1 + r2.
3. Ваш FPS также будет зависеть не только от алгоритма, но и от способа рендеринга. Постарайтесь прекомпретировать ваше растровое изображение или все, что вы хотите отобразить, чтобы позднее только «blit» (копировать пиксели) на экране. Используйте методы, которые ускоряются аппаратными средствами.
4. Возможная оптимизация: использование целочисленной арифметики вместо плавающей запятой.

Similiar question on SO.

Answer 2

Это то, что я в конечном итоге придумывают для базового раствора.

• Он получает удовольствие от всех вычитаний из теста.
• Это значительно уменьшает количество тестов, которые необходимо выполнить.
• Он может легко разделить на разные темы.
• Это дало мне hela bost to исполнение.
• Это заставило меня чувствовать себя круто, когда оно сработало.

• Основное внимание уделяется компьютеру.

  void Collider::test_one(Actor * actor){ 
      std::sort(this->_stack->begin(),this->_stack->end(),*Collider::sort_x); 
  
      vector<Actor*>::iterator it_target = std::find(this->_stack->begin(),this->_stack->end(),actor); 
      vector<Actor *> possible_x; 
      vector<Actor *> possible_y; 
  
  
  
      int x = 1; 
      int count = 0; 
  
      Actor * one = *(it_target); 
      Actor * two; 
  
  
  
      /* 
      for(int x= 0; x < this->_stack->size(); x++){ 
      cout << this->_stack->at(x)->x_loc << "\n"; 
      } 
      */ 
  
      //cout << "***" << "\n"; 
  
      while (it_target +x != this->_stack->end()) { 
       two = *(it_target+x); 
  
       //cout << one->half_width+two->half_width+one->x_loc << "\n"; 
       //cout << two->x_loc << "\n"; 
  
       if(one->half_width+two->half_width+ one->x_loc > two->x_loc){ 
        possible_x.push_back(two); 
       }else{ 
        break; 
       } 
       count ++; 
       x++; 
      } 
  
      reverse_iterator<vector<Actor*>::iterator> rit_target(it_target); 
      x=0; 
      while (rit_target +x != this->_stack->rend()) { 
       two = *(rit_target+x); 
       if(two->half_width+one->half_width+ two->x_loc > one->x_loc){ 
        possible_x.push_back(two); 
       }else{ 
        break; 
       } 
       count ++; 
       x++; 
      } 
  
      //cout <<count <<" POSSIBLE X \n"; 
  
  
  
      x=1; 
      count=0; 
      std::sort(this->_stack->begin(),this->_stack->end(),*Collider::sort_y); 
      it_target = std::find(this->_stack->begin(),this->_stack->end(),actor); 
  
      /* 
      for(int x= 0; x < this->_stack->size(); x++){ 
       cout << this->_stack->at(x)->y_loc << "\n"; 
      } 
      */ 
  
      while (it_target +x != this->_stack->end()) { 
       two = *(it_target+x); 
  
       //cout << one->half_width+two->half_width+ one->y_loc << " DISTANCE\n"; 
       //cout << two->y_loc << " Y_LOC \n"; 
  
       if(one->half_width+two->half_width+ one->y_loc > two->y_loc){ 
        possible_y.push_back(two); 
       }else{ 
        break; 
       } 
       count ++; 
       x++; 
      } 
  
  
      reverse_iterator<vector<Actor*>::iterator> yrit_target(it_target); 
      x=0; 
      while (yrit_target +x != this->_stack->rend()) { 
       two = *(yrit_target+x); 
       if(two->half_width+one->half_width+ two->y_loc > one->y_loc){ 
        possible_y.push_back(two); 
       }else{ 
        break; 
       } 
       count ++; 
       x++; 
      } 
  
      //cout <<count <<" POSSIBLE Y \n"; 
  
      vector<Actor *> result; 
  
      std::sort(possible_x.begin(),possible_x.end()); 
      std::sort(possible_y.begin(), possible_y.end()); 
  
      std::set_intersection(possible_x.begin(), possible_x.end(),possible_y.begin(),possible_y.end(),back_inserter(result)); 
  
  
      for(int x=0; x< result.size();x++){ 
       //cout << result.at(x) << " COLLISION"; 
       result.at(x)->collision(*actor); 
      } 
  
  
  } 
  

  Любые предложения по его ускорению? Я знаю, что у меня беспорядок здесь, я даже не знал, как гадать с итератором неделю назад.