2D Platform Games Part 1: Collision Detection for Dummies

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.

Try the demo! This article will teach you how to write the following sample project from start to finish: 2D collision detection demo (use the left and right arrow keys to move and the space bar to jump)

Since the one-day game coding challenges of SimpleTetris and SimpleAsteroids, several people asked me if I could do a timed challenge to make a Mario or Donkey Kong-style platform game. For shame, I haven’t had chance to do this yet, but while I’ve been thinking about that I thought it might be nice to look at how collision detection works, as this is surely the trickiest part of coding a 2D platform game.

Now, let’s not beat about the bush: collision detection is a nightmare when done right. There are many types of 2D platform game, from strictly grid-based to Mario-style platformers where collision detection is simplified by limiting the game world to using certain specific types of platform at certain specific slope angles, all the way to modern games like LittleBigPlanet where the world is completely free-form with arbitrary platform geometry.

There are some brilliant articles on 2D collision detection on the net and I have linked to my favourites at the end of this article. The important thing that they have in common is they are either quite theoretical, use a certain degree of non-trivial math to get the job done or do not have complete source code available for free (and the best ones are written in Flash / ActionScript or Java anyway, not C++). Here I would like to present a practical, hands-on approach to 2D collision detection, developing a complete example in C++ from start to finish. We will look at the various problems that crop up and how to solve them.

The code presented below is not particularly elegant, efficient and may contain a few bugs, but it should be a good start, with the theory and math kept to a minimum. Nevertheless, collision detection is an ugly business, and to quote the Queen of Sparta: this will not be easy, you will not enjoy this (and you are very probably not my King).

Goals

As mentioned there are many types of 2D platform game and collision detection. For this article, I am going to present a demo which does the following:

• Allows use of arbitrary geometry (any obstruction can be anywhere on screen)
• Allows free-form player movement (the player can move freely on a per-pixel basis) – left, right and jumping
• Handles all possible collisions between the player and the geometry

We will not look at player-enemy, player-power-up or other such collisions here (although with the bounding box technique explained below this is fairly trivial to implement), nor will we look at enemy-landscape collisions for situations where the enemies are allowed to move free-form as well rather than being on fixed pre-defined paths. The player is assumed to be a rectangular sprite.

We will also look at and solve these problems:

• Application of gravity
• The so-called ‘jitter’ problem
• The so-called ‘bullet through paper’ problem

An Historical Aside

Some of you may even be old enough to remember the 80s, in which case, you may also remember these classic techniques:

The Grid-Based Approach

Figure 1. Spelunker is a grid-based 2D platform game (source: http://www.theexaminer.com)

Every level in the game is arranged in a rectangular grid, where each grid square contains a platform tile, or not. The player always resides in exactly one square too (the game may be animated to give the appearance of being half in one square and half in the other, but when you move left or right, the character always moves so that it ends up exactly in the next grid square). See Figure 1.

Collision detection for these types of games is simple. You can simply maintain the game world in a two-dimensional array and check if the player’s desired movement will cause them to end up in a tile, and if so, prevent the movement. No pixel-based collision detection is needed, and there are no angular collisions to worry about since you can only move in one of four directions.

The Pixel Colour Approach

Commonly used on computers which had a limited number of colours (8 or 16 for example), the platforms would be plotted in one colour, and all other game elements in other colours. The player can move around freely, but the colour of adjacent pixels is tested before movement is allowed to check if it would cause the player to collide with a platform or wall. This of course has the obvious disadvantage that you can never use the platform colour for other scenery or characters, or most significantly, in the background.

Pixel tile terrain example. ‘S’ is a sky tile, ‘N’ is a solid ground tile and ‘H’ is a hill tile (source: Programming MC Kids, link in references)

The Pixel Tile Method

Here, the player can move free-form, but the available platforms are limited to a pre-defined selection of square tiles. These may be ‘sky’, ‘solid’, ‘flat’, ‘sloping’ etc. A number of collision points are defined around the player sprite, for example his feet, and for each tile type, a table is stored indicating what to do when a collision occurs on a specific pixel of the tile. Imagine an 8×8 pixel tile containing a piece of hill sloping down from top-left to bottom-right (see image to the right). The collision table will specify that when moving left, if a collision occurs between the player’s feet and the solid part of the tile, to move up 1 pixel, and conversely to move down 1 pixel when moving right. Thus, the correct response to a collision to bring things back into equilibrium is encoded in the tile information.

The Mask Approach

In this technique a copy of the level (or part of it) is stored in memory in black and white, where white represents platforms or other obstructions, and black represents anything else. A copy of the player sprite is also stored where white represents solid points on the player’s avatar where collisions should be considered, and black pixels are ignored. Such black and white images corresponding to other colour images are called masks. When the player tries to move, each white pixel in the player mask is compared with each pixel in the level mask at the corresponding position of the player in the actual level. If any two pixels are both white, a collision has occurred.

This technique has the advantages that the player can move free-form, the platforms or scenery can be any shape, and collision testing is accurate to a single pixel, but has the downside of being potentially expensive in terms of memory consumption, as large bitmaps may need to be stored. This technique or variations of it is still used today in some applications.

The Bounding Box Method

A bounding box refers to the smallest possible rectangle that can entirely contain a piece of geometry. In the bounding box method of collision detection, the bounding box of the player is compared with the bounding box of each platform and enemy (or more usually, just the ones in the vicinity of the player). If the bounding boxes intersect, a collision has occurred. This works great for flat (horizontal or vertical) platforms and when the player and most enemies are mostly rectangular. It fails horribly with sloped surfaces, abstract shapes and shapes such as circles. However the bounding box method is used as a basis and optimization for other more modern methods, since checking the bounding boxes of scenery against the bounding box of the player is a quick way to narrow down which pieces of geometry need further testing for a more accurate collision check. We use this technique in the example in this article.

Discrete Collision Detection

This technique is one used by many modern video games and can deal with many simultaneous moving objects colliding with one another in a single frame, rather than just one object colliding with a static set of geometry (scenery).

For each moving object, the total bounding box of both its current position and expected position after the current frame is calculated. This is called an axis-aligned bounding box or AABB for short. Any AABBs which overlap are considered to be at risk of their objects colliding in the frame, as their paths may (or may not) cross each other. Each set of intersecting (overlapping) AABBs is grouped together into a so-called Time of Impact island or TOI island for short.

Potential collisions in each TOI island are then handled one at a time using a so-called contact solver (collision solver) which uses various mathematics to determine the time of impact ordering of each object in the island and its new trajectory (the exact mathematics are complex and beyond the scope of this article). Because solving all the collisions and changing the trajectory of objects can cause new collisions, the whole process of AABB calculation, TOI island calculation and contact solving is then iterated (repeated) for a programmer-defined arbitrary number of times. The purpose of this is to increase the visible stability of objects, since over-corrections and constant toggling of an object against a surface between colliding and non-colliding can give rise to the so-called jitter problem.

TOI ordering is generally only needed for simulations rather than 2D platform games; in video games, AABBs are calculated to check if a player or other object is about to hit some scenery, and the amount of movement beyond which would cause the player or other object to end up inside a wall or stuck in the ground is culled (removed, or subtracted from the total movement). This is called penetration resolution and we use the technique in the example in this article.

Speculative Contacts

Figure 2. LittleBigPlanet uses speculative contacts with arbitrary geometry on three discrete 2D planes (foreground, middle, background) (source: ign.com)

The latest and greatest in collision detection, used in the latest video games and intended to solve the so-called bullet-through-paper problem present in discrete collision detection whereby a fast-moving object can pass completely through a piece of geometry (for example, a thin horizontal platform when the player is falling from a great height at high speed). This happens because in discrete collision detection, only the initial and final position of the object during each frame is considered, not all of the theoretical in-between positions that the object would occupy during this movement. For example, if you are a single-pixel dot falling at 50 pixels per frame and there is a 5-pixel tall platform 30 pixels below you, then no collision is detected as both your current position, and your position 50 pixels further down, are in mid-air and do not touch the platform at all. To solve this problem, the positions in between the initial and final positions of per frame movement must be examined. Speculative contacts aims to do this, and we will use a simplified version of the technique in the example in this article.

Our Approach

While trying to keep the math as simple as possible, the approach I shall demonstrate below uses a 2D bitmap as the player sprite, and employs a simplified version of speculative contacts against Direct2D Geometry objects to mitigate the bullet-through-paper problem, followed by a simple form of penetration resolution to correct the player’s position when hitting walls, the ground or walking up slopes, all done over multiple iterations per frame to reduce the jitter problem. The player’s AABB is used against pre-computed bounding boxes of each piece of geometry as an optimization to check only those objects near the player.

Before going any further, I recommend you download and try the finished product from the link at the top of the article so that you have a better understanding of what we are aiming towards as we go along.

Creating the Application

As usual we’re going to use Simple2D so the application will follow the Simple2D framework, but it is only used for rendering and all of the collision detection code can be easily supplanted into a program using a different engine. If you want to see the results but don’t want the hassle of installing and compiling everything and aren’t planning to use Simple2D, don’t worry! Ready-made executables are included for download at the end with the source code.

Let’s kick things off with the basic skeleton code:

#include "Simple2D.h"
#include

using namespace S2D;

class MyProgram : public Simple2D
{
	// API entry points
	bool SetupResources();
	void ReleaseResources();
	void DrawScene();
	void UpdateObjects();

	// The bitmap brush to use to draw the platforms
	ImageBrush tile;

	// The sprite to use for the player
	Image player;

public:
	MyProgram()
	{
		// Load graphics
		tile = MakeBrush(MakeImage(L"tile.png"), Custom, D2D1_EXTEND_MODE_WRAP);
		player = MakeImage(L"stickman.png");
    }
};

// Geometry matrix transformations are render-target dependent as they rely on the window/screen size
// so the layout of the platforms in the game must be defined here
bool MyProgram::SetupResources()
{
    return true;
}

// Free up game world resources
void MyProgram::ReleaseResources()
{
}

// Per-frame game world update / physics
void MyProgram::UpdateObjects()
{
}

// Render the game world
void MyProgram::DrawScene()
{
}

// Application entry point
void Simple2DStart()
{
	MyProgram test;
	test.SetWindowName(L"2D Geometry Collision Demo");
	test.SetBackgroundColour(Colour::Black);
	test.SetResizableWindow(true);
	test.Run();
}

That’s the boilerplate code out of the way. Before we can look at the collision detection, we need to:

• Create some platforms (world geometry)
• Accept user input to move the player around
• Render the game world (geometry and player sprite)

Creating the world geometry

We’ll need an array of objects, one for each piece of geometry, and we’ll need to fill it with data. Add the following code to the class definition:

// The number of objects in the game world
int worldObjectCount;

// The geometry of all the landscape objects (platforms and walls)
Geometry *worldObjects;

All of the following code goes in SetupResources(). First we will make a struct to allow us to define how each platform should be scaled, skewed and rotated, plus its width, height and position in the game world. This is just for convenience, you can define the geometry however you like:

typedef enum { Rectangle, Ellipse } ShapeType;

// This structure allows us to quickly define the layout of each landscape object
typedef struct {
	int width;
	int height;
	ShapeType shape;
	float scaleX;
	float scaleY;
	GeometryTransformPoint scalePoint;
	float skewAngleX;
	float skewAngleY;
	GeometryTransformPoint skewPoint;
	float rotAngle;
	GeometryTransformPoint rotPoint;
	int topLeftX;
	int topLeftY;
} ObjectDefinition;

Now we’ll populate an array with the actual list of platforms for our game world using this struct:

worldObjectCount = 12;

// Create the landscape definition
ObjectDefinition objdef[] =
{
	// Gently sloping straight surface
	{ 80*6,  80*1, Rectangle, .5f,  .5f,  PointBottomLeft, 0.f, -10.f, PointBottomLeft, 0.f,  PointBottomLeft, 80,  ResolutionY - 200 },

	// Block to help climb up steep sloping wall
	{ 80*1,  80*1, Rectangle, .5f,  .5f,  PointTopLeft,    0.f, 0.f,   PointBottomLeft, 0.f,  PointBottomLeft, 250, ResolutionY - 60  },

	// Steep sloping wall
	{ 80*8,  80*1, Rectangle, .6f,  .6f,  PointBottomLeft, 0.f, 0.f,   PointBottomLeft, 75.f, PointTopLeft,    240, ResolutionY - 250 },

	// Edge walls
	{ 80*32, 80*1, Rectangle, .25f, .25f, PointTopLeft,    0.f, 0.f,   PointBottomLeft, 0.f,  PointBottomLeft, 0,   ResolutionY - 20  },
	{ 80*24, 80*1, Rectangle, .25f, .25f, PointTopLeft,    0.f, 0.f,   PointBottomLeft, 90.f, PointTopLeft,    20,  0                 },
	{ 80*24, 80*1, Rectangle, .25f, .25f, PointTopLeft,    0.f, 0.f,   PointBottomLeft, 90.f, PointTopLeft,    ResolutionX, 0         },

	// Gently sloping curved surface
	{ 150,   40,   Ellipse,   1.f,   1.f, PointTopLeft,    0.f, 0.f,   PointBottomLeft, 0.f,  PointTopLeft,    460, 380               },

	// Square blocks ('stairs')
	{ 80*1,  80*1, Rectangle, .75f, .75f, PointTopLeft,    0.f, 0.f,   PointBottomLeft, 0.f,  PointTopLeft,    20,  ResolutionY - 80  },
	{ 80*1,  80*1, Rectangle, .4f,  .4f,  PointTopLeft,    0.f, 0.f,   PointBottomLeft, 0.f,  PointTopLeft,    20,  ResolutionY - 110 },

	// Two sloping platforms on left-hand side to give access to a long fall through a thin platform
	{ 80*5,  80*1, Rectangle, .25f, .25f, PointTopLeft,    0.f, 10.f,  PointBottomLeft, 0.f,  PointTopLeft,    20,  200               },
	{ 80*20, 80*1, Rectangle, .25f, .25f, PointTopLeft,    0.f, -15.f, PointBottomLeft, 0.f,  PointTopLeft,    100, 150               },

	// Very thin platform (to test fall-through)
	{ 80*20,  80*1, Rectangle, .1f, .05f,  PointTopLeft,    0.f, 0.f,   PointBottomLeft, 0.f,  PointTopLeft,    420, 250               }
};

This kind of data should ideally go into an external file so that you and other team members can design levels without having to re-compile the application.

We now need to convert this into actual Direct2D geometry data as follows:

// Generate the game world landscape geometry
worldObjects = new Geometry[worldObjectCount];

for (int o = 0; o < worldObjectCount; o++)
{
	ObjectDefinition &obj = objdef[o];

	if (obj.shape == Rectangle)
		worldObjects[o] = MakeRectangleGeometry(obj.width, obj.height);

	if (obj.shape == Ellipse)
		worldObjects[o] = MakeEllipseGeometry(obj.width, obj.height);

	worldObjects[o].SetTransform(
		worldObjects[o].Scale(obj.scaleX, obj.scaleY, obj.scalePoint)
		* worldObjects[o].Skew(obj.skewAngleX, obj.skewAngleY, obj.skewPoint)
		* worldObjects[o].Rotate(obj.rotAngle, obj.rotPoint)
		* worldObjects[o].Move(obj.topLeftX, obj.topLeftY));

	worldObjects[o].SetAutoAdjustBrushTransform(true);
}

Finally, add clean-up to ReleaseResources():

delete [] worldObjects;

When rendered, this will produce the landscape shown in Figure 3 (I have added the array indices (plus 1) so you can see which platform is which).

Figure 3. The platforms in our sample project

Player tracking

We now need to handle the position and movement of the player. Add the following to the class definition:

// The player's current position (top-left co-ordinate of sprite)
float playerX, playerY;

// The amount of X acceleration to apply when the player moves left or right
// The amount of X deceleration to apply when the player does not move left or right
float accX, decX;

// The amount of X and Y movement to occur on the next frame
float speedX, speedY;

// The maximum movement speed allowed for the player
float maxSpeedX, maxSpeedY;

// The amount of upward force to apply when the player first presses jump
float jumpStartSpeedY;

// The amount of Y acceleration to apply on each frame due to the force of gravity
float accY;

// True if currently jumping (prevents the player jumping while in mid-air)
bool jumping;

// True if the jump key is currently held down (key must be released to allow a new jump)
bool jumpKeyDown;

Then set default values in the class constructor:

// Set default player position
playerX = 200.f;
playerY = 150.f;

// Set acceleration and speed
float mScale = 60.f;

accX = 0.2f * mScale;
decX = 0.3f * mScale;
maxSpeedX = 5.0f * mScale;
maxSpeedY = 10.0f * mScale;

speedX = 0.f;
speedY = 0.f;

// Set jump and gravity forces
jumpStartSpeedY = 8.f * mScale;
accY = 0.5f * mScale;

jumping = false;
jumpKeyDown = false;

A few things to note here. First of all movement will be calculated relative to the time elapsed between the previous and current frame, so that the movement of the player in the game world remains correct even if the frame rate lags. Here I have defined the speeds and accelerations as I would like them per pixel per frame, and then multiplied them by the optimal frame rate of 60fps (optimal is a relative term here). Note the use of fractional (float) values for smoother and more precise motion.

Note that the player will decelerate 50% faster than he or she will accelerate when moving left or right (0.3 vs 0.2); this creates the familiar effect of building up speed relatively slowly then screeching to a halt relatively fast when no movement input is detected. maxSpeedX will prevent the player from accelerating forever by clamping the sprite’s maximum horizontal speed.

jumpStartSpeedY will be subtracted from the player’s vertical (downward) speed when a jump begins, while accY will be added each frame to give a constant force of gravity. This is important otherwise jumping would cause the player to launch into space never to return otherwise, and also ensures that the player moves downwards appropriately when walking down a sloped surface. The effect of adding the gravity constant each frame during a jump gives rise to a smooth sinusoidal-like jumping motion (moving upwards gradually slower and slower, plateauing and then falling with increasing speed until a surface is hit).

The jump-tracking flags are needed to prevent the player both from holding down the jump button to jump repeatedly (which can cause unwanted effects when they land on a platform different to the one they jumped from), and to prevent the player from jumping when they are already jumping. The collision detection code will determine when a jump has ended and reset the flag.

Now we add the physics and keyboard input code to make all of this work in UpdateObjects():

// The current time
int updateTick = GetTickCount();

// Update the player's position
playerX += LinearMovement(speedX, updateTick);
playerY += LinearMovement(speedY, updateTick);

// Process player keyboard input
bool moveRequest = false;

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

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

	// Jump if not already jumping and the jump key was released earlier
	if (GetAsyncKeyState(' ') && !jumping && !jumpKeyDown)
	{
		jumping = true;
		jumpKeyDown = true;
		speedY = -jumpStartSpeedY;
	}

	// Jump key released
	if (!GetAsyncKeyState(' '))
		jumpKeyDown = false;
}

// Limit the sideways acceleration of the player
if (speedX > maxSpeedX) speedX = maxSpeedX;
if (speedX < -maxSpeedX) speedX = -maxSpeedX; // Limit the force of gravity (terminal velocity) if (speedY > maxSpeedY) speedY = maxSpeedY;
if (speedY < -maxSpeedY) speedY = -maxSpeedY;

// Apply the force of gravity
speedY += accY;

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

	// 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 < decX) speedX = 0;
	if (speedX < 0 && speedX > -decX) speedX = 0;
}

Review the source code comments for further explanation. For those not familiar with Simple2D, LinearMovement is a function that takes the desired amount of pixel movement per second and returns the number of pixels to move this frame, based on the time between the previous and current frames. The definition is rather simple:

float Simple2D::LinearMovement(float pixelsPerSecond, DWORD tickCount)
{
	if (!tickCount)
		tickCount = GetTickCount();

	float secs_elapsed = static_cast(tickCount - LastUpdateTime) / 1000.0f;
	return secs_elapsed * pixelsPerSecond;
}

LastUpdateTime is set to GetTickCount() every time the application receives the WM_PAINT message in the Windows message pump, indicating the start of rendering of the next frame.

Note that the ordering of the code is very important. The player’s position is updated before keyboard input is checked, and if the user is pressing a key (and when gravity is applied) the movement is added to speedX and speedY – not the player’s position directly. These variables are the movement vector to be applied to the player on the next frame, and they are only a request. Later, we will place collision detection code at the start, ie. before the player’s position is updated, to check and modify the movement vector (speedX and speedY) to resolve any collisions. In this way, the player and the force of gravity request movement on a given frame, then any collisions are resolved before the movement is applied on the next frame.

Rendering the game world

Nearly there! Rendering code goes in DrawScene() and is actually remarkably simple:

// Draw the landscape objects
SetBrush(tile);

for (int o = 0; o < worldObjectCount; o++)  	worldObjects[o].Fill(); // Draw the player player->Draw(static_cast(playerX), static_cast(playerY));

If you now run the application, you will see the world geometry and if you are quick, observe the player sprite fall ungracefully through the bottom of the game world since there is no collision detection to stop him from hitting anything. If you want to see how the player controls, add this fudge code in UpdateObjects() after PlayerY is updated (if you add it before, you will get all sorts of bizarre effects):

if (playerY > 420)
{
    playerY = 420;
    jumping = false;
}

Figure 4. Our 20×40 player sprite with 8 collision points shown in white

IMPORTANT! Make sure you remove this code before continuing on with the example.

Source code and compiled EXE file for this section

Collision Detection

Now it’s down to business. We’ll start by defining 8 points in an octagonal shape on the edges of the player sprite. Specific pairs of these points will be selected to test for collisions depending on the player’s direction of movement – see figure 4. The reason we use 8 points is because it has advantages over the other obvious method of using the 4 corners (bounding) box of the sprite, namely that the collision detection will be less visually coarse. When using the corners, a player can stand completely off the edge of a platform with only a bottom corner touching it, and still not fall, for example. Conversely, collisions with ceilings and walls may be detected where none exist. Therefore it is better to use actual points on the character itself for improved accuracy.

Add the following code to the class definition:

// Collision points to test on the player sprite
D2D1_POINT_2F collisionPoint[8];

and define the points for our 20×40 player sprite in the class constructor:

// Set collision points to test on the player sprite
D2D1_POINT_2F points[8] = {
	{ 5,  0  }, { 15, 0  },	// Top of head
	{ 5,  40 }, { 15, 40 },	// Feet
	{ 0,  10 }, { 0,  30 },	// Left arm
	{ 20, 10 }, { 20, 30 }	// Right arm
};

for (int i = 0; i < 8; i++)
	collisionPoint[i] = points[i];

Penetration Resolution

Penetration resolution refers to adjusting the player’s position slightly to correct any collisions. Collisions will always be happening when the player is on the ground due to the force of gravity trying to pull the player into the platform, as well as when walking into walls, hitting the ceiling while jumping etc, so we need to nudge the player away from the collision object until they are no longer touching it.

We are first going to look at a crude and inefficient implementation. Direct2D has a massive constraint in that it is not possible to easily calculate the normal vector or distance between two geometries. Our first approach will simply wind the player’s position backwards from the current to the previous position one pixel at a time and re-test until there is no longer a collision in lieu of the ability to measure the exact distance. Later we will look at a novel optimization which makes the code much faster. Suffice to say, do not use the following method in production games. Let’s begin.

Penetration resolution is an iterative process, meaning that it should be performed multiple times per frame. This is because resolving one collision can cause another, so all the nearby objects must be re-calculated and re-checked until there are no collisions. We store the maximum number of iterations in the class definition:

// The maximum number of iterations for the contact solver to run per frame
static const int iterations = 3;

The more iterations allowed, the more stable the result will be, with less jittering of colliding objects as they are constantly corrected and re-corrected.

All of the following code will be placed after updateTick is set in UpdateObjects() and before playerX and playerY are updated. Let’s look at it step by step.

// Flags to specify what kind of collision has occurred
bool contactX = true, contactYbottom = true, contactYtop = true;

We will need to know the direction the collision came from so that we can adjust the player’s speed in that direction to zero, and also to turn off the jumping flag if needed.

// Keep iterating the contact solver until the maximum number of iterations is reached
// or no collisions are detected
for (int iteration = 0; iteration < iterations && (contactX || contactYbottom || contactYtop); iteration++)
{

Everything in the penetration solver goes into this for loop. Note that it only continues iterating while there is a collision; as soon as no more collisions are detected, the loop exits to avoid doing wasted calculations.

// Calculate the amount of X and Y movement expected by the player this frame
float nextMoveX = LinearMovement(speedX, updateTick);
float nextMoveY = LinearMovement(speedY, updateTick);

// No collisions found yet
contactX = contactYbottom = contactYtop = false;

We reset the collision flags and calculate the desired X and Y movement of the player this frame based on the player’s movement vector (speedX and speedY), and place it into nextMoveX and nextMoveY.

float projectedMoveX, projectedMoveY, originalMoveX, originalMoveY;

// Store the original final expected movement of the player so we can
// see if it has been modified due to a collision or potential collision later
originalMoveX = nextMoveX;
originalMoveY = nextMoveY;

The desired move vector is copied so that we can determine what type of collision – if any – occurred.

// Iterate over each object whose bounding box intersects with the player's bounding box
// until a collision is found
for (int o = 0; o < worldObjectCount && !contactX && !contactYbottom && !contactYtop; o++)
{

We now begin going through every object in the game world to test each one for a collision with the player. Later we will optimize this to examine only objects near the player.

// We will test the four possible directions of player movement individually
// dir: 0 = top, 1 = bottom, 2 = left, 3 = right
for (int dir = 0; dir < 4; dir++) {     // Skip the test if the expected direction of movement makes the test irrelevant     // For example, we only want to test the top of the player's head when movement is     // upwards, not downwards. This is really important! If we don't do this, we can     // make corrections in the wrong direction, causing the player to magically jump     // up to platforms or stick to ceilings.     if (dir == 0 && nextMoveY > 0) continue;
    if (dir == 1 && nextMoveY < 0) continue;
    if (dir == 2 && nextMoveX > 0) continue;
    if (dir == 3 && nextMoveX < 0) continue;
    projectedMoveX = (dir >= 2? nextMoveX : 0);
    projectedMoveY = (dir <  2? nextMoveY : 0);

As the comments show, we will look at the four possible directions of movement separately. projectedMoveX and projectedMoveY are set to the desired movement and will be adjusted below to resolve any collision.

while ((worldObjects[o].ContainsPoint(static_cast(collisionPoint[dir*2].x + playerX + projectedMoveX),
										static_cast(collisionPoint[dir*2].y + playerY + projectedMoveY))
	|| worldObjects[o].ContainsPoint(static_cast(collisionPoint[dir*2+1].x + playerX + projectedMoveX),
										static_cast(collisionPoint[dir*2+1].y + playerY + projectedMoveY))))
{
	if (dir == 0) projectedMoveY++;
	if (dir == 1) projectedMoveY--;
	if (dir == 2) projectedMoveX++;
	if (dir == 3) projectedMoveX--;
}

if (dir >= 2 && dir <= 3) nextMoveX = projectedMoveX;
if (dir >= 0 && dir <= 1) nextMoveY = projectedMoveY;

// Close the for loop (repeat for all four directions)
}

Using the collision points on the player sprite we made earlier, we now check if the geometry intersects with (contains) any of these points, one pair at a time (the top pair, bottom, left and right). In case of a collision, the projected movement vector is adjusted by one pixel until it no longer collides with the geometry. The movement vector is set to the adjusted projection when all the work is done.

At this point, what we have in nextMoveX and nextMoveY is a movement vector which does not cause any collisions with the object currently being tested. It may not have changed at all if there was no collision with the object, so we now compare against the original desired movement vector to determine what type of collision – if any – was resolved:

// 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;
}

if (abs(nextMoveX - originalMoveX) > 0.01f)
{
	contactX = true;
}

Note the comparison for X collisions; due to floating point errors which can occur in the subtraction to find the difference, we check for an amount greater than 0.01 rather than 0 to ensure we don’t generate a false positive.

Effect of penetration resolution on jumping

We now need to add something to the jump mechanic:

// The player can't continue jumping if we hit the side of something, must fall instead
// Without this, a player hitting a wall during a jump will continue trying to travel
// upwards
if (contactX && speedY < 0)
	speedY = nextMoveY = 0;

Note that this behaviour is optional. With the condition above, the player won’t be able to jump while standing still directly next to a wall, in the direction of the wall. Without it, jumping upwards and hitting a sloping overhang can cause the player to spring backwards while still moving upwards.

There is a third alternative which I like best (I have used it in the final version of the demo):

if (contactX && contactYtop && speedY < 0)
    speedY = nextMoveY = 0;

This version allows the player to jump in the direction of a wall when standing next to it, but prevents continued upward movement if an overhang is hit.

Finishing off

Now close the for loop which processes all of the objects:

}

Now we are back in the outer iteration loop. If a collision has been detected, we update the player’s position immediately and set the movement for the rest of the frame to zero (no movement), then re-iterate to test for new collisions. Otherwise, we do nothing. Additionally, if the player has fallen and hit a ground surface, we reset the jumping flag so the player can jump again.

// If a contact has been detected, apply the re-calculated movement vector
// and disable any further movement this frame (in either X or Y as appropriate)
if (contactYbottom || contactYtop)
{
	playerY += nextMoveY;
	speedY = 0;

	if (contactYbottom)
		jumping = false;
}

if (contactX)
{
	playerX += nextMoveX;
	speedX = 0;
}

Finally, close the iteration loop:

}

Excellent! The first version of our penetration resolution code is finished and you can now try it out. Go ahead, try it out!

Source code and compiled EXE file for this section

Pretty cool huh?

Bounding Box Optimization

Checking every single object in the game world for a collision with the player is both pointless and computationally expensive. Is there a simple way to find out which objects are in the vicinity of the player so we can just check those instead?

Indeed there is, the so-called bounding box optimization. We will pre-calculate (before the game starts) the bounding boxes of every static object (ie. the platforms) in the game world, and then on each frame, compare these with the total bounding box of the player’s current position and desired position after movement this frame. Any which intersect (overlap) are considered to be nearby and will be passed for penetration resolution.

You still have to examine the bounding box of every object, but this is a couple of quick subtractions and is a far cheaper operation than testing for intersections with every piece of arbitrarily-shaped geometry. If you want to get fancy, you can put the objects in a series of buckets or an n-tree to prune the ones you need to test, but I leave this as an exercise for the reader.

First up, we’re going to need storage for the bounding boxes, and we’ll also be needing the width and height of the player sprite for this. In the class definition:

// Pre-calculated bounding boxes for all the landscape objects
D2D1_RECT_F *worldObjectBoundingBoxes;

// The width and height of the player sprite
int playerW, playerH;

// A list of objects this frame for which the player is currently within the bounding boxes of
// (these are the only objects that will be tested for collision)
std::set boundObjects;

(you don’t actually need to store boundObjects in the class definition but I used it to render the currently used bounding boxes for debugging, so it needs to be accessible from the drawing function in that case)

Set the player width and height in the class constructor:

playerW = 20;
playerH = 40;

This should of course match the dimensions of the sprite you are using.

In SetupResources, after all the geometry has been created, and right before the return statement, pre-calculate the bounding boxes for everything:

// Calculate bounding boxes for each landscape object
worldObjectBoundingBoxes = new D2D1_RECT_F[worldObjectCount];

for (int o = 0; o < worldObjectCount; o++)
	worldObjectBoundingBoxes[o] = worldObjects[o].GetBounds();

GetBounds() is a Simple2D function which at its core gets the bounds of a Direct2D ID2D1Geometry object (equivalent as follows but simplified):

D2D1_MATRIX_3X2_F worldTransform;
pRenderTarget->GetTransform(&worldTransform);

D2D1_RECT_F bounds;
pGeometry->GetBounds(worldTransform, &bounds);

return bounds;

I include this just for illustration in case you aren’t using Simple2D.

Re-write ReleaseResources() to make sure it releases everything:

// Free up game world resources
void MyProgram::ReleaseResources()
{
	delete [] worldObjects;
	delete [] worldObjectBoundingBoxes;
}

We will now modify the collision detection code to do the bounding box testing. All of this code should go right inside the main iteration loop, near the start but directly after the two lines which set nextMoveX and nextMoveY:

// Clear list of bounding boxes the player is within
boundObjects.clear();

// Calculate the total bounding box of the player's current position
// and his/her expected movement this frame

// IMPORTANT! We must include the expected movement within the bounding box
// so that we can correctly select which landscape objects to consider for
// a potential collision
D2D1_RECT_F playerBounds = {
	min(playerX, playerX + nextMoveX),
	min(playerY, playerY + nextMoveY),
	max(playerX + playerW, playerX + playerW + nextMoveX),
	max(playerY + playerH, playerY + playerH + nextMoveY)
};

First we calculate the total bounding box of the player’s current and desired positions (the player AABB) and store it in playerBounds.

// Check each object to see whether it intersects with the player's bounding box
for (int o = 0; o < worldObjectCount; o++)
{
	// We don't need to check all four corners on each object and player by hand
	// Using a neat quirk of mathematics, we can take the combined bounding box
	// of the player and the object. If it's width or height exceeds the total
	// width or height of the object + the player, then the bounding boxes do
	// not intersect, otherwise they do.
	D2D1_RECT_F bounds = {
		min(playerBounds.left,   worldObjectBoundingBoxes[o].left),
		min(playerBounds.top,    worldObjectBoundingBoxes[o].top),
		max(playerBounds.right,  worldObjectBoundingBoxes[o].right),
		max(playerBounds.bottom, worldObjectBoundingBoxes[o].bottom)
	};

	// If a bounding box intersects with the player's bounding box, add the
	// geometry to the list of geometries to check for collisions
	if (   bounds.right - bounds.left < worldObjectBoundingBoxes[o].right - worldObjectBoundingBoxes[o].left + playerBounds.right - playerBounds.left
		&& bounds.bottom - bounds.top < worldObjectBoundingBoxes[o].bottom - worldObjectBoundingBoxes[o].top + playerBounds.bottom - playerBounds.top)
	{
		boundObjects.insert(o);
	}
}

We now iterate over all the objects in the game world, and – using some mathematical jiggery-pokery to take into account all four possible directions of movement – compare the player AABB with each object’s bounding box and add it to the list in boundObjects if they intersect.

It now just remains to modify the for loop which iterates over all objects checking for collisions to only iterate over those listed in boundObjects. Change this line:

for (int o = 0; o < worldObjectCount && !contactX && !contactYbottom && !contactYtop; o++)

to:

for (auto it = boundObjects.begin(); it != boundObjects.end() && !contactX && !contactYbottom && !contactYtop; it++)

and change the while loop to refer to the selected object (by replacing o with *it):

while (!worldObjects[*it].ContainsPoint(static_cast(collisionPoint[dir*2].x + playerX + projectedMoveX),
    static_cast(collisionPoint[dir*2].y + playerY + projectedMoveY))
    && !worldObjects[*it].ContainsPoint(static_cast(collisionPoint[dir*2+1].x + playerX + projectedMoveX),
    static_cast(collisionPoint[dir*2+1].y + playerY + projectedMoveY))

All done! The code is functionally the same before but much more efficient for game worlds with many objects.

Source code and compiled EXE file for this section

Speculative Contacts

First an apology to Paul Firth for blatantly stealing the following diagrams from his web site, I can’t draw to save my life. His excellent article on speculative contacts is linked in the references section at the end.

At this point, all may seem well and working as expected. There are, however, some problems. For example, go down to the floor on the right and move left against the block in the bottom middle. You may see that the character repeatedly shifts between two adjacent positions. This happens because a collision repeatedly occurs and is corrected – we need to stop this collision from happening.

Figure 5. Bullet through paper problem (source: Paul Firth, see references)

There is also the opposite problem. I invite you to jump off the platform at the top onto the thin platform below on the right. You may sometimes fall right through it. This is the so-called bullet-through-paper problem and happens because penetration resolution only considers where an object starts and finishes in a frame, and not any of the theoretical positions it would have occupied in between to move between the two points.

This is where speculative contacts comes in. In essence, speculative contacts does the opposite of penetration resolution: it tries to prevent collisions before they occur. This works by calculating the distance between the player and a piece of geometry, and if the player’s movement would cause the object to be passed through, the movement vector is adjusted so that the player just reaches the edge of the geometry instead.

The version of speculative contacts I present here is not a full-blown implementation as it does not consider time-of-impact ordering of multiple moving objects, only player-vs-static-geometry collisions. However, in a 2D platform game, TOI ordering is not usually necessary and we can cut out the complexity.

Figure 6. Speculative contacts resolves the bullet-through-paper problem by shortening the player’s movement vector such that it just touches the edge of the geometry that would otherwise be passed through.

Once again, we are severely constrained by Direct2D not allowing us to calculate the position between two geometries, so we do the opposite of our work in penetration resolution: we start at the player’s current position and advance one unit at a time until we find a collision. Once again this is very inefficient and I show a partial optimization to this further below. Note I say ‘unit’ and not ‘pixel’, because we are going to have to resort to a bit of vector maths here. Unfortunately, and as Figure 6 shows, we cannot only work in the X or Y direction in isolation as we need to traverse along the path of movement. The crude initial approach I have used is to calculate the length of the movement vector (nextMoveX and nextMoveY), in pixels, and then work along it from start to end, one pixel at a time, until a collision is found or the end is reached (in which case there is no collision). Some of this expensive work can be cut out even under the limitations of Direct2D, as I will show later.

The following code goes before the penetration resolution code, inside the iteration loop, after the bounding boxes are calculated. It immediately follows the lines which set originalMoveX and originalMoveY:

float vectorLength;
int segments;

First we’ll need variables to store the length of the movement vector and how far we are along it.

// Iterate over each object whose bounding box intersects with the player's bounding box
// until a collision is found
for (auto it = boundObjects.begin(); it != boundObjects.end() && !contactX && !contactYbottom && !contactYtop; it++)
{

We re-employ the bounding box optimization here to consider only nearby objects. Remember, after penetration resolution, the whole process repeats including speculative contacts, and new bounding boxes will be calculated on each iteration.

// We will test the four possible directions of player movement individually
// dir: 0 = top, 1 = bottom, 2 = left, 3 = right
for (int dir = 0; dir < 4; dir++) {
     // Skip the test if the expected direction of movement makes the test irrelevant
     // For example, we only want to test the top of the player's head when movement is     // upwards, not downwards. This is really important! If we don't do this, we can
     // get stuck in a ceiling when falling for example.
     if (dir == 0 && nextMoveY > 0) continue;
    if (dir == 1 && nextMoveY < 0) continue;
     if (dir == 2 && nextMoveX > 0) continue;
    if (dir == 3 && nextMoveX < 0) continue;

    // Our current position along the anticipated movement vector of the player this frame
    projectedMoveX = projectedMoveY = 0;

So far this is all rather similar to penetration resolution. Even though we have to work along the movement vector in the right direction (rather than X and Y individually), we still test the collision points of the player sprite in pairs according to the direction of movement. If we don’t do this, and test all 8 points regardless of movement direction, we can become stuck in the game world.

// Calculate the length of the movement vector using Pythagoras
vectorLength = sqrt(nextMoveX * nextMoveX + nextMoveY * nextMoveY);
segments = 0;

Alright, relax gentlemen (and ladies too I hope)! This is the only vaguely trigonometry-related piece of maths in the article! As an aside, Pythagoras’ theorem states that the length of the longest side of a right-angled triangle is equal to the square root of the length of the other two sides squared, added together. You don’t need to understand this so don’t worry too much; the point is that by performing this calculation on the expected X and Y movement, we get the length of the movement vector (in pixels, since the X and Y movement distances are also specified in pixels), and that’s what we need.

// Advance along the vector until it intersects with some geometry
// or we reach the end
while (!worldObjects[*it].ContainsPoint(static_cast(collisionPoint[dir*2].x + playerX + projectedMoveX),
										static_cast(collisionPoint[dir*2].y + playerY + projectedMoveY))
	&& !worldObjects[*it].ContainsPoint(static_cast(collisionPoint[dir*2+1].x + playerX + projectedMoveX),
										static_cast(collisionPoint[dir*2+1].y + playerY + projectedMoveY))
	&& segments < vectorLength)
{
	projectedMoveX += nextMoveX / vectorLength;
	projectedMoveY += nextMoveY / vectorLength;
	segments++;
}

This while loop’s condition states that we should continue until either a collision is found, or we have reached the end of the movement vector (in which case there is no collision). Inside the loop, we advance our position along the movement vector by one unit (note the division: it stands to reason that if the X movement is 6 and the Y movement is 8, giving a vector length of 10, that if you half the amount of movement so that X becomes 3 and Y becomes 4, the vector length will also be halved to 5; therefore we can use division to neatly split our position along the movement vector into its X and Y components at even intervals).

Now we deal with the case of an intersection being found (collision occurring):

// If an intersection occurred...
if (segments < vectorLength) {
  	// Apply correction for over-movement
  	if (segments > 0)
	{
		projectedMoveX -= nextMoveX / vectorLength;
		projectedMoveY -= nextMoveY / vectorLength;
	}

	// Adjust the X or Y component of the vector depending on
	// which direction we are currently testing
	if (dir >= 2 && dir <= 3) nextMoveX = projectedMoveX;
  	if (dir >= 0 && dir <= 1) nextMoveY = projectedMoveY;
}

What’s happening here? Well, if a collision was found, we backtrack by one unit so that the player’s movement will land him or her at the edge of the geometry rather than slightly inside it. If there was already a collision at the starting position (meaning that segments would be 0 since no advancement was made), we do nothing as there is no backtracking to do.

Finaly, we update the player’s movement vector for the frame depending on which direction we were testing. This is a notable difference from other implementations described on the net: generally you shorten the vector length, which means shortening both the X and Y components. However, here we actually distort the direction of movement; taking the example in Figures 5 and 6, when the ball hits the platform downwards, its X movement is retained so it will still end up moving as far to the right as originally intended rather than stopping dead as in figure 6 – it will just be on the platform instead of passing through it. The reason I have written it like this is because with the constant force of gravity being applied, any left or right movement by the player is actually a left-down or right-down movement. If we shortened the movement vector to zero when standing on a platform due to gravity, we would also shorten the X movement vector to zero, meaning the player would be permanently stuck in one place and unable to move left or right.

Round off by closing out the direction checking loop:

}

If you try the code below you will see that it is no longer possible to fall through the thin platform at high speed – speculative contacts saves you from certain death.

And that’s it, you now have a fully-functioning 2D platform collision system! Unfortunately, even with the bounding box optimization, it’s dog slow.

Source code and compiled EXE file for this section

Optimizing Penetration Detection under the constraints of Direct2D

As mentioned, the real problem with collision detection against arbitrary geometry in Direct2D is that we are not provided a way to compute the shortest distance between two geometries. But is there anything we can do? Indeed there is, using some lateral thinking.

In penetration resolution where we know we are starting with an object colliding with the player, what we actually need to avoid backtracking one pixel at a time is a measurement of how many pixels the player and object have collided by in both X and Y so we can just do a direct subtraction and avoid re-testing per pixel. Rather cunningly, if we take the intersection of the player and the geometry and compute its bounding box, its width and height give us just such information!

Since the player is a sprite, we will need a geometric representation before we can do anything else. In the class definition, add:

// Geometric version of player
Geometry playerGeom;

Then create it in the class constructor:

// Make geometric representation of player
D2D1_POINT_2F pg[8] = {
	{ 5, 0 }, { 15, 0  }, { 20, 10 }, { 20, 30 }, { 15, 40 }, { 5, 40 }, { 0, 30 }, { 0, 10 }
};

playerGeom = MakeLineGeometry(pg, 8);

Note this uses the same collision points we used on the sprite to define a solid octagon shape.

Now remove the directional for loop in the penetration resolution code. We will replace it with the following code. First, some calculations:

Geometry intersection = worldObjects[*it].GetIntersectedGeometry(playerGeom,
		playerGeom.Move(static_cast(playerX + nextMoveX), static_cast(playerY + nextMoveY)));

D2D1_RECT_F intersectedBounds = intersection.GetBounds();

// Convert to int to prevent juddering of the character due to floating point rounding errors
int intX = static_cast(intersectedBounds.right - intersectedBounds.left);
int intY = static_cast(intersectedBounds.bottom - intersectedBounds.top);

We first find the intersection of the player’s intended final position and the object currently being tested and find its bounding box. The Simple2D function GetIntersectedGeometry uses the Direct2D function ID2D1Geometry::CombineWithGeometry with the D2D1_COMBINE_MODE flag set to D2D1_COMBINE_MODE_INTERSECT, which returns a new geometry that is the intersection of the two supplied geometries – see the CombineWithGeometry MSDN reference page for the gory details.

intX and intY are set to the width of the intersection bounding box, and importantly, rounded down to the nearest pixel to prevent on-screen juddering of the player.

Finally we re-write the loop which checks the four movement directions, and the entire code comes down to:

for (int dir = 0; dir < 4; dir++)
{
	if (intersection.ContainsPoint(static_cast(collisionPoint[dir*2].x + playerX + nextMoveX),
											static_cast(collisionPoint[dir*2].y + playerY + nextMoveY))
		|| intersection.ContainsPoint(static_cast(collisionPoint[dir*2+1].x + playerX + nextMoveX),
											static_cast(collisionPoint[dir*2+1].y + playerY + nextMoveY)))
	{
		switch (dir) {
		case 0: nextMoveY += intY; break;
		case 1: nextMoveY -= intY; break;
		case 2: nextMoveX += intX; break;
		case 3: nextMoveX -= intX; break;
		}
	}
}

All we do here is check each pair of collision points for intersection with the geometry so that we know which direction to apply the correction in – if it is one of the left-hand points which intersects, we know we have to move the player to the right and so on.

And there you have it, a crude initial method replaced by something really quite simple and fairly elegant considering what it does.

Optimizing Speculative Contacts under the constraints of Direct2D

De-crapifying the speculative contacts code (I made that word up all by myself) is considerably more tricky. Here we really do need the shortest distance between two geometries and we really have no good way to find it, so all we can do is optimize any otherwise unnecessary work.

Figure 7. The red box shows the player’s current position, and the green box is the total bounding box of the current and desired position this frame. Part of the game world intersects with this anticipated movement, but there is space in between (highlighted by the blue arrows) where no collision can occur.

Our current implementation starts at the beginning of the movement vector and works its way along one pixel at a time until a collision is found. We will still need to use this technique, however we can prune away some of the start of the vector and start the traversal part-way along it. To do this, we once again employ geometry intersections to do something a bit sneaky. This time, we take the intersection of the player’s AABB (total bounding box of current plus desired position) and the piece of geometry we are examining. Consider:

• If there is no intersection (a bounding box width and height of zero), there can be no collision this frame and the object can be ignored altogether
• If there is an intersection in the AABB, then since we already know there is no collision at the player’s current position, then the difference between the size (width or height) of the player’s bounding box and player’s AABB, minus the size (width or height) of the intersection, gives a portion of space where no collision can occur. We can skip over any part of the movement vector occupying this space and start at the edge of the intersection’s bounding box.

Whew! This is pretty hard to visualize so take a look at figure 7 which I drew just for you. It is quite obvious when diagrammed that it is clearly not possible for any collision to occur between the player and the geometry until the player’s bounding box reaches an edge of the bounding box of the geometry’s intersection with the player’s total movement bounding box. So we can cut out crawling one pixel at a time along the movement vector prior to reaching this bounding box as follows:

Geometry specAABB = MakeRectangleGeometry(playerBounds);
Geometry specIntersection = worldObjects[*it].GetIntersectedGeometry(specAABB);

D2D1_RECT_F specIntBounds = specIntersection.GetBounds();

if (specIntBounds.bottom - specIntBounds.top >= 1 && specIntBounds.right - specIntBounds.left >= 1)
{

First we need a geometric representation of the player’s movement AABB so we create this (green box in figure 7). Then we take the intersection with the current object being tested (blue triangle in figure 7) and calculate its bounding box (black box in figure 7).

We proceed only if the bounds of the intersection are non-zero as described above. You should place the direction testing loop inside this if statement (and nothing else).

Under the continue statements in the direction testing loop, add:

float safeMoveX = max(max(specIntBounds.left - (playerX + playerW), playerX - specIntBounds.right), 0);
float safeMoveY = max(max(specIntBounds.top - (playerY + playerH), playerY - specIntBounds.bottom), 0);
float safeVecLen = sqrt(safeMoveX * safeMoveX + safeMoveY * safeMoveY);

This calculates the X and Y distances of the ‘safe space’ (the blue arrows in figure 7) and uses Pythagoras once again to calculate from this how much of the beginning of the desired movement vector can be safely ignored.

It’s worth commenting on the slightly weird use of max() here. For each axis (X and Y), there are three possibilities. For X:

1. The right-hand edge of the intersection bounding box is to the left of the player’s left-hand bounding box edge
2. The left-hand edge of the intersection bounding box is to the right of the player’s right-hand bounding box edge
3. Neither of the above (any other possibility)

Whenever case 1 is true, the distance between the edges in case 2 will be a negative number and vice versa, so the inner max call selects the one which is positive (ie. the one which represents the safe distance between the player at the intersection bounding box). If case 3 is true, the distances between the edges in cases 1 and 2 will both be negative; in this case, we are already colliding on this axis and there is no safe movement, so the outer max call sets the safe distance to zero for case 3.

The zero definitions of projectedMoveX and projectedMoveY can now be replaced with:

// Our current position along the anticipated movement vector of the player this frame
projectedMoveX = nextMoveX * (safeVecLen / vectorLength);
projectedMoveY = nextMoveY * (safeVecLen / vectorLength);

vectorLength -= safeVecLen;

Instead of starting at the start of the vector, we move along it by safeVecLen units, then chop that amount off the remaining length to traverse.

Don’t forget to close the if statement after the direction testing loop closes with a swift:

}

The Final Result

This 2D collision detection demo includes everything above with full source code and compiled executable. In addition I have added some basic statistics and the ability to toggle the display of nearby bounding boxes on or off. I omitted these parts of the code from the article for, uhm, brevity 🙂

Things to consider

Now you’ve successfully nailed the most irksome part of writing a 2D platform game, here are a few things for you to think about while you tinker with the code above:

• What if you want ladders? (Hint: use a separate array of ladder objects, but instead of preventing collisions, turn off gravity when a collision is active – see 2D Platform Games Part 6: Creating Platforms and Geometry the Player can be Inside (Ladders, Ropes and Water) for the implementation)
  
• What about baddies? (Hint: make an array of sprites and geometries and handle them the same as the player, only you must provide their movement programmatically; if you want a mechanic whereby touching an enemy damages the player but jumping on one destroys it, check which collision points on the player are touching the enemy and proceed accordingly – see 2D Platform Games Part 12: A Framework For Interactive Game Objects and the subsequent related parts for the implementation)
• What about scrolling? (Hint: scroll the display, not the object positions, using the player’s co-ordinates as the centre point of the screen – see 2D Platform Games Part 3: Scrolling and Parallax Backgrounds for the implementation)
  
• What about moving platforms? Ah, that’s a good one. Yes 🙂 (see 2D Platform Games Part 4: Moving Platforms and Crush Detection for the implementation)
  

That just about wraps up this practical demonstration of penetration resolution and speculative contacts in action in a Direct2D-based platform game. I really hope you enjoyed it, please leave comments below!

I’m a software developer with very limited work capacity due to having the debilitating illness M.E. – please read my article Dying with M.E. as a Software Developer and donate to the crowdfund to help me with my bucket list if you found this article useful. Thank you so much!

Move onto Part 2 for some tweaks to the collision detection and player physics.

References

Don’t miss these excellent articles which were a great resource to me while learning:

Speculative Contacts – a continuous collision approach – a theoretical discussion of speculative contacts in good detail, with code snippets in ActionScript

How To Make a 2D Platform Game – Collision Detection – use of speculative contacts in a tile-based game world

Programming M. C. Kids – an article from the developers of the NES game MC Kids on how they implemented pixel tile collision detection

Platformer Game Source In Processing – an article about the use of collision points around the edge of a player character

2D Platformer Advanced Collision Detection – an article about the use of collision points in a game world composed from series’ of rectangles

Also useful:

Direct2D Geometry reference

Many thanks to my friend and colleague Jeremy Ward for the graphics.

Footnote

Part 11 contains some bug fixes to the code in this article.

Advertisement