C++ - Collision response leads to clipping -

i'm trying implement collision detection system, , working part, no overlapping (or @ little overlapping) of characters, , wall collisions. problem have bunch of characters following player , run it, , when there 15-20 of characters pushing @ player, can lead player or other objects being pushed through walls.

my code works follows, first update of characters, , check collisions against each other, check character collisions walls. feel problem eventual push of characters leads pushing 1 or more of characters large distances, i'm not sure how fix problem. code below if necessary, thorough explanation of how fix sufficient.

character update/collisions:

void charactermanager::updateall(float elapsedtime) {     for(std::vector<std::shared_ptr<character>>::iterator = _characters.begin(); != _characters.end(); i++) {         (*i)->update(elapsedtime);     }     collisions(); }  void charactermanager::collisions() {     for(std::vector<std::shared_ptr<character>>::iterator = _characters.begin(); != _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);             }         }     } } 

generally run collision code 2 objects when 2 objects intersect each other. 2 objects intersect each other if share @ least 1 point in space. problem if objects intersecting means there collision in past , not there collision right now.

ideal collision code should calculate energy transfer , modify velocity of objects @ the exact moment when objects touch each other. collision code roll time , try find out moment when collision happened, calculate new velocities based on moment , roll time forward. these rather hard , might overkill simple computer game.

the easy robust solution can recommend is:

1. move objects forward
2. check collision, if no collision repeat beginning
3. move objects away each other until don't collide proportional mass. since walls don't move can consider have infinite mass , move characters
4. recalculate velocity of colliding objects after objects don't intersect anymore
5. repeat

you can use constraint 'objects can never intersect wall' , apply constraint checking if new position valid when moving characters. , move character if new position valid.

this small example should exemplify validation. make position updatable moveto() method , inside moveto() method can validate new position , return whether move successful. if move wasn't successful, caller want take different action. (move object less until contact position , perfect opportunity process collision)

class character{      bool moveto(float x, float y)     {         if (this.isvalidposition(x,y))         {             this.x = x;             this.y = y;             return true;         }         return false;     }      void update(float deltatime)     {         float new_x = x + velocity_x*deltatime;         float new_y = y + velocity_y*deltatime;          if (!this.moveto(new_x, new_y))         {             console.write("cannot move " + + " new position, there\n");         }     }  }