Sign in to follow this  
chiranjivi

2D collision detection woes

Recommended Posts

Blah blah 2D platform game, trying to implement proper collision detection between the player and the environment. I'm using the method of testing for a simple collision, then if that check returns true, I go back to where the player was prior to the collision, then add in the x- and y- components of motion separately to test which direction the player was moving in when he collided with the obstacle. The platforms I'm using are 12x12 tiles, and as long as the player doesn't move *fast*, this method works perfectly. However, when the player starts travelling at greater than 12 pixels per frame, problems present themselves... even if my grandma violate, she gotta go As you can see, the player is colliding with two platform tiles (marked 'B') which the directional collision detection function cannot check, as the process it follows is: * If I add in the X-velocity only, did we collide? > NO * If I add in the Y-velocity only, did we collide? > NO * Well I dunno then This results in silly behaviours like the player falling through the floor if he starts to run fast, which isn't much fun. I've tried to mitigate this by putting in a secondary check, where if the first check doesn't find the collision direction, the game breaks the velocity down into chunks and applies it bit by bit (i.e. the game adds (velocity/N) for N successive iterations and checks the incremental position each time for a directional collision). Doing this finds the collision at least, but when the x-component of motion is so much greater than the y-component, it almost always reports it as a horizontal collision, so if the player is travelling left/right at high speed he will frequently stop dead as the collision-detection function reports that he has collided sideways into an obstacle. (Also it results in buggy behaviour if the player jumps at speed into a vertical wall [depressed]). I would appreciate any help that people could offer. I'm sorry if this is a basic question but this is my first time attempting to implement collision detection that is any more complex than
if ( collision(player,monster)==true ) { player.explode(); }

Share this post


Link to post
Share on other sites
Well, one way to do it would be to add x AND y velocity to a *phantom position* and then test the phantom position against collisions. If there is a collision, stop player movement. Afterwards, test against the Y coordinate only. If the Y coordinate only collides, stop player movement at the Y axis only. If X only collides, stop player movement at X only.
If all three positions collide or only the first, stop player movement completely. If the game needs to handle very high speeds, you might to need to break the players movement up in chunks and test each chunk for collisions.

Share this post


Link to post
Share on other sites
One thing you can try is averaging your results at the end of the current frame. If the player encounters 2 or more tiles in a single frame, average the results from each test, and locate the player at that average position.

Example:

player collides with tile A
calculate new position relative to tile A
player collides with tile B
calculate new position relative to tile B
average the 2 positions
locate player at average position

Share this post


Link to post
Share on other sites
PAndersson,

I don't understand how any of that is in any way different to what I have already done? Everything you suggested I do seems to be exactly what I explicitly described that I am already doing.

You said:
Quote:
Original post by PAndersson
Well, one way to do it would be to add x AND y velocity to a *phantom position* and then test the phantom position against collisions. If there is a collision, stop player movement. Afterwards, test against the Y coordinate only. If the Y coordinate only collides, stop player movement at the Y axis only. If X only collides, stop player movement at X only.


I said:
Quote:
I'm using the method of testing for a simple collision, then if that check returns true, I go back to where the player was prior to the collision, then add in the x- and y- components of motion separately to test which direction the player was moving in when he collided with the obstacle.


You said:
Quote:
Original post by PAndersson
If the game needs to handle very high speeds, you might to need to break the players movement up in chunks and test each chunk for collisions.


I said:
Quote:
I've tried to mitigate this by putting in a secondary check, where if the first check doesn't find the collision direction, the game breaks the velocity down into chunks and applies it bit by bit


Am I missing something here? I assume you're trying to direct me to do something differently but you just worded it badly, because you appear to have just rewritten my original post.

Share this post


Link to post
Share on other sites
Quote:
Original post by Whatz
One thing you can try is averaging your results at the end of the current frame. If the player encounters 2 or more tiles in a single frame, average the results from each test, and locate the player at that average position.

Example:

player collides with tile A
calculate new position relative to tile A
player collides with tile B
calculate new position relative to tile B
average the 2 positions
locate player at average position


Whatz,

Thanks for your reply.

This method would probably mean that the player gets stuck inside tiles a bit less, but thinking about it, I can't see what I would do about the velocities? In the example image, the first collision would (probably) return vertical, and the second as horizontal. Averaging out the two positions would still leave the player halfway inside the platform, and I'm not sure how I'd handle modifying the velocities when the function reports one vertical collision and one horizontal one? I couldn't average the velocity change out, otherwise the player would lose x-velocity when landing on a flat surface, which is the problem I'm trying to avoid to begin with.

Share this post


Link to post
Share on other sites
Quote:
Original post by chiranjivi
snip


Sorry if I was unclear. I mean, did you try to block the movement completely if you cannot detect any x or y collision but you can detect one when you add both velocities?

Another option might be to do it pixel by pixel (similar to the other method you described). Divide each velocity by the highest of the two and then you simply test every position the player will pass. If he/she collides with something, only stop checking along the axis that the collision occurred along and keep checking the other axis until you you run out of speed or a collision along that occurs as well. The resulting coordinates is the players new coordinates.
IIRC, this was the method I used when I wrote a platformer a couple of years back.

Share this post


Link to post
Share on other sites
Quote:
Original post by PAndersson
Quote:
Original post by chiranjivi
snip


Sorry if I was unclear. I mean, did you try to block the movement completely if you cannot detect any x or y collision but you can detect one when you add both velocities?


Oh, I see - sorry, I couldn't for the life of me see what you were saying before, I feel a bit silly now. The way I'm doing it at present is that if the x- and y-components alone don't produce a collision, then the game doesn't alter the velocities at all, but instead goes on to obtain a collision via the incremental testing (which gives incorrect results the way I've implemented it currently).

Quote:
Original post by PAndersson
Another option might be to do it pixel by pixel (similar to the other method you described). Divide each velocity by the highest of the two and then you simply test every position the player will pass. If he/she collides with something, only stop checking along the axis that the collision occurred along and keep checking the other axis until you you run out of speed or a collision along that occurs as well. The resulting coordinates is the players new coordinates.


This sounds promising. I'd shied away from pixel-by-pixel collision up until this point because I'd read it's very computationally expensive (and I'm a total scrub coder at the moment so my collision detection is literally just checking everything vs everything else for every frame), but if it's the simplest way of getting the results I'd like, then I may give it a try.

Share this post


Link to post
Share on other sites
This is a tough topic =) I've been working through some of the same logic myself lately. I've been working on Sphere-Segment collision, very similar to what you're doing.

When it comes to these types of collisions, player velocity is important, but not as important as the player's vector and the obstacle's normal.

One thing you're keeping track of is whether you collided with a horizontal or vertical tile, then doing something different for each type. That approach is not bad but you might want to consider expressing each tile's orientation mathematically as a simple normal. For example, in OpenGL which is what I use, a floor tile would have a normal of 0,1. A ceiling would be 0,-1. Left wall would be 1,0 and Right wall would be -1,0. That way, no matter which obstacle you collide with, the math can all generally be the same.

Consider a ball bouncing around a room with 4 walls, deep in space with no gravity. As the ball collides with a given wall, you can use the wall's normal and the ball's current vector to calculate a new vector for the ball.

Now, in your case you don't want your player to bounce (unless he falls off a cliff haha) you just want your player to land smoothly on the tile and continue running along. Or maybe he runs face first into a wall and he should just quickly stop.

Anyway, the point is that can use the tile's normal along with the player's current vector to do exactly what you need to do, just like with the bouncing ball.

I hope this made sense - I tried writing it up a couple times and it seemed way too technical haha

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this