Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 [Module] Collision
Index -> Programming, Turing -> Turing Tutorials
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Aange10




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

Download
 Filename:  Collision.rar
 Filesize:  2.35 KB
 Downloaded:  361 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
Raknarg




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




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




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




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

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




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




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




PostPosted: 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
Sponsor
Sponsor
Sponsor
sponsor
Aange10




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




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




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




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




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


Critiques, please?


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



Collision.rar
 Description:

Download
 Filename:  Collision.rar
 Filesize:  2.63 KB
 Downloaded:  297 Time(s)

Zren




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




PostPosted: 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:   
   Index -> Programming, Turing -> Turing Tutorials
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: