Collision complications...

Apprentice
Posts: 5
Joined: 2008.06
Post: #1
Hey there!!

Recently, for some inexplicable reason, I've had the irresistible urge to program my own game. So I looked at the options for languages, and decided to learn python + the pygame library.

I've been doing pretty well so far. My game idea involves a little spherical robot that rolls around levels, destroying its enemies by various means. My first milestone is to write a physics engine for the little ball. Right now I've got a program that has a little blue ball, and you can click anywhere within the pygame window to "throw" it, and it will bounce off of the edges and bottom of the screen.

I'm working on trying to get the ball to bounce off an angled surface though. I implemented a little white angled "bar" in my game, and am testing my engine with that.

I've got the basics down: I'm using the point-line distance formula to detect collision, and I've got the bounce-angle calculation figured out. What I don't know how to do, though, is this: when a collision is detected, the ball is most likely somewhere embedded within the surface its colliding against, because of the fact that the ball moves more than 1 pixel at a time in both the x and y values. If a collision is detected, I would like to move the ball backwards slightly until the ball is just touching the collision surface, not embedded within it (i.e. point-line distance = radius of ball).

Does anyone know the mathematics of how to do this? I would think it would involve the intersection between two lines: a line formed by the position of the ball in the current frame and the previous frame, and a line that is d distance away from but parallel to the collision surface (d being equal to the ball's radius).

Any help is greatly appreciated!!

Peace,
dgm
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #2
You can push out the ball along the normal of the surface. You can calculate the "push vector"'s direction and length.
The direction is perpendicular to the "bar", so if the bar goes from p1 to p2 = delta, the normal direction is (-delta.y, delta.x). It is like this because of the dot product which is 0 if the angle between two vectors is 90 degrees. so delta.x*-delta.y + delta.y*delta.x = 0.
The length is the difference between the radius and the distance. So if the actual distance is d, you want to push the ball back by radius-d.

In conclusion, you would do something like:
Code:
if(distance < radius) {
    vector delta = bar.end - bar.start; //the start and end points of the bar
    vector normal = vector(-delta.y, delta.x);
    normal.normalize();
    
    normal = normal * (radius-distance);
    ball.move_by_vector(normal);
}

Hope that helps.
-ibd
Quote this message in a reply
Apprentice
Posts: 5
Joined: 2008.06
Post: #3
_ibd_ Wrote:You can push out the ball along the normal of the surface. You can calculate the "push vector"'s direction and length.
The direction is perpendicular to the "bar", so if the bar goes from p1 to p2 = delta, the normal direction is (-delta.y, delta.x). It is like this because of the dot product which is 0 if the angle between two vectors is 90 degrees. so delta.x*-delta.y + delta.y*delta.x = 0.
The length is the difference between the radius and the distance. So if the actual distance is d, you want to push the ball back by radius-d.

In conclusion, you would do something like:
Code:
if(distance < radius) {
    vector delta = bar.end - bar.start; //the start and end points of the bar
    vector normal = vector(-delta.y, delta.x);
    normal.normalize();
    
    normal = normal * (radius-distance);
    ball.move_by_vector(normal);
}

Hope that helps.
-ibd

Hey, thanks for the advice!!

Based on your advice to use vectors, I decided to rewrite my collision detection system to use vectors. Rather than using the point-line distance formula to detect collision, I'm using another method. I have two line segments, each defined by a point and a vector: the collision surface; and a segment from the closest point on the ball to the surface one frame ago, and that point on the current frame. I'm using Cramer's Rule to detect whether the two segments intersect, as was suggested in an online reference.


I seem to be making significant progress, BUT... there's still one glitch I have to work out. It seems that if the x velocity of the ball is positive (ball is moving to the right), collision is detected and it bounces off the collision surface flawlessly. But if the x velocity is negative or 0 (ball is moving to the left or in a straight vertical line), the ball passes right through the collision surface.

A frustrating phenomenon indeed. If anyone knows where my math might be going wrong, please let me know...

Peace,
dgm.
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #4
I'm not sure how you use Cramer's rule (does it have to do with Vector cross products in this case?), but it seems like x <= 0 seems to be a case when it doesn't work. This might be if you use cross products because they are anti commutative ( a x b = - b x a).

Maybe you can use another line intersection test. I like the one described at http://www.macs.hw.ac.uk/~alison/ds98/node114.html because it is easy to remember. Note "The implementation must cope with the fact that the slopes may be infinite, or that they are equal, but that's just a minor fiddle - see Sedgewick", though.
Quote this message in a reply
Apprentice
Posts: 5
Joined: 2008.06
Post: #5
_ibd_ Wrote:I'm not sure how you use Cramer's rule (does it have to do with Vector cross products in this case?), but it seems like x <= 0 seems to be a case when it doesn't work. This might be if you use cross products because they are anti commutative ( a x b = - b x a).

Maybe you can use another line intersection test. I like the one described at http://www.macs.hw.ac.uk/~alison/ds98/node114.html because it is easy to remember. Note "The implementation must cope with the fact that the slopes may be infinite, or that they are equal, but that's just a minor fiddle - see Sedgewick", though.

Thanks for the link - I'll take a look at it, but my intersection test seems to be working for now:

I copied my intersection detection algorithm into a test program, which generated two random segments and flashed the screen if there was an intersection, and it detected every single intersection perfectly.

I was looking over the code, and it turns out that there was a line of code that basically said that if the x or y velocities were less than 0.0, then it wouldn't check for an intersection. That would explain it. Wacko


I only have one glitch that I need to work out now, and that is, if the X or Y velocities are equal to zero, then my intersection detection algorithm doesn't work because of division by zero (just like the test in the link you gave me). I think I had added the line of code that I just mentioned to temporarily avoid this glitch while working on the collision detection.

EDIT: Nevermind... it turns out that division by zero is only a problem if BOTH the X and Y velocities are zero. So I just skip intersection checking if the ball isn't moving, which would be totally unnecessary anyway.
Quote this message in a reply
Apprentice
Posts: 5
Joined: 2008.06
Post: #6
O.K...

I've got my 2D bouncing ball engine working completely, with only one exception. I got to the point where the ball could bounce off of any surface at any angle with no glitches... but I just need to implement corner collision-detection & bouncing, and that's where I'm stuck.

Currently, my program consists of a ball, and two rectangular bars each defined by four collision surfaces. You can click anywhere in the screen to "throw" the ball from that point. The ball will then fall, and if it collides with either one of the two bars, or one of the edges of the window, it will bounce accordingly. But, since I currently have no implementation of corner collision detection or reaction physics, the ball will fall through the corner of a bar if it doesn't collide flat-on with the bar surface.

Here's the Python+Pygame script bundled up into a .app. You can view/edit/play with the source by viewing package contents, and opening up the "bouncingball.py" script under Resources.

bouncingball.zip

Any ideas are greatly appreciated!
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #7
Conceptually, you could treat corners as circles of radius 0, and do circle-circle collision detection to handle them. Seems like that would solve the problem.
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #8
You might get more accurate results by sweeping the circle against the corners/edges. The Math will become more complicated, though.
Quote this message in a reply
Apprentice
Posts: 5
Joined: 2008.06
Post: #9
The circle-circle collision idea seems like it would work...

_ibd_ Wrote:You might get more accurate results by sweeping the circle against the corners/edges. The Math will become more complicated, though.

What exactly do you mean by "sweeping"?
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #10
It essentially means that you don't check for collisions at discrete steps, but that you calculate the exact time the circle will collide with anything by parameterizing the movement. Search for it, there are quite some tutorials/guides on it.
Quote this message in a reply
Post Reply