Collision: Basic 2D Collision Detection + Jump Physics

This post will cover some various collision techniques for use in 2D games. Types of collisions to be covered in this article are:

• Static point to static circle 
• Static circle to static circle
• Static point to static rectangle
• Static rectangle to static rectangle
• Static circle to static rectangle
• Jumping physics (optimal equation technique)

Static Circle to Static Point

In order to detect whether or not a point is colliding with a circle there are only a few very simple checks required. Luckily a circle is simply a radius and a point. Find the distance from the center of your circle and your colliding point, and check to see if it is larger, greater, or smaller than the radius. Larger means that the point is outside the circle, the same means the point is directly on the edge, and smaller means a collision is occuring.

// Given that CP is the center of the circle, P is the point,
// and R is the radius
if dist( CP, P ) is equal to R: Collision or Non-Collision (you choose)
if dist( CP, P ) is greater than R: No collision
if dist( CP, P ) is less than R: Collision

Static Circle to Static Circle
This collision test is going to be the exact same as Point to Circle, with one difference: you will be comparing the distance from the center of the circles to the radius of the first circle added with the radius of the second circle. This should make sense since the only time two circles will intersect is when their distances are smaller than their radii. Just be sure to avoid this scenario:

Internally tangent intersection.

This internally tangent intersection can be avoided by checking for whether or not the distance between the circles' centers is smaller than the radii combined before checking to see if the distances are equal.


Static Point to Static Rectangle Collision
This algorithm is extremely straightforward. Think of a rectangle as four values: top, left, bottom and right. Here are the checks required to see if a point is within a square or not (it shouldn't require much of any explanation):

// B is bottom of the rectangle
// T is top of the rectangle
// L is the left side of the rectangle
// R is the right side of the rectangle
// P is the point
// Perform the following checks:
if(P.X < L) and if(P.X > R)
and if(P.Y < B) and if(P.Y > T)
then no collision

All of these conditions will fail if there is a collision. To check for a tangent point, check to see if the point's X value equals the left or right side, while being under the top and above the bottom. Vice versa for the top and bottom tangents. This algorithm is going to be very similar to the ActionScript hittest function.


Static Rectange to Static Rectangle
Rectangle to rectangle collision is very simple as well. This should be quite similar to the point to rectangle, except we just use some basic logic to make sure none of the sides of the two rectangles are between each other's sides.

// Given rectangles A and B
if(leftA > rightB) or
if(leftB > rightA) or
if(topA < bottomB) or
if(topB < bottomA)
then no collision

Circle to Rectangle Collision
Circle to rectangle collision is going to be the most complicated algorithm here. First consider a circle to consist of only a point and a radius. The way we detected two circles colliding was by checking the distances from the centers to their radii. Sadly, a rectangle does not have a radius. However, given the closest point on the rectangle to the center of the circle, we can apply the same algorithm as the Static Point to Static Circle collision detection. All we need do now is find out how to find the closest point on the rectangle to the circle's center.


To find this point, clamp a copy of the circle's center coordinate to the edges of the rectangle:

// "Clamping" a point to the side of a rectangle
// Given left right bottom and top are sides of a rectangle
// P is a new variable created and assigned the value of the
// circle's center -- do not modify the circle's coordinate
Point P (new copy of the circles center) = Circle's Center
if(P.X > right) then P.X = right
else(P.X < left) then P.X = left


if(P.Y > top) then P.Y = top
else(P.Y < bottom) then P.Y = bottom then no collision

After the above code is run point P will be somewhere on the edge of the rectangle and will also be the closest point along the rectangle's sides to the center of the circle. Now compare the distance from these two points to the radius with the Static Point to Static Circle algorithm. Results will be the same.

Optimization of Distance Formula
By using some simple algebra one can remove the sqrt function from the distance formula for the purpose of checking two values:

This allows one to compare the distance squared with another distance squared; multiplication is much faster than a sqrt function. This should be applied to all of the above collision algorithms that require a distance function between two points.


Jumping Physics Technique
There are a few different ways to have a character jump in a game. I'm going to share a singular way that I find very efficient and effective. As detailed here in my article on simple physics integration, in order to move something along the screen you are required to use the following equations:

pos.x += vel.x * dt;
pos.yx += vel.y * dt;
vel.x += accel.x * dt;
vel.y += accel.y * dt;

This works just fine for moving images around! In order to simulate a jump you suddenly add a large value to the image's y velocity, and then apply a negative acceleration on it each timestep. Like I said, this works just fine. However as a designer this is a headache. How are you going to tweak the jumping height? Just apply random values to the velocity and guess/check to see how high the character goes? It would be best to be able to set how high you'd like the character to jump, and use some form of automation so solve for the necessary velocity.

This equation comes from a conservation of energy. Take a look at the algebraic manipulation:

The equation you start with represents an upward jump. The two sides are equal due to energy being conserved throughout the jump. At the start of a jump (and the end, assuming the start and end positions are the same y value) all of the energy is kinetic, thrusting the object upward. As it slows down energy is converted into potential energy, which is the distance from the ground the object is currently at. Once all kinetic energy is used potential energy is maxed out, which means this is the peak of the jump. We can take advantage of the fact that the kinetic energy is zeroed out and come up with a simple equation to solve for the necessary upward velocity to reach a specific height. Here's what the final equation can look like in use within code to initialize the y velocity for a jump:

// JUMP_HEIGHT will usually be in tiles.
// Example: perhaps to jump exactly 3 tiles, or 4
vel.y = sqrt( 2.f * -GRAVITY * JUMP_HEIGHT );

This technique not only can be used on jumping characters but projectiles as well. I find this equation exceptionally useful in initializing various values! An optimization to this function would be to pre-compute the velocity by hand and assign it to y velocities of objects from a constant. This method would work well in any situation where the velocity of the jumping height is not changing throughout the duration of the game (perhaps turrets shooting bullets in the same path over and over, or an enemy with only one type of jump).

Tile Maps: Binary Collision

Back in the day binary collision maps (also known as a type of tile map) were used as a simple and efficient way to check for collision between an object with coordinates of floating point value, and square blocks. What sorts of games used binary collision arrays? Well, pretty much any game that had square tile based levels likely used some form of binary collision, here's a few NES screenshots:

Zelda

Mario

Metroid

Zelda

A binary collision array is an array of booleans representing collision or non-collision. In our above examples any square tile that the player could not walk on, or was not empty space would have been represented by a value meaning collision. There would then be a separate array of the same dimensions as the binary collision array, which would represent the different images to draw for each tile.

Example Collision and Data Arrays

Above is an example of what the collision and data arrays might look like for the Zelda screenshot with a bridge. Each 1 would be a block that is unwalkable by the character, and each 0 would be a space the character could walk on. The data array holds different numbers, and each number would represent a different image. These image values could perhaps have been stored in some sort of enumeration, or a CBlock in assembly.


Though, how is the character handled? The character in these games seems to have a position of floating point value. I'm not actually sure if they did or didn't for optimization reasons, but what I'll show you uses a floating point coordinate for different characters/enemies. Here's an image showing an example of a floating point coordinate perhaps representing the player's character:

This point would represent the center of the position of the player. The image drawn for this character at this point would be centered directly onto the point. So now how does one go about detecting when the sides of an image on this point are touching a box that represents collision? In order to do that I'll show a method I've learned called "hotspots".


Hotspots are simply points that are offsets of a coordinate, like the coordinate above. The smallest amount of offset hotspots you can have that I'd recommend is four: one for each side of your square image. When implementing a binary collision array for a simple platformer, I found that eight hotspots worked very well. Here's an example image showing eight hotspots on the edges of a square:

Each of those dots are offset by 1/4 of the square's side length, and 1/2 of the square's side length. For example the bottom two hotspots are offset from the center by -1/2 * side length (assuming origin bottom left of the screen). By using these hotspots you can then detect when any of these hotspots points are within the bounds of a binary tile. There are multiple ways to do this, but the way I chose to was to just floor the floating point value of each hotspot and look at only the integer value left. You can do these with an integer typecast, or a floor function. This works since any floating point value in the range of 1.0 through less then 2.0 will still be within the coordinate tile of 1. If this float truncation is confusing, read the next paragraph, if you understand go ahead and skip the next paragraph.


Say you have a coordinate of 3.7 and 4.3 representing one of your hotspots, and you need to check to see if this coordinate is within a tile that represents collision. If you take a look you'll realize that all values from 3.0 to just before 4.0 are all within the x axis on of the value 3 (as in on column 3 of your grid). This goes the same for 4.3; all values from 4.0 through just before 5.0 are in row 4. This means that any coordinate from 3.0 - 3.99999, 4.0 - 4.999999 are within the tile of 3, 4. So then to check to see where any floating point coordinate is on your integer coordinate system, just throw away your decimal value and treat your float as an integer. 3.7 would be 3, and 4.3 would be 4. Thus your resulting coordinate is 3, 4.


Once this is accomplished you can then execute your code to move the character back to the tile they are currently on. This can be done by also flooring the value of the character's coordinate (not the hotspots). However, you want to snap your character back to the closest tile, not just floor the entire floating point value. To do this you use a simple trick:

coordinate = (int)(coordinate + 0.5f);


This will round your floating point number to the nearest tile by offset the decimal portion of your value by 0.5.


Lastly, if you ever implement a coordinate system like here I suggest normalizing your coordinate system. That is have one tile be represented by the value of 1. This allows for simpler mathematics, and allows you to easily transform (scale, rotate, translate) your entire grid/game to whatever exact size you desire. If you normalize your entire grid in your data, you can separate the drawing logic from your data thus decoupling your code overall.


Here's a screenshot for a platformer I worked on for a CS assignment! I had a normalized grid system with the origin represented by the bottom left of the map. I was scaling this map by a factor of 3. I also implemented some simple AI with a statemachine for the red guys! They walk left and right up the edge of their platform, and turn around at the edge, or turn around when they hit a wall.