Hi,

i've been trying to create a very simple 2D platformer game over the last few weeks. I'm basically trying to make a megaman clone. That's it.

No fancy physics or anything, just regular rectangle vs rectangle collision, non-rotated.

The problem is, i can't get the collision handling to work... i have rewritten the code a billion times and even though it should work, it doesn't and the player is just falling through the floor or not being able to walk on the floor, getting stuck in the floor, being teleported along tiles, being able to stand on walls and so on... For me this is something i ABSOLUTELY cannot wrap my head around

While looking for a solution i found 1000 pages describing how to detect collision and then just leaving it at that, as if that was the hard part...

I have found only a few pages that actually show some method on how it's supposed to be done, i tried implementing this one:

http://go.colorize.net/xna/2d_collision_response_xna/

But i can't get it to work... I also tried 100 different ways on my own:

1. Moving the player first, check if he's colliding, if so, move him out on the axis with smallest overlap, then check again and do the same for the other axis. Didn't work, i don't know why.

2. Moving the player first, check if he's colliding, if so, place him beside/on top of the block. Didn't work, i don't know why.

3. Check if player would collide in the next frame, given current position and velocity, if so, place him beside/on top of the block. Didn't work, and again, i can't figure out WHY...

And a few more that i already forgot, they are all kinda similiar except for one thing they have in common: THEY DON'T WORK

Another thing that happens with most of the techniques is, the player bounces on top of the tiles because i have to place him 1 pixel above the tile, or else he gets stuck inside. That means he will fall 1 pixel per frame and constanly bounce just a tiny bit. Looks very unprofessional and to me means the method is very poorly executed.

This is the most complicated thing i have ever come across and i need some help to understand what the best way to implementing something like a 2D Platformer like Megaman or Mario or whatever is.

I seriously doubt that i will ever in my life intuitively understand how it's supposed to work.

Moving player out of 1 tile on just 1 axis works, as soon as the other axis comes into play or more tiles, everything breaks and nothing works like it should.

Anyone out there who has real experience with this matter?

I'm not asking for how it theoretically should work, i know that, but when i try to write the code for it, it just DOESN'T work

Only moving the player when he's not colliding is ugly, because he will just float above the tiles or stop beside a wall with a gap inbetween.

The only thing left is brute force, move player pixel by pixel until he collides with something, but that's not very efficient and extremely bad code in my opinion, there has to be a better, more sophisticated way

Here's just one example of what i tried (left out the code for the other axis):

COLLISION_INFO ResolveCollisions(RECT* rect, std::vector<RECT>* obstacles, int dirX, int dirY)
{
    COLLISION_INFO ci = {0,0};
    int pushX = GetMinOverlapX(rect, obstacles);
    int pushY = GetMinOverlapY(rect, obstacles);
 
    if(abs(pushX) < abs(pushY)) // resolve smallest overlap first
    {
        ci.pushDirectionX = ResolveCollisionOnXAxis(rect, pushX, dirX);
        pushY = GetMinOverlapY(rect, obstacles);
        if(abs(pushY) > 0) // if other axis still overlapping
        {
            ci.pushDirectionY = ResolveCollisionOnYAxis(rect, pushY, dirY);
        }
    }
    else
    {
        ci.pushDirectionY = ResolveCollisionOnYAxis(rect, pushY, dirY);
        pushX = GetMinOverlapX(rect, obstacles);
        if(abs(pushX) > 0) // if other axis still overlapping
        {
            pushX = GetMinOverlapX(rect, obstacles);
            ci.pushDirectionX = ResolveCollisionOnXAxis(rect, pushX, dirX);
        }
    }
    return ci;
}
 
 
int ResolveCollisionOnXAxis(RECT* rect, int pushX, int dirX)
{
    if((dirX > 0 && pushX < 0) || (dirX < 0 && pushX > 0)) // don't push in the same direction as player is moving, or else bugs occur
    {
        if(pushX > 0)
        {
            rect->left += pushX+1; // 1 more to get out of the tile
            return 1;
        }
        if(pushX < 0)
        {
            rect->left += pushX-1;
            return -1;
        }
    }
    return 0;
}
 
 
int GetMinOverlapX(RECT* rect, std::vector<RECT>* obstacles)
{
    int minPushX = INT_MAX;
 
    for(auto obstacle = obstacles->begin(); obstacle != obstacles->end(); obstacle++)
    {
        int dx1 = rect->left - obstacle->right;
        int dx2 = rect->right - obstacle->left;
        int thisPushX = 0;
 
        if(abs(dx1) < abs(dx2))
        {
            // push player to the right
            thisPushX = -dx1;
        }
        else
        {
            // push player to the left
            thisPushX = -dx2;
        }
        if(abs(thisPushX) < abs(minPushX)) minPushX = thisPushX;
    }
 
    if(minPushX == INT_MAX) return 0; // if for whatever reason the vector was empty dont move
    else return minPushX;
}

What I have done in the past is to use 3 to 4 different collision rectangles for a player character. The first one is a short (small height) rectangle the width of the player that is near the feet. If this rectangle is overlapping a platform then we move the player up. Then a rectangle that is thin (small width) on both the left and right sides of the player. If the right rectangle overlaps a rectangle we move to the left. If the left rectangle overlaps a rectangle we move to the right. You could also add a rectangle on the top to detect collisions with the players head hitting a platform.

Here is a really nice article on the subject that uses a more complex but probably better approach: How to make a 2d platform game part 2.

I handle collisions pretty easily, first i calculate the distance it traveled in the x axis only, then i check if it collides with anything not passable, like a block.

if i collides with anything, i reduce the distance it traveled in this frame and move it back to its previous position, and then i do the same for the y axis.

so for psuedocode it would look like this, actually its closer to c++ code than psudocode, but it's pretty self explanatory:

//so add the distance traveled this frame, distance = velocity * time

//save the distance traveled so i can subtract it later and move back to previous position in case of collision

float distance_Traveled = x_Velocity * delta_Time;

x_Position += distance_Traveled;

if(check for collision with any entity)

{

x_Position -= distance_Traveled;

}

then i just repeat that for the y axis, and the object will move to the last position it existed on before it had a collision. note there are some problems, for example if there is a collision before and after it moves, like the bounding box is located inside a block before it moves, and inside a block after it moves, it will move back to its previous position even if its still colliding with something. another problem is if it travels too far within a single frame, and crosses a huge gap at once and collides with something, it will move back to its original position even if the distance is enormous.

lets say the square bracket is the player, and the 0 is a wall

[] 0

if its that far, and in one frame the square bracket moves inside the 0

[(])

then it wil move all the way back to its last position

[] 0

and not take into account the entire gap in between.

another problem has more to do with collision detection than handling, if an entity moves from one side of a block to another in a single frame without touching it, it wont count as a collision and he will pass through the block.

ex:

frame 1:

[] 0

frame 2:

0 []

no collision, so it will keep moving just fine.

anyways this simple way to handle collision works fine until it starts lagging or objects move at high velocities. also if it looks like the player is floating over a block then just make the bounding boxes of the player / block smaller than the image, that way it looks a little bit better. and one last thing, if you move one axis at a time, handling slopes will be easy because you just handle slope on the x axis and you can easily use something like y=mx + b to determien the position.

here is a final guide that you can look over to help you understand how to implement platformers, i really suggest you read it, its great.

http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/

its on gamedev.net too but my computer lags too badly to search for it so i just used the first link i found. Good luck

Yeah i read those two articles already, problem with the first one (the one at wildbunny.co.uk) is, it's really hard for me to understand

Maybe i just have to read it a hundred times more, what else can i do...

The other article (http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/) doesn't really explain anything, at least nothing concrete, except maybe for the slopes (which at this rate i should never even be able to think about implementing in my lifetime).

shadowisadog, your idea sounds good, and i tried that in the past, but just like every other method i couldn't get it to work.

What if the player moves into a wall, so both the lower and right rectangles will be inside it and because of that the player will get pushed on top of the wall, if the lower rectangles collisioncheck is performed first.

If the other is done first, the player will be pushed around on the floor.

endless11111, your approach is the same as only moving if the player is not colliding in the next frame, right?

Something like: if( !colliding(position + velocity) ) move();

But i can't accept the huge gaps between the player and the collidable objects. He absolutely needs to be right beside the wall or on top of the block, not 2-3 pixels above or beside it. It just wouldn't have a good "gameplay-feeling". The collisions should be fairly accurate.

But i tried something similiar which kind of works but i don't really like it because it's inefficient:

Every frame, move the player pixel by pixel in the x direction until he has moved all the way or collides. If he does collide, set the velocity.x to 0 and break out of the loop. Next do the same for y.

It's essentially a blind "try to move as far as you can without colliding" method.

That's velocity.x+velocity.y collision checks per frame just for the player. It kind of works, but meh..... it's very inefficient and feels cheap

I think the biggest problem with all of my attempts are the floating point numbers i'm using for the position and velocity.

But that's the only reasonable way to move objects smoothly. Then when it comes to collision detection/handling, it doesn't work right because of rounding errors. I have no clue if and when i should use floor() or ceil() so i can do the collision checks and position correction by integers, because 99.9999% of the time, the player and the tiles won't have a fractional width/height and when i correct the positions, the new position will aways be an integer. I think most problems just arise because of a false collision because of rounding or not pushing the player far enough out of the tile, because it only pushes by pixels and not fractions of pixels. So if the player is still 0.0001 pixels inside, it doesn't work.

Isn't there any book or guide on how to make a good platformer game from start to finish? Every game programming book i found only ever touched on asteroids type of games, or some trivial stuff like tic tac toe... and then just leaves it at that.

I think i really need a good, easy to understand book for intermediate 2D game programming.

I found a lot on 3D game programming, some reeeeeeaaaaaally complicated ones too.

And then the super easy beginner books, but absolutely nothing in between.

It seems to me that there is a huuuuuuge chasm between me and being able to finally make a game.

There's an absolutely ridiculous amount of things i need to learn and everything takes forever for me to understand.

Well, anyways, i'll try to read this guide here a few hundred times more: http://www.wildbunny.co.uk/blog/2011/12/14/how-to-make-a-2d-platform-game-part-2-collision-detection/

This method obviously works, so it's probably the best method IF i would be able to understand it.

Why does everything in the math world have to be explained so horribly complicated? I can't understand any of that gobbledygook...

Super complicated words so nobody understands it and people think they're too stupid to understand, when in reality it's not that hard, just not well explained.

Tried to find out more about that "Minkowski Difference" thing that http://www.wildbunny.co.uk/blog/2011/12/14/how-to-make-a-2d-platform-game-part-2-collision-detection/ mentions, but what i found is all just purely abstract math without any code or examples and for more complicated polygons, not just squares.

I don't get that part with the distance function. So i shrink the red box to a point and extend the green one by the same amount and take a vector from the middle of the green box to the red point?

Then why expand/shrink the boundaries, the midpoint doesn't change at all and doesn't take into account the dimensions of the bounding box?

If i'm using squares it may work, but then i wouldn't need to shrink/expand. How do i shrink the red rectangle? To the center of it? To the topright? What if the red box is to the left of the green box? Does the direction in which i have to shrink the red box change? Probably... I have no idea...

He only explains how to get the major axis of that vector, but how do i get that vector, how do i create that point from the bounding box, and what's the point in expanding the other box if i just take a vector from the center to the point anyways? Guess i'll have to experiment and figure it out on my own.

I got my code working previously somehow, but then realized the player still gets pushed trough walls sometimes, and only takes into account the first tile in the collision, if there's a collision with more than 1 tile it's not working correctly anymore, so i had to delete it all and start over for the billionth time.

By the way, is it a good sign if my collision handling code is 1000 lines long and has lots and lots of if branching?

Hahahaha.... i have no idea what i'm doing and it's driving me crazy :D

Well anyways, thanks for your input everyone :)

The only advice I have is to stick with it. Testing if one rectangle is within another rectangle isn't that complicated but making sure you doing all the tests you need to do, when you need to do them, and responding to the results of those tests properly can get tricky. It took me quite some time and several tries to get my collision stuff working as well as it is. It's not efficient and the code is just plain ugly but it does what I need it to do for the time being. I can always make it pretty later.