Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

There seems to be a lot of somewhat related questions answered already, but none I read answered my exact problem.

I have a 2D platformer whose world is made entirely out of tiles that are in a regular grid. When there is a collision, I just move the character to the position he was in prior to the collision and it works well enough for me.

The character can fly/slide in the world, so I also want to set the speed towards the collided tile to zero. Here lies my problem.

At the moment the only way to do this I can think of is to check the difference between the character position and the center of the tile. If (the absolute value of the) x-difference is greater, then it is a horizontal collision. If y-difference is greater, then it's a vertical one. However, as the character is sliding horizontally on tiles, from one tile to another, sometimes he stops at the seam of the tiles because momentarily the x-difference becomes a tiny bit greater than the y-difference (due to float inaccuracies I suspect). I don't know if it's possible to change this algorithm to fix this, or if I need a new one. Any algorithm will do, as long as it fulfills the "requirements" stated above.

If at all possible, I want to treat the x- and y-collisions identically, because the movement is not just walking horizontally.

Image illustration: http://i.stack.imgur.com/URkoV.png

share|improve this question
    
Is this one of the questions you read? If so, how does it not solve the problem? Unless I misunderstood the requirements, it seems to fit. For instance, in the linked video I'm flying around within the world, and sliding along walls in every direction without getting stuck at seams. –  David Gouveia May 13 '12 at 19:53
    
I had not read that, but I don't think it is a solution for my problem. Elaboration: The problem occurs even when not moving diagonally. I suspect a key difference is that in my game there is momentum, so losing speed for even one step in physics is enough to ruin the experience. –  DohnJoe May 13 '12 at 20:01
    
I no longer have the test project I used for that answer, but it worked just as well under momentum - I simply set the X or Y component of velocity to zero when colliding with a wall, but seams between tiles were never a problem. In sum, it worked well in every situation I tested it. Also by moving diagonally, I meant any situation where the player is pushing into the wall while sliding. For instance, moving horizontally while acted upon by gravity would be considered moving diagonally too. –  David Gouveia May 13 '12 at 20:10
    
Good to know. I will try to investigate. In the mean time, I uploaded an illustration of the problem to the OP. –  DohnJoe May 13 '12 at 20:16
    
Applying the idea to your algorithm is simple. If I understood correctly, at the moment you have a velocity vector that you're applying to your object. You apply velocity as a vector by adding it to the position, detect collisions with tiles, if there's a collision you move back to the original position, and use the relative positions of the object and tiles to figure out in which direction the collision happened, so that you can cancel out the velocity in that direction. So there are borderline cases where this direction is figured out wrong. (Continued) –  David Gouveia May 13 '12 at 20:17

1 Answer 1

up vote 4 down vote accepted

This is a really common problem, and I'd be very surprised if it hasn't been answered several times already.

Short version of several potential fixes:

1) Ignore internal edges between tiles using flags. For each tile, set a flag for each of its four sides indicating whether that side is external (adjacent to an empty cell) or not. Then only do collision tests against edges that have the flag set. So in your example, since the edge between the two floor tiles is an internal edge, you would not perform the x axis test against that edge. There is a great series of articles by the N+ author on metanet that takes this technique a bit further, with working Flash demos.

2) Collapse external edges into a simplified set of lines. This is a bit more complicated that the previous method, but can be more flexible. Essentially, find all the external edges and convert them into line segments. The find all line segments that share a vertex and have the same normal an merge them into a single line segment. Then switch your collision detection to use AABB to line segment tests. The result is that you won't have any internal edges to test against in the collision data structure. Also, this makes it easier to add arbitrarily shaped tiles later.

3) A simple but error prone method is to just special case a lot of your collisions logic. This is what some old school classic platformers did. It's often sufficient to take the direction of movement and then do collision detection against the "most perpendicular" of the x or y axis, then do the other. For instance, if the player is mostly moving horizontally, first do collision along the y axis and resolve, then against the x axis. Include a small bit of tolerance. Result will be that the player is pushed out of the floor enough that the problematic internal edge collision falls within the error tolerance and is ignored.

4) use hot spot collision detection. This is what most old school platformers did. I don't care for this method myself and it takes some work to explain (although it's very simple to implement), but Google can likely find a few articles on it for you. You may find this method best suits your needs if youre aiming for simplicity.

share|improve this answer
    
What's your recommendation from the four methods (especially when both the tiles and the player are represented by AABBs)? –  David Gouveia May 13 '12 at 20:43
    
This looks very good! I'll test and report back. –  DohnJoe May 13 '12 at 20:45
    
Without more information on the game's specific need, I'd say that option 1 will give the best results for little effort. I've used it before and have been fairly happy with it. Still need a few game-specific tweaks to make it perfect. –  Sean Middleditch May 13 '12 at 22:45
    
I just implemented 1, it was easy to code and it works very well! However, I had also to check that the movement direction is such that it can collide. For example when "walking off" a tile I sometimes had a collision, since the side where I was walking to was empty. After adding the direction check, it seems to work flawlessly. –  DohnJoe May 13 '12 at 23:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.