[SOLVED] 2d platformer collision

[jaybee]

So I'm going to go ahead and ask a question that many have asked before, not because I haven't read the relevant posts, but because I can't seem to square away an implementation that works for me. I'm going to assume this is a lack of experience and knowledge on my part, however, maybe some of you can steer me in a useful direction. I've got a simple tile rendering system set up that reads from a file and stores my tiles into a std::vector. I have implemented some crude gravity that constantly pulls the player downward. I am having some serious issues with resolving the collisions. What I am trying to do is to calculate the amount of overlap between the bounding box of the player and the bounding box of the tile, and "pop" the player out of the tile by the amount of overlap. Here is the code I'm working with:

Code: Select all

void CEntity::OnUpdate()
{
    X += SpeedX * CFPS::FPSControl.GetSpeedFactor();
    Y += SpeedY * CFPS::FPSControl.GetSpeedFactor();

    PosValid(X, Y);


    if (SpeedY < 10)
    {
        SpeedY += Gravity * CFPS::FPSControl.GetSpeedFactor();  //apply gravity
    }

    if(Y > Floor)
    {
        Jumping = false;
        Y = Floor;
    }

    if(X > 640 - 32)
    {
        X = 608;
        SpeedX = 0.0f;
    }

    if (X < 0)
    {
        X = 0;
        SpeedX = 0.0f;
    }
}

So this is my update function for entities. PosValid basically looks at the tiles the player is occupying and when one of them is impassable, it passes a pointer to it to a function called HandleTileCollisions. Here are the relevant functions:

Code: Select all

bool CEntity::PosValid(int x, int y)
{
    int StartX = x / TILE_SIZE;
    int StartY = y /TILE_SIZE;
    int EndX = (x + Width) / TILE_SIZE;
    int EndY = (y + Height) / TILE_SIZE;
    for(int iY = StartY;iY <= EndY;iY++)
    {
        for(int iX = StartX;iX <= EndX;iX++)
        {
            CTile* Tile = CMap::MapControl.GetTilePtr(iX * TILE_SIZE, iY * TILE_SIZE);
            if(Tile->TypeID == 2)
            {
                SDL_Rect tileRect;
                tileRect.x = iX * TILE_SIZE;
                tileRect.y = iY * TILE_SIZE;
                tileRect.w = TILE_SIZE;
                tileRect.h = TILE_SIZE;

                HandleTileCollision(&tileRect);
            }
        }
    }
    return true;
}

void CEntity::HandleTileCollision(SDL_Rect* Tile)
{
    SDL_Rect player = GetRect();

    //set x and y coordinates to the center
    float pX = player.x + 0.5 * player.w;
    float pY = player.y + 0.5 * player.h;
    float tX = Tile->x + 0.5 * Tile->w;
    float tY = Tile->y + 0.5 * Tile->h;

    //determine overlap for each axis
    float xDist = fabs(pX - tX);
    float yDist = fabs(pY - tY);

    //minimal amount of distance that the two can be apart and not collide
    float xMinDist = Tile->w + player.w;
    float yMinDist = Tile->h + player.h;

    if(xDist >= xMinDist || yDist >= yMinDist) return;   //neither axis is colliding

    float xOverlap = xDist - xMinDist;
    float yOverlap = yDist - yMinDist;

    if(xOverlap < yOverlap) X += xOverlap;
    else Y += yOverlap;
}

The HandleTileCollisions function is an algorithm I got from one of falco's posts that delt with this very same issue. When I actually run this code, it's beyond broken. Is there something obvious that I'm missing?

[Rebornxeno]

Ah the ole' overlap problem ehh? It's definitely a "lack of knowledge" problem on your part. If you know the position of the tile (top left bottom right), and the player, you should be able to figure out how much it's overlapping and move accordingly. I suggest taking out your 9th grade geometry book and giving it a good read.

Okay. Harshness away!!!!! I handled this a while back by finding out whether my box of interest was to the left of the other box, above , to the right, or below it, so i'd know which direction i'd be moving it at the end. If my box of interest was to the left, i'd know that if there was overlap, I would have to move my box to the left, and not to the right, by the amount of overlap. I moved my box either left or right, or up or down, depending on if there was a smaller overlap on the x or y axis. So if my box is to the left of another box, my box's right side would be overlapped with the other box's left side. mybox.rightsidelocation - otherbox.leftsidelocation = amount of x overlap. And if my box was also above the other box, mybox.bottomsidelocation - otherbox.topsidelocation = amount of y overlap. Now depending on which was smaller, I'd move by that amount in that axis. What you want to do with that overlap information is your choice, but this is very very primitive. A good read for when you move onto 3d is Real Time Collision Detection by Christer Ericson. Have fun.

[jaybee]

I'm not sure what type of high school you went to, but in mine, we had to give the books back at the end of the semester . I have tried to do exactly that and it has failed. I'm not sure exactly what the problem is. Can you possibly point me in a direction other than:

1.) Find a book you had to return to your public school 10 years ago.
2.) Read all 400 pages of it.
3.) Fix your code.

?

I was hoping maybe someone could point out where I had gone wrong, or at least give me some kind of nudge that wasn't quite so vague.

[Rebornxeno]

I never gave my books back. Fuck that shit.

[EccentricDuck]

Find the coordinates of the corners of your bounding rect (this will work even if you decide to use rotations later, just the math for finding the corner will be more involved). Check which corners intersect. Depending upon if you want a physical pushback or to just land squarely on the tile, you can do something like add a force or acceleration in the direction of the vector between the corner(or corners) that are intersecting and the center of the bounding rect, or simply "reset" the offending corner(s) to the outside of the tile until they're all outside the tile (you'd "reset" the one that is intersecting the most deeply).

There are fancier solutions, but either of these are good (though the former may give you springy physics you weren't expecting).

Think about it intuitively if you still don't get it. Sketch it on paper. Think, what is it that defines the location of the boxes? What is happening and what is my goal? How do I get from here to there?

[jaybee]

Find the coordinates of the corners of your bounding rect (this will work even if you decide to use rotations later, just the math for finding the corner will be more involved). Check which corners intersect. Depending upon if you want a physical pushback or to just land squarely on the tile, you can do something like add a force or acceleration in the direction of the vector between the corner(or corners) that are intersecting and the center of the bounding rect, or simply "reset" the offending corner(s) to the outside of the tile until they're all outside the tile (you'd "reset" the one that is intersecting the most deeply).

There are fancier solutions, but either of these are good (though the former may give you springy physics you weren't expecting).

Think about it intuitively if you still don't get it. Sketch it on paper. Think, what is it that defines the location of the boxes? What is happening and what is my goal? How do I get from here to there?

This is exactly what I've attempted to do but when I compile and run it, its extremely glitchy. Do you see any obvious problems with my code? I understand the concept, I just can't seem to get it to work right.

this code finds the corners of the bounding box and determines which tiles I'm overlapping:

Code: Select all

bool CEntity::PosValid(int x, int y)
{
    int StartX = x / TILE_SIZE;
    int StartY = y /TILE_SIZE;
    int EndX = (x + Width) / TILE_SIZE;
    int EndY = (y + Height) / TILE_SIZE;
    for(int iY = StartY;iY <= EndY;iY++)
    {
        for(int iX = StartX;iX <= EndX;iX++)
        {
            CTile* Tile = CMap::MapControl.GetTilePtr(iX * TILE_SIZE, iY * TILE_SIZE);
            if(Tile->TypeID == 2)
            {
                SDL_Rect tileRect;
                tileRect.x = iX * TILE_SIZE;
                tileRect.y = iY * TILE_SIZE;
                tileRect.w = TILE_SIZE;
                tileRect.h = TILE_SIZE;

                HandleTileCollision(&tileRect);
            }
        }
    }
    return true;
}

and this code finds the shallower of the two penetrations and pushes it out (well that's what I was hoping it would do).

Code: Select all

void CEntity::HandleTileCollision(SDL_Rect* Tile)
{
    SDL_Rect player = GetRect();
    //set player x and y to origin
    float pX = player.x + 0.5 * player.w;
    float pY = player.y + 0.5 * player.h;

    //set tile x and y to origin
    float tX = Tile->x + 0.5 * Tile->w;
    float tY = Tile->y + 0.5 * Tile->h;

    //determine overlap for each axis
    float xDist = fabs(pX - tX);
    float yDist = fabs(pY - tY);

    //minimal amount of distance that the two can be apart and not collide
    float xMinDist = Tile->w + player.w;
    float yMinDist = Tile->h + player.h;

    if(xDist >= xMinDist || yDist >= yMinDist) return;   //neither axis is colliding

    float xOverlap = xDist - xMinDist;
    float yOverlap = yDist - yMinDist;

    if(xOverlap < yOverlap) X += xOverlap;
    else Y += yOverlap;
}

I've gone over this code over and over but I can't seem to figure out why it is behaving the way it is.

[jaybee]

Ok So I figured out what I was doing wrong here. I wasn't comparing the ABSOLUTE VALUE of the overlaps or setting the minimum distance to the half widths and half heights of the rects

[EccentricDuck]

There you go

Sometimes you just need to work through it all again by explaining it to someone else to find your own bugs.