Help with Resolving Pixel Perfect Collision

Question

Hi I'm having trouble resolving "Collision detection between axis-aligned bounding box and bitmap (pixel perfect) terrain on a Worms type game". (Read previous question to find more information about the game).

The player has got properties such as velocity, acceleration, gravity applied to it on its update method. I have controls that allow the player to "land" on a surface by detecting the pixel immediately below it and then stopping the velocity if that object is solid. I am having trouble with moving the character.

Currently when I move the character left or right the code should work in my head to move the character up, but it seams to still want to go into the ground. Could you help me to resolve the collisions for moving?

Below is the code I implement for Walking left or right. It is called immediately before the update method for sprite. This method is called from the Player class update method.

            boolean solidPixel;
            //Create a bitmask from top to bottom of the pixels 
            for(int i=0;i<boundHeight;i++){
                //If true then collision
                solidPixel = TerrainObj.isPixelSolid(x+(getBound().halfWidth*direction),y-getBound().halfHeight+i);
                //if any of the pixels are solid then we've hit a wall
                //so act accordingly and exit the application
                if(solidPixel && i < getBound().halfHeight/4){
                    //
                    //Cannot move in the direction
                    velocity.x = 0;
                    break;
                }
                //if the bottom (left/right)quater of the sprite is
                //solid then its a slope
                if(solidPixel && i >= getBound().halfHeight/4){
                    //Position the item -(up) by the amount of pixels the 
                    //gradient is
                    position.y+=(getBound().halfHeight*2)-i;
                    break;
                }
            }

Any help is much appreciated how I could approach the issue to stop the player ever moving into the ground to provide prefect collision detection.

Sorry for the long post, wanted to put as much information in as possible.

Answer 1

You can try calculating the surface normal using central finite differencing, and then colliding with a locally linear plane at the collision point.

Vector2 GetNormal(Grid grid, int x, int y)
{
    float dx = grid[x + 1, y] - grid[x - 1, y];
    float dy = grid[x, y + 1] - grid[x, y - 1];
    return Vector2(dx * 0.5f, dy * 0.5f);
}

When your grid is binary (1's and 0's) this normal will either point to the right, left, up, down, or at some 45 degree increment. You will get a better result if you first convert your map into a signed distance field instead.

After you find the normal of the surface, computing the collision between the plane and the bounding box should be easy. Essentially, just cancel out the velocity parallel to the plane normal.

Answer 2

I will give you a different approach you might wanna try.

How i would do this is I would use shapes for the objects. A rectangle for the terrain, a rectangle for the bottom half of the worm and a circle for the top half of the worm. So the worm is a combination of 2 shapes. Now, if the user presses left worm gets a (-5,0) velocity if the user pressed up the worm gets a (0,-5) velocity. After the velocity is applied, you check for collisions using trigonometry, and if any of the 2 shapes of the worm collide with the terrain, then you move it outside of the terrain, by moving the worm up. So you basically force it not to be inside the terrain. This velocity would have to be calculated according to the angle of the terrain, otherwise your worm would move very quickly on terrains placed at high angles.

For example, according to the image in your question, if the user pressed left, the worm would get a (-5,0) velocity applied to it, so it would move 5 pixels to the left. But then it would be inside the terrain, so we would have to force it outside of the terrain by moving it k pixels up. You will have to calculate k using Euclid theorem. So not only the worm will never be inside the terrain, but it will also move as a result of forcing it outside of the terrain.

So, basically the worm goes inside the terrain, and then the terrain pushes it upwards (only). That way your worm is never drawn inside the terrain, and also it moves.

You will simply need collision detection of rotated rectangle with a rectangle/circle. Or instead of a "rectangle" you could check collisions with 4 lines. That way you would not only solve rectangle with an angle - rectangle/circle collision detection, but any given polygon - circle/rectangle intersection, which you might need in the future. Because a polygon is nothing other than N lines. Now, the problem with that is that if your worm has a big velocity, your worm might pass right through the terrain, because lines are thin. For that to happen you worm would need to have a velocity of greater than 2*radius of the circle, or greater than 2*width of the rectangle (but in reality that is really unlikely, your worm would have to move like 50 pixels per frame for that to happen, which is too high for a worm anyway). The "circle" and "rectangle" i am talking about are the shapes of the worm. This problem is known as continuous collision detection.

Not that it is necessary, but if you had a physics engine with collision detection functions, you could check polygon collisions much easier. And probably a tiny bit more efficiently than any code you will write alone, unless you are familiar with mathematics.