Sign up ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

The code that I am using is:

    std::vector <PhysicsBody*> physicsChildren; //containing all objects


    std::sort(physicsChildren.begin(), physicsChildren.end(), sortByLeft);
    std::vector <PhysicsBody*> activeList;

    unsigned int one;
    unsigned int two;
    for(one = 0; one < physicsChildren.size(); ++one)
        for(two = 0; two < activeList.size(); ++two)
            if (physicsChildren[one]->m_position.x + physicsChildren[one]->m_radius > activeList[two]->m_position.x - activeList[two]->m_radius)
                CheckIntersectionBetween(physicsChildren[one], activeList[two]);
            } else {

I think something is wrong because for 800 objects 309169 calls to CheckIntersectionBetween. A bruteforce would use 640000 calls, I didn't think this was much improvement (considering only objects close in the x-axis should test).

I wrote the code from reading Jitter-Physics article about SAP:

Create a new temporary list called “activeList”.
You begin on the left of your axisList, adding the first item to the activeList. 

Now you have a look at the next item in the axisList and compare it with all items
 currently in the activeList (at the moment just one):
 - If the new item’s left is greater then the current activeList-item right, then remove 
the activeList-item from the activeList 
 - otherwise report a possible collision between the new axisList-item and the current

Add the new item itself to the activeList and continue with the next item in the axisList.

What have I done wrong?

share|improve this question

closed as too localized by Tetrad Feb 21 '13 at 20:33

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer 1

up vote 0 down vote accepted

I misinterpreted remove the activeList-item from the activeList to mean pop_back the item just added(I had just been added an active item, it was logical! ;) ) when, because the activeList was being looped, meant remove that specific one. Hence:

activeList.erase(activeList.begin() + two);

has replaced that line. Now 11408 checks are being done for the 800 objects (55x less than brute) and this seams much more logical to me.

share|improve this answer
I was reading the exact same article, and am struggling to implement this. It seems that you did not add the "new item" to the active list when a potential overlap is found... Did you succeed in implementing this after this question ? – JamesAMD Jun 17 at 11:16
That is what activeList.push_back(physicsChildren[one]); is doing. When an overlap is found, CheckIntersectionBetween is called (as instructed by the 'otherwise report a possible collision' line) – andrew Jun 17 at 15:26
About an hour ago, I took a look at the source code for Jitter Physics (Collision/CollisionSystemSAP.cs in particular, for future visitors) and got it right. Thanks for commenting me back even though this question is 2 years old :) – JamesAMD Jun 17 at 15:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.