Collision Detection
Author 
Message 
Andy

Posted: Thu Oct 19, 2006 2:59 am Post subject: (No 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 





Sponsor Sponsor



Cervantes

Posted: Thu Oct 19, 2006 9:00 am Post subject: (No 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. 





blaster009

Posted: Sat Oct 28, 2006 6:44 pm Post subject: (No 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! 





[Gandalf]

Posted: Sat Oct 28, 2006 6:52 pm Post subject: (No 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. 





Cervantes

Posted: Sat Oct 28, 2006 10:51 pm Post subject: (No 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. 





[Gandalf]

Posted: Sat Oct 28, 2006 11:09 pm Post subject: (No 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. 





Andy

Posted: Sun Oct 29, 2006 4:55 am Post subject: (No 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? 





vertozia

Posted: Fri Dec 29, 2006 12:06 am Post subject: (No 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? 





Sponsor Sponsor



Cervantes

Posted: Fri Dec 29, 2006 5:27 pm Post subject: (No subject) 


Did you read the whatdotcolour tutorial? That would be a good place to start. 





richcash

Posted: 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 :
if and for loop constructs
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.
code:  View.Set ("offscreenonly")
var x1, y1, x2, y2, x, y, b, r : int
x1 := 100
y1 := 100
x2 := 200
y2 := 200
r := 60
fcn circleRectangle (x, y, r, x1, y1, x2, y2 : real) : boolean
if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y  r > y1 and y  r < y2) then
result true
end if
if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x  r > x1 and x  r < x2) then
result true
end if
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
result true
end if
result x > x1 and x < x2 and y > y1 and y < y2
end circleRectangle
loop
Mouse.Where (x, y, b)
Draw.Box (x1, y1, x2, y2, black)
Draw.Oval (x, y, r, r, blue)
put circleRectangle (x, y, r, x1, y1, x2, y2)
View.Update
delay (10)
cls
end loop 
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.
code:  View.Set ("offscreenonly")
type ellipse :
record
x, y, rx, ry : real
clr : int
end record
var e : ellipse
var x, y, button : int
e.x := 100
e.y := 100
e.rx := 85
e.ry := 32
e.clr := green
fcn pointEllipse (e : ellipse, x, y : real) : boolean
result ((e.x  x) / e.rx) ** 2 + ((e.y  y) / e.ry) ** 2 <= 1
end pointEllipse
loop
Mouse.Where (x, y, button)
Draw.Oval (round (e.x), round (e.y), round (e.rx), round (e.ry), e.clr)
put pointEllipse (e, x, y)
View.Update
delay (10)
cls
end loop 
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.
code:  View.Set ("offscreenonly")
var x1, y1, x2, y2, x3, y3, x4, y4, angle : real
var x, y, button : int
angle := 90
x1 := 100
y1 := 100
x2 := 200
y2 := 200
fcn lineLine (x1, y1, x2, y2, x3, y3, x4, y4 : real) : boolean
var m1 := (y2  y1) / (x2  x1 + 1e5)
var m2 := (y4  y3) / (x4  x3 + 1e5)
var intX := round ((m2 * x3 + y3 + m1 * x1  y1) / (m1  m2))
var intY := round ((m1 * (intX  x1) + y1))
result 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))
end lineLine
loop
Mouse.Where (x, y, button)
x3 := x
y3 := y
if button = 1 then
angle += 1
end if
x4 := x + 70 * cosd (angle)
y4 := y + 70 * sind (angle)
Draw.Line (round (x1), round (y1), round (x2), round (y2), blue)
Draw.Line (round (x3), round (y3), round (x4), round (y4), red)
put lineLine (x1, y1, x2, y2, x3, y3, x4, y4)
View.Update
delay (10)
cls
end loop 
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
code:  View.Set ("offscreenonly")
var x, y, button, x1, y1, x2, y2, r : int
x1 := 100
y1 := 100
x2 := 100
y2 := 200
r := 25
fcn circleLine (px, py, r, x1, y1, x2, y2 : real) : boolean
var m := (y2  y1) / (x2  x1 + 1e8)
var M := 1 / m
var X := (m * x1  y1  M * px + py) / (m  M)
var Y := m * (X  x1) + y1
if round (X) >= min (x1, x2) and round (X) <= max (x1, x2)
and round (Y) >= min (y1, y2) and round (Y) <= max (y1, y2) then
result (px  X) ** 2 + (py  Y) ** 2 <= r ** 2
else
result min ((px  x1) ** 2 + (py  y1) ** 2, (px  x2) ** 2 + (py  y2) ** 2) <= r ** 2
end if
end circleLine
loop
Mouse.Where (x, y, button)
put circleLine (x, y, r, x1, y1, x2, y2)
Draw.Line (x1, y1, x2, y2, black)
Draw.Oval (x, y, r, r, blue)
View.Update
delay (30)
cls
end loop 
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.
code:  View.Set ("offscreenonly")
type ellipse :
record
x, y, rx, ry, clr : int
end record
var e1, e2 : ellipse
var x, y, b : int
e1.x := 100
e1.y := 100
e1.rx := 90
e1.ry := 50
e1.clr := red
e2.rx := 45
e2.ry := 25
e2.clr := blue
fcn ellipseEllipse (e1, e2 : ellipse) : boolean
result ((e2.x  e1.x) / (e1.rx + e2.rx)) ** 2 + ((e2.y  e1.y) / (e1.ry + e2.ry)) ** 2 <= 1
end ellipseEllipse
loop
Mouse.Where (x, y, b)
e2.x := x
e2.y := y
Draw.Oval (e1.x, e1.y, e1.rx, e1.ry, e1.clr)
Draw.Oval (e2.x, e2.y, e2.rx, e2.ry, e2.clr)
put ellipseEllipse (e1, e2)
View.Update
delay (15)
cls
end loop 
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.
code:  View.Set ("offscreenonly")
var px : array 1 .. 8 of int := init (100, 80, 80, 100, 120, 140, 140, 120)
var py : array 1 .. 8 of int := init (100, 120, 140, 160, 160, 140, 120, 100)
var x, y, button : int
fcn pointPolygon (px, py : array 1 .. * of int, x, y : real) : boolean
var n := upper (px)
var z : array 1 .. n of real
for i : 1 .. n  1
z (i) := (y  py (i)) * (px (i + 1)  px (i))  (x  px (i)) * (py (i + 1)  py (i))
end for
z (n) := (y  py (n)) * (px (1)  px (n))  (x  px (n)) * (py (1)  py (n))
for i : 2 .. n
if sign (z (i)) not= sign (z (1)) and sign (z (i)) not= 0 then
result false
end if
end for
result true
end pointPolygon
loop
Mouse.Where (x, y, button)
Draw.Polygon (px, py, 8, blue)
put pointPolygon (px, py, x, y)
View.Update
delay (10)
cls
end loop 
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
code:  View.Set ("offscreenonly")
var x1 : array 1 .. 6 of int := init (100, 70, 100, 130, 160, 130)
var y1 : array 1 .. 6 of int := init (100, 130, 160, 160, 130, 100)
var a : array 1 .. 8 of int := init (0, 30, 30, 0, 30, 60, 60, 30)
var b : array 1 .. 8 of int := init (0, 30, 60, 90, 90, 60, 30, 0)
var x2, y2 : array 1 .. upper (a) of int
var x, y, button : int
fcn Min (arr : array 1 .. *, 1 .. * of real, n : int) : real
var minimum := arr (n, 1)
for i : 2 .. upper (arr, 2)
if arr (n, i) < minimum then
minimum := arr (n, i)
end if
end for
result minimum
end Min
fcn Max (arr : array 1 .. *, 1 .. * of real, n : int) : real
var maximum := arr (n, 1)
for i : 2 .. upper (arr, 2)
if arr (n, i) > maximum then
maximum := arr (n, i)
end if
end for
result maximum
end Max
fcn polygonPolygon (x1, y1, x2, y2 : array 1 .. * of int) : boolean
var X11 : array 1 .. upper (x1), 1 .. upper (x1) of real
var X12 : array 1 .. upper (x1), 1 .. upper (x2) of real
var X21 : array 1 .. upper (x2), 1 .. upper (x1) of real
var X22 : array 1 .. upper (x2), 1 .. upper (x2) of real
for i : 1 .. upper (x1)
var nx1, ny1 : real
if i = upper (x1) then
nx1 := 1 / (x1 (1)  x1 (upper (x1)) + 1e8)
ny1 := 1 / (y1 (1)  y1 (upper (y1)) + 1e8)
else
nx1 := 1 / (x1 (i + 1)  x1 (i) + 1e8)
ny1 := 1 / (y1 (i + 1)  y1 (i) + 1e8)
end if
for j : 1 .. upper (x1)
X11 (i, j) := ((x1 (j) * nx1 + y1 (j) * ny1) / (nx1 ** 2 + ny1 ** 2)) * nx1
end for
for j : 1 .. upper (x2)
X12 (i, j) := ((x2 (j) * nx1 + y2 (j) * ny1) / (nx1 ** 2 + ny1 ** 2)) * nx1
end for
end for
for i : 1 .. upper (x1)
if Max (X11, i) < Min (X12, i) or Max (X12, i) < Min (X11, i) then
result false
end if
end for
for i : 1 .. upper (x2)
var nx, ny : real
if i = upper (x2) then
nx := 1 / (x2 (1)  x2 (upper (x2)) + 1e8)
ny := 1 / (y2 (1)  y2 (upper (y2)) + 1e8)
else
nx := 1 / (x2 (i + 1)  x2 (i) + 1e8)
ny := 1 / (y2 (i + 1)  y2 (i) + 1e8)
end if
for j : 1 .. upper (x1)
X21 (i, j) := ((x1 (j) * nx + y1 (j) * ny) / (nx ** 2 + ny ** 2)) * nx
end for
for j : 1 .. upper (x2)
X22 (i, j) := ((x2 (j) * nx + y2 (j) * ny) / (nx ** 2 + ny ** 2)) * nx
end for
end for
for i : 1 .. upper (x2)
if Max (X21, i) <= Min (X22, i) or Max (X22, i) <= Min (X21, i) then
result false
end if
end for
result true
end polygonPolygon
loop
Mouse.Where (x, y, button)
for i : 1 .. upper (a)
x2 (i) := a (i) + x
y2 (i) := b (i) + y
end for
Draw.Polygon (x1, y1, upper (x1), red)
Draw.Polygon (x2, y2, upper (x2), blue)
put polygonPolygon (x1, y1, x2, y2)
View.Update
delay (10)
cls
end loop







richcash

Posted: 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. 





Clayton

Posted: 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. =) 





zylum

Posted: 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 





richcash

Posted: 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. 





richcash

Posted: 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!
Turing:  View.Set ("offscreenonly")
var x1, y1, rx1, ry1, x2, y2, rx2, ry2, x, y, button : int
x1 := 100
y1 := 100
rx1 := 50
ry1 := 180
rx2 := 200
ry2 := 40
%(X1, Y1) and (X2, Y2) are centers of ellipses
%a and c are xradii of each ellipse; b and d are yradii of each ellipse
fcn ellipseEllipse (X1, Y1, a, b, X2, Y2, c, d : real) : boolean
var x1, y1, x2, y2 : real
x1 := X1
x2 := X2
y1 := Y1
y2 := Y2
for i : 1 .. 2
%rectangular collision among the ellipses' rectangles first
if x1 + a < x2  c or x1  a > x2 + c or y1 + b < y2  d or y1  b > y2 + d then
result false
end if
%if the original discriminant failed, check if it was because there 4 real intersection
%points among the two ellipses by moving one so that it will ensure to have two intersection
%points if it previously had 4, and still have 0 if it previously had 0
if x2  c < x1 and x2 + c > x1 and i = 2 then
x2 := x1 + c
end if
if x1  a < x2 and x1 + a > x2 and i = 2 then
x1 := x2 + a
end if
%the constant at the end of the quartic
var a0 :=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** 4 2*c** 4*b** 4*x1** 2*a** 2 2*c** 4*a** 4*y1** 2*b** 2 2*c** 4*a** 4*y1** 2*d** 2+ 6*c** 4*a** 4*
y1** 2*y2** 2 2*c** 4*a** 4*b** 2*d** 2 2*c** 4*a** 4*b** 2*y2** 2 2*a** 4*c** 2*d** 4*x2** 2 2*a** 4*
c** 4*d** 2*y2** 2 4*c** 4*y2*a** 4*y1** 3 4*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** 2 2*c** 2*b** 2*x1** 2*a** 2*d** 2*x2** 2+ 2*c** 4*b** 2*x1** 2*a** 2*y2
** 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
** 2 4*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** 2 4*c* *
2*y2*a** 4*y1*d** 2*x2** 2
%the coefficient of the x^4 term in the quartic
var a4 := c** 4*b** 4+a** 4*d** 4 2*c** 2*b** 2*a** 2*d** 2
%the coefficient of the x^3 term
var a3 := 4*c** 2*b** 2*
a** 2*d** 2*x2+ 4*c** 2*b** 2*x1*a** 2*d** 2 4*a** 4*d** 4*x2 4*c** 4*b** 4*x1
%the coefficient of the x^2 term
var a2 := 6*a** 4*d* *
4*x2** 2 2*c** 2*b** 2*a** 2*d** 2*x2** 2+ 2*c** 2*a** 4*d** 2*y2** 2 2*c** 4*b** 4*a** 2+ 2*c** 4*b** 2
*a** 2*y1** 2 4*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** 2 2*c** 2*b** 2*x1** 2*a** 2*d** 2+ 2*c** 2*a** 4*d** 2*b** 2 4*c** 2*y2*a** 4*y1*d** 2 2
*c** 2*a** 4*d** 4+ 2*c** 4*b** 2*a** 2*y2** 2 8*c** 2*b** 2*x1*a** 2*d** 2*x2
%the coefficient of the x term
var a1 :=  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*x1 4*c** 2*a** 4*d** 2*x2*y2** 2 4*c** 2*a** 4*d** 2*x2*y1** 2 4*a** 4*d** 4*x2** 3 4*c** 4*b
** 2*x1*a** 2*y1** 2+ 4*c** 2*b** 2*x1** 2*a** 2*d** 2*x2 4*c** 4*b** 4*x1** 3 4*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*x2 4*c** 2*a** 4*d** 2*x2*b** 2
%the discriminant of the quartic; will be negative if there are exactly two roots
var D := ((a1*a2*a3 )** 2  4* (a1*a3 )** 3  4*a1** 2*a2** 3*a4 + 18*a1** 3*a2*a3*a4  27*a1** 4*a4** 2 + 256* (a0*a4 )** 3) +
a0* ( 4*a2** 3*a3** 2 + 18*a1*a2*a3** 3 + 16*a2** 4*a4  80*a1*a2** 2*a3*a4  6*a1** 2*a3** 2*a4 + 144 * a1** 2 * a2 * a4** 2) +
a0** 2* ( 27*a3** 4 + 144*a2*a3** 2*a4  128* (a2*a4 )** 2  192*a1*a3*a4** 2)
%check if the discriminant is less than 0
%also check for trivial intersections that the discriminant may not pick up
%due to rounding errors using the similar ellipse  similar ellipse expression
if D < 0 or ((x2  x1 ) / (a + c )) ** 2 + ((y2  y1 ) / (b + d )) ** 2 <= 1 then
result true
elsif i = 2 then
result D < 0 or ((x2  x1 ) / (a + c )) ** 2 + ((y2  y1 ) / (b + d )) ** 2 <= 1
end if
end for
end ellipseEllipse
loop
Mouse.Where (x, y, button )
x2 := x
y2 := y
Draw.Oval (x1, y1, rx1, ry1, blue)
Draw.Oval (x2, y2, rx2, ry2, red)
put ellipseEllipse (x1, y1, rx1, ry1, x2, y2, rx2, ry2 )
View.Update
delay (20)
cls
end loop 







