What to do with collision detection?

Question

I am able to get collision detection (CD) into my game but... what do I do with it? Do I push the player back to the last location? Something else?

I am programming the game in C++ using the Irrlicht 3D rendering engine, everything is blocks, because the game is a voxel game so there is no need to throw different techiniques of doing CD. All I can find are different methods of doing CD but nothing about what to actually do when I detect collision. The code I use is the following:

// ^^^ all character movement is redundant for this post but is is above this comment
std::vector<scene::ISceneNode *> objects; // A vector containing all of the different blocks

objects.push_back(block); // I add the objects in an array, for later access and easability

// after all character movement, check if player rect intersects with any block
    for(int i = 0; i < objects.size(); i++) { // go through all the block objects
        if(player->getTransformedBoundingBox().intersectsWithBox(objects[i]->getTransformedBoundingBox())) { // if they intersect, do the following
            falling = false;
            can_jump = true;
            walk = false;
            player->setPosition(last_pos); // makes the character stuck, since it always collides with floor
            break;
        } else {
            falling = true;
            can_jump = false;
            walk = true;
        }
    }

I have tried to create a variable BEFORE ALL MOVEMENT in a frame called last_pos = player->getPosition(); and then if there is a collision then I do player->setPosition(last_pos); but the issue is that I constantly collide with the floor, therefore I never move since I always go back to last position because of the collision. So what should I do?

Edit: the way I understand it: one way to do collision detection is to get the coordinate of EVERY corner of every voxel block I have in the world and check if that corner is in between any one of the corners of my character? Is that waaaayy off or does someone has an actual tutorial / concrete code that actually deals with 3D collision and not just tutorials and theory?

Edit 2: Each block the player can collide with is exactly 10 units long. I crafted up this piece of code to check if ANY corder of ANY block is colliding with my character who is 10x20x10 (x, y, z) where y is heigh.

bool axisCollision(vector3df object1, vector3df object2, int axis) {

int pos1_x = object1.X;
int pos1_y = object1.Y;
int pos1_z = object1.Z;

int pos2_x = object2.X;
int pos2_y = object2.Y;
int pos2_z = object2.Z;

// x, y, z
if(pos2_x < pos1_x + 10 && pos2_x > pos1_x &&
   pos2_y < pos1_y + 20 && pos2_y > pos1_y &&
   pos2_z < pos1_z + 10 && pos2_z > pos1_z) {
    std::cout << "collision!\n";
    return false;
}

// x, y, z + 10
if(pos2_x < pos1_x + 10 && pos2_x > pos1_x &&
   pos2_y < pos1_y + 20 && pos2_y > pos1_y &&
   pos2_z + 10 < pos1_z + 10 && pos2_z + 10 > pos1_z) {
   std::cout << "collision!\n";
   return false;
}

// x, y + 10, z + 10
if(pos2_x < pos1_x + 10 && pos2_x > pos1_x &&
   pos2_y + 10 < pos1_y + 20 && pos2_y + 10 > pos1_y &&
   pos2_z + 10 < pos1_z + 10 && pos2_z + 10 > pos1_z) {
   std::cout << "collision!\n";
   return false;
}

// x, y + 10, z
if(pos2_x < pos1_x + 10 && pos2_x > pos1_x &&
   pos2_y + 10 < pos1_y + 20 && pos2_y > pos1_y &&
   pos2_z < pos1_z + 10 && pos2_z > pos1_z) {
   std::cout << "collision!\n";
   return false;
}

// x + 10, y, z
if(pos2_x + 10 < pos1_x + 10 && pos2_x + 10 > pos1_x &&
   pos2_y < pos1_y + 20 && pos2_y > pos1_y &&
   pos2_z < pos1_z + 10 && pos2_z > pos1_z) {
   std::cout << "collision!\n";
   return false;
}

// x + 10, y, z + 10
if(pos2_x + 10 < pos1_x + 10 && pos2_x + 10 > pos1_x &&
   pos2_y < pos1_y + 20 && pos2_y > pos1_y &&
   pos2_z + 10 < pos1_z + 10 && pos2_z + 10 > pos1_z) {
   std::cout << "collision!\n";
   return false;
}

// x + 10, y + 10, z
if(pos2_x + 10 < pos1_x + 10 && pos2_x + 10 > pos1_x &&
   pos2_y + 10 < pos1_y + 20 && pos2_y + 10 > pos1_y &&
   pos2_z < pos1_z + 10 && pos2_z > pos1_z) {
   std::cout << "collision!\n";
   return false;
}

// x + 10, y + 10, z + 10
if(pos2_x + 10 < pos1_x + 10 && pos2_x + 10 > pos1_x &&
   pos2_y + 10 < pos1_y + 20 && pos2_y + 10 > pos1_y &&
   pos2_z + 10 < pos1_z + 10 && pos2_z + 10 > pos1_z) {
   std::cout << "collision!\n";
   return false;

}

return true;

}

The function takes in the players coordination and every single coordination for each block in the world. It then checks if ANY corner of ANY block is inside the character, then it will return false, which results in the player not executing the movement. My issue with this code snippet is that... well... it never returns false! It never detects wall collision, whether I walk inside a wall or on a floor does not matter. Any ideas why?

Answer 1

This problem of "I found a collision/overlap, now what do I do about it?" is called collision-resolution.

There are lots of different ways that games handle this, roughly in order of increasing complexity:

1. Undo (as you described)
   Store the position before this movement integration step. If an overlap occurs, revert to this previous-good position.

This is very simple to implement, very efficient, but often feels rough in gameplay - once you get close to an obstacle, you'll tend to get stuck a small distance away, rather than moving all the way up to the surface or sliding along it. This is because a full move would overlap, so we cancel the whole thing. Worse, the exact distance at which this happens can change depending on your movement angle and where the obstacle lands in the rhythmic phase of your movement strides, creating visible inconsistencies in your gameplay.

This also gets more complicated when you have multiple moving objects that all need to avoid overlaps with each other - one could safely move into the empty space another left, detecting no overlap, but then the previous occupant could hit an overlap and get undone, creating a new overlap that wasn't present on your first collision detection pass, forcing you to re-evaluate at least some collision checks a second time.

2. Sub-Stepping
   Instead of taking your full move all at once, divide it into steps, collision checking at each step. Move to the last non-overlapping spot. This is how Mario 64 handled Mario's movement, splitting the move into 4 so you can move 0, 25, 50, 75, or 100% of your expected movement, cutting the maximum position error proportionately.

This mitigates the more egregious problems with rewinding, but it's strictly only reducing them in degree. And it multiplies your collision-checking cost, so you might want to apply this only to the most visible objects like the player character, or collisions against static walls.

3. Resolve Penetration / Separation
   Given a pair of overlapping colliders, compute the smallest position change that gets them to no longer overlap. This is called the minimum separation vector / minimum separation distance. It's usually easy to compute for pairs of primitives like boxes/circles/spheres/capsules... but gets more complicated with polygons/meshes, especially if they can be concave...

   Once you have this vector, you can use it to resolve the overlap in two ways:

   • Shift the two colliders along this vector, one positively, one negatively. You can move each away by 1/2 the distance, or move one by the full vector and the other not at all (eg. if one is static/kinematic or vastly greater in mass) or any weighting you want in between.

     The advantage of this is that you can fully resolve simple collisions in a single step. And unlike the first two approaches, it doesn't stop objects before the collision, leaving a ghost buffer between the objects - you can run right up into kissing contact with a wall, from any distance. The disadvantage is that, like with undoing, resolving one pair of overlaps could cause or worsen another pair. Some multi-way collisions aren't fully resolvable in one step this way, and can lead to unexpected jumps or jittering .

   • Apply an impulse to the bodies along this vector, so that their next movement step will move them apart. This roughly simulates elastic rebounding, and you can scale the magnitude of the impulse up or down to represent bouncier or squishier materials.

     The disadvantage of relying on impulses over shifts is that you might observe the penetration persisting for a frame or two before the objects manage to jostle their way apart. Or objects can accumulate so much velocity from these impulses that they're catapulted out of overlap at a silly-looking speed. But the advantage is that it's tolerant to complex multi-collisions that might not be fully resolvable in a single step, using only local pairwise interactions rather than needing a more complex global constraint solver tackling multi-way collisions.

   Many game physics engines use these two strategies in tandem, both applying a position correction to resolve the simple collisions immediately, and impulses to create rebounds and iteratively solve more complex pile-ups over multiple frames.

   One hazard to these approaches is that they don't take into account where the objects came from / how they got into this mess. If an object is moving at such great speed that in one step it passes 60% of the way through an obstacle, then the minimal vector that resolves the collision might be one that continues pushing it through the far side, contributing to "tunneling" bugs where objects seem to pass clear through solid walls. This also rears its head when walking along a flat ground made of multiple tiles with their own colliders, when you just straddle the corner of a new tile: the smallest vector to correct the overlap might be to push the player backward instead of up, making it feel like you're snagged on the corner where it should be seamless.

4. Time of Impact
   An improvement to the method above is to take the velocities of the two bodies into account, and compute the moment within the timestep where these two objects first touched. Then we rewind them to that moment, apply any rebound impulses using the actual points/manifold of contact, and then allow them to continue from there.

This solves many cases of tunneling (as long as the object doesn't hop fully past the obstacle in one step - we have to detect an overlap in order to run this routine), stopping/rebounding an object from the same side of the obstacle it came from. And it can give more physically accurate / plausible results.

But again, this does get more complicated as you add ingredients, like rotation or more complex collider shapes. Then the math to compute this moment of contact might get much more costly or require iterative approximation. And again, when you get three bodies or more colliding, resolving them all accurately can become intractable.

Some physics engines will also let you enable continuous collision detection for select objects, where instead of jumping all objects forward and checking for overlaps at the final position, you can sweep the objects through their whole travel - like a raycast/boxcast/spherecast - and find this moment of contact as part of the collision detection phase. This can completely solve tunnelling, but it is often much more expensive to compute.

This is by no means an exhaustive listing - games will use strategies beyond these, or mix elements of several strategies. But this covers some of the common themes you'll see in many games, and hopefully equip you with some conceptual frameworks and search terms you can use to find deeper documentation/Q&A/tutorials to build a solution that works for you.