Allegro.cc Forums » Programming Questions » Circle Collision Detection

 Circle Collision Detection
 Fishcake Member #8,704 June 2007 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 )
 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
 Fishcake Member #8,704 June 2007 wow thanks Johan Halmén and James Stanley! and with graphical explanation! wootness
 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 ____"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.
Fishcake
Member #8,704
June 2007

ok, i got a problem...

 1 double 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 5 void 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. 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

 1 Function 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 actualDistanceGraphicsWidth()-c.radius 59 c.x=GraphicsWidth()-c.radius 60 c.dx=c.dx*-0.9 61 End If 62 If c.yGraphicsHeight()-c.radius 67 c.y=GraphicsHeight()-c.radius 68 c.dy=c.dy*-0.9 69 End If 70 Next 71 End Function

 Fishcake Member #8,704 June 2007 brilliant solution gary_ramsgate! thanks!Quote: Actually that's so funny yeah, its funny but its not when a whole circle is inside another circle 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 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! [My site] [Tetrominoes]
 Neil Black Member #7,867 October 2006 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 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 Johan Halmén said: my balls stick, too. It must hurt!
 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 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.compassword: password _________________________________________________"God speed, my lonely angel."Bitcoin | Bitcoin Ponzi Scheme
 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: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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads