You can store whatever other useful information about the two touching shapes you need (like the normal of the surface they are touching that represents the axis of minimum penetration, by how far they are penetrating, etc).

Quoted for emphasis. This may sound like a subtle step, but the order of resolving collisions by the axis of minimum penetration makes a difference for better collision responses.

Here's a relevant article: http://www.geoffblair.com/blog/order-matters-tile-map-collision-response/

Now, this article presents other approaches to resolving axis of least separation, but for platform games they're not always necessary. I tend to just loop through the boxes/tiles that are colliding with the moving entity, no matter how they are ordered, and start resolving with the first one found in the loop. If penetration for X is shallower than Y, push away on the X axis.

@Randy Gaul

Thanks, I'll take a look at the slides.

Yeah that's a video of what my "game" actually looks like :) (I wish I could call it a game but I dont seem to be able to advance past the collision part...)

It may look like a lot is going wrong because of floats, but I don't think it actually is. Through all my debugging I never found the floats to be a problem.

At least not anymore, one change that fixed most bugs was changing the representation of my rectangle class to x,y for the top left corner and width and height instead of x2,y2 for the bottom right corner. Maybe I'm wrong and am just missing some sneaky cases.

But I think the main reason why its not working is because of the order the collisions get resolved in. Especially when I have to skip some collisions for special tiles/obstacles, like ladders.

I already had some kind of tile based system but then I realized I wanted freely moving platforms etc, so I rewrote everything.

Another reason why I wanted to rewrite it is because I thought tile based would be too restrictive and I might as well go with the "real" thing.

@CC Ricers

Hmm I think I tried something like that and a few things didn't work out, thats why I switched to calculating the "time of impact" instead of penetration amount checking.

One of the things was the same thing that's being adressed in the article: Wrong resolutions. But I'm not sure If I tried it with the correct ordering.

Maybe I could try swapping the techniques around and do it with the least penetration amount technique again.

I'm kind of sick of fiddling around with it. For two years I am stuck with this problem now and I'm making next to no progress... soooooo frustrating argh...

But of course I didn't work 2 years non-stop on it. Otherwise I would already have gone insane

Have been procrastinating a lot because I have absolutely no idea what to do anymore and I'm kind of lazy and demotivated.

@CC Ricers

Hmm I think I tried something like that and a few things didn't work out, thats why I switched to calculating the "time of impact" instead of penetration amount checking.

One of the things was the same thing that's being adressed in the article: Wrong resolutions. But I'm not sure If I tried it with the correct ordering.

Maybe I could try swapping the techniques around and do it with the least penetration amount technique again.

I'm kind of sick of fiddling around with it. For two years I am stuck with this problem now and I'm making next to no progress... soooooo frustrating argh...

But of course I didn't work 2 years non-stop on it. Otherwise I would already have gone insane

Have been procrastinating a lot because I have absolutely no idea what to do anymore and I'm kind of lazy and demotivated.

I know that feeling... it was the same for me for a other game prototypes i made.

But regarding platformer physics, i got pretty good results using technique called speculative contacts with sonics sensors for the entities.

The core idea behind that technique is use sensor points on the left/right edges and top/bottom edges for every entity to determine which tiles needs to be checked.

This is your broadphase if you will, then grow every tile with the entity half-size (minkowski difference) and determine the closest point against that fatten tile aabb. This closest point is extremly simple to determine of your sensors include the separating normal as well - so its just a simple vector projection. Lastly you get the difference between entity position and the closest point. Then you project this difference against the separating normal from the sensor and create a contact for it including its distance even when positive. At final stage, you just need to solve this contact using the speculative contacts approach descriped here:

http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

This technique works for non-tile shapes as well, you just need a way to calculate the closest point and the distance between the centers using minkowski difference.

Of course for non-aabb cases, the sensor approach may not work, but i never tried it.

The only downside to this technique you cannot control how a wall bounces you off. Bouncing will be solved by automatically when you include its in the solver as well. But you cannot control how the object bounces - like in box2d for example, where you can specifiy the coeffecient of restitution. Therefore this technique is mostly suited for platformer - just to give you an example: Little big planet use this technique and is therefore extremely stable.

But the main benefit of this technique is to not worry about TOI at all and get continous collisions out-of-the-box - the system finds a global state very fast and can be used for rigidbody physics as well.

If you need further explanations, check out the link i posted in the block above.

Greetings,

Final

Aren't we all over thinking and over engineering the solution and seeing a bigger problem than actually exists?

If you look at how games like Mario did this (these games have been heavily disassembled and analysed and reverse engineered) there wasn't such heavy physics involved. For most platform games even with sloping floors and curved surfaces like sonic the hedgehog it can be done with simple pixel based logic comparisons for collision detection and bresenham style integer based algorithms for climbing slopes.

I suggest simplifying the problem, heavyweight physics libraries and polygon collision with matrices are like trying to cross a small stream using an ocean liner in my opinion. As we always say, KEEP IT SIMPLE. :)

You seem articulate and sharp. I think you may be hanging up on more of a human thought problem than a programming problem.

When working on a narrow problem, it is sometimes hard to "see out of the box". All the details of our current attempts seem to just box us into a narrow set of possibilities.

Instead of telling us (and yourself) about your worry that you may not be able to solve it..change your perspective...

You know *someone* has done similar work in a satisfactory way. So it is possible (probably). Ask yourself "how can i get behavior x out of the system", then do research (like you are doing here) or brainstorm.

Help your brain climb out of the box by giving it the confidence that there must be a way out of the box, and you just need to find it. Expect it to solve your actual problems, not achieve perfect purity (which is not possible for software).

If you want code review and suggestions, im happy to take a look. Hit me up at davidj (at) gmail .

But what if the solution is inside the box, it's just too small or too obvious to see it? Like when your looking for your glasses but you have them on already :) Then stepping out of the box would be a mistake ;)

That's another problem I often have, not knowing if I'm moving in the right direction. Should I keep going, am I close to a solution? Or am I heading into a dead end and should rather turn around, look for another way?

My current approach seems to be kind of working and my gut tells me I just need to fine-tune it somehow, it's likely just some minor mistake that messes everything up.

Like an "off by one" error. (i.e. > instead of >=). Found one just yesterday, after a long time of not noticing it at all.

A big problem is that I currently have no real idea how to catch bugs that happen in real time, like when my game is running at 60 fps and from one frame to the other, suddenly the player falls through the floor. I can't go back in time and look at all the possible states the player was in, and I can't set a breakpoint if I don't know when, why or where in the code it happens. If I set a breakpoint before collision resolution happens, it will break EVERYtime, even when the resolution works correctly.

Displaying the coordinates etc on the screen is also useless because it changes way too fast.

Maybe I need to implement some way to only move one timestep per keypress or a giant array of past states of everything, I don't know.

I have read a few articles explaining algorithms like GJK, SAT, minkowski sum/diff in the past but somehow I find it hard to get a good intuition for it and putting it together into a working system.

But I don't think I will need any of those more advanced algorithms anyway in a "simple" project like mine, I will never have any polygons or rotated rectangles, just plain old AABBs.

Simple arithmetic on position, size and velocity should be enough, like braindigitalis suggested, or am I wrong?

It's just a matter of correct order of operations, update first, then check for collisions, or check before moving, solve collsion A first then B or other way around, if solved, start a new iteration of collision checks or keep going etc...

Well, I will keep trying, I guess it's just a matter of trial and error. By the way, thanks for all your input, everyone :)

An important problem I noticed is that you hope to deal with enormous time steps in which arbitrarily complex event sequences take place. Specifically, you have forces and impulses applied in the middle of movement (gravity when not standing, returning to a desired velocity, etc.), which should instead be respectively constant and applied between movement steps.

Instead, decompose the simulation into elementary collision and control steps in which complexity is manageable. You can always advance simulation time several times in small steps that add up to the desired frame duration.

For example, the falling into a gap example includes multiple events and states: walking on the first platform, crossing the first platform edge, flying over the gap, and then either crossing the far platform edge and walking on the far platform or hitting the vertical wall and sliding down.

Correct handling requires separating walking on a platform from walking into the pit: in the latter case the character would fall down slightly and reach the far platform edge with his feet below the platform level; at this point you have a wall-hitting event, with a certain wall height and velocity (which, assuming a standard walking speed, depend only on platform heights and pit width).

When the characters hits the far vertical wall you can proceed with the physically orthodox outcome of sliding down or perform specific platformer-appropriate animations according to the situation (for example, sorted by increasing height loss: just raise legs and feet a little; land with the knees on the platform and stand up; tumble rather badly; grab the ledge with hands and stop; brace for impact against the wall and fall down).