c++ - 圈圈碰撞资源少

Question

我想在一台低资源机器上测试 1000 个圈子在 60 FPS 上碰撞，一台 Iphone（好吧，这绝不是低资源）。我明白这不是一个小问题。我从多个角度看了它，觉得我没有黑客的能力来弄清楚它，实际上我觉得有人可能会立即回应 PFFFFFFF 1000 多么菜鸟。事实上，这正是我所祈求的回应！

我希望我能为这个简单的问题找到这样一个高质量的答案。

例如，这非常出色，我以前从未听说过 BAMS 一词。
https://stackoverflow.com/a/1049285/310678
和我一无所知的东西。

当您说 20 30 50 100 200 而说 1000 2000 5000 10000 20000 时，这很容易！
请帮我争取高分。

score 2 · Accepted Answer

使用四叉树来划分空间并显着减少比较次数。这是一个很好的教程。
检查 2 个圆圈之间的碰撞非常快。半径为 r1 且圆心在 (x1, y1) 的圆与其他半径为 r2 且圆心在 (x2, y2) 的圆碰撞当且仅当：
euclideanDistance(x1, y1, x2, y2) <= r1 + r2。
您的 FPS 不仅很大程度上取决于算法，还取决于渲染方式。尝试预先计算您的位图或您想要显示的任何内容，以便稍后仅在屏幕上“blit”（复制像素）。使用硬件加速的方法。
可能的优化：使用整数算法而不是浮点数。

关于SO的类似问题。

score 0 · Accepted Answer

这就是我最终提出的基本解决方案。

它可以从测试中扣除所有减法。
它极大地减少了需要完成的测试数量。
它可以很容易地分成不同的线程。
它给了我一个很好的表现。
它工作时让我感觉很酷。

它专注于计算机擅长的领域。

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


}

关于加快速度的任何建议？我知道我这里一团糟，一周前我什至不知道如何使用迭代器。

c++ - 圈圈碰撞资源少

2 回答 2

Related

Reference