Collision Resolution with “Pseudo” Normals

In working on my 2D side-scroller game, one big part of work came from collision handling. I felt a tile-based approach was inefficient and archaic (and rather unsuitable in any case), so I went with a polygon collision system using the Separating Axis Theorem. You can find specific details of the implementation/idea here at metanet software.

In short, you project each vertex of two polygonal shapes onto each perpendicular axis of one shape, then you test for overlap. If the shapes do not overlap on ALL axes, then the shapes cannot be intersecting (and thus are not colliding).

This implementation is pretty straightforward, and is explained in a lot of places on the net. What does not seem to be explained, however, is how to resolve the collision after one has been found. While this varies from situation to situation, my focus was on player-to-world collision, which meant leaving the world still and moving the player out of the world’s geometry whenever a collision was made.

This is actually simple enough to do if you are already using SAT; just store the overlap value and which axis it occurred on, and correct by the smallest amount of overlap so that you will be pushed correctly out of the object.

However, in my game problems began to arise when I started introducing slopes into the mix. Originally, I was calculating the displacement of the polygons in a manner like this (excuse the pseudo-code):

disp = dotProduct(mtv.axis, dir);
if(disp < 0)
	mtv.axis = -mtv.axis;

this would tell us if the correction (or ‘push’) vector and the world polygon were in the same direction. We don’t want that; it would push our player further into the world geometry, instead of away from it (and ultimately, with enough corrections, could push us through the other side, or get stuck in an infinite loop in some cases). If the displacement is less than 0, we flip the correction axis to fix this.

But the problem is, with slopes, the displacement varies. For example, look at this mockup shot below (hastily done of course):

As you can see, on the slope, the displacements are all over the map! At the bottom of the slope, he’s to the right and below, at the middle he’s above and to the right, and near the top, he’s to the left and above! This causes the displacement to flip the correction vector incorrectly in about half the positions on the slope, not to mention it totally screws up with ceiling slopes; the player’s push direction is completely wrong if we cannot tell that the player is coming at the slope from below! Compare this to the two players on the left near the rectangular object; the displacement is always correct because there can only be a single general direction for the player to be relative to the polygon.

How do we solve this?

The answer is with a sort of trick, something that actual physics engines would implement on a full scale, and that is to calculate a sort of normal direction (a unit vector with a length of 1, indicating as such a direction) for the polygon surface. Now obviously it’s not a true normal; we are not calculating in 3D and therefore are not making use of tangent space (although maybe my terminology is wrong, so forgive me).

The way I implemented it was to calculate the midpoint of the polygon edge, and subtract the pre-calculated centroid of the polygon shape from that midpoint location. Luckily, I managed to make this quite efficient by modifying SFML and having it calculate the centroid for me whenever the polygon received an “update” (I can post the code if needed). The code for this whole fix looks like this:

	// Get normal direction
	mp = Midpoint(getPoint(shape_1, i), getPoint(shape_1, next_i));
	sf::Vector2f normal = mp - center1;
	normal = unitVector(normal); // normalize
	// perpendicular axis is not the same for the slope
	// we must change it
	mtv.slopeAxis = unitVector(side);
	mtv.slopeamt = std::abs(mtv.slopeAxis.y / mtv.slopeAxis.x);	// rise / run = slope
	mtv.axis = normal;
	// Don't change x movement if a floor slope
	// only push the player on both axes if
	// the slope is on the ceiling
	if(normal.y < 0)
		mtv.axis.x = 0;

And that’s it! Using a sort of “fake” normal (while very approximate, good enough), we can tell which side and where the player is relative to the polygon, and this gives us enough information to know if we should flip the correction vector or not!

Leave a Reply