Jump to content

  • Log In with Google      Sign In   
  • Create Account


2D Platformer collision handling...


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 Horscht   Members   -  Reputation: 221

Like
0Likes
Like

Posted 16 June 2013 - 03:50 PM

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 sad.png

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 smile.png

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 sad.png

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 sad.png

 

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;
}


Sponsor:

#2 shadowisadog   Crossbones+   -  Reputation: 2163

Like
0Likes
Like

Posted 16 June 2013 - 08:07 PM

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.



#3 endless11111   Members   -  Reputation: 135

Like
0Likes
Like

Posted 16 June 2013 - 11:14 PM

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


Edited by endless11111, 16 June 2013 - 11:19 PM.


#4 Horscht   Members   -  Reputation: 221

Like
0Likes
Like

Posted 17 June 2013 - 05:20 AM

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 sad.png

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 sad.png

 

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. sad.png

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.



#5 BeerNutts   Crossbones+   -  Reputation: 2191

Like
1Likes
Like

Posted 17 June 2013 - 03:50 PM

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();

 

No, it's not the same.

 

Updating a player's position can be a 4 step process.  

Step #1, Move the Player in the X axis only.

Step #2, Check if the Player Collidied with anything.  If so, we know the player hit something on the side, so we can move it back the number of pixels it has moved into the colliding block

Step #3 and #4, repeat, but only move in the Y-axis.

// Update the X location and ahdnle that mvoement
Player.XLocation += Player.XVelocity*TimeDelta;
HandleMovement(Player);
 
// Repeat for Y-axis
Player.YLocation += Player.YVelocity*TimeDelta;
HandleMovement(Player);
 
// Call this every time you move the player on the X-axis, then after you move him on the Y-Axis
void HandleMovement(TPlayer& Player)
{
  // returns the object the player is colliding with, so we can adjust the player's location
  TPhysicalObject* CollisionObject =  IsCollising(Player);
 
  if (CollisionObject != NULL) {
    // move the player back on the axis the amount of pixels he's moved into the given Block
    CollisionResolve(Player, CollisionObject);
  }
}

 

This would allow the player to collide with walls, but still move up and down, as well as allow them to run along the ground with constant gravity pushing down on them.


My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#6 marcClintDion   Members   -  Reputation: 431

Like
0Likes
Like

Posted 19 June 2013 - 01:04 AM

If collision detection and response doesn't drive you nuts then you must already be nuts.  Just a joke, some people love complex logic.

 

You can modify the script on the following page as the 'game' runs, it's super basic and has a mods section below it that users can build up then post.

https://www.khanacademy.org/cs/jumpgirl/939844470

 

Personally, I've had success by making four collision functions(2D), one for each direction.  It helps to conceptualize what's taking place without trying to complicate things with compactness and optimization. 

Doing additional bounding box tests within the main test can help you to resolve direction, This is pretty important for determining the proper response.  It's similar to what shadowisadog mentioned about giving the character several bounding boxes to determine what is hitting what in the various directions.  If you detect a hit then you can run another bounding box test that is a slender rectangle along the left edge of the box being tested against.  Then test for a slender rectangle along each of the other three edges and you will know from which direction the collision occurred.  Otherwise you can measure the relative velocities of the collided objects to resolve the collision vector. 

 

Some of your problems sound like you are moving the character away from the contacted object but by an amount that was less then the velocity at which the character hit.

For instance, if you move 1.1 units into an object but only move the character back 1.0 unit, then the character will become stuck in a loop of being sent back and forth because going back 1.0 unit will still register a hit, now because of this, the character will be sent back into the wall 1.0 unit, then sent back almost out of the wall by the same 1.0 unit then sent back in, etc..  You can help clear this up by expanding either of the bounding boxes according to velocity.  The faster the character, the larger the bounding area.  This then stops the players movement, the player stopping decreases the bounding volume.  If you give a slight extra margin of error to unsure that the moving object does not get stuck then the error you see visually will appear like a soft bouncy effect effect where the character appears to gently settle in against an object instead of coming to a dead stop when a hit occurs. It's nothing at all like that horrible 'seizure' effect you see when the character is pushed away from collision object that is being pressed up against.  If you dial it in then the settling in effect minimizes.  Maybe use a non-linear scaling here to compensate for faster moving objects.  The faster the objects move, the more likely they are to get stuck or even pass right through without registering a hit.

 

If you are setting all direction movements to false when a collision occurs then you have to be sure to then set the other three directions back to true.  This is why you should resolve the collision direction.  If the character hits a right wall then make sure that UP, DOWN, and LEFT are true, if you don't get the directional test correct then the character might get stuck and slide along the surface.  

 

Well, this isn't perfect but hopefully it will help.  Next on the slate for bringing us premature baldness.... momentum for both elastic and non-elastic collisions...

 

Oh! I almost forgot to mention.  Redundant testing in collision detection can be a little disastrous.  By this I mean that if every box tests against every other box then you can end up in a situation where let's say.. box[10] tests against box[15], then a response is triggered, this is all fine and dandy but serious problems can occur when box[15] performs its test against box[10].  If you are reversing the velocity when a hit occurs, the same reversal will then take place again when the second test occurs and now the two moving objects will end up bouncing off each other and will be stuck together at the same time because they are both reversing the response of the other one.  You should try and come up with a scheme where:

 

box[0] performs no test at all.

box[1] only tests against box[0]

box[2] only tests against box[1] and box[0]

box[3] only tests against box[2] and box[1] and box[0]

...

.....

Now you've also made things much more efficient since only half the number of tests are being performed.


Consider it pure joy, my brothers and sisters, whenever you face trials of many kinds, because you know that the testing of your faith produces perseverance. Let perseverance finish its work so that you may be mature and complete, not lacking anything.


#7 Horscht   Members   -  Reputation: 221

Like
0Likes
Like

Posted 20 June 2013 - 07:58 AM

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 :)



#8 kseh   Crossbones+   -  Reputation: 1563

Like
0Likes
Like

Posted 20 June 2013 - 12:24 PM

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.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS