Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
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  
  Poly to Poly or Poly to Rect Collision detection?  (Read 1826 times)
0 Members and 1 Guest are viewing this topic.
Offline CyanPrime
« Posted 2011-05-25 02:19:23 »

How would I be able to make poly to rect collision? Or would Poly to Poly be easier?
Here is a example:

I want the user controlled rect to not be able to go through any part of the polygon.
Offline Karmington

Senior Member


Medals: 1
Projects: 1


Co-op Freak


« Reply #1 - Posted 2011-05-25 02:32:33 »

poly to rect makes no difference in my opinion, an unnecessary optimisation unless necessary for some reason.

Offline lhkbob

JGO Knight


Medals: 32



« Reply #2 - Posted 2011-05-25 03:17:19 »

If you had the polygons all convex, you could do GJK for collision detection or Minkowski portal refinement: http://xenocollide.snethen.com/mpr2d.html.  Even so, these are somewhat complex algorithms and they're limited to convex polygons.

If you want concave polygons (as you show in the screenshot), you're best bet is to decompose them into sets of convex polygons (such as triangles).

This is a HARD problem.  My best bet is for you to use some physics engine (like JBox2D) and use the collision detection code from that.  You can use collision detection from a physics engine without using it for movement usually fairly easy.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CyanPrime
« Reply #3 - Posted 2011-05-25 04:57:14 »

Well, I'm trying to understand how this works. I got my poly on poly code written, but it is giving false positives when I'm like +50 units away. This is what I got so far:

Ship:
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  
public void update(Player other, GPos gpos, Wall[] w1)
   {
      angle = (float) Math.toDegrees(Math.atan2(x - other.ship.x, -(y - other.ship.y)));
     
      edges = new Vector2f[] {
            new Vector2f(rotate(x, y, (x + (width/2)), (y + (height/2)), angle, true),
                 rotate(x, y, (x + (width/2)), (y + (height/2)), angle, false)),
                   
            new Vector2f(rotate(x + width, y, (x + (width/2)), (y + (height/2)), angle, true),
                 rotate(x + width, y, (x + (width/2)), (y + (height/2)), angle, false)),
           
            new Vector2f(rotate(x + width, y + height, (x + (width/2)), (y + (height/2)), angle, true),
               rotate(x + width, y + height, (x + (width/2)), (y + (height/2)), angle, false)),

            new Vector2f(rotate(x, y + height, (x + (width/2)), (y + (height/2)), angle, true),
               rotate(x, y + height, (x + (width/2)), (y + (height/2)), angle, false))
      };

[...]
public float rotate(float x, float y, float ox, float oy, float a, boolean b)
    {
         float dst = (float) Math.sqrt(Math.pow(x-ox,2.0)+ Math.pow(y-oy,2.0));

         float oa = (float) Math.atan2(y-oy,x-ox);

         if(b)
            return (float) Math.cos(oa + Math.toRadians(a))*dst+ox;

         else
            return (float) Math.sin(oa + Math.toRadians(a))*dst+oy;

    }


Ship collision code:
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  
public boolean colision(Vector2f[] enemyEdges)
    {  
       boolean collision = true;
       
       if(edges == null)
          edges = new Vector2f[] {
             new Vector2f(9f,9f),
             new Vector2f(9f,9f),
             new Vector2f(9f,9f),
             new Vector2f(9f,9f)};
             
       
       if(enemyEdges == null)
          enemyEdges = new Vector2f[] {
             new Vector2f(0f,0f),
             new Vector2f(0f,0f),
             new Vector2f(0f,0f),
             new Vector2f(0f,0f)};

       Vector2f edge = new Vector2f();
       
       for (int i = 0; i < edges.length + enemyEdges.length; i++) {
            if (i < edges.length) {
                edge = edges[i];
            }
           
            else {
                edge = enemyEdges[i - edges.length];
            }
           
            Vector2f axis = new Vector2f(-edge.y, edge.x);
            axis.normalise();
           
            Vector2f a = new Vector2f();
            Vector2f b = new Vector2f();
            ProjectPolygon(axis, edges, a);
            ProjectPolygon(axis, enemyEdges, b);
           
            //System.out.println("minA: " + minA + " maxA" + maxA + "minB: " + minB + " maxB" + maxB);
           
            if (IntervalDistance(a.x, a.y, b.x, b.y) > 0)
               collision = false;
        }
       
       return collision;
    }
   
    public void ProjectPolygon(Vector2f axis, Vector2f[] polygon, Vector2f vec) {
      // To project a point on an axis use the dot product
      float dotProduct = axis.dot(polygon[0]);
      vec.x /*min*/ = dotProduct;
      vec.y /*max*/ = dotProduct;
      for (int i = 0; i < polygon.length; i++) {
         dotProduct = polygon[i].dot(axis);
         if (dotProduct < vec.x) {
            vec.x = dotProduct;
         }
         else if (dotProduct> vec.y) {
            vec.y = dotProduct;
         }
      }
   }
   
    public float IntervalDistance(float minA, float maxA, float minB, float maxB) {
        if (minA < minB) {
            return minB - maxA;
        }
       
        else {
            return minA - maxB;
        }
    }


Where am I going wrong?  Cry
Offline CyanPrime
« Reply #4 - Posted 2011-05-25 06:28:39 »

Here is some debug info of whats going on when I get the false positive.

1  
2  
3  
4  
5  
6  
7  
8  
Edge[0] x:447.3233 y:142.10612
Edge[1] x:488.89386 y:114.32329
Edge[2] x:516.6767 y:155.89388
Edge[3] x:475.1061 y:183.67671
enemyEdges[0] x:300.0 y:100.0
enemyEdges[1] x:350.0 y:100.0
enemyEdges[2] x:350.0 y:200.0
enemyEdges[3] x:300.0 y:200.0


Offline CyanPrime
« Reply #5 - Posted 2011-05-25 07:43:53 »

okay I needed to calcualte edges, but now that I've done that it's still giving false posititves.

1  
2  
3  
4  
5  
6  
7  
8  
Edge[0] x:-52.869385 y:46.955597
Edge[1] x:-46.955566 y:-52.869385
Edge[2] x:-748.5653 y:-151.4778
Edge[3] x:851.34717 y:107.479095
enemyVertices[0] x:300.0 y:100.0
enemyVertices[1] x:350.0 y:100.0
enemyVertices[2] x:350.0 y:200.0
enemyVertices[3] x:300.0 y:200.0


This is the new code:

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  
public boolean colision(Vector2f[] enemyVertices)
    {  
       boolean collision = true;
       
       if(vertices == null)
          vertices = new Vector2f[] {
             new Vector2f(9f,9f),
             new Vector2f(9f,9f),
             new Vector2f(9f,9f),
             new Vector2f(9f,9f)};
             
       
       if(enemyVertices == null)
          enemyVertices = new Vector2f[] {
             new Vector2f(0f,0f),
             new Vector2f(0f,0f),
             new Vector2f(0f,0f),
             new Vector2f(0f,0f)};

       Vector2f[][] ourEdges = calcEdges(vertices);
       Vector2f[][] theirEdges = calcEdges(enemyVertices);
       
       
       Vector2f edge = new Vector2f();
       
       for(int i = 0; i < vertices.length; i++){
          System.out.println("Edge[" + i + "] x:" + vertices[i].x + " y:" + vertices[i].y);
       }
       
       for(int i = 0; i < enemyVertices.length; i++){
          System.out.println("enemyVertices[" + i + "] x:" + enemyVertices[i].x + " y:" + enemyVertices[i].y);
       }
       
       
       for (int i = 0; i < ourEdges.length + theirEdges.length; i++) {
            if (i < ourEdges.length) {
                edge = ourEdges[i][0].sub(ourEdges[i][1]);
            }
           
            else {
                edge = theirEdges[i - ourEdges.length][0].sub(theirEdges[i - ourEdges.length][1]);
            }
           
            Vector2f axis = new Vector2f(-edge.y, edge.x);
            axis.normalise();
     
[...]
    public Vector2f[][] calcEdges(Vector2f[] vertices){
      Vector2f[][] edges = new Vector2f[vertices.length][2];
       
      for(int i = 0; i < vertices.length; i++){
         int iPlus = (i+1);
         if(iPlus >= vertices.length)
            iPlus = 0;
         
         edges[i][0] = vertices[i];
         edges[i][1] = vertices[iPlus];
      }
     
       return edges;
    }


Edit: swapped around edges[][1] and [][0] like it's suppose to be but it's still messing up:
1  
2  
3  
4  
5  
6  
7  
if (i < ourEdges.length) {
                edge = ourEdges[i][1].sub(ourEdges[i][0]);
            }
           
            else {
                edge = theirEdges[i - ourEdges.length][1].sub(theirEdges[i - ourEdges.length][0]);
            }
Offline philfrei
« Reply #6 - Posted 2011-05-25 09:53:54 »

I'm wondering about treating the polygon a series of Line2D.Float objects. There is a function on Line2D that returns a boolean if the line intersects any any part of the interior of a Rectangle (your ship, presumably). Or would this be too slow? (I'm noticing you have a really fast FPS going!)

Also, when you mention false positives due to being off by +50, I wonder if the rotation is happening exactly like you think it is. It is easy to mix up whether the rotation is occurring from a midpoint or topleft corner or whatever. An error that is off on only one side and similar in size to the object being rotated is kind of suspicious in this regard.

So, I'm having trouble understanding how you are representing the enemy object. It's a series of vectors that are subject to rotation, rather than an actual Polygon object? How are they drawn? Are lines extracted at the point of drawing? If so, perhaps the same lines can be used for collision detection.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline pjt33
« Reply #7 - Posted 2011-05-25 10:53:40 »

I'm wondering about treating the polygon a series of Line2D.Float objects. There is a function on Line2D that returns a boolean if the line intersects any any part of the interior of a Rectangle (your ship, presumably). Or would this be too slow? (I'm noticing you have a really fast FPS going!)
Go the whole hog: Path2D.Float.intersects. It would need profiling, but if it performs well enough then getting the standard library to do the work is always a good plan.
Offline CommanderKeith
« Reply #8 - Posted 2011-05-25 11:25:46 »

If collision detection is what you want, line-line collision tests are cheap. I posted some code in shared code about the quickest method. This is not the same as the distance until collision though.

You can also calc the centroid of the polygon and cache it, as well as a circular bound or radius, then just do distance checks of each poly's centroid to the other's and see if it's less than the sum of the radii. In my straightedge project there's a KPolygon class for this.

Offline Abuse

JGO Coder


Medals: 11


falling into the abyss of reality


« Reply #9 - Posted 2011-05-25 12:50:13 »

I hope you only want discrete collision detection.
Continuous CD and/or collision response will make your ears bleed. (though CCD does make CR a little easier)

I recall an excellent tutorial on the algorithms for detecting collisions between various primitive types(based around Separating Axis Theorem); let me see if Google can find it.....
Hmm, THIS isn't what I was looking for - but it might very well come in handy to you.

:edit:

Ah, THIS is what I was looking for.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CyanPrime
« Reply #10 - Posted 2011-05-25 18:19:41 »

Vector2f.sub in slick doesn't return a vector, so I had to make the code like this:

1  
2  
3  
4  
5  
6  
7  
if (i < ourEdges.length) {
                edge = new Vector2f(ourEdges[i][1].x - ourEdges[i][0].x, ourEdges[i][1].y - ourEdges[i][0].y);
            }
           
            else {
               edge = new Vector2f(theirEdges[i - ourEdges.length][1].x - theirEdges[i - ourEdges.length][0].x, theirEdges[i - ourEdges.length][1].y - theirEdges[i - ourEdges.length][0].y);
            }


Now the collision works, but figuring out how to use it is proving to be a problem. Right now I got two problems. Shakes when you collide, and the ability to go through the polygon walls.

This is my movement code. gpos is my global positioning class, and the rest should speak for it's self. If not, I'll be happy to answer any questions, but please help.

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  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
public void moveLeft(GPos gpos, Wall[] walls, float moveSpeed){
      float prevX = x;
      x -= moveSpeed;
     
      if(x < 0)
         x = 0;
     
      float prevWorldX = gpos.worldX;
     
      if(x - gpos.worldX < 320){
         gpos.worldX -= moveSpeed;
         
         if(gpos.worldX < 0)
            gpos.worldX = 0;
      }
     
        int wallHit = -1;
        for(int i = 0; i < walls.length; i++){
           while(colision(walls[i].vertices)){
                 wallHit = i;
                 x+= 0.1f;
                 computeVertices();
            }
        }
       
        if(wallHit >= 0){
           //System.out.println("collision detected!");
          //x = prevX;
          boosting = false;
           boostingLeft = false;
           boostDelay = 20;
           boostTime = 0;
           boostsFired = 0;
           rapidBoostDelay = 0;
           gpos.worldX = prevWorldX;
        }
   }
   
   public void moveRight(GPos gpos, Wall[] walls, float moveSpeed){
      float prevX = x;
      x += moveSpeed;
      if(x + width > 800)
         x = 800 - width;
     
      float prevWorldX = gpos.worldX;
     
      if(x - gpos.worldX > 320 && gpos.worldX < (800 - 640)){
         gpos.worldX += moveSpeed;
         
         if(gpos.worldX > (800 - 640))
            gpos.worldX = (800 - 640);
      }
     
        int wallHit = -1;
        for(int i = 0; i < walls.length; i++){
           while(colision(walls[i].vertices)){
                 wallHit = i;
                 x-= 0.1f;
                 computeVertices();
            }
        }
       
        if(wallHit >= 0){
           //x = prevX;
          boosting = false;
           boostingRight = false;
           boostDelay = 20;
           boostTime = 0;
           boostsFired = 0;
           rapidBoostDelay = 0;
           gpos.worldX = prevWorldX;
        }
   }
   
   public void moveUp(GPos gpos, Wall[] walls, float moveSpeed){
      float prevY = y;
      y -= moveSpeed;
       
      if(y < 0)
         y = 0;
     
      float prevWorldY = gpos.worldY;
     
      if(y - gpos.worldY < 320){
         gpos.worldY -= moveSpeed;
         
         if(gpos.worldY < 0)
            gpos.worldY = 0;
      }
     
      int wallHit = -1;
        for(int i = 0; i < walls.length; i++){
           while(colision(walls[i].vertices)){
                 wallHit = i;
                 y+= 0.1f;
                 computeVertices();
            }
        }
       
        if(wallHit >= 0){
           //y = prevY;
          boosting = false;
           boostingUp = false;
           boostDelay = 20;
           boostTime = 0;
           boostsFired = 0;
           rapidBoostDelay = 0;
           gpos.worldY = prevWorldY;
        }
   }
   
   public void moveDown(GPos gpos, Wall[] walls, float moveSpeed){
      float prevY = y;
      y += moveSpeed;
       
      if(y + height > 600)
         y = 600 - height;
     
      float prevWorldY = gpos.worldY;
     
      if(y - gpos.worldY > 320 && gpos.worldY < (600 - 480)){
         gpos.worldY += moveSpeed;
         
         if(gpos.worldY > (600 - 480))
            gpos.worldY = (600 - 480);
      }
     
      int wallHit = -1;
        for(int i = 0; i < walls.length; i++){
           while(colision(walls[i].vertices)){
                 wallHit = i;
                 y-= 0.1f;
                 computeVertices();
            }
        }
       
        if(wallHit >= 0){
           //y = prevY;
          boosting = false;
           boostingDown = false;
           boostDelay = 20;
           boostTime = 0;
           boostsFired = 0;
           rapidBoostDelay = 0;
           gpos.worldY = prevWorldY;
        }
}
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.

CogWheelz (14 views)
2014-07-30 21:08:39

Riven (21 views)
2014-07-29 18:09:19

Riven (14 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (32 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (42 views)
2014-07-23 21:16:32

Riven (29 views)
2014-07-23 21:07:15

Riven (30 views)
2014-07-23 20:56:16
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!