You are here

Chapter 20: Collision detection basics

Now that we have five different objects moving around on the screen, there's a golden opportunity to implement some sort of collision detection mechanism.

(I'm not sure that I want the asteroids to be able to collide in the finished game, but they do represent a good test case.)

But which method should we use? 

  1. Check if the borders of any object intersects with any other object's borders? (There is a Rect.intersects() method that could be used for that.)
  2. Check while we are drawing and see if one more pixels are occupied already? (Drawback is that objects only can collide with other objects that are already drawn - meaning that the idea of separate update() and draw() in our GameEngine doesn't really fly.)
  3. Check within a circle from each objects midpoint? (Better than within a rectangle, but not quite pixel-perfect.)

(If you want to dig deeper into the details, there's a very thorough article here:

Method 1 isn't really applicable in our case, as our asteroids are very far from being rectangular. So I think I start elaborating around using a combination of method 2 and 3 or just method 3.

Consider two asteroids traveling in trajectories that will make them collide in the very near future:


As we already decided, the shapes of the asteroids are pretty close to circles, so we will use circles in our detection algorithm. The question is: How large circles?

There are two main options here:

Option 1: We use circles that completely covers the asteroids, and if they intersect - we look more closely into the rectangular area that covers the intersection:


Option 2: ​We use circles that aligns with the real borders as good as possible, and if they intersect - we call it a collision. (Sometimes they should have collided already before, and sometimes they shouldn't have collided at all.):


Option 1 is the solution that can be "pixel perfect", but it will cost us many expensive CPU-cycles. First we need to know whether the circles intersect or not, preferably by calculating the distance between the center points of asteroid A and B and see if that distance is smaller than the sum of both circles' radiuses. That's a pretty fast operation, but the second part is worse. Far worse. 

Remember how we decided to rotate the whole canvas instead of the asteroids while drawing them on the display? That choice bites back now.

Take a look at these two scenarios as an example of what I mean:

The circles are on identical positions in both scenarios, as well as the x,y positions of the asteroids. What differs is the rotation. One scenario is a collision, the other one is not. But we don't have any rotated bitmap images in our code... We never rotate anything at all in the update() method. We just increase the value of a rotation-counter.

If our assignment was to really, really make a pixel-perfect collision detection, we could have solved it by:

  1. Check for collisions in the draw() method instead
  2. Make sure that our GameEngine calls draw() every frame, and skip our nice timing functionality
  3. Draw one asteroid at a time, and between each canvas rotation and asteroid draw, loop through the whole bitmap and check if the corresponding position on the canvas is empty or if there's part of an already drawn asteroid there (the "method 2 strategy")

We could of course make all asteroids perfectly circular. Or rectangular. Or as a series of different polygons... (Real "Big-League" game engines would probably use a huge set of 2-D triangular shapes in a 3-D space. But let's not get into that now. Maybe later...)

Ok, that was about the first option. Now let's take a deeper look at Option 2.

Nah - let's just go for it. It's so much faster and easier.

So, I will try to implement the option-2-collision-detection as a nested for-loop just after each asteroid's move, looping through all previously processed asteroid. I know that it will lead to a number of calculations that corresponds to number-of-asteroids * number-of-asteroids / 2, which isn't really that optimal... (Actually it's a lot like the "Good Morning"-goldfish-scene in Monty Python's The Meaning of Life.)

But let's try it out anyway in the next chapter, as we now know how to profile our app.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer