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.

I'm developing a physics engine for a 2D platform game. I'm using the separating axis theorem for collision detection. The ground surface is constructed from oriented bounding boxes, with the player as an axis aligned bounding box. (Specifically, I'm using the algorithm from the book "Realtime Collision Detection" which performs swept collision detection for OBBs using SAT). I'm using a fairly small (close to zero) restitution coefficient in the collision response, to ensure that the dynamic objects don't penetrate the environment.

The engine mostly works fine, it's just that I'm concerned about some edge cases that could possibly occur. For example, in the diagram, A, B and C are the ground surface. The player is heading left along B towards A. It seems to me that due to inaccuracy, the player box could be slightly below the box B as it continues up and left. When it reaches A, therefore, the bottom left corner of the player might then collide with the right side of A, which would be undesirable (as the intention is for the player to move smoothly over the top of A). It seems like a similar problem could happen when the player is on top of box C, moving left towards B - the most extreme point of B could collide with the left side of the player, instead of the player's bottom left corner sliding up and left above B.

Box2D seems to handle this problem by storing connectivity information for its edge shapes, but I'm not really sure how it uses this information to solve the problem, and after looking at the code I don't really grasp what it's doing.

Any suggestions would be greatly appreciated.

share|improve this question
    
A general physics engine is great for effects and falling boxes and all that, but not for character physics, as laid out in the answer section. Consider writing "static" physics for your character, so you can be 100% in control, and use properly simulated dynamics for the rest. –  Domi Apr 19 at 6:13
add comment

2 Answers

Platforming and Physics

These edge cases are numerous. Good fun platformers do not behave in any kind of physically-accurate manner, and the control and behavior that players expect after years of "perfect" platformers like Mario are incredibly difficult to implement with general techniques like you get with Box2D or other physics engines. Most good platformers do not use any kind of generic physics or collision response in their player controllers.

Generate Hulls

Regarding your specific question, the best solution is to stop using boxes as your ground. Use a series of connected line segments (a hull). That allows the collision detection engine to only focus on the actually walkable surfaces and not look at the "fake" edge that exists between A-B and B-C. That is what Box2D does, in fact. The shapes are used to generate the outward surfaces, which are linked together to form a hull.

You need this even in tile-based games, or in situations where you have two AABB objects next to other acting as the floor. The collision engine will pick up those vertical edges and cause the player to catch on them. There are hacks that can help, but not eliminate the problem. The solution is to just have a single line segment representing the surface rather than a full 2D box.

You can generate the hulls in the generic case by clipping the polygons against each other and joining the clip points into an edge list.

Sloping Surfaces

Since your example includes a slope and you're mentioning restitution and other physical properties, I'll point out a few other problems you're going to notice soon, which further illustrates why generic collision detection and response does not work well for platformers. First, try standing on the angled platform, jump up, and then land. You will likely notice that the character will "slide" a bit when landing. The problem is that the contact normal you're generating is usually going to be pointing out from the angled surface. Then, when resolving the collision, the player is pushed out in that direction. Even though the character was fall straight down, he'll be pushed up and a little to the right when landing, resulting in the slide. This can be hacked by taking the relative velocities into account, or by just hacking it so that the contact normals for static surfaces are always snapped to be axis-aligned.

The second problem you're going to notice, which is much harder to fix, is what happens when you try to run quickly down a ramp. The player is going to "hop" down the ramp. This is very visible even in most AAA games today. It not only looks silly, but if your game requires the player to be footed on the ground to jump, it makes it difficult to run down a ramp and jump halfway down, because the player is only contacting the ramp during a small portion of the time spent going down it. A simpler fix is to simply do some ray casts when the player moves, and snap the player position down to the nearest surface (if it's very close to the player) if the player is not jumping and was previously on the ground.

You may also find that the player launches into the air when running up a ramp if you try to model velocity, friction, and restitution on the player as if he were a normal rigid body. The player's movement should be constrained to horizontal movement unless falling/jumping. Of course, if you play older golden-age platformers, you may notice that the player's horizontal velocity is often constant between horizontal and sloped surfaces. This needs to be taken into account when walking up/down slopes as well.

There's going to be a number of other odd corner cases you'll eventually run into, too. If you're trying to make a good platformer, it's really just best to implement a platformer player controller separate from physics and hardcode the movement and control behavior you want, rather than relying on generic physics and collision response algorithm.

share|improve this answer
    
Thanks for your reply. I had considered reducing the boxes that represent the ground into lines, but I actually don't think that in itself will fix the problem. For example, if the ground boxes are now lines, and if the player is standing on line C and travelling left towards B, due to inaccuracy it's possible that the player box is slightly below line C. Then, the left edge of the player box could still collide with line B and cause that undesirable collision, –  Kovsa Mar 31 '12 at 3:19
    
unless there is some other mechanism to stop this from happening. It's not the fact that Box2D uses lines instead of boxes that fixes the problem, it's that Box2D uses a chain shape, which uses connectivity information between the line segments to prevent some collisions from happening. The main problem at the moment is I don't quite understand the details of how exactly it does this. –  Kovsa Mar 31 '12 at 3:19
    
You raised some other really good points about the problems with taking ideas from generic physics engines and applying them to platform games. I've seen similar engines that implement the ideas you discussed (modifying the collision normal for slopes, and sucking the player onto the slope), so at least those problems are fairly easily solvable. The main sticking point for me is the tricky edge cases related to numerical errors. –  Kovsa Mar 31 '12 at 3:19
    
@Kovsa: again, those particular errors disappear when you get rid of the edges that shouldn't be a part of the collision in the first place. Chain the edges together to form an uninterrupted shape. When designing your level, I'd also recommend snapping the vertices together so you don't have any small crevices in the surfaces. Not any different really than how you design the level in a 3D mesh editor. –  Sean Middleditch Mar 31 '12 at 3:28
    
Hmm... I don't think I follow. In my diagram, if I chain the edges together to make an uninterrupted shape, I would get a shape composed of three line segments: the top of boxes A, B, and C, right? Even though it's a single shape, I would still need to perform collision detection separately against line A, then B, then C, wouldn't I? Unless you meant an algorithm that can detect a collision between the box and this combined shape? I'm assuming it wouldn't be SAT then, since a series of edges could be concave? –  Kovsa Mar 31 '12 at 4:34
add comment

I think both problems could be solved by treating your boxes, for collision response purposes, as if they had rounded corners (of a similar radius to your numerical error). This will make the effective combined surface of the meeting corners between A and B, and B and C, smoother.

Thus if PLAYER moving left hits the corner of A, the collision normal would be diagonal rather than purely rightward, so allowing continuation of the left-and-up motion.


However, a more typical solution, on reviewing what I know of platformer physics, is to make the player a more highly rounded shape, and leave the terrain alone. In particular, consider making the player's shape a capsule (stretched-in-the-middle circle (2D)/sphere (3D)) — then your collision normals will naturally be nearly vertical, eliminating any catching problem.

You say you're using a collision algorithm specifically for OBBs, but you should still be able to, after finding an OBB-OBB collision, use a further test against a shape which is entirely within the OBB.

share|improve this answer
    
Hmm, interesting idea... how would you go about implementing it? It does go somewhat against the simplicity of using boxes though :(I agree that it seems like it should be a common issue with a definitive solution, but I can't find any coverage about it really... apart from what is being done in Box2D. I posted a similar question on their forum to hopefully get more insight. –  Kovsa Mar 29 '12 at 1:50
    
I don't have any implementation details, sorry — I'm not an expert on this sort of physics engine code. However, I did have a better idea for a solution which is not based on fudge factors — see my edit. –  Kevin Reid Mar 30 '12 at 21:02
1  
Note that while using rounded shapes does work, it's both more complex mathematically and it can result in sub-optimal behavior for platformers. Players expect to have near pixel-perfect control over characters standing on ledges, for instance, which rounded shapes will make more or less impossible, and characters will slide off the ledges unexpectedly. –  Sean Middleditch Mar 30 '12 at 23:16
    
Ledges: D'oh! OK, not as simple as I was thinking. –  Kevin Reid Mar 30 '12 at 23:18
    
Yeah, after thinking about it, the capsule approach seems perhaps more suited to a 3D game rather than a 2D platformer. Having pixel perfect control is definitely a priority for me (as it was in all those old 2D platformers). But there must be a solution that allows boxes to be used! –  Kovsa Mar 30 '12 at 23:35
add comment

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.