2D Platform Games Part 2: Collision Detection Tweaks

IMPORTANT! All of the articles in this series require you to have either Visual Studio 2010 or the Visual C++ 2010 Redistributable Package (4.8MB) installed in order to be able to try the pre-compiled EXEs provided with the examples. The Redistributable Package can be freely bundled with your own applications.

This article builds upon the demo project created in 2D Platform Games Part 1: Collision Detection for Dummies. Start with that article if you just stumbled upon this page at random!

Download source code and compiled EXE for the code in this article.

Now we have a working collision detection system, let’s have a look at a couple of problems with it.

Time stepping acceleration and deceleration

When implementing the player’s physics model, we were careful to ensure that changes to his/her movements were scaled relative to the time elapsed between the previous and current frames, rather than a fixed per-frame change. This is to ensure that if the frame rate drops, the player continues to move at the same rate: the longer the time between frames, the more movement is done on the next frame.

Unfortunately, the same cannot be said for acceleration and deceleration. These are added to the (time-stepped) movement vector as absolute values. When the frame rate drops, the player may jump too fast, fall too slowly and come to a halt during sideways movement too slowly as well. The solution uses a lucky quirk of mathematics.

First, we change all references to adding and subtraction acceleration/deceleration to be calculated relative to the frame rate as well:

// Move (accelerate) leftwards
if (GetAsyncKeyState(VK_LEFT))
{
	speedX -= LinearMovement(accX, updateTick);
	moveRequest = true;
}

// Move (accelerate) rightwards
if (GetAsyncKeyState(VK_RIGHT))
{
	speedX += LinearMovement(accX, updateTick);
	moveRequest = true;
}

...

// Apply the force of gravity
speedY += LinearMovement(accY, updateTick);

// Decelerate the player's sideways movement if left or right wasn't pressed
if (!moveRequest)
{
	if (speedX < 0) speedX += LinearMovement(decX, updateTick); 	if (speedX > 0) speedX -= LinearMovement(decX, updateTick);

	// Deceleration may produce a speed that is greater than zero but
	// smaller than the smallest unit of deceleration. These lines ensure
	// that the player does not keep travelling at slow speed forever after
	// decelerating.
	if (speedX > 0 && speedX < LinearMovement(decX, updateTick)) speedX = 0;
	if (speedX < 0 && speedX > LinearMovement(-decX, updateTick)) speedX = 0;
}

In short, wherever we used accX, decX or accY before, we now replace it with a call to LinearMovement (the time-stepping calculation function we discussed in the previous article) – even in conditions.

We then need to set the initial acceleration parameters to be multiplied by mScale squared (times by itself), instead of just by mScale alone (where mScale is the hypothetical desired frame rate although you can use any scaling factor you like):

accX = 0.2f * mScale * mScale;
decX = 0.3f * mScale * mScale;
accY = 0.5f * mScale * mScale;

If you now run the modified code, you will see that acceleration and deceleration work as expected even when the frame rate drops.

But how does this work? It seems like a strange thing to add a time-stepped acceleration vector to an absolute movement vector which is then modified to be time-stepped for each frame. The mathematical answer is that when the combined time-stepped acceleration and absolute movement is then time-stepped again, we are performing the equivalent of an integration. When a force of acceleration is integrated, it becomes a velocity (speed). When a velocity is integrated, it becomes a position.

If you don’t know what integration is, don’t worry; just use the trick above to ensure your acceleration works on a per-frame time-stepped basis.

Internal edges

Consider the following problem. Add this piece of geometry to the landscape:

ObjectDefinition objdef[] =
{
    ...
    // Internal edge problem test
    { 80*6, 80*1, Rectangle, .25f, .25f, PointTopLeft, 0.f, -10.f, PointBottomLeft, 0.f, PointTopLeft, 120, ResolutionY-20 }
};

(don’t forget to add 1 to worldObjectCount so this object is added to the world if you are following along)

This adds a sloping platform on the bottom-left side of the screen which intersects with the flat ground platform. Now try standing on the ground to the left and walking right up the slope. What happens? You stay on the ground and get stuck in the sloping platform at the base as if it is a wall.

Figure 1. The internal edges problem

This is a variation of the classic and infuriating so-called internal edges problem, whereby the collision solver incorrectly ‘solves’ a collision which includes an edge created between two touching objects in the game world.

The internal edges problem only occurs when you have objects which directly touch or overlap each other. Speculative contacts makes this problem much worse since instead of just finding when the player has hit a surface and moving him/her out of the way, speculative contacts forward predicts collisions with edges, but has no knowledge of which edges are external or internal.

Figure 1 (from Paul Firth’s blog – see below) illustrates the problem when two vertices (highlighted as green and red dots) collide. It is almost as if the player ‘trips up’ on the game world.

Normally, the ‘solution’ to this (which is really only a partial solution) is to detect internal edges and exclude them from hit testing, but this is tricky. For more details and another approach I refer you to Paul Firth’s article 2D Polygonal Collision Detection and Internal Edges for a thorough treatise on this thorny topic.

I don’t offer a real solution here; careful level design can mitigate the problem. With Direct2D, we have the saving grace that geometries can be arbitrary shapes, and via judicious use of ID2D1Geometry::CombineWithGeometry in union mode (which combines overlapping geometries into a single geometry) and ID2D1Geometry::Outline (which creates a version of a geometry with no internal edges – the outline shape only), we can avoid the issue altogether. See the Direct2D Geometry Overview for more information and examples.

In our collision detection code, we can fix the rest of the problem by simply removing some conditions that are no longer necessary:

// Detect what type of contact has occurred based on a comparison of
// the original expected movement vector and the new one
if (nextMoveY > originalMoveY && originalMoveY < 0)
{
	contactYtop = true;
}

if (nextMoveY < originalMoveY && originalMoveY > 0)
{
	contactYbottom = true;
}

becomes:

// Detect what type of contact has occurred based on a comparison of
// the original expected movement vector and the new one
if (nextMoveY > originalMoveY)
{
	contactYtop = true;
}

if (nextMoveY < originalMoveY)
{
	contactYbottom = true;
}

The original purpose of the removed conditions was to only mark the top or bottom collision points on the player as collided if we were moving up and corrected downwards, or moving down and corrected upwards. In the case of our slope, the bottom collision points of the player should also be marked when moving right from the ground up onto the slope, so that the player’s position is corrected upwards even when only moving horizontally, so these conditions must be removed.

Astute readers will notice that such ‘slope correction’ already works on slopes that aren’t connected to other platforms even when the player is trying to only move horizontally along it, but this is because speculative contacts corrects the Y movement vector for gravity while leaving X intact due to the way we coded it. When an internal edge is involved on the horizontal ground platform, speculative contacts corrects the player against the first iterated platform for gravity, setting the new desired Y movement to zero, which stops penetration resolution from making the correction when dealing with the slope. Phew, eh?

Rounding up

The source code and executable for the changes in this article are linked at the top. In Part 3 we’ll look at how to make your game world bigger than a single screen, scroll when the player moves, and how to add a scrolling background.

Advertisement