Collision Detection

[richcash]

Collision Detection Tutorial

What is collision detection?

Collision detection is a programming technique used to determine whether two objects or pictures on a screen are touching (or have collided!). It is especially used in games to check if two balls, two characters, or two of anything have collided. While there may be unlimited methods of checking for collision, the two main ones that we will be discussing are known as rectangular collision detection and circular collision detection.


Rectangular Collision Detection

The method referred to as rectangular collision detection determines whether or not two rectangles have collided (hence, the name!). In order to use rectangular collision detection, you must have these pieces of information about both of your rectangles :

• lowest x value of the rectangle
  
• lowest y value of the rectangle
  
• greatest x value of the rectangle
  
• greatest y value of the rectangle

These are often referred to as : x1, y1, x2, and y2. If you draw a rectangle (box) in Turing, you automatically know these pieces of information, because the first four parameters for drawbox are x1, y1, x2, and y2.

(If you're using an imported picture, read this. Otherwise, you can skip it.)
For an imported picture, you only know x1 and y1 and those are the first two parameters to your Pic.Draw. However, we can easily find x2 and y2 by adding a function known as Pic.Width ("picture_name") to our x1 value. For y2, we simply add Pic.Height ("pic_name") to y1. Simple enough.

Now, to check if two rectangles on the screen have collided or are touching (some might even say they are overlapping!), we have to check for the following conditions. Let's use box #1 and box #2 to represent our two rectangles and assume that they have the 4 parameters needed.

• box #1's x1 (lowest value) has to be LESS than box #2's x2 (greatest value)
  
• box #1's x2 (greatest value) has to be GREATER than box #2's x1 (lowest value)
  
• box #1's y1 (lowest value) has to be LESS than box #2's y2 (greatest value)
  
• box #1's y2 (greatest value) has to be GREATER than box #2's y1 (lowest value)

So, if all of those conditions are met, then box #1 and box#2 have collided. But why are these the conditions? Well, in your mind, suppose if one of the conditions above wasn't true. Why wouldn't the boxes have collided if any of those conditions weren't true. Think about it for each condition.

Well, it's fairly simple if you can picture it like below. Look at the x-axis only, in the first diagram you can see that the the first box has a right end and this is obviously its greatest value. The second box has a left end and this is its lowest value. The second box's left end is to the left of the first box's right end, which means the second box's lowest value (left end) is less than the first box's greatest value (right end). The second diagram shows what would happen if this wasn't so. Picture it the same way for the y-axis except (of course!) up and down instead of left and right.

code:

_____           _____ |___|__         |___|   _____    |___|                |___|

Now that we fully comprehend rectangular collision detection, let's use it in some code!

code:

%declare some variables for box1 and box2 var box1_x1, box1_y1, box1_x2, box1_y2 : int var box2_x1, box2_y1, box2_x2, box2_y2 : int %assign our variables to values for boxes. These can be anything. box1_x1 := 100 box1_y1 := 100 box1_x2 := 150 box1_y2 := 150 box2_x1 := 300 box2_y1 := 125 box2_x2 := 350 box2_y2 := 175 loop     %draw the boxes     cls     drawbox (box1_x1, box1_y1, box1_x2, box1_y2, 9)     drawbox (box2_x1, box2_y1, box2_x2, box2_y2, 12)     delay (20)     %move our first box horizantally     box1_x1 += 1     box1_x2 += 1     %check for all four of our conditions!     if box1_x2 > box2_x1 and box1_x1 < box2_x2 and box1_y2 > box2_y1 and box1_y1 < box2_y2 then         put "They have collided!"         exit     end if end loop

One other thing. Rectangular collision detection can sometimes also be used with non-rectangular shapes, but in this case you make your own theoretical rectangle (x1, y1, x2, y2) around the object and use this as a rectangle. Obviously, it is inaccurate, but if the shape is rectangular enough it will work considerably well. And that's all for rectangular collision detection!


Circular Collision Detection

Circular collision detection detects collision between (you guessed it!) two circles. (Please note that this type of collision detection does not work with non-circular ovals!). The method of doing it is actually quite simple. In order to use this method, you must know the following about both of the circles colliding :

• co-ordinates of the centre point (x and y) of both circles
  
• radius of both circles

In order to use drawoval (or drawfilloval), you have to use these values as your parameters anyway. To clarify, the x- and y- radii are the same in our case because we are using circles.

Now, the actual method to check for collision between the two circles has three steps (well, kind of one!). These three steps are :

1. Find the distance between the centres of the two circles.
   
2. Add the two radii of the circles (radius of one circle + radius of the other circle).
   
3. Check if the distance between the centres of the circles is less than the sum of the two radii and, if it is, then the two circles have collided or are overlapping.

Why does this method work? Think of it this way. How would we detect collision if the circles were just dots and had no radii. We would just check if the distance between them was 0 (they would be equal). But, since we do have circles and actual radii, the distance between the centres doesn't have to be 0, it can be more. How much more? It can be one circle's radius + the other circle's radius more. If the distance between the centres of the circles is less than or equal to the two radii added up, then that means the "circles" are theoretically on top of each other, which means a collision has happened.

So, now we know the method to detect circular collision, but there is one thing we are missing. How do find the distance between the two circles' centres? Well, we use the distance formula (or the distance-between-two-points formula!) that is learned in high school math and is derived from the pythagorean theorem. For more information about the distance formula in specific (and the derivation of it), you can search on the internet or go here.
Now, let's write the distance formula in Turing :

code:

distance := sqrt ((x2 - x1) ** 2 + (y2 - y1) ** 2)

And, for our case of circular collision detection, x1 would be the x coordinate of the centre of circle 1, y1 would be the y coordinate of the centre of circle 1, x2 would be the x coordinate of the centre of circle 2, and y2 would be the y coordinate of the centre of circle 2.

Now, let's implement our collision detection system into a program!

code:

%declare our variables var circle_1_x, circle_1_y, circle_1_radius : int var circle_2_x, circle_2_y, circle_2_radius : int var distance_between_centres : real %give our two circles values. These can obviously be changed. circle_1_x := 100 circle_1_y := 100 circle_1_radius := 5 circle_2_x := 210 circle_2_y := 190 circle_2_radius := 20 %main program loop     %draw our circles. Remember, the x-radius and y-radius are the same!     cls     drawoval (circle_1_x, circle_1_y, circle_1_radius, circle_1_radius, 12)     drawoval (circle_2_x, circle_2_y, circle_2_radius, circle_2_radius, 9)     delay (20)     %Move the first oval diagonally     circle_1_x += 1     circle_1_y += 1     %calculate the distance between the centres of the circles     distance_between_centres := sqrt ((circle_2_x - circle_1_x) ** 2 + (circle_2_y - circle_1_y) ** 2)     %Our collision detection method     if distance_between_centres <= circle_1_radius + circle_2_radius then         put "The circles have collided!"         exit     end if end loop

Remember, as was the same for rectangular collision detection, this method can also be used inaccurately with non-circular objects by making a theoretical circle around the object and using the data from your theoretical circle for your collision detection.
Also note that if you need it so that circles or balls are colliding and then bouncing off of each other (like billiards), you will need to use more advanced methods. Check out these tutorials :

A Start to Pool
More Specific Implementation of Pool in Turing
Circular Collision Data

And that does it for circular collision detection!

Mod edit: vastly improved formatting, seems it was all caused by a couple of misplaced BBCode tags.

[[Gandalf]]

You'll definately want to work on that formatting... A lot. As it stands, my eyes hurt just from glancing at this monstrosity...

[richcash]

LOL, now that you mention it, the formatting could be improved greatly. I'll try to do that soon. Thanks for the constructive criticism.

[zylum]

not a very good tutorial. first off, like gandalf already mentioned, the formatting is terrible. i had to zoom out just to be able to read it without straining my eyes.

as for the content, it only covers the very basics and doesnt do a very good job at that. ie your four rules for rectangle collision detection. you keep using 'less than' or 'greater than' when it actually has to be less than or equal etc.. furthermore, your code examples show poor programming practice. read the records tutorial if you havent done so already. your circle - circle collision detection can be improved performance wise. ie you can omit the costly sqrt call and just check if (rad1 + rad2)^2 >= (x2-x1)^2 + (y2-y1)^2.

sorry if im sounding so harsh, but there is no need for another sub-par collision detection tutorial.


perhaps, i'll write a tutorial on collision detection. i was thinking of writing an intro tutorial to 3D but i think more people will benefit from a good collision detection tutorial...

[richcash]

I don't know, guys. I had my tutorial approved by a mod (and indirectly by another mod). It was only meant to be a replacement for the current one from three years ago. Now that I read it over again I realize that it's not as good as I thought it was when I originally wrote it. This is not a good display of my best work.

Quote:

furthermore, your code examples show poor programming practice. read the records tutorial if you havent done so already.

I'm offended! Just joking, but on a serious note I wanted to keep this very simple. I just thought that if someone doesn't know the concept of collision detection, then how will they know records. Perhaps I should've made it with more advanced coding.

Quote:

ie you can omit the costly sqrt call and just check if (rad1 + rad2)^2 >= (x2-x1)^2 + (y2-y1)^2.

Yeah, I know, or you can just ^0.5, but these are just things you simplify by yourself. I'm trying to relate the code to the distance formula learned in math class. I took a conceptual approach, I tried to explain everything like I was talking to somebody who just learned loops and for loops.

Quote:

perhaps, i'll write a tutorial on collision detection. i was thinking of writing an intro tutorial to 3D but i think more people will benefit from a good collision detection tutorial...

While I certainly couldn't compete with a tutorial by you, I want to finish what I started. Please, let me re-attempt this tutorial. I'll go from scratch and include much more advanced algorithms. Let me prove myself. Just name some of the things you want included and I'll try to do them. I'm starting all over so it will be a while before I finish.

[Cervantes]

Fixing up the BBCode would go a long way to fixing this tutorial. I think the content is good, but maybe I should read it more closely. I think the presentation (aside from the BBCode issues) is good.

Try posting the version you sent me (and that I sent back to you a little while ago). It's got good BBCode.

Feel free to use this thread while you're making changes. When we're all satisfied, I'll delete this thread and you can post it fresh.

[zylum]

richcash wrote:

Quote:

ie you can omit the costly sqrt call and just check if (rad1 + rad2)^2 >= (x2-x1)^2 + (y2-y1)^2.

Yeah, I know, or you can just ^0.5, but these are just things you simplify by yourself. I'm trying to relate the code to the distance formula learned in math class. I took a conceptual approach, I tried to explain everything like I was talking to somebody who just learned loops and for loops.

the point isnt that you could use exponentiation rather than the sqrt() function. ^0.5 is the same as the sqrt function which is a very costly operation compared to addition, subtraction or multiplication. that is why you use my method which involves multiplication and addition and no square roots which can slow down you program.

if i were going to write a collision detection tutorial i would go roughly like this (though i find writing tutorials is a very dynamic process):

- intro:
- brief intro to topic
- discuss what your tutorial will cover
- background info needed to comprehend tutorial
- perhaps a preview of what you can accomplish or something to motivate reader

- basics: simple collision detection
- rectangle - rectangle
- circle - circle
- circle rectangle

- intermediate:
- line - line
- circle - line
- bounding boxes

- advanced:
- arbitrary polygonal shapes
- time based collision detection to prevent over lap and increase precision (used in games like pool where collision detection is very important)

- conclusion (at the end of each section)
- review key concepts
- practice problems
- solutions

basically thats it. i would add stuff if i saw the need. if you dont have the knowledge to do all that or you just dont have the time/ dont feel like it, make your tutorial the "basics of collision detection" and ill continue the series.

[Tony]

The sqrt comment was kind of harsh. Although valid, it has to do with optimization, not the concept of collision. sqrt conveys the message better at a simpler level. (optimized version could be mentioned in the comments)

The formatting throws things off... a lot.

The language could use some improvement.

Quote:

Well, in your mind, suppose if one of the conditions above wasn't true. Why wouldn't the boxes have collided if any of those conditions weren't true. Think about it for each condition.

Learning is best achieved when the students comes up with the answer on their own. Here you throw out the answer, and tell them "think about why I'm right".

A better approach would be to provide an illustration (it's a tutorial for graphical application - use some graphics), ask what conditions describe the situation (collision) presented, and follow through with that.

There are some technical points to address as well

Quote:

* lowest x value of the rectangle
* lowest y value of the rectangle
* greatest x value of the rectangle
* greatest y value of the rectangle
These are often referred to as : x1, y1, x2, and y2. If you draw a rectangle (box) in Turing, you automatically know these pieces of information, because the first four parameters for drawbox are x1, y1, x2, and y2.

x1/y1, x2/y2 are just two opposing corners, not neccessary the lowest/greatest.

code:

Draw.Box(200,200,100,100,blue)

If you are making an assumption that the values will always be in a more convinient order, do state that assumption. It will clear up any possible confusions.

When writing a tutorial on an existing subject, do make sure to take it a step higher. Try to address the weaker points of the existing material, and answer applicable questions from follow-up comments.

[richcash]

Alright, thanks to everyone for pointing out my weakness. I'll see what I can finish in the next couple of weeks, and if it is too much for me then I'll just cover the basics. The version I sent Cervantes was a bit better, but still subpar seeing what you guys have pointed out. I'll just make my adjustments and revisions in this thread as advised.

[zylum]

yeah i realise i was sort of harsh, i was sort of in a hurry and wanted to write down as somethings before i had to go. sorry about that

i find it takes a lot of skill to write a good tutorial. there are always ways you can improve an existing tutorial, whether it is to improve the language, add an image to explain something better or to simply add more colour for visual appeal. when i write a tutorial i always write an outline, then a rough copy. as i go over the rough copy i add extra info and try to clarify ideas. even now when i go through some of my old tutorials, i find ways i could improve them (but of course am to lazy to update them )

maybe someone should write a tutorial on how to write a tutorial

oh wait... http://compsci.ca/v2/viewtopic.php?t=9619

[ZeroPaladn]

I've ben reading thru this thread and there seems to be no mention of dual layer collision detection (the one with the collision layer drawn before the actual stuff to be seen by the user, usually is done by comparing colours). Perhaps you can add this? It works well with tile-based games, and it's pretty simple (though is a hog for computing power)

[Cervantes]

ZeroPaladn wrote:

I've ben reading thru this thread and there seems to be no mention of dual layer collision detection (the one with the collision layer drawn before the actual stuff to be seen by the user, usually is done by comparing colours). Perhaps you can add this? It works well with tile-based games, and it's pretty simple (though is a hog for computing power)

You're talking about whatdotcolour?

Actually, I'd be happy if whatdotcolour didn't make any appearance in the collision detection tutorial. A separate tutorial for whatdotcolour is just fine, but I think it should be kept out of the main collision detection tutorial if only for the fact that it would help to prevent people from thinking that collision detection is whatdotcolour.

And as for whatdotcolour with tile based games... I'm shocked. The collision detection in tile-based games is as easy as it can possibly get. Using whatdotcolour totally obfuscates things.

[ZeroPaladn]

Cervantes wrote:

...The collision detection in tile-based games is as easy as it can possibly get. Using whatdotcolour totally obfuscates things.

To each his own. I personally prefer to use whatdotcolour collision detection over conventional co-ordiante collision detection. I think whatdotcolour could make a small appearance in the tutorial (if even just a link to a whatdotcolour tutorial) to give people choice on what they want to do.

[Cervantes]

I'm interested in hearing why you think whatdotcolour is superior in tile-based games.

Heck, I'm interested in hearing why you think whatdotcolour is superior in any situation.

There is a fundamental flaw in whatdotcolour collision detection: What the program draws determines what the program draws in the next iteration. Ideally, drawing is based solely on the state of the variables, not on the state of the output buffer.

Another fundamental flaw of whatdotcolour is how limited it is. Consider a situation in which there are two balls both moving a great many pixels per frame. It is conceivable that, in one frame, the balls could pass through each other. If we could slow things down, we would see that the balls actually should have collided. Whatdotcolour only sees two snapshots of the balls, and in neither snapshot have they collided. Solving this using math would show us that they do collide. It would be like doing whatdotcolour an infinite number of times. What's more, the math will tell us properties of the collisions, such as the positions of both balls exactly when they collide.

[ZeroPaladn]

I've just never used basic collision detection for my programs, i was taught to use whatdotcolour, and what is what i use to this day. i prefer to use what i allready know (even if it does suck) instead of learning something else, when they both serve the same purpose (depending on useage). one day ill learn normal collision detection, and this conversation would be pointless...

time to learn.