circle circle collision low resources

Question

I want to test 1000 circles colliding @ 60 FPS on a low resource machine, an Iphone( Ok, it is not by any means low resource ). I understand this is not a trivial problem. I have looked at it from many angles and feel I do not have the hacker chops to figure it out, in fact I feel some one might immediately respond with PFFFFFFF 1000 what a rookie. Exactly the response I am praying for in fact!

I hope I can find such a high caliber answer such as this for this simple problem.

For example this was quite brilliant, I had never even heard the term B.A.M.S before.
https://stackoverflow.com/a/1049285/310678
and something I knew nothing about.

Its easy when you say 20 30 50 100 200 but a 1000 2000 5000 10000 20000!
Please Help me go for high score.

efficient high-scale colission detection almost always comes down to finding a good data structure to store all objects in, one that enables you to skip comparisons of most objects at once (e.g. octrees). — KillianDS, Mar 17 '13 at 10:14
Seems a bit broad for a question, but for circles, it's very easy to see if they're colliding - distance formula between their centers is greater than or equal to their summed radiuses. Then you just have to figure out how you choose what circles actually need to be checked. Partition the space, store in something like a k-d tree, and run collision detection for possible collisions. — Tawnos, Mar 17 '13 at 10:19
Lets say then we are limiting the question to a single frame with 50 000 circles in it. Of course that is a way to calculate it but there must be other more computery ways. I was wondering just now how it would work out to try to keep an array of sorted pointers by location. If you calculated the collisions out then you could just run down the pointers and exclude anything beyond the collision but that would be nuts. — Tegra Detra, Mar 17 '13 at 10:23

score 2 · Answer 1 · edited May 23 '17 at 12:21

Use a quadtree to divide your space and significantly reduce the number of comparisons. Here is a nice tutorial.
Checking collision between 2 circles is pretty fast. Circle with radius r1 and center in (x1, y1) collides with other circle with radius r2 and center in (x2, y2) if and only if:
euclideanDistance(x1, y1, x2, y2) <= r1 + r2.
Your FPS will also depend a lot not only on the algorithm, but also on a way of rendering. Try to precompute your bitmap or whatever you want to display, to later only "blit" (copy pixels) on the screen. Use methods which are hardware accelerated.
Possible optimization: using integer arithmetics instead of floating point.

Similiar question on SO.

Massive bounds away from a rendering bottle neck. – Tegra Detra Mar 17 '13 at 10:36 — Tegra Detra, Mar 17 '13 at 10:36

Tegra Detra · Answer 2 · 2013-03-22T09:50:09.387

This is what I ended up coming up with for a base solution.

It gets ride of all subtractions from the test.
It reduces tremendously the number of tests that need to be done.
It can easily be split into different threads.
It gave me a hela bost to performance.
It made me feel cool when it worked.

It focuses on what a computer is good at.

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


}

Any suggestions on making this faster? I know I have a mess here I didn`t even know how to muck with an iterator a week ago.

circle circle collision low resources

2 Answers2