2D collision response for XNA

Abstract

Collision response in a 2D space with the use of minimum translation distance (MTD) for collisions with multiple objects. Axis resolution priority by summed directions for correction. Sounds a bit dry, bit it's actually quite fun when you get it to work. Before you start implementing this article I would suggest that you are familiarize yourself with XNA and it's different types.

Introduction

I'm writing a platformer and the first brainteaser I went upon was the collision resolution. I've found a couple of articles, but not many that describes the collision resolution very good. I'm currently working with the XNA playform and I really do love the simplicity behind it. Collision detection should be treated separatly from the response, since the former is just a tool for the later.

Here is an image describing a collision resolution. I will do into detail later on.

summing up directions

The problem that I have found is when you have objects of different sizes intersecting each other you can't just use the minimum translation distance, since this sometimes freezes the object when sliding over blocks, etc. This can be solved by using certain velocities, but also with a different response. I worked this method to accomodate my problem. One thing that this code will not cover is if the player moving has a higher velocity that the width of the walls. To resolve that problem, another method called multisampling can be used.

In this example, the player is 70 pixels wide and 90 pixels high. The walls are composed by blocks that are 36 pixels in width and height. I'm using Microsoft.Xna.Framework.Rectangle for bounds and collision detection. A Rectangle can be used for collision detection with another Rectangle with Rectangle.Intersects(Rectangle).

Flow for resolution

This is the simple codeflow. I've refrained from detailing step 5 since it would clutter the code. I'll do the further down in the article.

  1. Get all colliding objects
  2. Check for collisions
  3. Calculate the resolution direction for all collisions
  4. Sum up the directions
  5. Correct the players position
  6. Go to step 2

Classes/types (add your own methods for drawing, etc)

I'll expose variables directly to keep the code breif. Use properties where ever you wish, but remember that you can't modify a structs fields through a property. (Vector2, Rectangle, etc.)

CollidableSprite

public class CollidableSprite
{
	private bool IsCollingWith(List<CollidableSprite> spritesThatMightBeColliding)
	
	private void correctCollision(CorrectionVector2 correction, bool correctHorizontal)
	
	private CorrectionVector2 getSmallestCorrectionX(DirectionX directionX,
	                                                 List<CorrectionVector2> corrections)

	private CorrectionVector2 getSmallestCorrectionY(DirectionX directionY,
	                                                 List<CorrectionVector2> corrections)
	                                                 
	public CorrectionVector2 GetCorrectionVector(CollidableSprite target)

	public Vector2 Position;
	public Rectangle Bounds;
}
				

The methods could/should be moved out to a static class to clear up the code and reduce the size. Their contents will be described further down.

CorrectionVector2 and direction enums
CorrectionVector2 is used when calculating the axis where the displacement/translation will occur. Translation and displacement is the same thing as moving the object/player.

public struct CorrectionVector2
{
	public DirectionX DirectionX;
	public DirectionY DirectionY;
	public float X;
	public float Y;
}

public enum DirectionX
{
	Left = -1,
	None = 0,
	Right = 1
}

public enum DirectionY
{
	Up = -1,
	None = 0,
	Down = 1
}

1. Get all colliding objects

This is where you parse your walls to check which of them are colliding with your player. I've put my blocks in a grid, so I can easily make a matrix that provides easy and fast access to adjacant blocks.

The matrix with blocks (walls and platforms)

BlockSprite[,] blockMatrix = new BlockSprite[100,50];
				

2. Check for collisions

Iterate throught all of your sprites, testing their Bounds against the players Bounds. Is any of them Intersects, continue.

private bool IsCollingWith(List<CollidableSprite> spritesThatMightBeColliding)
{
	foreach (ECollidableSprite sprite in spritesThatMightBeColliding)
	{
		if (PlayerSprite.Bounds.Intersects(BlockSprite.Bounds))
			return true;
	}

	return false;
}
			

3. Calculate the resolution direction for all collisions

Create a function that calculates the correction between two objects

public CorrectionVector2 GetCorrectionVector(CollidableSprite target)
{
	CorrectionVector2 ret = new CorrectionVector2();

	float x1 = Math.Abs(Bounds.Right - target.Bounds.Left);
	float x2 = Math.Abs(Bounds.Left - target.Bounds.Right);
	float y1 = Math.Abs(Bounds.Bottom - target.Bounds.Top);
	float y2 = Math.Abs(Bounds.Top - target.Bounds.Bottom);

	// calculate displacement along X-axis
	if (x1 < x2)
	{
		ret.X = x1;
		ret.DirectionX = DirectionX.Left;
	}
	else if (x1 > x2)
	{
		ret.X = x2;
		ret.DirectionX = DirectionX.Right;
	}

	// calculate displacement along Y-axis
	if (y1 < y2)
	{
		ret.Y = y1;
		ret.DirectionY = DirectionY.Up;
	}
	else if (y1 > y2)
	{
		ret.Y = y2;
		ret.DirectionY = DirectionY.Down;
	}

	return ret;
}

Store all corrections in a list

List<CorrectionVector2> corrections = new List<CorrectionVector2>();

foreach (ECollidableSprite sprite in collidingSprites)
{
	corrections.Add(GetCorrectionVector(playerSprite, sprite));
}

We now have a list of all the corrections needed to move away from each block/object that the player is colliding with.

4. Sum up the directions

In the image below, where are currently at the "Calculate correction"-scenario. We have our corrections, and we need to sum them up do determine what direction that should be used to calculate the displacement.

summing up directions

Lets go through the different corrections

  1. Horizontal: Right, Vertical: Down
  2. Horizontal: Right, Vertical: Down
  3. Horizontal: Right, Vertical: Up
  4. Horizontal: Right, Vertical: Up
  5. Horizontal: Right, Vertical: Up
  6. Horizontal: Left, Vertical: Up
Horizontal sum: 5 Right, 1 Left. According to the enum DirectionX, Left is worth -1 and Right is worth 1. The horizontal sum would be 4.
Vertical sum: 2 Down, 4 Up. According to the enum DirectionY, Up is worth -1 and Down is worth 1. The vertical sum would be 2.

With the following code we can determine the direction for the two axis (X and Y)

int horizontalSum = SumHorizontal(corrections);
int verticalSum = SumVertical(corrections);

DirectionX directionX = DirectionX.None;
DirectionY directionY = DirectionY.None;


if (horizontalsum <= DirectionX.Left)
	directionX = DirectionX.Left;
else if (horizontalsum >= DirectionX.Right)
	directionX = DirectionX.Right;
else
	directionX = DirectionX.None; // if they cancel each other out, i.e 2 Left and 2 Right


if (verticalSum <= (float)DirectionY.Up)
	directionY = DirectionY.Up;
else if (verticalSum >= (float)DirectionY.Down)
	directionY = DirectionY.Down;
else
	directionY = DirectionY.None; // if they cancel each other out, i.e 1 Up and 1 Down

5. Correct the players position

This is the most complicated step. Detailed flow for this step is as follows.

  1. if (Math.Abs(verticalSum) > Math.Abs(horizontalSum))
  2. else if (Math.Abs(horizontalSum) > Math.Abs(verticalSum))
Note: Math.Abs() makes all number absolute/positive. So -4 would become 4.

CorrectionVector2 smallestCorrectionY = getSmallestCorrectionY(directionY, corrections);
CorrectionVector2 smallestCorrectionX = getSmallestCorrectionX(directionX, corrections);

if (Math.Abs(verticalSum) > Math.Abs(horizontalSum)) // start with Y, if collision = then try X
{
	correctCollision(smallestCorrectionY, false);
	CreateBounds();
	if (IsCollidingWith(collidingNodes))
		correctCollision(smallestCorrectionX, true);
	else
		directionX = DirectionX.None;
}
else if (Math.Abs(horizontalSum) > Math.Abs(verticalSum)) // start with X, if collision = then try Y
{
	correctCollision(smallestCorrectionX, true);
	CreateBounds();
	if (IsCollidingWith(collidingNodes))
		correctCollision(smallestCorrectionY, false);
	else
		directionY = DirectionY.None;
}			

Unresolved condition: These two conditions take care of most scenarios, but sometimes there are as many corrections along the Y-axis as there are on the X-axis. I.e: 2 Up, 2 Left or 2 Down, 2 Left, etc.

How to resolve: Check all the corrections along both axis (accoring to directionX and directionY which we got in step 4) and save the corrections that have the smallest displacement-value. If the correction along Y is less that along X, use that first. If both are equal in size, then resolve X before resolving Y.

if (smallestCorrectionX.X > smallestCorrectionY.Y) // start with Y
{
	correctCollision(smallestYCorrection, false);
	CreateBounds();
	if (IsCollidingWith(collidingNodes))
		correctCollision(smallestXCorrection, true);
	else
		directionX = DirectionX.None;
}
else // start with X
{
	correctCollision(smallestXCorrection, true);
	CreateBounds();
	if (IsCollidingWith(collidingNodes))
		correctCollision(smallestYCorrection, false);
	else
		directionY = DirectionY.None;
}

Method for correcting position

private void correctCollision(CorrectionVector2 correction, bool correctHorizontal)
{
	if (correctHorizontal) // horizontal
		Position.X += CorrectionVector2.X * CorrectionVector2.DirectionX;
	else // vertical
		Position.Y += CorrectionVector2.Y * CorrectionVector2.DirectionY;
}			
			

Method for getting smallest correction along X

private CorrectionVector2 getSmallestCorrectionX(DirectionX directionX, List<CorrectionVector2> corrections)
{
	CorrectionVector2 smallest = new CorrectionVector2();
	smallest.X = int.MaxValue;

	foreach(CorrectionVector2 correction in corrections)
	{
		if (correction.DirectionX == directionX && correction.X < smallest.X)
			smallest = correction;
	}
	
	return smallest;
}
			

Afterwords

This is what I've gotten to work, I don't have any source code since my then I would have to deliver my whole framework and that would just be confusing since there are hundreds of classes. Some code I've written up just now and might not compile due to syntax errors. This article is to show the concept and it works. The only known problem is that if your standing on an edge, far out, and jump straight up, this will correct your position so you would end up outside of the block you're stood on. Well, write that off as the player having slippery shoes.

You could implement a virtual method CollisionResponse() that takes care of the collision after the Position has been corrected. This method could check if directionX == DirectionX.Up and tell you if the sprite(player/enemy/object) has hit the ground or not. This goes for hitting the ceiling aswell. If you hit the ceiling, set the vertical velocity to 0, etc.