Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Circle Collision Detection

This thread is locked; no one can reply to it. rss feed Print
Circle Collision Detection
Fishcake
Member #8,704
June 2007
avatar

does anyone know any tutorials of circle collision detection written with allegro? or source code maybe? i'm really into physics stuff and simulations, the main reason I decided to try on programming :) hopefully i can make a pool game...

i want to know how to calculate the angle after impact, and if you are kind enough, maybe collision that involve mass (i think its momentum...errr...donno ???) ;D

Johan Halmén
Member #1,550
September 2001

Here. No spin effects, though.

If the circles/spheres/balls don't have different masses, just work with velocity vectors, no mass stuff.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

James Stanley
Member #7,275
May 2006
avatar

Fishcake
Member #8,704
June 2007
avatar

wow thanks Johan Halmén and James Stanley! and with graphical explanation! wootness ;D

julian_boolean
Member #8,201
January 2007

Just curious. How do you guys make a link to another page and give it a name like you just did?

Paul whoknows
Member #5,081
September 2004
avatar

____

"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.

julian_boolean
Member #8,201
January 2007

Awesome!! Thank you very much. ;D

Fishcake
Member #8,704
June 2007
avatar

ok, i got a problem...

1double distance(double pos1_x, double pos1_y, double pos2_x, double pos2_y) {
2 return sqrt((pos1_x-pos2_x)*(pos1_x-pos2_x) + (pos1_y-pos2_y)*(pos1_y-pos2_y));
3}
4 
5void bounce(Carrom* c1, Carrom* c2){
6
7 double cNorm = atan2(c2->y - c1->y, c2->x - c1->x);
8 double nX = cos(cNorm);
9 double nY = sin(cNorm);
10
11 double a1 = c1->dx*nX + c1->dy*nY;
12 double a2 = c2->dx*nX + c2->dy*nY;
13 double optimisedP = (2.0 * (a1-a2)) / (c1->m + c2->m);
14
15 if( distance(c1->x, c1->y, c2->x, c2->y) < (c1->r + c2->r) ){
16 c1->dx = c1->dx - (optimisedP * c2->m * nX);
17 c1->dy = c1->dy - (optimisedP * c2->m * nY);
18 c2->dx = c2->dx + (optimisedP * c1->m * nX);
19 c2->dy = c2->dy + (optimisedP * c1->m * nY);
20 }
21
22}

this code is actually from http://www.allegro.cc/forums/thread/591703. i changed it into a function. the problem is that sometimes when the circles collide, they stick together, which is not a nice scene..:-/ its sticking to each other just like magnet, except that they're overlapping...how do i fix that?

Johan Halmén
Member #1,550
September 2001

I know. I'm in the middle of a game development and my balls stick, too. :-X
The problem is, I think, when they collide and they get their new speeds and directions and in the next frame they still overlap. That would cause a negative collision, turning the velocity vectors once again against each other. Something like that.

Somehow it happens not very often in my game. First of all I thought my balls would never actually overlap. I thought I did the collision stuff in the frame before the overlap. I haven't checked that yet. Anyhow, if they overlap in the collision frame and still overlap in the next frame and that's what causes the stickyness, I must set a flag for collision and reset the flag not until there is no overlap anymore between the two balls in concern.

In my game I shoot balls against each others. The funny thing is that if two balls stick together like that, I can separate them by shooting a third ball against them. Actually that's so funny I think I won't fix the problem. I just have to find out a funny explanation for that in the gameplay. Extra bonus for shooting at magnetized balls, or something.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

gary_ramsgate
Member #8,619
May 2007

This may be of use

1Function UpdateBallPhysics()
2' This is the main physics function for the
3' balls. It contains the very basic movement
4' physics as well as the collision response code
5 For Local c:ballType = EachIn ballList
6 ' update positions
7 c.x=c.x+c.dx
8 c.y=c.y+c.dy
9 ' gradually slow down
10 c.dx=c.dx*FRICTION
11 c.dy=c.dy*FRICTION
12 ' stop completely when below a certain speed
13 If Abs(c.dx)<0.068 Then c.dx=0
14 If Abs(c.dy)<0.068 Then c.dy=0
15 ' COLLISION CHECKING
16 ' Check each ball in the loop against
17 ' every other (c against c2)
18 For Local c2:ballType = EachIn ballList
19 Local collisionDistance# = c.radius+c2.radius
20 Local actualDistance# = Sqr((c2.x-c.x)^2+(c2.y-c.y)^2)
21 ' collided or not?
22 If actualDistance<collisionDistance Then
23 Local collNormalAngle#=ATan2(c2.y-c.y, c2.x-c.x)
24 ' position exactly touching, no intersection
25 Local moveDist1#=(collisionDistance-actualDistance)*(c2.mass/Float((c.mass+c2.mass)))
26 Local moveDist2#=(collisionDistance-actualDistance)*(c.mass/Float((c.mass+c2.mass)))
27 c.x=c.x + moveDist1*Cos(collNormalAngle+180)
28 c.y=c.y + moveDist1*Sin(collNormalAngle+180)
29 c2.x=c2.x + moveDist2*Cos(collNormalAngle)
30 c2.y=c2.y + moveDist2*Sin(collNormalAngle)
31 ' COLLISION RESPONSE
32 ' n = vector connecting the centers of the balls.
33 ' we are finding the components of the normalised vector n
34 Local nX#=Cos(collNormalAngle)
35 Local nY#=Sin(collNormalAngle)
36 ' now find the length of the components of each movement vectors
37 ' along n, by using dot product.
38 Local a1# = c.dx*nX + c.dy*nY
39 Local a2# = c2.dx*nX + c2.dy*nY
40 ' optimisedP = 2(a1 - a2)
41 ' ----------
42 ' m1 + m2
43 Local optimisedP# = (2.0 * (a1-a2)) / (c.mass + c2.mass)
44 ' now find out the resultant vectors
45 '' Local r1% = c1.v - optimisedP * mass2 * n
46 c.dx = c.dx - (optimisedP*c2.mass*nX)
47 c.dy = c.dy - (optimisedP*c2.mass*nY)
48 '' Local r2% = c2.v - optimisedP * mass1 * n
49 c2.dx = c2.dx + (optimisedP*c.mass*nX)
50 c2.dy = c2.dy + (optimisedP*c.mass*nY)
51 End If
52 Next
53 ' Simple bouncing off walls.
54 If c.x<c.radius
55 c.x=c.radius
56 c.dx=c.dx*-0.9
57 End If
58 If c.x>GraphicsWidth()-c.radius
59 c.x=GraphicsWidth()-c.radius
60 c.dx=c.dx*-0.9
61 End If
62 If c.y<c.radius
63 c.y=c.radius
64 c.dy=c.dy*-0.9
65 End If
66 If c.y>GraphicsHeight()-c.radius
67 c.y=GraphicsHeight()-c.radius
68 c.dy=c.dy*-0.9
69 End If
70 Next
71End Function

Fishcake
Member #8,704
June 2007
avatar

brilliant solution gary_ramsgate! thanks!

Quote:

Actually that's so funny

yeah, its funny ;D but its not when a whole circle is inside another circle :o which always happens in my program

Johan Halmén
Member #1,550
September 2001

I guess your step size is somewhat equal to a circle diameter, which is too much. My own project is still at that phase where I just calculate everything and then I draw everything, no matter of fps. My step size is maybe 5 pixels while the circle diameter is 31 pixels. Separating the game loop freq from the drawing freq will probably decrease the step size, increasing the quality of the simulation.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Thomas Harte
Member #33
April 2000
avatar

Depending on what you're doing with the circles, it might make sense to use a continuous time simulation rather than discrete time stepping. That means you start each frame with knowledge of object positions and trajectories, then you work out the first time at which something touches something else. Advance to that time, do the bounce or whatever, then work out how long until the next touch. And so on until you've reached the end of the time encapsulated by that frame.

It's SDL based, but that's what I did for my brief "messing about" work on a Robotron-ish thing. Check it out at the bottom of this page (no Windows binary, but I'll correct that later this evening) — it's not perfect but you can introduce a ridiculous number of balls onto the display and everything continues to run correctly for a very long time. Also you can move a little squashed guy around and push the balls. What fun!

Neil Black
Member #7,867
October 2006
avatar

About that sticking, back when I was using QBASIC, one of my first games was a Ball Breaker game(you know, the one where you hit the ball with the paddle and it breaks the blocks). Anyway, sometimes the ball would get stuck on the paddle and bouce along it, then shoot off the other end. This bug turned into an interesting feature when I changed the ball into a ring, and claimed that it was supposed to do that. ;)

Andrei Ellman
Member #3,434
April 2003

Thomas Harte said:

Depending on what you're doing with the circles, it might make sense to use a continuous time simulation rather than discrete time stepping. That means you start each frame with knowledge of object positions and trajectories, then you work out the first time at which something touches something else. Advance to that time, do the bounce or whatever, then work out how long until the next touch. And so on until you've reached the end of the time encapsulated by that frame.

One way of immagining how this would work is to immagine time being turned into an extra dimension (the time between the current frame and the next frame is the start and end points). If doing 2D circle-circle collisions, the moving circles will be turned into slanted cylinders (stationary circles become regular cylinders). You should try and find out if any of the cylinders (regular or slanted) intersect in the 3D space (2 spatial dimensions + 1 temporal dimension). If there's at east one intersection find the first point in the temporal dimension (the earliest point in time) in which two cylinders overlap. At that point in time, do a static circle-circle collision check (as described previously in this thread) to find out the velocities of the circles post-collision. Afterwards, repeat the process but starting with the time of the collision instead of the time of the start of the current frame (you can save time if you've calculated the other collisions already, but even they could be affected by the new trajectories of the collided objects). To prevent infinite iteration/recursion where the circles are colliding forever, apply some friction or slow down the circles on each collision and once the velocity drops below a certain point, set it to 0.

AE.

--
Don't let the illegitimates turn you into carbon.

Fishcake
Member #8,704
June 2007
avatar

ok, im trying to make a carrom game. its going pretty well. except for this problem...

lets say i have this one piece of carrom, with radius 10 pixels, making its diameter 20 pixels. and the striker (the one which you are controlling) is moving with a speed of lets say, 50 pixels per frame. sometimes, the striker just go through the carrom piece when a collision is supposed to happen.

Johan Halmén
Member #1,550
September 2001

Do you have to move 50 pixels per frame? Usually, rendering a frame takes so long that if you do it in each game loop, you really have to move 50 pixels. But it might be possible that if you render the graphics only in every 50th game loop, the striker might move only one pixel and the collision detection will be easier. And the rendering rate might still be say 50 fps. If this won't work, you have to find out the collision analytically. In frame n you have two pieces at two coordinates. In frame n+1 they have moved somewhere. Find out the least distance inbetween. A bit like what Thomas and Andrei said.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Roberto
Member #7,391
June 2006
avatar

Johan Halmén said:

my balls stick, too.

It must hurt! ;D

Johan Halmén
Member #1,550
September 2001

  • edited and moved to a new post below *

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Tobias Dammers
Member #2,604
August 2002
avatar

Quote:

And I can reduce the step size by separating the redraw rate from logic loop rate. I think.

It should work well for a small number of objects; any kind of billiards will be fine. When larger quantities of objects are involved, and high speeds are possible (and thus many iterations of the logic loop per frame), you may experience performance problems though. This is where space partitioning algorithms come in.

About the sticky balls: This happens if the balls travel a smaller (relative) distance in the first frame AFTER the collision than they did in the frame BEFORE, so they travel into each other further in one frame than they travel away from each other in the next one; the reason can be rounding errors, and / or the fact that you probably apply some sort of force that reduces their velocities - frictions, and maybe a constant damping factor on the collision.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

Billybob
Member #3,136
January 2003

Here's a neat article that was featured in Game Dev Magazine: Physics on the Back of a Cocktail Napkin.
If it asks for login:
Username: js8464@emailaccount.com
password: password

Johan Halmén
Member #1,550
September 2001

  • moved from an earlier post and edited (url didn't work)*

I just downloaded Copernicus, a screen capture application for OSX, and did this:

http://kotisivu.dnainternet.fi/johan25/bomberballs.mov (4.4 MB)

The frame rate in the game is much better than in that video. The game needs lots of polishing and developing of the game idea. But the bouncing balls work great. The biggest step size is now about 5 pixels, while the radius is 15 pixels. And I can reduce the step size by separating the redraw rate from logic loop rate. I think.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Go to: