Kilobolt
  • Home
  • Tutorials
    • Game Development Tutorial >
      • Unit 1: Beginning Java >
        • Before you begin...
        • Day 1: Setting Up
        • Day 2: Java Basics
        • Day 3: More Basics
        • Day 4: Java Math
        • Day 5: More Math
        • Day 6: If... else...
        • Day 7: More Control Flow
        • Day 8: Looping
        • Day 9: More on Looping
        • Day 10: Inheritance, Interface
        • Day 11: Threads and Graphics
      • Unit 2: Creating a Game I >
        • Day 1: Foundations
        • Day 2: Basic Framework
        • Day 3: Taking User Input
        • Day 4: Enter the Robot
        • Day 5: Background and Sprites
        • Day 6: Adding Enemies
        • Day 7: Shooting Bullets
        • Day 8: Animations
        • Day 9: 2D-Arrays
        • Day 10: Painting the Tilemap
      • Unit 3: Creating a Game II >
        • Day 1: Level Creation - Part 1
        • Day 2: Level Creation - Part 2
        • Day 3: Level Creation - Part 3
        • Collision Detection Basics
        • Day 4: Collision Detection Part 1
        • Day 5: Collision Detection Part 2
        • Day 6: Collision Detection Part 3
        • Day 7: Health System & Death
        • Day 8: Basic AI & Final Touches
      • Unit 4: Android Game Development >
        • Day 1: Introduction to Android
        • Day 2: Setting up for Development
        • Day 3: Creating our First Android Application
        • Day 4: Parts of an Android Application
        • Day 5: The Android Game Framework: Part I
        • Day 6: The Android Game Framework: Part II
        • Create an Android Game From Scratch (or port your existing game)
        • Day 7: Creating an Android Game (From Start to Finish)
      • Reference Sheet
    • Zombie Bird Tutorial (Flappy Bird Remake) >
      • Unit 1: Building the Game >
        • Introduction
        • Day 1: Flappy Bird - An In-depth Analysis
        • Day 2: Setting up libGDX
        • Day 3: Understanding the libGDX Framework
        • Day 4: GameWorld and GameRenderer and the Orthographic Camera
        • Day 5: The Flight of the Dead - Adding the Bird
        • Day 6: Adding Graphics - Welcome to the Necropolis
        • Day 7: The Grass, the Bird and the Skull Pipe
        • Day 8: Collision Detection and Sound Effects
        • Day 9: Finishing Gameplay and Basic UI
        • Day 10: GameStates and High Score
        • Day 11: Supporting iOS/Android + SplashScreen, Menus and Tweening
        • Day 12: Completed UI & Source Code
    • Android Application Development Tutorial >
      • Unit 1: Writing Basic Android Apps >
        • Before you begin...
        • Day 1: Android 101
        • Day 2: Getting to Know the Android Project
        • Day 3: The Development Machine
        • Day 4: Building a Music App - Part 1: Building Blocks
        • Day 5: Building a Music App - Part 2: Intents
        • Day 6: Building a Music App - Part 3: Activity Lifecycles
  • New Forum
  • About Us
    • Contact Us
  • Our Games
    • TUMBL: FallDown
  • Facebook
  • Twitter

Intro to Collision Detection: Collision Detection Basics

12/7/2012

22 Comments

 
Picture
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. 
Picture
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.
Picture

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:
Picture
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.
Picture
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:
Picture
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 cOLLISIONS

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.
Picture
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.
Picture
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.
Picture
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!
Picture

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.

Thank you for reading, and please Like us on Facebook if this guide helped you!
Picture
Go to Unit 3: Day 3
Go to Unit 3: Day 4
22 Comments

    Author

    James Cho is the lead developer at Kilobolt Studios. He is a college student at Duke University and loves soccer, music, and sharing knowledge


© 2014 Kilobolt, LLC. All rights reserved.