Circle collisions and draw circles

Previous topic - Next topic

AndyH

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 dx = x2 - x1
ELSE
dx = x1 - x2
ENDIF
IF y1 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

AndyH

Oh, I forgot to ask, as well as any suggestions for optimising this function, anyone know how to detect if two ellipses collide?

PeeJay

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

matchy

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.

PeeJay

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

PeeJay

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

AndyH

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 dx = x2 - x1
ELSE
dx = x1 - x2
ENDIF
IF y1 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

PeeJay

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        dx = x2 - x1
    ELSE
        dx = x1 - x2
    ENDIF
    IF y1        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

AndyH

This is more than enough for what I need Peejay - many thanks for your help on it.

BumbleBee

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

AndyH

Thanks for the tip!  I shall give that a go.

AndyH

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.

Kitty Hello

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.

AndyH

Thanks Gernot, will try that.  I'm using these for some collisions on my GP2X competition entry so speed is good :D