How to move multiple rectangles as collision response?

Question

I'm trying to make a game (using irrlicht engine with c++) where you can trap your enemy using boxes. But I just don't get how to detect what should be moved when a collision between the user and one or more boxes is detected. Another thing is that there will also be some objects called bricks which will be able to block movements.

Since I'm not very good in explaining things, I included an image, so it will hopefully clarify what I mean:

I tried several things with my code but without success. So I really hope someone will take the effort to give an answer to this issue. Thanks in advance. By the way, I don't need the answer necessarily in c++, java or .Net languages are also ok.

For anyone interested in the code:

content of bool Game::tryMove(user, dir) which tries to move everthing away from the player

bool thereIsCollision = false;
bool undoMovements = false;
bool userCollision = false;
do{
    thereIsCollision = false;
    for (int i = 0; i < totalObjects; i++) {
        //First check if object hits the user
        if(gameObjects[i].hits(user)){
            if (gameObjects[i]->isMovable()) {
                MovableObject* mObject = (MovableObject*) gameObjects[i];
                mObject->move(dir);
                mObject->setPushVector(dir);
                userCollision = true;
                //thereIsCollision = true;
            }
            else{
                undoMovements = true;
                thereIsCollision = false; //To break do-while loop
                userCollision = true;
                break;
            }
        }
    }
    if(undoMovements)
        break;
    for (int i = 0; i < totalObjects; i++) {
        //Then check if objects hit each other
        for (int i2 = 0; i2 < totalObjects; i2++) {
            if(i == i2)
                continue;
            if (gameObjects[i2].hits(gameObjects[i])){
               //thereIsCollision = true;
               if(gameObjects[i]->isMovable() && gameObjects[i2]->isMovable()){
                   MovableObject* mObject = (MovableObject*) gameObjects[i];
                   MovableObject* mObject2 = (MovableObject*) gameObjects[i2];
                   if(mObject->getPushVector().X > 0 
                           || mObject->getPushVector().Y > 0 
                           || mObject->getPushVector().Z > 0){
                       mObject2->move(mObject->getPushVector());
                       mObject2->setPushVector(mObject->getPushVector());
                       mObject->setPushVector(irr::core::vector3df(0, 0, 0));
                   }
                   else if(mObject2->getPushVector().X > 0 
                           || mObject2->getPushVector().Y > 0 
                           || mObject2->getPushVector().Z > 0){
                       mObject->move(mObject2->getPushVector());
                       mObject->setPushVector(mObject2->getPushVector());
                       mObject2->setPushVector(irr::core::vector3df(0, 0, 0));
                   }
               }
               else{
                   undoMovements = true;
                   thereIsCollision = false; //To break do-while loop
                   break;
               }
           }
        }
    }
}while(thereIsCollision);

for (int i = 0; i < totalObjects; i++) {
    if (gameObjects[i]->isMovable()) {
        MovableObject* mObject = (MovableObject*) gameObjects[i];
        if(undoMovements){
            // Resets position of gameObject to its previous one
            mObject->undoMovement();
        }
        else{
            // confirms movement(i.e. prevPosition=curPosition)
            mObject->confirmMovement();
        }
    }
}
return !(userCollision);

Answer 1

As I understand it, you're using 2d or 3d space, and your objects aren't placed on a some kind of grid (i.e. coordinates are floats). In this case there are 2 solutions:

Solution #1:

Use Physics engine, such as PhysX.

Solution #2:

1. Repeat 10 or 20 times or until there are no more collisions:
   1.1 Find all overlapping (colliding) objects. That includes player and boxes. Also boxes colliding with other boxes.
   1.2 For each object create "move" vector (how much object should move in response to collision)m and initilize it to all zeroes (x: 0, y: 0, z: 0).
   1.3 For each pair of colliding(overlapping) objects A and B, calculate vector(say "pushAwayVector") that would push them away from each other. Add that vector to A.move and B.move. Keep in mind that objects are pushed away to each other, so you should be careful about signs and magnitude. i.e. A.move += pushAway*0.5f; B.move += -0.5f*pushAway;. Do not replace .move with pushAway vector, but add pushAway to move. Otherwise results will be less reliable. You can also take object's mass into account, like this: A.move += (B.mass/(A.mass + B.mass))*pushAway; B.move += -(A.mass/(A.mass+B.mass))*pushAway;, in this case it will be more difficult for lighter object to push heavier object;
   1.4 Once all overlapping objects are processed, for all objects do obj.position += obj.move;

Note that in each case boxes are not guaranteed to maintain exact relative positions. But they will be pushed away when player moves, and they will block player's movement.

Note that using physics engine will yield results that are closer to what you want.

Another solution is once player touches a box, find group of boxes that collide to each other and a player, then remove boxes that wouldn't be affected by current player movement. However, I do not like that solution - it is messy, lacks elegance, although it will maintain relative object positions (which will also look unrealistic).

I'd recommend using Physics Engine.

Answer 2

Is this a sort of Sokoban game where the player can move in 8 directions, and is able to move several boxes at once? Is the play field viewed from birds eye view like in Sokoban, or are they falling boxes that we see in the example (side view, like in Tetris)? Is the friction between boxes and player infinite (in another words, is it forbidden for the box that player is touching to slide away from direction the player is moving, when it moves diagonally)? Is the friction between two boxes infinite?

I couldn't focus on your code, but here's my 2cents algorithm. The algorithm implies that friction between any two objects is infinite.

When player moves you need to establish which movable objects may be affected. Put the ones the player is touching in the moving direction into some search stack, then for each item in the search stack repeat the search process by putting more objects into it. Finally you'll run out of movable objects. If at any point you stumble upon a non-movable object then the player can't move as well (because of infinite friction rule), and so nothing moves. If there are no non-movable objects involved then move all objects in the stack by one grid unit.