c++ - サークル サークル コリジョン 低リソース

Question

低リソースのマシンである Iphone で 60 FPS で衝突する 1000 個の円をテストしたい (わかりました、決して低リソースではありません)。これは些細な問題ではないことを理解しています。私は多くの角度からそれを見て、それを理解するハッカーのチョップを持っていないと感じています. まさに私が実際に祈っている反応です！

この単純な問題に対して、このような質の高い答えを見つけられることを願っています。

たとえば、これは非常に素晴らしいものでした。BAMS という言葉を聞いたことがありませんでした。
https://stackoverflow.com/a/1049285/310678
と私が何も知らなかったもの。


20 30 50 100 200 と言うと簡単ですが、1000 2000 5000 10000 20000 です。
ハイスコ​​アを目指してください。

Answer 1

1. 四分木を使用してスペースを分割し、比較の数を大幅に減らします。ここに素晴らしいチュートリアルがあります。
2. 2 つの円の間の衝突のチェックは非常に高速です。半径 r1 で中心が (x1, y1) の円が、半径 r2 で中心が (x2, y2) の他の円と衝突するのは、次の場合のみです
   euclideanDistance(x1, y1, x2, y2) <= r1 + r2。
3. FPS は、アルゴリズムだけでなく、レンダリング方法にも大きく依存します。ビットマップまたは表示したいものを事前に計算して、後で画面上で「ブリット」(ピクセルをコピー) するだけにしてください。ハードウェアで高速化されたメソッドを使用します。
4. 考えられる最適化: 浮動小数点の代わりに整数演算を使用します。

SOに関する同様の質問。

Answer 2

これが、基本的なソリューションとして思いついたものです。

• テストからのすべての減算に乗ります。
• これにより、実行する必要のあるテストの数が大幅に削減されます。
• 異なるスレッドに簡単に分割できます。
• それは私にパフォーマンスを向上させました。
• それが働いたとき、私は涼しく感じました。

• コンピューターの得意分野に焦点を当てています。

  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);
      }
  
  
  }
  

  これをより速くするための提案はありますか？私はここで混乱していることを知っています.1週間前はイテレータをいじる方法さえ知りませんでした.