Take the 2-minute tour ×
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)
    {
        activeList.push_back(physicsChildren[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 {
                activeList.pop_back();
            }
        }
    }

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
 activeList-item. 

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

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