Collision detection/resolution clipping

Question

I'm trying to implement a collision detection system, and it is working for the most part, no overlapping (or at most very little overlapping) of characters, and wall collisions. The problem is that I have a bunch of characters following a player and just run into it, and when there are about 15-20 of those characters all pushing at the player, it can lead to the player or other objects being pushed through walls.

My code works as follows, first I update all of the characters, and they check collisions against each other, then I check for any character collisions with the walls. I think the problem is that I'm only ever checking one object against another, where as i need to be able to correctly detect multiple simultaneous collisions.

I've been looking into speculative contact and continuous collisions, but unfortunately i start to get lost when the non-code math equations come up. I don't necessarily need a real code example, but a good pseudo code/explanation would be great.

Code below if necessary, although a thorough explanation of how to mend this is also sufficient.

Character update/collisions:

void CharacterManager::updateAll(float elapsedTime)
{
    for(std::vector<std::shared_ptr<Character>>::iterator i = _characters.begin(); i != _characters.end(); i++) {
        (*i)->update(elapsedTime);
    }
    collisions();
}

void CharacterManager::collisions()
{
    for(std::vector<std::shared_ptr<Character>>::iterator i = _characters.begin(); i != _characters.end(); i++) {
        for(std::vector<std::shared_ptr<Character>>::iterator j = _characters.begin(); j != _characters.end(); j++) {
            if(i == j) continue;
            float xi = (*i)->position().x;
            float yi = (*i)->position().y;
            float xj = (*j)->position().x;
            float yj = (*j)->position().y;
            float dx = xi - xj;
            float dy = yi - yj;
            float distSquared = dx * dx + dy * dy;
            float ri = (*i)->xRect().width/2;
            float rj = (*j)->xRect().width/2;
            if(distSquared < (ri + rj) * (ri + rj)) {
                // fix collisions
                float angle = atan2f(dy,dx);
                float overlap = (ri + rj) - sqrt(distSquared);
                if(xi < xj) {
                    if(yi < yj) {
                        (*i)->position(xi - cosf(angle) * overlap/2, yi - sinf(angle) * overlap/2);
                        (*j)->position(xj + cosf(angle) * overlap/2, yj + sinf(angle) * overlap/2);
                    } else {
                        (*i)->position(xi - cosf(angle) * overlap/2, yi + sinf(angle) * overlap/2);
                        (*j)->position(xj + cosf(angle) * overlap/2, yj - sinf(angle) * overlap/2);
                    }
                } else {
                    if(yi < yj) {
                        (*i)->position(xi + cosf(angle) * overlap/2, yi - sinf(angle) * overlap/2);
                        (*j)->position(xj - cosf(angle) * overlap/2, yj + sinf(angle) * overlap/2);
                    } else {
                        (*i)->position(xi + cosf(angle) * overlap/2, yi + sinf(angle) * overlap/2);
                        (*j)->position(xj - cosf(angle) * overlap/2, yj - sinf(angle) * overlap/2);
                    }
                }
                // calc new velocities
                float vxi = (*i)->velocity().x;
                float vyi = (*i)->velocity().y;
                float vxj = (*j)->velocity().x;
                float vyj = (*j)->velocity().y;
                float vx = vxj - vxi;
                float vy = vyj - vyi;
                float dotProduct = dx * vx + dy * vy;
                if(dotProduct >= 0) {

                    float collisionScale = dotProduct / distSquared;
                    float xCollision = dx * collisionScale;
                    float yCollision = dy * collisionScale;
                    float combinedMass = (*i)->weight() + (*j)->weight();
                    float collisionWeightA = 2 * (*j)->weight() / combinedMass;
                    float collisionWeightB = 2 * (*i)->weight() / combinedMass;
                    (*i)->velocity(vxi + collisionWeightA * xCollision, vyi + collisionWeightA * yCollision);
                    (*j)->velocity(vxj - collisionWeightB * xCollision, vyj - collisionWeightB * yCollision);
                }
            }
        }
    }
}

Wall collisions:

void Stage::characterCrossCollisions(std::shared_ptr<Character> character)
{
    for(std::vector<std::shared_ptr<Tile>>::iterator tile = tiles.begin(); tile != tiles.end(); tile++) {
        if(!(*tile)->walkable) {
            sf::Rect<float> cxr = character->xRect();
            sf::Rect<float> cyr = character->yRect();
            sf::Rect<float> tr = (*tile)->getRect();

            if(!(cxr.left > tr.left + tr.width ||
                 cxr.left + cxr.width < tr.left ||
                 cxr.top > tr.top + tr.height ||
                 cxr.top + cxr.height < tr.top)) {
                float ox = 0;
                if(character->position().x > (*tile)->position().x) {
                    ox = cxr.left - (tr.left + tr.width);
                }
                else {
                    ox = cxr.left + cxr.width - tr.left;
                }
                character->position(character->position().x - ox, character->position().y);
            }

            if(!(cyr.left > tr.left + tr.width ||
                 cyr.left + cyr.width < tr.left ||
                 cyr.top > tr.top + tr.height ||
                 cyr.top + cyr.height < tr.top)) {
                float oy = 0;
                if(character->position().y > (*tile)->position().y) {
                    oy = cyr.top - (tr.top + tr.height);
                }
                else {
                    oy = cyr.top + cyr.height - tr.top;
                }
                character->position(character->position().x, character->position().y - oy);
            }
        }
    }
}

Answer 1

You need to put your thinking level one step backward, and try to imagine that there is a different way than the quadratic solve. You can use iterative solving. This will not give you a perfect solution in all cases, but when many entities moves relative to each other with 2 or 3 contact points in average, this is the fastest and gives very good results. All physics libraries implement this as default.

Try it like that:

for each entity
   determine contact points and store them (e.g. in an array limited to some MAX_CONTACTS like ODE does)
for X in range(1, iterative-steps-limit)
    for each entity
        find a heuristical solution that frees the body from interesections by creating impulses opposed to contact points.
    update positions from impulses

then you can add stuff like resting epsilons to let your bodies sleep when they don't move...