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

#### AndyH

• Dr. Type
• Posts: 383
##### 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 x2=320
GLOBAL y2=240

WHILE TRUE

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

SHOWSCREEN
WEND

// ------------------------------------------------------------- //
// -=#  CIRCOLL  #=-
// ------------------------------------------------------------- //

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) )
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

• Dr. Type
• Posts: 383
##### 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?

#### PeeJay

• Mr. Polyvector
• Posts: 244
##### 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

#### matchy

• Prof. Inline
• Posts: 1540
##### 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.

#### PeeJay

• Mr. Polyvector
• Posts: 244
##### 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

#### PeeJay

• Mr. Polyvector
• Posts: 244
##### 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

IF rx1=ry1                              // circle - fairly accurate
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)
ENDIF

IF rx2=ry2                              // circle - fairly accurate
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)
ENDIF

distx=x2-x1
disty=y2-y1

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

• Dr. Type
• Posts: 383
##### 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 x2=320
GLOBAL y2=240

WHILE TRUE

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

SHOWSCREEN
WEND

// ------------------------------------------------------------- //
// -=#  CIRCOLL  #=-
// ------------------------------------------------------------- //

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) )
RETURN TRUE
ELSE
RETURN FALSE
ENDIF

ENDFUNCTION // CIRCOLL

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

IF rx1=ry1                // circle - fairly accurate
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)
ENDIF

IF rx2=ry2                // circle - fairly accurate
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)
ENDIF

distx=x2-x1
disty=y2-y1

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

• Mr. Polyvector
• Posts: 244
##### 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!
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

#### AndyH

• Dr. Type
• Posts: 383
##### 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.

#### BumbleBee

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

Replace
Code: GLBasic [Select]
by

Code: GLBasic [Select]

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

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

#### AndyH

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

Code: GLBasic [Select]
// ------------------------------------------------------------- //
// -=#  CIRCOLL  #=-
// ------------------------------------------------------------- //

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

RETURN TRUE
ELSE
RETURN FALSE
ENDIF

ENDFUNCTION // CIRCOLL
Thanks Peejay and Bumblebee.

#### Kitty Hello

• code monkey
• Prof. Inline
• Posts: 10695
• here on my island the sea says 'hello'
##### Circle collisions and draw circles
« Reply #12 on: 2008-Jan-22 »

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

• Dr. Type
• Posts: 383
##### 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