BASIC

Author Topic: Circle collisions and draw circles  (Read 5772 times)

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« on: 2008-Jan-19 »
Hi all

I have made a circle to circle collision test function (would be nice to have one of these built in *hint* *hint*).  I've also half-inched a nice circle drawing routine and ellipse drawing routine off these forums (I think Minion and Gernot to credit) to show the collisions visually.  Again, would be nice to have a fast and optimised version of these two functions built in (*hint* *hint*) ;)

I would gladly welcome any suggestions for optimising the circoll collision function.

Code: GLBasic [Select]
SETSCREEN 640,480,0
LIMITFPS 60

BLACKSCREEN

GLOBAL x1=320
GLOBAL y1=240
GLOBAL rad1= 100

GLOBAL x2=320
GLOBAL y2=240
GLOBAL rad2= 50


WHILE TRUE
        drawCircle(x1,y1,rad1, RGB(255,255,255))
       
        LOCAL a,b
        MOUSESTATE x2,y2, a,b
       
        drawCircle(x2,y2, rad2, RGB(200,100,100))
       
        IF circoll(x1,y1,rad1, x2,y2,rad2) THEN PRINT "Collision!", 10,10
       
        SHOWSCREEN
WEND



// ------------------------------------------------------------- //
// -=#  CIRCOLL  #=-
// ------------------------------------------------------------- //
FUNCTION circoll: x1,y1,radius1, x2,y2,radius2

        LOCAL dx, dy
       
        IF x1<x2
                dx = x2 - x1
        ELSE
                dx = x1 - x2
        ENDIF
        IF y1<y2
                dy = y2 - y1
        ELSE
                dy = y1 - y2
        ENDIF
       
        LOCAL dist= SQR( (dx*dx) + (dy*dy) )
        IF dist < (radius1+radius2)
                RETURN TRUE
        ELSE
                RETURN FALSE
        ENDIF

ENDFUNCTION


// ------------------------------------------------------------- //
// -=#  ELLPISE  #=-
// ------------------------------------------------------------- //
FUNCTION drawEllipse: x, y, w, h, col
LOCAL dy, xi
    w=w/2
    h=h/2
    x=x+w
    FOR dy = -h TO h
        xi = w/h * SQR(h*h - dy*dy)
        DRAWLINE x-xi, y+dy+h, x+xi, y+dy+h, col
    NEXT
ENDFUNCTION // ELLIPSE


// ------------------------------------------------------------- //
// -=#  CIRC  #=-
// ------------------------------------------------------------- //
FUNCTION drawCircle: x, y, r, c
    // These values are defined LOCAL:
        // x, y, r, c
       
        LOCAL x1=SIN(0)*r
        LOCAL y1=COS(0)*r
        FOR j=1 TO 360
            LOCAL x2=SIN(j)*r
            LOCAL y2=COS(j)*r
            DRAWLINE x+x1,y+y1,x+x2,y+y2,c
            x1=x2
            y1=y2
        NEXT

ENDFUNCTION // CIRC

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« Reply #1 on: 2008-Jan-19 »
Oh, I forgot to ask, as well as any suggestions for optimising this function, anyone know how to detect if two ellipses collide?

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Circle collisions and draw circles
« Reply #2 on: 2008-Jan-19 »
Yes, You need to calculate the angle between the centre of the ellipses (using arctan) - from this, you can calculate the radii at that point, then do the same pythagorean calculation as your circle collision system.
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Offline matchy

  • Prof. Inline
  • *****
  • Posts: 1540
    • View Profile
Circle collisions and draw circles
« Reply #3 on: 2008-Jan-20 »
That's some useful functions there. I sometime just simply calculate the distance from one point to another for circle collisions, but an ellipse collision function would be cool.

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Circle collisions and draw circles
« Reply #4 on: 2008-Jan-20 »
It's on my list of things to code :)
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Circle collisions and draw circles
« Reply #5 on: 2008-Jan-20 »
Okay, here you go, Be aware that while the maths is perfect, the limitations of accuracy within GL do not allow for pixel perfect calculations (sometimes it is several pixels out!) - this is only true of the elliptical calculations (where the trigonometrical functions require the greater accuracy.)  I'll leave it to someone else to code in C (not my forte, I'm afraid!)

Code: GLBasic [Select]
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
//                                                                      //
// Project: Oval Collisions in GL Basic                                 //
//                                                                      //
// (C)opyright PeeJay 2008                    www.peejays-remakes.co.uk //
//                                                                      //
// Rough and ready code for drawing ovals, but, more signifanctly,      //
// code to check for collisions between circles and ovals (ellipses)    //
//                                                                      //
// Important Note: This is NOT accurate - in order to achieve pixel     //
// perfect accuracy, it would be necessary to use a C inline call to    //
// take advantage of the 64 bit precision. This has only been coded to  //
// demonstrate the maths behind it.                                     //
//                                                                      //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//

SETSCREEN 640,480,1
LIMITFPS 60

LOCAL mx,my,b1,b2

WHILE KEY(01)=0

        MOUSESTATE mx,my,b1,b2

        DrawOval(320,240,180,100,200,0,0)
        DrawOval(mx,my,50,80,200,200,0)
       
        IF CollideOval(320,240,180,100,mx,my,50,80)
                PRINT "COLLISION!",280,234
        ENDIF
       
        SHOWSCREEN
       
WEND

END

FUNCTION DrawOval: x,y,rx,ry,cr,cg,cb // x,y are centre, rx,ry are radii

        LOCAL ang
       
        FOR ang=0 TO 360 STEP 0.5
                SETPIXEL x+rx*COS(ang),y+ry*SIN(ang),RGB(cr,cg,cb)
        NEXT
       
ENDFUNCTION

FUNCTION CollideOval: x1,y1,rx1,ry1,x2,y2,rx2,ry2

        LOCAL rad1,rad2,dx,dy,distx,disty,a
       
        IF rx1=ry1                              // circle - fairly accurate
                rad1=rx1
        ELSE
                a=ATAN(y2-y1,x2-x1)     // ellipse - needs 64 bit accuracy
                IF a<0 THEN a=360+a
                dx=rx1*COS(a)
                dy=ry1*SIN(a)
                rad1=SQR((dx*dx)+(dy*dy))
        ENDIF
       
        IF rx2=ry2                              // circle - fairly accurate
                rad2=rx2
        ELSE
                a=ATAN(y1-y2,x1-x2)     // ellipse - needs 64 bit accuracy
                IF a<0 THEN a=360+a
                dx=rx2*COS(a)
                dy=ry2*SIN(a)
                rad2=SQR((dx*dx)+(dy*dy))
        ENDIF
       
        distx=x2-x1
        disty=y2-y1
       
        IF rad1+rad2>=SQR((distx*distx)+(disty*disty))
                RETURN TRUE
        ELSE
                RETURN FALSE
        ENDIF
       
ENDFUNCTION
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« Reply #6 on: 2008-Jan-20 »
Thanks Peejay!!!  That works a treat.  This is my final code, this example I can't see any errors in the collisions - if there are they must be hard to spot.  Cheers mate.

Code: GLBasic [Select]
SETSCREEN 640,480,0
LIMITFPS 60

BLACKSCREEN

GLOBAL x1=320
GLOBAL y1=240
GLOBAL rad1= 20
GLOBAL rad1b = 30

GLOBAL x2=320
GLOBAL y2=240
GLOBAL rad2= 40
GLOBAL rad2b = 30


WHILE TRUE
        //drawCircle(x1,y1,rad1, RGB(255,255,255))
        drawEllipse(x1,y1,rad1, rad1b, RGB(255,255,255))

        LOCAL a,b
        MOUSESTATE x2,y2, a,b

        //drawCircle(x2,y2, rad2, RGB(200,100,100))
        drawEllipse(x2,y2,rad2, rad2b, RGB(255,200,200))

        //IF circoll(x1,y1,rad1, x2,y2,rad2) THEN PRINT "Collision!", 10,10
        IF ovalcoll(x1,y1,rad1, rad1b, x2,y2,rad2,rad2b) THEN PRINT "Collision!", 10,10

        SHOWSCREEN
WEND


// ------------------------------------------------------------- //
// -=#  CIRCOLL  #=-
// ------------------------------------------------------------- //
FUNCTION circoll: x1,y1,radius1, x2,y2,radius2

        LOCAL dx, dy

        IF x1<x2
                dx = x2 - x1
        ELSE
                dx = x1 - x2
        ENDIF
        IF y1<y2
                dy = y2 - y1
        ELSE
                dy = y1 - y2
        ENDIF

        LOCAL dist= SQR( (dx*dx) + (dy*dy) )
        IF dist < (radius1+radius2)
                RETURN TRUE
        ELSE
                RETURN FALSE
        ENDIF

ENDFUNCTION // CIRCOLL


// ------------------------------------------------------------- //
// -=#  OVALCOLL  #=-  By PeeJay
// ------------------------------------------------------------- //
FUNCTION ovalcoll: x1,y1,rx1,ry1,x2,y2,rx2,ry2

    LOCAL rad1,rad2,dx,dy,distx,disty,a
   
    IF rx1=ry1                // circle - fairly accurate
        rad1=rx1
    ELSE
        a=ATAN(y2-y1,x2-x1)    // ellipse - needs 64 bit accuracy
        IF a<0 THEN a=360+a
        dx=rx1*COS(a)
        dy=ry1*SIN(a)
        rad1=SQR((dx*dx)+(dy*dy))
    ENDIF
   
    IF rx2=ry2                // circle - fairly accurate
        rad2=rx2
    ELSE
        a=ATAN(y1-y2,x1-x2)    // ellipse - needs 64 bit accuracy
        IF a<0 THEN a=360+a
        dx=rx2*COS(a)
        dy=ry2*SIN(a)
        rad2=SQR((dx*dx)+(dy*dy))
    ENDIF
   
    distx=x2-x1
    disty=y2-y1
   
    IF rad1+rad2>=SQR((distx*distx)+(disty*disty))
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
   
ENDFUNCTION // OVALCOLL

// ------------------------------------------------------------- //
// -=#  DRAWELLPISE  #=-  Filled ellipse
// ------------------------------------------------------------- //
FUNCTION drawEllipse: x, y, rw, rh, col
LOCAL dy, xi
    //w=w/2
    //h=h/2
    x=x+w
    FOR dy = -rh TO rh
        xi = rw/rh * SQR(rh*rh - dy*dy)
        DRAWLINE x-xi, y+dy+h, x+xi, y+dy+h, col
    NEXT
ENDFUNCTION // DRAWELLPISE


// ------------------------------------------------------------- //
// -=#  DRAWCIRCLE  #=-  Outline circle fast
// ------------------------------------------------------------- //
FUNCTION drawCircle: x, y, r, c
        LOCAL x1=SIN(0)*r
        LOCAL y1=COS(0)*r
        FOR j=1 TO 360
            LOCAL x2=SIN(j)*r
            LOCAL y2=COS(j)*r
            DRAWLINE x+x1,y+y1,x+x2,y+y2,c
            x1=x2
            y1=y2
        NEXT

ENDFUNCTION // DRAWCIRCLE

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Circle collisions and draw circles
« Reply #7 on: 2008-Jan-20 »
No probs - just a couple of tips for you. My coll routine works with circles too (so would save you a function), and you can scrap the
Code: GLBasic [Select]
    IF x1<x2
        dx = x2 - x1
    ELSE
        dx = x1 - x2
    ENDIF
    IF y1<y2
        dy = y2 - y1
    ELSE
        dy = y1 - y2
    ENDIF
bit anyway - it doesn't matter if it produces a negative value, since you are going to square it, so it will always give a positive result.

In your example, it will be pretty accurate, purely because of the smaller size of your ellipses - in my code, I made them pretty huge, thus magnifying the error so you could see it clearly.

I also used a very crap method of drawing the ellipse deliberately so you could see how the maths was done - purely because it is the same maths that is use to calculate the radius at any locus around the ellipse.

Anyhoo, happy to help :)

Edit: Oh, I should point out that this code only allows for collisions where the major axis and minor axis are perpendicular to each other (so not a skewed ellipse), and that they correspond to the x and y axis of the screen (so not on a slant.) I could code for these eventualities at a push, but then the maths starts to get really messy! Also, it does not cover ovoid shapes (eggs!) - this is where the minor axis is perpendicular to the major axis, but is offset from the central position. Again, I could code it, but then the maths goes from the sublime to the ridiculous! :D
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« Reply #8 on: 2008-Jan-20 »
This is more than enough for what I need Peejay - many thanks for your help on it.

Offline BumbleBee

  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 891
    • View Profile
Circle collisions and draw circles
« Reply #9 on: 2008-Jan-20 »
Hi
Tiny tip:  Multiplication is faster than root extraction.:D
For example:

Replace
Code: GLBasic [Select]
   IF rad1+rad2>=SQR((distx*distx)+(disty*disty))
by

Code: GLBasic [Select]
 
   IF (rad1+rad2)*(rad1+rad2)>=distx*distx+disty*disty
:D

Cheers
The day will come...

CPU Intel(R) Core(TM) i5-3570k, 3.4GHz, AMD Radeon 7800 , 8 GB RAM, Windows 10 Home 64Bit

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« Reply #10 on: 2008-Jan-20 »
Thanks for the tip!  I shall give that a go.

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« Reply #11 on: 2008-Jan-20 »
With all that in, the function now looks like:

Code: GLBasic [Select]
// ------------------------------------------------------------- //
// -=#  CIRCOLL  #=-
// ------------------------------------------------------------- //
FUNCTION circoll: x1,y1,radius1, x2,y2,radius2

        LOCAL dx, dy
        dx = x2 - x1
        dy = y2 - y1

        IF (rad1+rad2)*(rad1+rad2) >= (dx*dx)+(dy*dy)
                RETURN TRUE
        ELSE
                RETURN FALSE
        ENDIF

ENDFUNCTION // CIRCOLL
Thanks Peejay and Bumblebee.

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10695
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Circle collisions and draw circles
« Reply #12 on: 2008-Jan-22 »
uhm... radius1 instead of rad1 (function parameter name)

Code: GLBasic [Select]
FUNCTION circoll: x1,y1,r1,  x2,y2,r2
   x1 = x2-x1
   y1 = y2-y1
   r1 = r1+r2
   IF x1*x1 + y1*y1 < r1*r1 THEN RETURN TRUE
RETURN FALSE
ENDFUNCTION
should be the fastest.

Offline AndyH

  • Dr. Type
  • ****
  • Posts: 383
    • View Profile
    • http://www.ovine.net/
Circle collisions and draw circles
« Reply #13 on: 2008-Jan-22 »
Thanks Gernot, will try that.  I'm using these for some collisions on my GP2X competition entry so speed is good :D