Separating axis test glitch help

Question

I'm working on a pretty basic 2D platformer and I'm wondering if I could get advice on an issue I've run into. To keep collision detection simple I'm using AABBs and separating axis tests for collision detection and this works fine for most cases. The problem is that when something is moving too fast my algorithm gets confused and returns a bad correction.

For example; the hero stands at the very edge of a platform (1-5px from the edge) and jumps. When the hero falls back down to the platform he travels through the platform (> 5 pixels) and then my collision detection moves him beside the platform and the hero falls to his doom. I understand the reason - being on the edge of the platform the hero is penetrating the object more on the y-axis as it its the x-axis and I'm choosing the smaller distance to correct by.

The immediate answer is to change my movement code so it does multiple tests for a few locations between the objects start and end position but the OCD bit of my brain complains about wasted cycles, etc...

Before I start gutting my code I was wondering if there was a more elegant way to solve this problem? Am I wrong in my assumptions? Have I managed to bugger up AABB SAT tests? Should I use a different algorithm?

Answer 1

One way that I've found helps alleviate this problem in platforming games is to prioritize which axis gets checked first in your SAT algorithm. For example, even though the x distance is shorter than the y distance, you can adjust your algorithm to always push on the y axis first. That way, even when your character is standing over the edge of a platform, he gets pushed upwards.

Performing multiple collision tests between the start and end positions is a fine solution if you're not having any performance issues. You can optimize it somewhat by moving the maximum distance you can get away with instead of a single pixel at the time. For example if your shape is a circle with radius 40, then moving 20 pixels at a time would work (half the radius so you don't go through thin objects).

If you want a more robust and faster solution, then you should use a continuous collision detection algorithm. Instead of intersecting with objects and then correcting, a continuous algorithm takes velocity into account and determines the time of impact, which you can then you to position the object where it needs to be.

It's actually not too difficult to implement continuous collision detection using SAT (assuming no rotation). The algorithm that you're using probably has you moving the object, then checking for collisions on multiple axes by searching for overlapping ranges. To modify this to be continuous, don't move the object first. Instead, you can calculate collision time on multiple axes by finding the distance between the closest points on each axis and dividing by the speed that the object is moving (on that axis). The minimum time will be the time of impact for the object, and if it's less than zero, then the objects are already colliding.

Answer 2

In your game, you will need to separate the logic for collision detection and collision response. Collision detection is the answer to the question "Is object A colliding with object B", which in this case, you're able to identify. Collision response is the answer to the question "If object A is colliding with object B, how do I separate them?"

It seems like you're having trouble handling collision response. Depending on your game you will have to figure out what exactly you'd like the player to do in these circumstances. There are a lot of different questions that have been asked with this in mind:

Getting 2D Platformer entity collision Response Correct (side-to-side + jumping/landing on heads)

2D game collision response: SAT & minimum displacement along a given axis?

How do I prevent my platformer's character from clipping on wall tiles?

My personal suggestion would be to take the player's velocity into account instead of simply moving along the least penetrated axis:

• If the player is moving predominantly in the y-direction, abs(vel.y) > abs(vel.x), then move him out of collision in the y-direction.
• If the player is moving predominantly in the x-direction, abs(vel.x) > abs(vel.y), then move him out of collision in the x-direction.