Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Faulty circle-circle collision handling  (Read 1177 times)
0 Members and 1 Guest are viewing this topic.
Offline Aaron

Junior Newbie




Java games rock!


« Posted 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]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (34 views)
2014-07-18 06:55:21

Zero Volt (30 views)
2014-07-17 23:47:54

danieldean (25 views)
2014-07-17 23:41:23

MustardPeter (27 views)
2014-07-16 23:30:00

Cero (42 views)
2014-07-16 00:42:17

Riven (44 views)
2014-07-14 18:02:53

OpenGLShaders (32 views)
2014-07-14 16:23:47

Riven (33 views)
2014-07-14 11:51:35

quew8 (30 views)
2014-07-13 13:57:52

SHC (66 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!