Friday, May 23, 2014

Intro to Collision Detection: Collision Detection Basics

In this lesson, we will be discussing a few methods of collision detection and how one would go about implementing them.

What exactly does collision detection describe?
To put simply, collision detection is a way of checking for object interaction.

In most real-time games (both old and new), collision detection is an integral element that holds everything together. As such, a poor collision detection system can make the gaming experience painfully frustrating and, in worst scenarios, may even "break" your game.
No one likes broken games.

You should make every effort to implement as fluid and accurate a collision detection system as needed by your game.

How accurate must I be?
Depending on your game, your needs will vary. If your game is extremely high speed, players might not notice if your collision detection is not fully accurate. On the other hand, if your game is an action platformer, players might notice if your character gets hit prematurely.

You must spend time experimenting with your game to determine what system works best for you.

What are some examples of Collision Detection?

When Mega Man is jumping and sliding across platforms, the game is detecting a collision between the character and the surface.

When Mario leaps around to collect coins, the game checks to see if he has hit a coin and then reacts by playing a sound, removing the coin from the screen, and adding to the score.

If you are new to game development, the first thing you have to realize is that there are few built-in methods of checking whether your objects are colliding, because pixels, which are just visual representations, do not mean much to the computer.

1. Bounding Rectangle/Box Collisions

One of the simplest ways to handle collision detection is the bounding rectangle method.

If objects in your game can roughly be represented by a rectangle, this is probably the method you would choose. In this method, you check for vertical and horizontal overlap and make changes accordingly. Depending on the direction of the collision, your character may be lifted up or down or pushed left or right.

Programatically, you might represent the above collision like this (this is very simplified as we do not check vertical position):

Assume the following
Let MegaMan.right be the x coordinate of the right side of the rectangle.
Let Megaman.vX be MegaMan's velocity in the X direction.
Let brick.left be the x coordinate of the left side of the rectangle.

Sample Code:
if (MegaMan.right + MegaMan.vX > brick.left){
   System.out.println("Right side collision!") ;  
   // Handle Collision

If we apply this concept to all four sides of the rectangle, then we would have a bounding rectangle collision detection system.

How exactly would we "handle collision?"
In the example above, we might set MegaMan.vX equal to 0 so that Mega Man stops moving. In addition, we might change Mega Man's location so that the two rectangles are touching but no longer intersecting. This way we do not have to repeatedly handle collision.

How do you improve accuracy of this collision?
The above system is not a very accurate one, as we will end up with results like this:

With the above method, the game will register a collision even when certain parts of the sprite (the character image) are far away from hitting something. This would lead to a poor user experience.
Here are some solutions that you might try implementing:

1. Reducing the Size of the Rectangle

Rather than covering the tallest and widest parts of the character, you might try creating "a box of best fit." Doing this might improve collision significantly, and for most games, it might be perfectly satisfactory.

However if your game calls for a little more accuracy, you can always implement the next method.

2. Use Multiple Bounds

If your game needs to check which part of the character was getting hit, then you might use this method.

Rather than using one bounding box, you can use multiple ones as follows:

This will ensure that collision is as close to the sprite as possible and will also give you more control on each collision.

The downside of this method, however, is that:

  1. Performance will suffer if you check too many collisions.
  2. It takes a lot of time to implement.

2. Bounding Circle Collision

If your game has handles a lot of balls, a bounding rectangle may not work best. In those situations, you will want to use Bounding Circles.

Although you might think this will be complicated to implement, it is actually pretty simple due to the fact that a circle has a constant radius.

In the above example (created using characters of TUMBL) the radius of the two characters are represented by R1 and R2.

Given the properties of circles, we can assume the following:

  1. If the distance between the centers of the two circles are greater than R1 + R2, they are not colliding.
  2. If the distance between the centers of the two circles are LESSER than R1 + R2, then they must be colliding.

How would we implement this system?
Assuming that we know the (X, Y) coordinates of the two circles, this is rather simple to implement.
We would use the distance formula (if you have a hard time remembering it, try to derive it as an application of the Pythagorean theorem): sqrt( (x1 - x2)^2 - (y1 - y2)^2) .

We would then compare this value to R1 + R2, and then determine whether the two collided.

What if we want to make them bounce off of each other?
This would be slightly more tricky and would take a lot more time to implement, but it would not be too difficult.

By drawing a triangle using the distance formula, we can determine the angle of collision.

Then we would proceed by using vectors and kinematic equations to determine the velocity and direction that each character would be pushed. We won't be going over that in this lesson.

Maybe in a future lesson!

Of course, few games deal exclusively with circles, so there's always the third option!

3. A Combination of Both

In TUMBL, the main character is circular and all the platforms are rectangular.

By using techniques described above, you can create a collision detection system that incorporates both bounding rectangles and circles. Fun stuff!

Where will we go from here?
If you are following the game development tutorials, we will be implementing a few of these techniques to our game.

If you are not, be sure to check them out! They might be helpful.

No comments:

Post a Comment