Latest posts of: Aaron - Java-Gaming.org

Show Posts
Pages: [1]

Game Development / Game Mechanics / Re: Collision between circle and line

on: 2005-06-04 23:49:40

Thanks.

Anyway, that link you gave me helped me optimize some of my code, but I'm still having problems.

What I'm doing now is look for the possible intersection point on the circle's radius, which is where the line normal would cross if reaching for the circle's centre. I came up with two ways of calculating the distance between the line and this intersection point parallel to the circle's velocity; one from the web site you gave me Lilian and another site at http://www.gamespp.com/algorithms/collisionDetectionTutorial02.html.

First I get the intersection point:

1
2
3

// Point of possible intersection on ball.
double intsect1X = A.x() + (-Nx * A.radius());
double intsect1Y = A.y() + (-Ny * A.radius());

Getting the distance based on the second site:

1 2	double d = (line.getX1() * Nx) + (line.getY1() * Ny); double actDist = d - ((intsect1X * Nx) + (intsect1Y * Ny));

Getting the distance based on the first site:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

double intsect2X = A.x() + (-Nx * A.radius()) + A.dx();
double intsect2Y = A.y() + (-Ny * A.radius()) + A.dy();

// Find distance between intersection point on ball and line parallel to ball velocity.
        
double denom = ((line.getX2() - line.getX1()) * (intsect2Y -  intsect1Y)) - ((line.getY2() - line.getY1()) * (intsect2X - intsect1X));
        
if (denom == 0) // Lines are parallel.
    return 1.0;
        
double r2 = (((line.getY1() - intsect1Y) * (intsect2X - intsect1X)) - ((line.getX1() - intsect1X) * (intsect2Y - intsect1Y))) / denom;
        
// Z is intersection point.
double Zx = line.getX1() + (r2 * (line.getX2() - line.getX1())) - intsect1X;
double Zy = line.getY1() + (r2 * (line.getY2() - line.getY1())) - intsect1Y;
        
// Distance ball actually has to move.
double actDist = Math.sqrt((Zx * Zx) + (Zy * Zy));

Both of these are followed by this:

1
2
3
4

if (dV <= Math.abs(actDist))
    return 1.0;
        
return Math.abs(actDist) / dV;

The problem is first of all that it looks like my line is "one-sided," the ball is only blocked from one side. It can still pass through the other side. Even on the side where it's blocked, it seems to be still possible for the ball to pass through if I press the forward key long enough (I'm controlling the ball with the keyboard).

2	Game Development / Game Mechanics / Re: Collision between circle and line	on: 2005-06-04 16:33:21
Thanks for the site, Lilian. I've been looking at the "distance from a point to a line" part with interest, but what do they mean by "L**2"? Is that L squared?

3	Game Development / Game Mechanics / Collision between circle and line	on: 2005-06-04 03:31:12
I'm working on a collision method that detects at what time a moving circle makes contact with a line over the interval [0, 1] (it returns 1.0 if there's no collision). I'm able to determine whether or not the circle is moving toward the line and if the circle's velocity could ever move itself close enough to the line for there to be collision. However, I can't figure out how to find the distance the circle would have to go to hit the line, which I'd get my time from. Here's pseudo code for the part of my method that works. I assume the line is infinite: *** double calculateCollisionTime(Line2D line, Circle circle) { // Get unit vector of line's normal pointing to side of line circle is on, // as well as shortest distance between line and circle's centre coordinate. if (circle.velocityMagnitude() < circle_line_distance - circle.radius()) return 1.0; // Get unit vector of circle's velocity. // Get dot product of circle's unit velocity vector and line's unit normal vector. // This corresponds to the angle between the circle's velocity and the line. if (dotprod <= 0) // Circle parallel to or going away from line. return 1.0; // This is the part I'm having trouble with. // Find distance between circle and line parallel to circle's velocity. If it's less // than the circle's velocity, expect a collision. Divide this distance by the circle's // velocity to get time. return time. } *** I have searched on the internet, and the few articles I found didn't help me. Does anyone here have any suggestions? Thank you.

Game Development / Game Mechanics / Faulty circle-circle collision handling

on: 2005-05-23 22:55:44

Hello. I'm designing a game, and I'm trying to work out the collision detection and handling.

I made a test application with two balls; one that you move around with the arrow keys. I copied the algorithm described in this article. Generally when you try to move one ball over the other it's made to only go far enough to touch it, preventing overlap. However, there's still some overlap at the left and right sides of the stationary ball, and sometimes when coming from just off the top or bottom the movable ball can be blocked even when a small gap is shown between the balls. Only when you try to collide from the top or bottom do you get good results.

This is my method for handling collisions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

private boolean testForCollision(float Nx, float Ny) {
        // Ball B is stationary.
        float moveVecX = A.dx();
        float moveVecY = A.dy();
        float moveVecMag = (float)Math.sqrt((moveVecX * moveVecX)
           + (moveVecY * moveVecY));
        
        // Early Escape test: if the length of the movevec is less
        // than distance between the centers of these circles minus
        // their radii, there's no way they can hit.
        double dist = Math.sqrt(((B.x() - A.x()) * (B.x() - A.x()))
           + ((B.x() - A.x()) * (B.x() - A.x()))) - (A.radius() + B.radius());
        
        if(moveVecMag < dist) {
            return false;
        }
        
        // Normalize the movevec
        Nx = moveVecX / moveVecMag;
        Ny = moveVecY / moveVecMag;

        // Find C, the vector from the center of the moving
        // circle A to the center of B
        float Cx = B.x() - A.x();
        float Cy = B.y() - A.y();

        // D = N . C = NxCx + NyCy
        double D = (Nx * Cx) + (Ny * Cy);

        // Another early escape: Make sure that A is moving
        // towards B! If the dot product between the movevec and
        // B.center - A.center is less that or equal to 0,
        // A isn't isn't moving towards B
        if(D <= 0) {
            return false;
        }
        
        // Find the length of the vector C
        double lengthC = Math.sqrt((Cx * Cx) + (Cy * Cy));

        double F = (lengthC * lengthC) - (D * D);

        // Escape test: if the closest that A will get to B
        // is more than the sum of their radii, there's no
        // way they are going collide
        double sumRadiiSquared = (A.radius() + B.radius())
           * (A.radius() + B.radius());
        if(F >= sumRadiiSquared) {
            return false;
        }
        
        // We now have F and sumRadii, two sides of a right triangle.
        // Use these to find the third side, sqrt(T)
        double T = sumRadiiSquared - F;

        // If there is no such right triangle with sides length of
        // sumRadii and sqrt(f), T will probably be less than 0.
        // Better to check now than perform a square root of a
        // negative number.
        if(T < 0) {
            return false;
        }
        
        // Therefore the distance the circle has to travel along
        // movevec is D - sqrt(T)
        double distance = D - Math.sqrt(T);

        // Finally, make sure that the distance A has to move
        // to touch B is not greater than the magnitude of the
        // movement vector.
        if(moveVecMag < distance) {
            return false;
        }
        
        // Set the length of the movevec so that the circles
        // will just touch
        Nx *= distance;
        Ny *= distance;
        
        return true;
    }

If testForCollision() returns false, the ball is translated by its normal dx and dy. Otherwise it's translated by Nx and Ny, which should bring it to the surface of the other ball.

Any help would be apprieciated.

UPDATE
Well, I could never figure out what was wrong, so I ended up redoing it. It's based a lot on what I tried to do before, and I'm not sure I can pin-point what's different that made the fix. What I did change was that this time I find the time when the balls collide, then translate them accordingly. This is what I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

private double calculateTranslation(Ball A, Ball B) {
            // Relative position.
          double dPx = B.x() - A.x();
            double dPy = B.y() - A.y();
            double dP = Math.sqrt((dPx * dPx) + (dPy * dPy));
            
            // Relative velocity.
            double dVx = B.dx() - A.dx();
            double dVy = B.dy() - A.dy();
            double dV = Math.sqrt((dVx * dVx) + (dVy * dVy));
            
          double minDist = (B.radius() + A.radius());
            
            // Distance between A and B.
            double dist = dP - minDist;
          if(dV < dist)
                  return 1.0;

          // Normalize dV.
          double dVNx = dVx / dV;
            double dVNy = dVy / dV;
            
            // Are A and B moving away from each other?
            // Find dot product of dVN and dP.
          double dotProd = (dVNx * dPx) + (dVNy * dPy);
          if (dotProd >= 0)
            return 1.0;
            
            // dotProd is also the component of dP parallel to the normal of dV.
            // This can be used to find the shortest line between the center of B
            // and dV, which we'll call F.
            // dP is the hypotenuse.
          double Fsq = (dP * dP) - (dotProd * dotProd);
            
            double minDistSq = minDist * minDist;
            
          // Escape test: if the closest that A will get to B
          // is more than the sum of their radii, there's no
          // way they are going collide
          if (Fsq >= minDistSq)
                  return 1.0;

          // F and minDist form a right triangle (minDist the hypotenuse) with a
            // third line we'll call T.  Tsq is the square of T.
          double Tsq = minDistSq - Fsq;
            
            // Check that Tsq isn't negative.
            if (Tsq < 0)
                  return 1.0;
            
          // Therefore the distance the circle has to travel along
          // movevec is dotProd - T
          double distFinal = Math.abs(dotProd) - Math.sqrt(Tsq);

          // Finally, make sure that the distance A has to move
          // to touch B is not greater than the magnitude of the
          // movement vector.
          if (dV <= distFinal)
                  return 1.0;
            
          // Find the time it will take for A & B to make contact.
            double time = distFinal / dV;
          return time;
}

I'm going to keep this since I haven't encountered any problems like I did with the last method, and I prefer getting the time value anyway.

Pages: [1]

Check out our latest community projects!

Play Revenge of the Titans! The situation is critical. We need fancy commanders to defend Earth, the moon, Mars!