Computer Science Canada Collision Detection 
Author:  richcash [ Sun Oct 08, 2006 2:02 pm ]  
Post subject:  Collision Detection  
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 :
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.
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 xaxis 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 yaxis except (of course!) up and down instead of left and right.
Now that we fully comprehend rectangular collision detection, let's use it in some code!
One other thing. Rectangular collision detection can sometimes also be used with nonrectangular 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 noncircular 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 :
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 :
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 distancebetweentwopoints 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 :
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!
Remember, as was the same for rectangular collision detection, this method can also be used inaccurately with noncircular 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. 
Author:  [Gandalf] [ Sun Oct 08, 2006 6:47 pm ] 
Post subject:  
You'll definately want to work on that formatting... A lot. As it stands, my eyes hurt just from glancing at this monstrosity... 
Author:  richcash [ Sun Oct 08, 2006 9:20 pm ] 
Post subject:  
LOL, now that you mention it, the formatting could be improved greatly. I'll try to do that soon. Thanks for the constructive criticism. 
Author:  zylum [ Sun Oct 08, 2006 10:20 pm ] 
Post subject:  
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 >= (x2x1)^2 + (y2y1)^2. sorry if im sounding so harsh, but there is no need for another subpar 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... 
Author:  richcash [ Sun Oct 08, 2006 11:19 pm ] 
Post subject:  
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 >= (x2x1)^2 + (y2y1)^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 reattempt 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. 
Author:  Cervantes [ Mon Oct 09, 2006 12:26 am ] 
Post subject:  
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. 
Author:  zylum [ Mon Oct 09, 2006 12:31 am ] 
Post subject:  
richcash wrote: Quote: ie you can omit the costly sqrt call and just check if (rad1 + rad2)^2 >= (x2x1)^2 + (y2y1)^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. 
Author:  Tony [ Mon Oct 09, 2006 12:38 am ]  
Post subject:  
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.
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 followup comments. 
Author:  richcash [ Mon Oct 09, 2006 12:48 am ] 
Post subject:  
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. 
Author:  zylum [ Mon Oct 09, 2006 12:56 am ] 
Post subject:  
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 
Author:  ZeroPaladn [ Mon Oct 16, 2006 1:32 pm ] 
Post subject:  
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 tilebased games, and it's pretty simple (though is a hog for computing power) 
Author:  Cervantes [ Mon Oct 16, 2006 2:46 pm ] 
Post subject:  
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 tilebased 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 tilebased games is as easy as it can possibly get. Using whatdotcolour totally obfuscates things. 
Author:  ZeroPaladn [ Tue Oct 17, 2006 12:21 pm ] 
Post subject:  
Cervantes wrote: ...The collision detection in tilebased 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 coordiante 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. 
Author:  Cervantes [ Tue Oct 17, 2006 1:12 pm ] 
Post subject:  
I'm interested in hearing why you think whatdotcolour is superior in tilebased 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. 
Author:  ZeroPaladn [ Wed Oct 18, 2006 11:50 am ] 
Post subject:  
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. 
Author:  Andy [ Thu Oct 19, 2006 2:59 am ] 
Post subject:  
ZeroPaladn wrote: 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...
that is the dumbest justification you could've possibly gave. if that is your attitude, then we dont need your input. your job, as a student is to learn, and we are here to help you learn how to complete your tasks the most efficient way. and cervantes, whatdotcolor is superior in every situation. i'd like to see your math detect collision in the situation you mentioned with convex polygons 
Author:  Cervantes [ Thu Oct 19, 2006 9:00 am ] 
Post subject:  
Cervantes wrote: and cervantes, whatdotcolor is superior in every situation. i'd like to see your math detect collision in the situation you mentioned with convex polygons
I doubt I could do it, but I believe it can be done. I'd like to see whatdotcolour do the collision detection in that situation. Or even in the situation using circles instead of convex polygons. And remember, maintaining a good execution speed is important here. 
Author:  blaster009 [ Sat Oct 28, 2006 6:44 pm ] 
Post subject:  
God forbid you should be able to use decent looking pictures in your program with various different colours. I mean, thinking that far outside of the box would completely nullify whatdotcolour! 
Author:  [Gandalf] [ Sat Oct 28, 2006 6:52 pm ] 
Post subject:  
blaster009 wrote: God forbid you should be able to use decent looking pictures in your program with various different colours. I mean, thinking that far outside of the box would completely nullify whatdotcolour!
Ah but it's you who are not thinking outside the box. What if there was a collision detection layer, underneath your colourful pictures, which you used whatdotcolour on? I'm sure there's tons of other tricky stuff that can be done with whatdotcolour. 
Author:  Cervantes [ Sat Oct 28, 2006 10:51 pm ] 
Post subject:  
[Gandalf] wrote: Ah but it's you who are not thinking outside the box. What if there was a collision detection layer, underneath your colourful pictures, which you used whatdotcolour on?
Then you'd be doing far more drawing than necessary, and your code would be that much slower. Drawing is a hefty task. 
Author:  [Gandalf] [ Sat Oct 28, 2006 11:09 pm ] 
Post subject:  
Cervantes wrote: Then you'd be doing far more drawing than necessary, and your code would be that much slower. Drawing is a hefty task.
The point is that using multicoloured pictures doesn't "completely nullify" whatdotcolour. Indeed, using math is almost always faster and more flexible, but it's not the only way. 
Author:  Andy [ Sun Oct 29, 2006 4:55 am ] 
Post subject:  
cervantes, i am not suggesting a pure whatdotcolor approach. more like a combined effort between wdc and math. With whatdotcolour detection, you only need to traverse through the outer perimeter of the given shape. and when lines cross, you get a different colored pixel than you expect, thus signifying a collision. the perimeter of anyshape can be expressed as a first degree function, so your algorithm would be O(n), its really not that slow. blaster009, no offence, but who the hell do you think you're talking to? 
Author:  vertozia [ Fri Dec 29, 2006 12:06 am ] 
Post subject:  
I frankly understand the picture/rectangle collision. How is colour to picture collision performed. e.g. I'm making a Mario game, Mario is a pic, the pipe is a color? How? 
Author:  Cervantes [ Fri Dec 29, 2006 5:27 pm ] 
Post subject:  
Did you read the whatdotcolour tutorial? That would be a good place to start. 
Author:  richcash [ Fri Mar 16, 2007 9:40 pm ]  
Post subject:  Re: Collision Detection  
More Advanced Collision Detection
To get the most out of this tutorial, you will need to understand the following :
types records functions circular collision detection rectangular collision detection Circle vs Rectangle
Assume that : (x1, y1) is the lower left corner of the rectangle (x2, y2) is the upper right corner of the rectangle (x, y) is the center of the circle r is the radius of the circle The first way we can check if the circle and rectangle are intersecting is to check if any of the rectangle's four corners are inside of the circle. We already have two of the rectangle's corners (x1, y1) and (x2, y2). The other two corners will obviously be (x1, y2) and (x2, y1). if (x1  x)^2 + (y1  y)^2 <= r^2 or (x1  x)^2 + (y2  y)^2 <= r^2 or (x2  x)^2 + (y1  y)^2 <= r^2 or (x2  x)^2 + (y2  y)^2 <= r^2 then we know we have a collision between the circle and the rectangle But the circle and rectangle can intersect in such a way that none of the rectangle's corners are inside of the circle. Just imagine the circle on one of the rectangle's edges. First, let's think of this type of scenario happenning on one of the rectangle's horizontal edges. If this is the case, then either the highest point on the circle or the lowest point on the circle is inside of the rectangle. Similarly, for the vertical edges, the furthest left or furthest right point on the circle must be inside of the rectangle. So, we just check these four points to be in the rectangle. These four points on a circle are obvious : highest : (x, y + r) lowest : (x, y  r) furthest right : (x + r, y) furthest left : (x  r, y) This is one long expression, and we can even pin it on to the last one using an or. But, to keep it neat, you might want to separate them. For example, I separated them in horizontal edge collisions and vertical edge collisions : if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y  r > y1 and y  r < y2) then there is an intersection if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x  r > x1 and x  r < x2) then there is an intersection These cases above do not cover all intersections of a circle and a rectangle, though. Can you think of a scenario where none of the four corners of the rectangle are inside of the circle and the highest, lowest, furthest left, or furthest right points of the circle are not inside the rectangle? Imagine a circle and a square with the same center and the square's corners sticking out of the circle. If this is happening, then the center of the circle must be inside of the rectangle, so we can check for that last condition. if x > x1 and x < x2 and y > y1 and y < y2 then the rectangle and circle are intersecting So, we have created four expressions (that can all be combined into one expression using or if we really want to). If any of these expressions are true, then there is an intersection. If none of them are true, then there is no collision between the rectangle and the circle.
Point on Ellipse
The formula for a point (x, y) on an ellipse is : ((e.x  x)/rx)^2 + ((e.y  y)/ry)^2 = 1 where (e.x, e.y) is the center of the ellipse e.rx is the xradius (the distance from the center to the outside of the ellipse along the xaxis) e.ry is the yradius (the distance from the center to the outside of the ellipse along the yaxis) Let's write the expression for determining if a point (x, y) is inside of a circle : (c.x  x)^2 + (c.y  y)^2 <= r^2 this can be rewritten as : ((c.x  x)/r)^2 + ((c.y  y)/r)^2 <= 1 Do you see the similarity to the ellipse equation? It just so happens that for the ellipse, the expression is similar to the circle one except it uses the xradius and yradius : ((e.x  x)/rx)^2 + ((e.y  y)/ry)^2 <= 1 If the above expression evaluates to true, then the point is on or inside the ellipse. Otherwise, the point is outside of the ellipse. Go here to find out about the derivation of the ellipse formula and more information about the ellipse.
Math Review : Finding the point of intersection of two lines
The equation of a line is : y = mx + b OR where m is the slope and b is the yintercept y  y0 = m * (x  x0) where m is the slope and (x0, y0) is a known point on the line Suppose we are given two points on two different lines and we want to find the point of intersection of these two lines (x1, y1) and (x2, y2) are on the first line (x3, y3) and (x4, y4) are on the second line then, we have to first find the slopes of both lines so we can write the equation of each line : m1 = (y2  y1) / (x2  x1) slope of the first line m2 = (y4  y3) / (x4  x3) slope of the second line Now, we write the equations of both lines : y  y1 = m1 * (x  x1) y  y3 = m2 * (x  x3) To solve for the point of intersection, we solve for x and y in this system of equations. y = m1*x  m1*x1 + y1 y = m2*x  m1*x3 + y3 m1*x  m1*x1 + y1 = m2*x  m2*x3 + y3 m1*x  m2*x = m2*x3 + y3 + m1*x1  y1 (m1  m2) * x = m2*x3 + y3 + m1*x1  y1 x = (m2*x3 + y3 + m1*x1  y1) / (m1  m2) y = m1*(x  x1) + y1 <we substitute x which we computed above into this equation to get y And (x, y) will be the point of intersection. Line Segment vs. Line Segment
Lines extend infinitely (have an infinite length), while line segments have two endpoints and a finite length. When dealing with graphics, line segments are usually more relevant. Any two nonparallel lines are intersecting, but this can not be said for line segments. Suppose the first line segment has endpoints (x1, y1) and (x2, y2). Suppose the second line segment has endpoints (x3, y3) and (x4, y4). To determine whether or not two line segments are intersecting, we first treat them as lines. We find the slope of each line and calculate the intersection point. m1 = (y2  y1) / (x2  x1) m2 = (y4  y3) / (x4  x3) intX = (m2 * x3 + y3 + m1 * x1  y1) / (m1  m2) intY = (m1 * (intX  x1) + y1) Now we have the intersection point (intX, intY) of the two lines, but remember, we have line segments. So, we check if this point of intersection is on BOTH line segments. If it is, then the line segments are intersecting. If it's not on one or both of the line segments, then there is no intersection. To check if this point is on the line segment, we just check if its xcoordinates are between the x coordinates of the endpoints of the first and second line. We do the same with its y coordinate. After some logic, it can be shortened to : intX >= max (min (x1, x2), min (x3, x4)) and intX <= min (max (x1, x2), max (x3, x4)) and intY >= max (min (y1, y2), min (y3, y4)) and intY <= min (max (y1, y2), max (y3, y4)) if the above expression is true, then the line segments are intersecting.
Line Segment vs. Circle
We know by know that if the distance from the line to the center of the circle is less than the radius of the circle, then the line segment must be intersecting with the circle. But, we can do even better, the closest point on this line segment to the center of the circle must be inside the circle for an intersection to occur. So now the problem becomes finding the point on the line segment that is the closest to the center of the circle. Let : (x, y) be the center of the circle r be the radius of the circle (x1, y1) and (x2, y2) be the endpoints of the line segment Now, first let's treat the line segment as a line and find the point on the line closest to the center of the circle. We'll call the line (l). For this, we assume the geometric property that the shortest path from a point to a line is the path perpendicular to the line. Assuming this, we now have a second line and we know its slope will be perpendicular to the original line (l) and it will go through the center of the circle. We find the intersection point of the original line (l) and the new perpendicular line. m = (y2  y1) / (x2  x1) M = 1 / m X = (m * x1  y1  M * x + y) / (m  M) Y = m * (X  x1) + y1 where m is the slope of the original line (l) M is the slope of the new perpendicular line (X, Y) is the point of intersection between the two lines Now we have the point on the line that is the shortest distance away from the center of the circle. But wait, we have a line segment to start with, so we have to check if this point of intersection is actually even on our line segment. if X >= min (x1, x2) and X <= max (x1, x2) and Y >= min (y1, y2) and Y <= max (y1, y2) then the point of intersection is on the line segment. Now, we check if this point is inside the circle using circular collision. (px  X) ** 2 + (py  Y) ** 2 <= r ** 2 If that expression is true then the closest point on the line segment is inside of the circle and there is an intersection between the line segment and the circle. But what if the point of intersection was not on our line segment (the first if statement evaluated to false)? Then we conclude that the closest point on the line segment to the center of the circle must be one of the endpoints (whichever one is closer). Since our general circular collision compares if the distance squared is less than or equal to the radius squared, we can check which distance from endpoint to center squared is less and then see if it less than or equal to the radius squared. min ((px  x1) ** 2 + (py  y1) ** 2, (px  x2) ** 2 + (py  y2) ** 2) <= r ** 2 If the above expression evaluates to true, then you have an intersection between the circle and the line segment. If it evaluates to false, then there is no intersection. Bringing our two conditions together, we get pseudocode like this : if X >= min (x1, x2) and X <= max (x1, x2) and Y >= min (y1, y2) and Y <= max (y1, y2) then result (x  X) ** 2 + (y  Y) ** 2 <= r ** 2 else result min ((x  x1) ** 2 + (y  y1) ** 2, (x  x2) ** 2 + (y  y2) ** 2) <= r ** 2
Similar Ellipse vs Similar Ellipse
Well, if you use the circle again, let's write the expression that determines whether or not two circles are intersecting : (c1.x  c2.x)^2 + (c1.y  c2.y)^2 <= (c1.r + c2.r)^2 OR (c1.x  c2.x)^2 / (c1.r + c2.r)^2 + (c1.y  c2.y)/r)^2 / (c1.r + c2.r)^2 <= 1 Well, if we plug in the sum of the ellipses' xradii for the first r and the sum of the ellipses' yradii for the second r, then we have : (e1.x  e2.x) ** 2 / (e1.rx + e2.rx) ** 2 + (e1.y  e2.y) ** 2 / (e1.ry + e2.ry) ** 2 <= 1 Unfortunately, that does not work for all ellipses. It only works for what I call similar ellipses (probably not the right mathematical term!). When I say the ellipses are similar, I mean that their x and y radii are proportional. So, e1.rx / e1.ry = e2.rx / e2.ry For example, if an ellipse has an xradius of 25 and a yradius of 40, then a similar ellipse might have an xradius of 50 and a yradius of 80. I have yet to attempt to geometrically prove this, but the reason has something to do with the point of intersection of similar ellipses always being on the vector joining the two centers of the ellipses. So, if the expression we declared above is true, then the similar ellipses intersect. If that expression is false, then there is no collision.
Math Lesson : Determining which side of a vector a point is on (left or right?)
If you have a vector in 2 dimensions v with a tip of (x1, y1) and a tail of (x2, y2) and a point p (x, y), and you want to determine if the point is to the left or to the right of the vector, you use a cross product. First, we construct two new vectors. One will go from the point p to the tail (start) of the vector, and the other will go from the point p to the tip (end) of the vector. The first vector (tail to point) : (x  x1, y  y1, 0) The second vector (tip to point) : (x  x2, y  y2, 0) Note that the z component of the vectors will be 0 because we're dealing in 2 dimensions. Now, if the point p is to the right of the original vector v, then the cross product of our two constructed vectors will be pointing out of the screen (if you know the righthand rule, you can confirm this). If the point p is to the left, the cross product will be going into the screen. Well, if the cross product is coming out of the screen, then the zcomponent will be negative; and if the cross product is going into the screen then the zcomponent will be positive. (Note, if the point is right on the line, then the two constructed vectors' cross product would obviously be 0.) So, we just have to check the sign of the zcomponent of the cross product. The zcomponent of the cross product can be computed like this : (y  y1) * (x2  x1)  (x  x1) * (y2  y1) So, if the sign of the above calculation is negative, then the point is to the right of the vector. If the sign is positive, then the point is to the left of the vector. If the above calculation is 0, then the point is on the vector. Point in Convex Polygon
Let's say the array that represents the convex polygon's x coordinates is px and the array that represents the convex polygon's y coordinates is py. Let's call our point we are testing p (x, y). In order to use the Draw.Polygon procedure, you must have your coordinates in your arrays in order. Well, since we're dealing with a convex polygon, the points must go in a clockwise or counterclockwise direction. Now, imagine each edge of the polygon as a vector so that the polygon creates either a clockwise or counterclockwise path. If your path is clockwise, then all points inside of the polygon are to the right of each edge vector. If your path is counterclockwise, then all points inside the polygon are to the left of each edge vector. All points outside of the polygon are to the left of some edge vectors and to the right of others regardless if the path is clockwise or counterclockwise. Now, all we do is check if our point p is to the right of all the edges of the polygon or to the left of all the edges of our polygon using the method learned in the above section. for each edge of the polygon zcom = (y  y1) * (x2  x1)  (x  x1) * (y2  y1) where (x1, y1) is the start point (tail) of the edge vector and (x2, y2) is the ending point (tip) of the edge vector. We check if all the zcomponents are the same sign (or 0; if we include a point on the polygon as inside). If all of the zcomponents are the same sign then the point is inside of the polygon. If at least one of them is not the same sign, then the point is outside of the convex polygon.
Math Lesson : Projecting a point onto a line going through the origin
If we want to project a point p (x, y) onto a line going through (0, 0) called v(vX, vY), we can use this formula : proj.x = [(x * vx + y * vy) / (vx **2 + vy ** 2)] * vx proj.y = [(x * vx + y * vy) / (vx **2 + vy ** 2)] * vy Note that what's in the square brackets is the same for both proj.x and proj.y, and can be said as the dot product of the position vector of the point p with the vector v, divided by v dot v. Convex Polygon vs. Convex Polygon
If two polygons are not intersecting, there is always a line (with infinite length) that can be drawn between them. In fact, a line can be drawn between the polygons will actually be parallel to one edge of one of the polygons. If they are intersecting, then no such line can be drawn. So, how do we test if a line parallel to one of the 2 polygons' edges will be able to separate the polygons? Well, let's start with the first edge of the first polygon. We take a line perpendicular to this and, for simplicity, let's have this line going through (0, 0). This line will act as an axis. If we project both polygons onto this axis and the projections of the polygons are not overlapping, then the first edge of the first polygon has a line parallel to it that can separate the polygons. Simply put, there is no intersection between the polygons. We do this for every edge of both polygons. The instant that the projections of both polygons onto a perpendicular axis are not overlapping, then we know we have no collision between the two convex polygons. If the projections overlap on every perpendicular to every edge of both polygons, then there is an intersection between the polygons. We have one more problem which you may or may have not figured out. What is meant by projecting a polygon onto a line (axis)? By this, I just mean project every point of the polygon onto the axis and join them with a line. So, in psuedocode : for each edge of the polygon find perpendicular axis going through (0, 0) project polygon 1 onto this axis project polygon 2 onto this axis check if the two projection lines are overlapping

Author:  richcash [ Fri Mar 16, 2007 9:53 pm ] 
Post subject:  Re: Collision Detection 
I would like to apologize to anyone who has been waiting for this tutorial. I was supposed to do it in January and forgot all about it! I've been working on the second part of my collision detection tutorial for about a week now. I think I've gotten quite far with it. I have a tendancy to overexplain things, so in this tutorial I tried to keep it straight to the point. This is a work in progress. I plan on fixing up the format, adding 2 or 3 more sections, and I might still edit the polygon stuff if anyone doesn't get what I'm saying. I'm also still debating over whether or not to keep some of the math stuff in separate sections. I also forgot to provide a link to zylum's very excellent tutorial on timebased collision. Any comments or suggestions for impovements are appreciated. If anyone wants anything else included, I'll see if I can do it. 
Author:  Clayton [ Fri Mar 16, 2007 11:37 pm ] 
Post subject:  Re: Collision Detection 
This is excellent! Until I get a look at it, I'll start off with a good +100 bits. Suggestions to come. =) 
Author:  zylum [ Fri Mar 16, 2007 11:40 pm ] 
Post subject:  RE:Collision Detection 
wow that looks like a lot of work. and it looks like you covered a lot of topics. so far i have read from the bottom (convex polygon) up to similar elipses and it looks pretty solid so far! +Karma and 300 bits for the hard work if you manage to get elipse vs elipse to work for any arbitrary elipses i will add an additional 500 bits 
Author:  richcash [ Sat Mar 17, 2007 2:29 am ] 
Post subject:  Re: Collision Detection 
Whoa, thanks to both of you for the bits+karma!! zylum wrote: if you manage to get elipse vs elipse to work for any arbitrary elipses
hmm... I shall try my best to get a solution. Hopefully it won't mean computing the discriminant of some quartic every frame (which would be far too costly). Edit : My tutorial wrote: (c.x  x)^2 + (c.y  y)^2 <= r^2 OR
((c.x  x)/r)^2 + ((c.y  y)/r)^2 <= 1 The above is in the Similar Ellipse vs. Similar Ellipse section as the collision detection expression for two circles. This should obviously be : (c1.x  c2.x)^2 + (c1.y  c2.y)^2 <= (c1.r + c2.r)^2 OR (c1.x  c2.x)^2 / (c1.r + c2.r)^2 + (c1.y  c2.y)/r)^2 / (c1.r + c2.r)^2 <= 1 where c1 and c2 are two circles each with : (x, y) as the center r as the radius Freakman Edit: I've added that in there for you, any other changes, just post here and I'll add them in. Unfortunately, I can't edit my above post. 
Author:  richcash [ Thu Mar 22, 2007 4:14 pm ]  
Post subject:  Re: Collision Detection  
I think I have finally found a solution to zylum's challenge!! My function works for any 2 ellipses that can be drawn uses Turing's Draw.Oval command (have their major and minor axes on the x and y axes and can be defined using rx and ry). ((xx1)/a)^2 + ((yy1)/b)^2 = 1 ((xx2)/c)^2 + ((yy2)/d)^2 = 1 The intersection of two ellipses results in a quartic with 4 roots (2 real, 2 complex; 4 real; or 4 complex). So, someone plugged in the above two equations and found that quartic for me using Maple (algebra software). Here is the resulting ugly quartic : Quote: (c^4*b^4+a^4*d^42*c^2*b^2*a^2*d^2)*x^4
+(4*c^2*b^2* a^2*d^2*x2+4*c^2*b^2*x1*a^2*d^24*a^4*d^4*x24*c^4*b^4*x1)*x^3 +(6*a^4*d^ 4*x2^22*c^2*b^2*a^2*d^2*x2^2+2*c^2*a^4*d^2*y2^22*c^4*b^4*a^2+2*c^4*b^2 *a^2*y1^24*c^4*y2*a^2*y1*b^2+2*c^4*b^2*a^2*d^2+6*c^4*b^4*x1^2+2*c^2*a^4 *y1^2*d^22*c^2*b^2*x1^2*a^2*d^2+2*c^2*a^4*d^2*b^24*c^2*y2*a^4*y1*d^22 *c^2*a^4*d^4+2*c^4*b^2*a^2*y2^28*c^2*b^2*x1*a^2*d^2*x2)*x^2 +(4*c^4*b^2 *x1*a^2*d^2+4*c^4*b^4*x1*a^2+4*c^2*b^2*x1*a^2*d^2*x2^2+8*c^4*y2*a^2*y1*b ^2*x14*c^2*a^4*d^2*x2*y2^24*c^2*a^4*d^2*x2*y1^24*a^4*d^4*x2^34*c^4*b ^2*x1*a^2*y1^2+4*c^2*b^2*x1^2*a^2*d^2*x24*c^4*b^4*x1^34*c^4*b^2*x1*a^2 *y2^2+4*c^2*a^4*d^4*x2+8*c^2*y2*a^4*y1*d^2*x24*c^2*a^4*d^2*x2*b^2)*x +a^4*c^4*y2^4+a^4*d^4*x2^4+a^4*c^4*d^4+c^4*b^4*x1^4+c^4*a^4*y1^4+c^4*a^4 *b^42*c^4*b^4*x1^2*a^22*c^4*a^4*y1^2*b^22*c^4*a^4*y1^2*d^2+6*c^4*a^4* y1^2*y2^22*c^4*a^4*b^2*d^22*c^4*a^4*b^2*y2^22*a^4*c^2*d^4*x2^22*a^4* c^4*d^2*y2^24*c^4*y2*a^4*y1^34*c^4*y2^3*a^4*y1+2*c^4*b^2*x1^2*a^2*y1^2 +2*c^4*b^2*x1^2*a^2*d^22*c^2*b^2*x1^2*a^2*d^2*x2^2+2*c^4*b^2*x1^2*a^2*y 2^2+2*c^2*a^4*y1^2*d^2*x2^2+2*c^2*a^4*b^2*d^2*x2^2+2*c^2*a^4*d^2*x2^2*y2 ^24*c^4*y2*a^2*y1*b^2*x1^2+4*c^4*y2*a^4*y1*b^2+4*c^4*y2*a^4*y1*d^24*c^ 2*y2*a^4*y1*d^2*x2^2 That is awful, but it's still manageable. I calculated the coeffiecents and the constant at the end of the quartic and then calculated the discriminant. If the discriminant is less than 0, then there are two complex and two real roots. But we still have to find out whether or not when the discriminant is above 0 if the ellipses are intersecting in 4 points or in 0 points. For this you can try to see what I'm doing in my commented code. Basically, if one ellipse has its right and left ends on separate sides of the other ellipse's center, then they are intersecting in 4 points or in none. So you have to move the ellipse to a point where a new discriminant will be less than 0 if the original position of the ellipse had 4 intersection points. I can't explain anymore than that without going into all of the details. Because there are so many calculations going on in the computing of the coefficients, constant, and discriminant, any roundoff errors will be magnified. You'll notice that for really skinny ellipses, the accuracy is completely lost. I might write this in java to verify that it is only because of a roundoff error. To minimize the number of these errors, I use the collision expression for similar ellipse  similar ellipse (because although this function doesn't aways return true when it's supposed to, it will never return true when it's not supposed to. Therefore it can't make the collision detection worse). I'll write a tutorial section on this soon, but until then here's my code. Enjoy!

Author:  Clayton [ Thu Mar 22, 2007 4:31 pm ] 
Post subject:  Re: Collision Detection 
Wow! This is amazing, this amount of effort deserves some more bits! +400 bits sounds good for now 
Author:  richcash [ Thu Mar 22, 2007 9:28 pm ] 
Post subject:  Re: Collision Detection 
Thanks Freakman Well, it's not as amazing as I thought it would be before I made it. It's actually quite a bit slower than checking a point at every angle on one ellipse to be inside of the second ellipse. However, when it comes to ellipses that are almost as big as the screen and bigger, that method becomes inaccurate. Or, if you start checking a point at every 0.1 degrees or 0.01 degrees to increase the precision, then that method becomes much slower than mine. Mine can also be used in conjuction with timebased collision, if you want to do some crazy math. There still might be a really effiecient way to do it using geometric proprties (like I did with similar ellipses), but I can't think of one. More sections to come. 
Author:  Skynet [ Thu Mar 22, 2007 10:11 pm ] 
Post subject:  Re: Collision Detection 
Options I can think of: Approximate the ellipses with polygons Split your plane up into discrete parts (maybe integers mapped to screen pixels) and see if a coordinate is hit twice (Use Bresenham's line algorithm to fill the interior once you have the values of the points on the perimeter...it's really fast) Similar to the last, approximate perimeter of ellipses on a integer/fixed precision plane, then flood fill from the center of each ellipse. Compare result to the sum of the area of both ellipses. I may be talking out of my ass, but these ideas seem to make sense. Of course, they're all approximations. I believe you're 100% correct in saying that the equations Maple spit out run the risk of incurring huge truncation errors, and I'd hazard a guess that approximating an ellipse in integer or fixedpoint precision would produce better results. (Unless you're using something like Maple, which is powered by black magic) 
Author:  richcash [ Fri Mar 23, 2007 12:22 pm ] 
Post subject:  Re: Collision Detection 
Skynet wrote: Options I can think of:
Approximate the ellipses with polygons Split your plane up into discrete parts (maybe integers mapped to screen pixels) and see if a coordinate is hit twice (Use Bresenham's line algorithm to fill the interior once you have the values of the points on the perimeter...it's really fast) Similar to the last, approximate perimeter of ellipses on a integer/fixed precision plane, then flood fill from the center of each ellipse. Compare result to the sum of the area of both ellipses. ... but these ideas seem to make sense. Of course, they're all approximations. What you're saying does make sense, and it would be smarter to use an approximation for ellipses that are realistic sizes (can fit on the screen). Your methods are similar in performance to checking several points on one ellipse to be inside of the other ellipse (you can do this by plugging in theta at, say, every degree into the parametric equations of one ellipse). I call these collision detection by induction (I like naming things!). Like I said before, the rounding errors occur when the ellipses are too skinny (say that one ellipse's major axis is 20 times larger than its minor axis) or if the ellipses are too small (have radii under 10). But for huge ellipses, my function thrives. I tried out my function on two ellipses : one was 3000(xradius) X 800(yradius) and the other was 2000 X 500. It detected the collision perfectly with no loss of speed. Any above methods would become much worse than my function with these ellipses and larger. It's possible that there is an effiecient function out there using geometric properties, but I can't think of one and a quick internet search resulted in nothing. So I say just use my long function only for massive ellipses. 
Author:  Flipmc [ Fri Jan 30, 2009 6:30 pm ] 
Post subject:  RE:Collision Detection 
Wow! Thanks for this! I'll need it sooner or later. 
Author:  DanielG [ Fri Jan 30, 2009 7:16 pm ] 
Post subject:  RE:Collision Detection 
massive necro, good tutorial though. 
: 