2D Platform Games Part 11: Collision Detection Edge Cases for The Uninitiated

IMPORTANT! To run the pre-compiled EXEs in this article, you must have Windows 7 Service Pack 1 with Platform Update for Windows 7 installed, or Windows 8.

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

Download source code and compiled EXE for the code in this article as well as the complete source code and compiled EXE for the level editor.

With the ability to create levels easily comes the ability for your colleagues to produce gameplay scenarios you hadn’t thought of, and by consequence reveal a host of tricky bugs in your code. In this article, we shall look at a variety of so-called edge cases – an engineering term meaning things which don’t happen often, or only under a very specific set of circumstances – and how to fix them so they work correctly. The included source code includes a number of levels which demonstrate each problem so you can load them into the code from Part 10 to see how the behaviour compares with the updated code from this article.

Re-factoring forenotes

In this version of the code, some re-factoring has been done:

• the class definitions used by the game have been moved to their own header file, SimplePlatformer.h
• the Surface class now has a convenience constructor and the definitions for each surface have been moved to SurfaceTypes.cpp
• since we will be introducing new object types in the next part of the series, all references to worldObjects have been changed to worldGeometry for clarity
• we will be introducing a new variable indicating the previous platform the player was standing on, so all references to the existing previousPlatform have been changed to previousFramePlatform for clarity, to indicate the variable stores the platform the player was standing on in the previous frame only

With that out of the way, let’s proceed.

Thick and Steep-incline pass-through platforms

Original code: Part 8
Test level: big-pass-thru-test.splevel and big-pass-thru-test-2.splevel

Thick platforms

The problem: If a player jumps while fully contained within a thick (taller than the player) pass-through platform and doesn’t reach the top, he/she is collision-corrected to the top of its surface instead of being allowed to fall back down again.

The cause: The test which cancels out collisions between the bottom of the player and the pass-through platform when the player’s base is not fully above the platform’s top edge fails, and a large upwards correction is incorrectly applied.

The solution: Add a buffer zone such that the player’s position is only corrected upwards if the distance between the player’s base and platform top is less than a few pixels (we use 5 in this example).

Sloped platforms

The problem: When walking on or falling down to land on a highly sloped pass-through platform, the player may incorrectly fall through the platform.

The cause: Collisions for the bottom of the player vs the top of the pass-through platform are disabled when both the bottom of the player plus any other side of the player is intersecting the platform, or the player is moving upwards. The purpose of this is to prevent snapping the player up to the surface when partly inside but not wholly above the platform. When walking up a steeply-sloped platform, the left or right side of the player may be intersecting it slightly as well as the bottom, and the player is moving upwards, so collisions with the top of the platform are incorrectly disabled and the player falls through.

The solution: Only count contacts with the left and right sides of the player when considering whether to disable collision detection for the platform’s top edge if the player is moving in the opposite X direction. Ie. if the player is moving right, ignore contacts with the player’s right hand side and vice versa. This will not break the existing code which is designed to check if the player is inside the platform, since if they are wholly inside it, at least one of the left or right sides will be counted as intersecting it whichever direction the player is moving.

The code:

Change the pass-through processing code from:

if (!surfaces[(*it)->surface].allowInside)
{
	// If the top side is solid but we are not yet all the way through the platform,
	// don't apply penetration resolution to force the player up to the surface
	if (contactYbottom && (contactYtop || contactXleft || contactXright || preresMoveY < 0) && !surfaces[(*it)->surface].allowFromAbove && !standingPlatform)
		contactYbottom = false;

	// If the bottom side is solid but we are not yet all the way through the platform,
	// don't apply penetration resolution to force the player underneath
	if (contactYtop && (contactYbottom || contactXleft || contactXright || preresMoveY > 0) && !surfaces[(*it)->surface].allowFromBelow && !standingPlatform)
		contactYtop = false;

	// The same for one-way left and right 'doors'
	if (contactXleft && (contactXright || contactYtop || contactYbottom || preresMoveX > 0) && !surfaces[(*it)->surface].allowFromRight && !standingPlatform)
		contactXleft = false;

	if (contactXright && (contactXleft || contactYtop || contactYbottom || preresMoveX < 0) && !surfaces[(*it)->surface].allowFromLeft && !standingPlatform)
		contactXright = false;
}

to:

if (!surfaces[(*it)->surface].allowInside)
{
	if (contactYbottom && (contactYtop || (contactXleft && preresMoveX >= 0) || (contactXright && preresMoveX <= 0) || preresMoveY < 0) && intY > 5 && !surfaces[(*it)->surface].allowFromAbove && !standingPlatform)
		contactYbottom = false;

	// Same as above but in reverse for pass-through floors
	if (contactYtop && (contactYbottom || (contactXleft && preresMoveX >= 0) || (contactXright && preresMoveX <= 0) || preresMoveY > 0) && !surfaces[(*it)->surface].allowFromBelow && !standingPlatform)
		contactYtop = false;

	// The same for one-way left and right 'doors'
	if (contactXleft && (contactXright || (contactYtop && preresMoveY >= 0) || (contactYbottom && preresMoveY <= 0) || preresMoveX > 0) && !surfaces[(*it)->surface].allowFromRight && !standingPlatform)
		contactXleft = false;

	if (contactXright && (contactXleft || (contactYtop && preresMoveY >= 0) || (contactYbottom && preresMoveY <= 0) || preresMoveX < 0) && !surfaces[(*it)->surface].allowFromLeft && !standingPlatform)
		contactXright = false;
}

The additional conditions against preresMoveX and preresMoveY check which direction the player wants to move in this frame. The test of intY (which is the number of Y pixels intersection between the player and the platform) ensures that no upwards correction greater than 5 pixels occurs.

Unfortunately this fix re-introduces the problem described in Part 8 where the player gets snapped to the top of a pass-through platform when jumping from underneath it – but now only when the player’s bottom edge is 5 pixels or less penetrated into the top of the platform (which will happen during a jump which starts from underneath the platform and would plateau with the player’s bottom edge towards the top edge of the platform at the peak of the jump). To solve this, we also disable player bottom-edge player collision detection from the platform while the player is jumping, providing of course that the other conditions also hold:

if (!surfaces[(*it)->surface].allowInside)
{
	if (contactYbottom && (contactYtop || (contactXleft && preresMoveX >= 0) || (contactXright && preresMoveX <= 0) || preresMoveY < 0) && intY > 5 && !surfaces[(*it)->surface].allowFromAbove && !standingPlatform)
		contactYbottom = false;

to:

if (!surfaces[(*it)->surface].allowInside)
{
	if (contactYbottom && (contactYtop || (contactXleft && preresMoveX >= 0) || (contactXright && preresMoveX <= 0) || preresMoveY < 0) && (jumping || intY > 5) && !surfaces[(*it)->surface].allowFromAbove && !standingPlatform)
		contactYbottom = false;

Being killed by crush detection when the player is really just stuck

Figure 1. The crush/wedge problem. The player’s bounding box is represented by the white rectangle. At some point as the player moves to the right, the player’s top and bottom sides will both be making contact with a platform and the collision detection code will consider the player to be crushed as there is no correct resolution.

Original code: Part 4
Test level: wedge.splevel

The problem: Two horizontal platforms are angled such that the player’s top and bottom sides can intersect them both at the same time (see Figure 1). When the player walks far enough to the right, he/she is killed incorrectly.

The cause: The collision detection code considers the player to be crushed by the world geometry if the player’s top and bottom (or left and right) sides are touching platforms simultaneously. In this situation, there is no correct vertical (or horizontal) correction that can be applied, so if we don’t mark the player as dead, they will rapidly oscillate up and down (or left and right) as the contact solver fails to resolve the collision on each frame.

The solution: Only consider the player to be crushed when one or both of the intersecting platforms are moving platforms. You cannot be crushed by a platform that doesn’t move (the problem of failed penetration resolution is dealt with in the next section).

The code:

Add a new flag cPmoving to track whether any of the platforms intersecting with the player this frame are moving or not:

	// Reset the player collision point hit checks for crushing
	// Unlike the contact* variables, these are not reset after each object is tested
	// as we need to know whether the player is colliding with multiple objects from
	// different directions at the same time to detect being crushed or squashed
	bool cPtop = false, cPbottom = false, cPleft = false, cPright = false;

    /* NEW CODE */
	// We also need to know if at least one (or more) of the objects the player collides
	// with are moving, since you cannot be crushed by non-moving platforms (your
	// movement is blocked instead as per normal)
	bool cPmoving = false;

Update the penetration resolution directional testing loop to note whether the intersecting platform is moving:

switch (dir) {

case 0: if (!surfaces[(*it)->surface].allowInside && !surfaces[(*it)->surface].allowFromBelow)
	{
		nextMoveY += intY;
		cPmoving |= ((*it)->moving);
		cPtop = true;
	}
	else
		contactYtop = true;
	break;

case 1: if ((!surfaces[(*it)->surface].allowInside || (!previousFramePlatform && !surfaces[(*it)->surface].allowFallThrough)) && !surfaces[(*it)->surface].allowFromAbove)
	{
		nextMoveY -= intY;
		cPmoving |= ((*it)->moving);
		cPbottom = true;

		if (surfaces[(*it)->surface].allowInside)
			contactYbottom = true;
	}
	else
		contactYbottom = true;
	break;

case 2: if (!surfaces[(*it)->surface].allowInside && !surfaces[(*it)->surface].allowFromRight)
	{
		nextMoveX += intX;
    	cPmoving |= ((*it)->moving);
		cPleft = true;
	}
	else
		contactXleft = true;
	break;

case 3: if (!surfaces[(*it)->surface].allowInside && !surfaces[(*it)->surface].allowFromLeft)
	{
		nextMoveX -= intX;
		cPmoving |= ((*it)->moving);
		cPright = true;
	}
	else
		contactXright = true;
	break;
}

This code is identical to before with the exception that cPmoving is now updated with each piece of geometry tested.

The crush check then becomes:

if (((cPleft && cPright) || (cPtop && cPbottom)) && cPmoving)
    dead = true;

The player can now only be crushed by moving platforms, but if you run the updated code, you will see that when the player becomes wedged between the two static platforms when walking to the right, the player’s position is grossly over-corrected to the left as penetration resolution fails to find a good solution.

Over-correction when the player is wedged between platforms

Original code: Part 1 (penetration resolution, but problem only becomes apparent after crush fix above)
Test level: wedge.splevel

The problem: When the player becomes wedged between two platforms, his/her position is over-corrected when really we want the player to just not be able to move any further in the requested direction.

The cause: Referring to figure 1 again, when the player reaches the wedged location by walking right, about half of the width of the player’s bounding box is intersecting each platform. Correcting the player up or down will not help, so the code instead corrects the player to the left by this half-player-width amount – a sudden and unexpected over-correction.

The solution: Store the player’s original position before any iterations of the contact solver are executed. If, at the end, the crush point flags for either top and bottom or left and right are set, but the player is not dead, then he/she must be wedged, so completely override the results of the contact solver by restoring the player’s original position stored earlier. This prevents movement in any direction except away from the wedge location (where the crush points will not be set).

The code:

Before the start of the contact solver iteration loop:

// Store the original position of the player
// This is for if we find ourself in a situation where the player is wedged
// horizontally or vertically by two objects, and shouldn't be allowed to
// move in the desired axes at all
float originalPlayerX = playerX;
float originalPlayerY = playerY;

Immediately after the end of the contact solver iteration loop (because the player’s position is updated):

if ((cPtop && cPbottom) || (cPleft && cPright))
{
	playerX = originalPlayerX;
	playerY = originalPlayerY;
}

Astute readers may wonder why we don’t check and correct only one axis at a time. This is because if the player walks between two intersecting slopes (horizontally as in Figure 1), therefore touching the top and bottom of the player, he/she should not be allowed to continue walking on the X-axis, as well as not being corrected up and down in the Y-axis due to the penetration resolution code failing to find a correct solution.

Being propelled up a ladder when entering it from the side and jumping

Original code: Part 8 (bug introduced), relates to code in Part 5 and Part 6
Test level: 1-default.splevel

The problem: If you are moving left or right and jumping, then intersect with a ladder, you may suddenly move a large upward distance on the ladder.

The cause: The problem occurs in the code which determines whether we have just touched down on the surface of a platform which does not allow fall-through (which includes ladders). The check only considers the bottom edge of the player, not the top edge. Therefore we can be incorrectly assumed to have landed on top of a platform when we are in fact inside it (the ladder). A large amount of upwards penetration resolution is then applied. The problem only occurs while jumping because while not jumping, you are considered to be standing on another platform (the one you are actually standing on). The problem only occurs when moving sideways because falling on top of the ladder will apply the fall-through test correctly.

The solution: Add a check to the fall-through test to only allow penetration resolution to be applied when the bottom edge but not the top edge of the player is touching the platform where pass-through is disallowed.

The code:

Change:

if (previousFramePlatform != (*it) && contactYbottom && !surfaces[(*it)->surface].allowFallThrough)
{
}

to:

if (previousFramePlatform != (*it) && contactYbottom && !contactYtop && !surfaces[(*it)->surface].allowFallThrough)
{
}

Inability to jump when moving down a steep slope / Cheating acceleration on low-friction platforms

Original code: Part 1
Test level: test world 1-v1.splevel

The problem: When walking down a slope with a steep incline, you can’t always jump.

The cause: Jumping when in mid-air is disallowed. When you walk down a steep slope, gravity does not pull you down fast enough each frame to keep you touching the platform, so the code assumes the player is in mid-air and falling (which technically, he/she is).

The problem: The player can move a small amount on a low-friction, high-acceleration platform such as ice, jump up and then move very fast relative to the X axis during the in-air movement.

The cause: The physics model for X-acceleration of the player is based on the last platform the player was standing on; only Y-acceleration (gravity) is modified to the default behaviour during in-air movement.

The solution: The first problem can be improved for low-friction platforms, and the second problem can be solved, by resetting X-acceleration to the default behaviour when the player is in flight.

The code:

Adding two lines of code to the section which decides which physics model to use does the trick:

// The physics applied to the player depend on the type of surface we are standing on
if (standingPlatform)
{
	accXf = surfaces[standingPlatform->surface].accXf;
	accXb = surfaces[standingPlatform->surface].accXb;
	decX = surfaces[standingPlatform->surface].decX;
	accY = surfaces[standingPlatform->surface].accY;
	decY = surfaces[standingPlatform->surface].decY;
	maxSpeedX = surfaces[standingPlatform->surface].maxSpeedX;
	maxSpeedY = surfaces[standingPlatform->surface].maxSpeedY;
}

// We are in flight. Use standard gravity.
// Including the Y-deceleration is also important here because transitioning from a platform
// such as a ladder with no Y-deceleration to flight will cause gravity to malfunction
// if the Y-deceleration is not reset.
else
{
	/* These two lines prevent a player moving slightly on eg. ice, then jumping
	and accelerating really fast in X to cheat. They also prevent too much in-flight
	time when moving down a high-acceleration slope (eg. ice) which can prevent the
	player from jumping since jumping is disallowed when in flight */

    /* TWO NEW LINES OF CODE HERE */
	accXf = surfaces[Normal].accXf;
	accXb = surfaces[Normal].accXb;

	accY = surfaces[Normal].accY;
	decY = surfaces[Normal].decY;
}

Notice that the first problem is not solved completely, just somewhat improved if the player was moving very fast down the slope. Fixing the second problem is essentially replacing one issue for another: the player can now cheat on high-friction platforms by jumping in the air and moving left and right to escape the “stickiness” (friction). However, this is the lesser of the two cheats as their top speed and acceleration is restricted as soon as they land again.

Jumping while on a fast upwards-moving platform

Original code: Part 4
Test level: jez01.splevel

The problem: Jumping while standing on a platform that is moving upwards at high speed causes the player to die (be marked as crushed).

The cause: The platform’s upwards acceleration exceeds the player’s upwards acceleration. When the player starts to jump, the platform intersects the player, the top and bottom edges of the player (or the left and right edges) are both touching the inside of the platform at the same time, and since it is a moving platform, the crush flags are set and the player is considered to be dead, then re-spawned.

The solution: Make the player’s jump speed relative to the platform’s speed.

The code:

First, we’ll need to store the amount of vertical movement of the platform we are standing on this frame. Before the contact solver iteration loop (but after the vertical movement of the platform the player is standing on this frame is calculated):

// Remember how much movement the moving platform caused in Y because of we jump off it,
// we will need to add this to our vertical speed to stay at a speed relative to the platform
float originalNextMoveYextras = nextMoveYextras;

In the code where we initiate a jump in response to player input, we now need to check if we are standing on a vertically-moving platform, and if so, include its current acceleration in the upwards acceleration of the player, in addition to the upwards impulse generated by jumping:

// Jump if not already jumping and the jump key was released earlier
if (GetAsyncKeyState(' ') && !jumping && !jumpKeyDown)
{
	if ((standingB && !standingT)
		|| (standingB && standingT && speedX != 0))
	{
		jumping = true;
		jumpKeyDown = true;
		jumpPlatform = standingPlatform;

		speedY = -jumpStartSpeedY;

		// Include the speed of a moving platform we just jumped from to keep our
		// jump movement relative to the speed of the platform
                /* THESE TWO LINES OF CODE ARE NEW */
		if (originalNextMoveYextras < 0)
			speedY += originalNextMoveYextras * mScale * mScale;

		// Start jumping animation from the first frame
		playerJumpAnim.Reset();
	}
}

In truth, this is a time-of-impact ordering problem: the platform should push the player upwards rather than crushing them. However, since we have no TOI ordering code in our project, we will have to fudge the fix. Having said that, an object’s velocity should take into account the velocity of the object it is standing on anyway (think of jumping in an elevator; the jump is normal, you appear to be standing on a non-moving floor because your jump speed is relative to the speed of the elevator). The way we deal with standing on moving platforms in general is a horrible fudge because the player’s speed should be automatically aligned with the speed of the platform, instead of using the per-frame pixel movement calculation we currently employ. If we did this, the problem would never have occurred.

Why have we multiplied the upward pixel movement by mScale^2 and added it to the vertical speed? Essentially, we are differentiating the pixel movement of this platform per frame twice: once into speed, and again into acceleration.

Solving the false positive on crush detection reveals a new problem: now when you jump while standing on a pass-through platform, if the platform still overtakes you (because it continues accelerating upwards, while you are slowed down by gravity), you can fall through it. In an earlier fix above, we disable collision detection for the bottom edge of the player against pass-through platforms when they are jumping under certain conditions. We need to add another condition: ignore collision detection for the player’s bottom edge while they are jumping but only when the platform they are jumping from is not the platform being tested. This ensures that if we have just been hit by the top edge of the platform we just jumped from, that collision detection remains enabled and we land on it.

For this to work, we need to store the platform we were last standing on:

In the main game class definition:

// The platform we were previously standing on (if we are currently on a platform,
// this will be the same as standingPlatform)
Platform *previousPlatform;

In spawnPlayer():

// No previous platform
previousPlatform = nullptr;

Right after the player’s position is updated after the collision detection code:

/* EXISTING CODE */
// Update which platform we are standing on
standingPlatform = standing;

/* NEW CODE */
if (standingPlatform)
	previousPlatform = standingPlatform;

The net effect of this is that previousPlatform will be the platform we are currently standing on, if we are standing on one, or the last platform we were standing on if we are in flight.

Now we can add the condition described above to the pass-through processing. Change:

if (!surfaces[(*it)->surface].allowInside)
{
	if (contactYbottom && (contactYtop || (contactXleft && preresMoveX >= 0) || (contactXright && preresMoveX <= 0) || preresMoveY < 0) && (jumping || intY > 5) && !surfaces[(*it)->surface].allowFromAbove && !standingPlatform)
		contactYbottom = false;

to:

if (!surfaces[(*it)->surface].allowInside)
{
	if (contactYbottom && (contactYtop || (contactXleft && preresMoveX >= 0) || (contactXright && preresMoveX <= 0) || preresMoveY < 0) && ((jumping && previousPlatform != *it) || intY > 5) && !surfaces[(*it)->surface].allowFromAbove && !standingPlatform)
		contactYbottom = false;

Well… that was awkward

In Part 12 we shall move away from platform handling and collision detection, and on to the business of adding interactive game objects like baddies to the game world. There will also be some improvements to the level editor. Until next time!