Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
[Module] Collision
Author Message
Aange10

Posted: Mon Jan 16, 2012 12:54 am   Post subject: [Module] Collision

Features

This module does collision, so you don't have to! It takes all the stress out of collision, by allowing you to simply input the co-ordinates, and that's it. *Relatively no math involved.
Specifically, checking rectangular collisions becomes easier because this module checks 14 points, increasing accuracy, and keeping you from running needless perimeterfors. *Shutters*

How it Works

Here's a simple breakdown:

CircleToCircle : The module finds the distance between the centers of the two circles and compares it the the sum of the radii.
RectangeToRectangle : The module distinguishes a plane for the Rectangle, and detects 14 key points and looks for plane interception.
RectangleToCircle : The module fabricates a box to represent the Circle, and detects its 14 points along with the Rectangles.

Syntax

The syntax is super simple. [See The Turing Walkthrough for importing modules]

After importing the module you can call it by these parameters:

 Turing: Collision.circleToCircle (Ball_1_x, Ball_1_y, Ball_1_xr, Ball_1_yr, Ball_2_x, Ball_2_y, Ball_2_xr, Ball_2_yr) Collision.rectangleToRectangle (Rect_1_x1, Rect_1_y1, Rect_1_x2, Rect_1_y2, Rect_2_x1, Rect_2_y1, Rect_2_x2, Rect_2_y2) Collision.rectangleToCircle (Rect_x1, Rect_y1, Rect_x2, Rect_y2, Ball_x, Ball_y, Ball_xr, Ball_yr)

The syntax is very self explanatory, and all of the functions output a Boolean that indicates collision.

The parameters are also all integers.

Instructions

1) Import Collision.tu
2) Call the functions with their appropriate syntaxs.
3) Done!

The Module

Just copy and paste this in a Turing File, and name it "Collision.tu"!
 Turing: unit % David H module Collision     export circleToCircle, rectangleToCircle, rectangleToRectangle         var distance : real         %==========================================================================%     % = == = == = == = == = == = == Circle To Circle == = == = == = == = == = =%     %==========================================================================%     fcn circleToCircle (x1, y1, xr1, yr1, x2, y2, xr2, yr2 : int) : boolean         distance := sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)         if distance <= xr1 + xr2 then             result true         elsif distance <= xr1 + yr2 then             result true         elsif distance <= yr1 + yr2 then             result true         elsif distance <= yr1 + xr2 then             result true         else             result false         end if     end circleToCircle     %============================================================================%     % = == = == = == = = == Rectangle To Rectangle = == = == = == = == = == = == %     %============================================================================%     fcn CheckPointInBox (toCheckX, toCheckY, x1, y1, x2, y2 : int) : boolean         % See if an x,y point is within a plane (x1, y1, x2, y2)         if toCheckX >= x1 then             if toCheckY >= y1 then                 if toCheckX <= x2 then                     if toCheckY <= y2 then                         result true                     else                         result false                     end if                 else                     result false                 end if             else                 result false             end if         else             result false         end if     end CheckPointInBox     %   Rectangle to Rectangle     fcn rectangleToRectangle (x1_1, y1_1, x2_1, y2_1, x1_2, y1_2, x2_2, y2_2 : int) : boolean         var toCheckX : int := x1_1 % Far Left         var toCheckY : int := y1_1 % Bottom         var width : int := x2_1 - x1_1         var height : int := y2_1 - y1_1         % Bottom Left         if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then             result true         else             toCheckX := x2_1     % Far Right             % Bottom right             if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                 result true             else                 % Top Right                 toCheckY := y2_1 % Top                 if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                     result true                 else                     % Top Left                     toCheckX := x1_1 % Left                     if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                         result true                     else                         % Top .25                         toCheckX := round (width * .25) + x1_1 % .25 in                         if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                             result true                         else                             % Top .50                             toCheckX := round (width * .50) + x1_1 % half                             if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                 result true                             else                                 % Top . 75                                 toCheckX := round (width * .75) + x1_1 % 3/4                                 if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                     result true                                 else                                     % Bottom . 75                                     toCheckY := y1_1 % On bottom @ 3/4                                     if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                         result true                                     else                                         % Bottom .25                                         toCheckX := round (width * .25) + x1_1 % .25                                         if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                             result true                                         else                                             % Bottom .50                                             toCheckX := round (width * .50) + x1_1 % Half                                             if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                                 result true                                             else                                                 % Left and .50                                                 toCheckX := x1_1                                                 toCheckY := round (height * .50) + y1_1                                                 if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                                     result true                                                 else                                                     % Right and .50                                                     if CheckPointInBox (toCheckX, toCheckY, x1_2, y1_2, x2_2, y2_2) then                                                         result true                                                     else                                                         result false % Done                                                     end if                                                 end if                                             end if                                         end if                                     end if                                 end if                             end if                         end if                     end if                 end if             end if         end if     end rectangleToRectangle     %============================================================================%     % = == = == = == = = == = == Rectangle To Circle = == = == = == = == = == = =%     %============================================================================%     %   Rectange to Circle     fcn rectangleToCircle (recX1, recY1, recX2, recY2, circleX, circleY, xr, yr : int) : boolean         % Turn the circle into a box         var tx1 : int := round ((circleX - (xr * .8))) %tx1 stands for TempX1         var tx2 : int := round ((circleX + (xr * .8)))         var ty1 : int := round ((circleY - (yr * .8)))         var ty2 : int := round ((circleY + (yr * .8)))         result rectangleToRectangle (recX1, recY1, recX2, recY2, tx1, ty1, tx2, ty2)     end rectangleToCircle end Collision

Working Example

Posted Below!

Collision.rar
Description:
Filename:  Collision.rar
Filesize:  2.35 KB

Raknarg

Posted: Mon Jan 16, 2012 7:09 pm   Post subject: RE:[Module] Collision

Pretty useful. However, to be honest, the rectangle to rectangle seems to be like a lot more work than it should've been.
Aange10

Posted: Mon Jan 16, 2012 7:18 pm   Post subject: RE:[Module] Collision

Why so? A lot of times people settle for checking 4 points (corners), or decide to check the perimeter.

I do see how this could be a bit more, but i built it to reasonably check the entire rectangle, without actually doing so. The 14 strategic points allot a more accuracy than corners, but less time than scanning the perimeter.

However, I also designed it to check for collision at the most common intersections first, and find its result as quickly as possible.
Raknarg

Posted: Mon Jan 16, 2012 7:27 pm   Post subject: RE:[Module] Collision

Actually, now that I think about it, my way would have taken just as much time haha nevermind
Aange10

Posted: Mon Jan 16, 2012 7:31 pm   Post subject: RE:[Module] Collision

Out of curiosity, what would your way have been?
Raknarg

Posted: Mon Jan 16, 2012 7:35 pm   Post subject: RE:[Module] Collision

It would have just been a corner comparison... but I was thinking of my game where I only have to compare 1 corner to 4 corners instead of 4 to 4
mirhagk

Posted: Tue Jan 17, 2012 10:43 am   Post subject: RE:[Module] Collision

If x1 and x2 are ordered so x1 is smaller than x2, then your rectangular collision detection can be a lot shorter and faster.

 Turing: %   Rectangle to Rectangle fcn rectangleToRectangle (x1_1, y1_1, x2_1, y2_1, x1_2, y1_2, x2_2, y2_2 : int) : boolean     if (x2_1 > x1_2) then %right side or 1st is greater than left side of 2nd         if (x1_1 < x2_2) then %left side of 1st is less then right side of 2nd             %if both of these are true then we know that the first rectangle has intersecting the 2nd on the x-axis. just do the same with the y             if (y2_1 > y1_2) then                 if (y1_1 < y2_2) then                 end if             end if         end if     end if end rectangleToRectangle

EDIT: Also your circle to circle accepts 2 radius's for each circle, which suggests that the function calculates the intersection of 2 ovals (which it doesn't). You can shorten that to just accept one radius for each, and then only have the 1 if statement (instead of 4)
Zren

Posted: Tue Jan 17, 2012 11:23 am   Post subject: RE:[Module] Collision

You assume x1 and y1 are smaller than x2 and y2. You should *not* assume this. Your function should determine the smallest first. Otherwise you end up with a negative width.

Also learn about bitwise operators (and, or, ...). Your if chain could be broken down into:

 code: fcn blarg     result a <= b and b <= c and c <= d end blarg

Turing is also doesn't force you to end a statement at the end of the line. So for really long lines, you can do:

 code: fcn blarg     result a <= b         and b <= c         and c <= d end blarg

Aange10

Posted: Tue Jan 17, 2012 7:20 pm   Post subject: RE:[Module] Collision

Quote:
Also learn about bitwise operators (and, or, ...). Your if chain could be broken down into:

I do know about these. However, I was thinking that splitting up the if statements would allow the program to determine a false result faster. However my err is in that I forgot that in an or statement the program will stop computing the rest of the statement if one of the ors become true.

My mistake. I'm going to implement both of your suggestions.
crossley7

Posted: Tue Jan 17, 2012 10:29 pm   Post subject: RE:[Module] Collision

Just wondering why you need to check 14 points for rectangle to rectangle because if they intersect, 1 of the corners will overlap except in the case where 1 is very tall and narrow and the other is shorter and wider and the whole thing overlaps. you just have to check that case so there are really 9 cases. the 8 corners (2 rectangles) inside the other rectangle and the edge case where the centres overlap.

For circle to rectangle, you have to check 9 things again. The radius on corners and then radius overlapping a side and circle completely within rectangle. (Circle larger than rectangle should be covered by all of the first 8)
mirhagk

Posted: Wed Jan 18, 2012 1:09 am   Post subject: RE:[Module] Collision

Is there a reason the algorithm I suggested can't be used? Of course you will also need to make sure the points are ordered correctly (but this is easy to do)
Aange10

Posted: Wed Jan 18, 2012 7:52 am   Post subject: Re: RE:[Module] Collision

mirhagk @ 18/1/2012, 12:09 am wrote:
Is there a reason the algorithm I suggested can't be used? Of course you will also need to make sure the points are ordered correctly (but this is easy to do)

Nope, I'm working on that right now.
Aange10

Posted: Sat Jan 21, 2012 7:58 pm   Post subject: Re: [Module] Collision

Okay, I've implemented the new formulas, circle collision also now works with ovals.

I'm going to attach it, since it's 190 lines.

Collision.rar
Description:
Filename:  Collision.rar
Filesize:  2.63 KB

Zren

Posted: Sun Jan 22, 2012 1:16 am   Post subject: RE:[Module] Collision

Bounding boxes are usually suppose to surround the entire shape. It's usually better to have false positives then not detecting possible collisions (Eg: better to have some places the character can't move to then being half inside a wall).

Also this: http://imgur.com/usygV

There does exist ways to test oval collisions perfectly, but it's rather non-critical. You're better off wondering how to test collisions on regular shapes once those shapes have been rotated.
Aange10

Posted: Sun Jan 22, 2012 10:38 am   Post subject: RE:[Module] Collision

Quote:

Bounding boxes are usually suppose to surround the entire shape. It's usually better to have false positives then not detecting possible collisions (Eg: better to have some places the character can't move to then being half inside a wall).

I've made the boxes all bigger.

I'm going to implement that CircleToRectangle formula, and to insure ovals will still work, I'll use my current formula for ovals, and this new one for circles (when comparing to rectangles)
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: