C++ 3D perfect collision detection

Question

I'm having hard time learning collision detection by experience. I'm making a box game, à la Minecraft, and am at the stage of implementing collision detection.

I've done x and y axis', since everything consists of cubes I would like to make my own collision detector and make it as light as possible.

Is there a way to make "pixel perfect" collisions, that is when the player's bounding box (or circle) touches a box it registers as a collision? Right now this is what I did:

if(-TOUCH_DISTANCE-1 < yPlayer-yBox && yPlayer-yBox < TOUCH_DISTANCE-1)
{
    collisionNorth = true;
}
if(-TOUCH_DISTANCE+1 < yPlayer-yBox && yPlayer-yBox < TOUCH_DISTANCE+1)
{
    collisionSouth = true;
}

It basically detects the collision within a certain margin and that means errors, which I don't like :(. Notice the +/-1 which offsets the "collision wall" to the respective side of the box.

This works, on lower speeds, but once there's some action (when I crack up the speed variable) the collision can't be detected anymore since I go too fast and pass right through the cube... Is there a way to make it wallhax0r proof?

This is especially annoying on z axis, when the player falls at high speed and even when defining a respectable collision margin it will ultimately look nasty (player half buried).

ChrisF ChrisF · Accepted Answer · 2010-12-13T23:10:58

You've identified one of the problems of using discrete mathematics to model the path of an object. At time t the object is "here" and at time t + delta it's "there" - without actually having passed through the points in between.

You can get more accuracy by decreasing delta, but ultimately you are going to hit the limit of what you can calculate in that time interval.

If you can detect a collision approaching by using a relatively large time delta and loose bounding box you could then crank up the accuracy, but again you are going to hit limits.

Converting to a continuous model might help - but may take more computational power. You could switch to this when your objects are close so you're not doing it all the time.

Sorry I've not got a definite answer, only pointers.

C++ 3D perfect collision detection

2 Answers