Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (577)
games submitted by our members
Games in WIP (498)
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  
  Simplified Advanced Collision Detection (SAT)(v2.1) (updated 8/4/2011)  (Read 11083 times)
0 Members and 1 Guest are viewing this topic.
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Posted 2011-08-03 19:36:58 »

So I've been working on a little game and in beginning I was simply using Slick and regular rectangles for collision detection.  This worked fine for a while. Even with rotated shapes still generally worked.  But then I had a bad guy that was 2x as long as he was wide.  I tried to couple 2 rectangles to him but it was having issues.  Then I ran into a problem with my "laser beam" which I was trying to use a super long rectangle(100 long x 1 wide)

Anyways, I realized I needed to learn how to better do collision detection. I kept seeing separating axis theorem and AABB(Axis Aligned Bounding Boxes) stuff.  Most of the time it was either in other language code or abstract math.

I was frustrated.  Cry

I was always running into problems with built in polygons and other issues. Specifically when it came to rotating and whatnot.
I decided to build a custom detection system from the ground up, that works for me.
It may work for you.  Its more complicated then a simple rectangular or distance check.  Grin

This is not yet optimized, but I tried to simplify it as much as I can for right now.

FYI, this currently supports ANY Convex Polygons.
You can manually set it to any polygon you want, I just have it set to auto random polygons.

[size=12pt]Separating Axis Theorem Collision Detection[/size]

[size=16pt]Basic Collision Check Version 1.1[/size]
Example of it in action: http://code.newrog.com/examples/collide_v1_1.html
Source Code: http://code.newrog.com/examples/collide_v1_1.rar
(skeleton.class is just a modified java 4k template)(I abstracted it away to not interfere with trying to read what all I did)

You may do whatever you want with it.  Some code is mine, some are abstract ideas pulled from a dozen different sites.



I start with with 2 sets of Bodies.  persecutioncomplex Pointing
You can create multiple polygons per body if you would like for more complicated shapes.

It generates a random number of points and random angle then generates a polygon.

During update, we check if A collides with B. (or vice versa)
If they do, we notify both of them

First thing we do test separation of axises

From Wikipedia

Extract Example from inside 1 polygon:
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  
public boolean collide(Poly other){
   // test separation axes of current polygon
  for(int j = count-1, i = 0; i < count; j = i, i++)
   {
      Vector v0 = vertices[j];
      Vector v1 = vertices[i];
      Vector edge = new Vector(0,0);
      edge.x = v1.x - v0.x; // edge
     edge.y = v1.y - v0.y; // edge
     
      Vector axis = edge.perp(); // Separate axis is perpendicular to the edge
     if(separatedByAxis(axis, other))
          return false;
   }
   // test separation axes of other polygon
  for(int j = other.count-1, i = 0; i < other.count; j = i, i++)
   {
      Vector v0 = other.vertices[j];
      Vector v1 = other.vertices[i];
      Vector edge2 = new Vector(0,0);
      edge2.x = v1.x - v0.x; // edge
     edge2.y = v1.y - v0.y; // edge
     
      Vector axis = edge2.perp(); // Separate axis is perpendicular to the edge
     if(separatedByAxis(axis, other))
         return false;
   }
   return true;
}
public void calculateInterval(Vector axis) {
   this.min = this.max = (float) vertices[0].dot(axis);
   for (int i = 1; i < count; i++) {
      float d = (float) vertices[i].dot(axis);
      if (d < this.min)
         this.min = d;
      else if (d > this.max)
         this.max = d;
   }
}

public boolean intervalsSeparated(float mina, float maxa, float minb, float maxb) {
   return (mina > maxb) || (minb > maxa);
}

public boolean separatedByAxis(Vector axis, Poly poly) {
   calculateInterval(axis);
   mina = min;
   maxa = max;
   poly.calculateInterval(axis);
   minb = poly.min;
   maxb = poly.max;
   return intervalsSeparated(mina, maxa, minb, maxb);
}



You first need to find the perpendicular to each edge.  and then simply do a check against distance
If the distance between them overlaps, we have collision!

For interactive version of how all this works. Please visit http://www.metanetsoftware.com/technique/tutorialA.html

I plan to add more features/functions in other future versions/posts. If you see anything that could be simplified or optimized. Let me know.  Typically i want it to keep it as simple/short as possible so others can modify it to work with their code.

Future version's features:
Will add to this post as I add them.


p.s. I am an "Appreciation whore" Cheesy

[size=16pt]SAT Version 2.1:  Displacement[/size]

Example:http://code.newrog.com/examples/collide_v2_1.html
Source Code: http://code.newrog.com/examples/deflection_collide_v2.rar

Left click to toggle between the 2 bodies.  1 can push the other, whereas 1 resists movements.

You either are pushing or resisting toggle modes to demonstrate 2 separate principles.
As you can see in the picture, the blue shape will show the minimal deflected position. Its not perfect but its a fairly good behavior.

"Experience is what you get when you did not get what you wanted"
Offline civicdude95

Senior Newbie


Medals: 1



« Reply #1 - Posted 2011-08-03 20:17:38 »

Well done sir, I have always had trouble understanding SAT and this presentation makes it a lot easier to understand. Thumbs up for you. Smiley

Read about simple game development.
Download your free copy of Prospectus
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #2 - Posted 2011-08-03 20:51:16 »

Well done sir, I have always had trouble understanding SAT and this presentation makes it a lot easier to understand. Thumbs up for you. Smiley

Your welcome!
If you or anyone else would like me to modify this to help better fit it to your code or to better improve it overall. Just let me know!

edit:
for the one who requested I include a multiply bodies version(albeit a bit messy and inefficient method) here you go
multiple bodies brute force checked against all other bodies.
Example of multiple bodies:  http://code.newrog.com/examples2/collide_v1_2.html
Source Code: http://code.newrog.com/examples2/collide_v1_2.rar


"Experience is what you get when you did not get what you wanted"
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline counterp

Senior Member


Medals: 11



« Reply #3 - Posted 2011-08-03 22:46:15 »

For rectangles aligned with the axes you can also use this method (I couldn't find one already released so I wrote in Java based on pseudo-code :\, I guess I'll release here since related):

1  
2  
3  
   public static final boolean rectangleIntersectsRectangle(int x, int y, int w, int h, int x2, int y2, int w2, int h2) {
      return !(x + w < x2 || x2 + w2 < x || y + h < y2 || y2 + h2 < y);
   }


Pretty simple, just checks if the rectangles are completely separate of each other (to the left, right, above, or below each other).

It's very fast.
Offline Cero
« Reply #4 - Posted 2011-08-04 04:05:12 »

For rectangles aligned with the axes you can also use this method (I couldn't find one already released so I wrote in Java based on pseudo-code :\, I guess I'll release here since related):

1  
2  
3  
   public static final boolean rectangleIntersectsRectangle(int x, int y, int w, int h, int x2, int y2, int w2, int h2) {
      return !(x + w < x2 || x2 + w2 < x || y + h < y2 || y2 + h2 < y);
   }


Pretty simple, just checks if the rectangles are completely separate of each other (to the left, right, above, or below each other).

It's very fast.


This is a copy from the Java.awt.Rectangle which I have copied into my 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  
public boolean intersects(Rectangle r)
    {
      int tw = (int)this.width;
      int th = (int)this.height;
      int rw = (int)r.width;
      int rh = (int)r.height;
           
      if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0)
       {
          return false;
      }
           
      int tx = (int)this.x;
      int ty = (int)this.y;
      int rx = (int)r.x;
      int ry = (int)r.y;
           
      rw += rx;
      rh += ry;
      tw += tx;
      th += ty;
      //      overflow || intersect
     return ((rw < rx || rw > tx) &&
         (rh < ry || rh > ty) &&
         (tw < tx || tw > rx) &&
         (th < ty || th > ry));
    }

You're saying, your method works just as well and faster ?

Offline counterp

Senior Member


Medals: 11



« Reply #5 - Posted 2011-08-04 06:17:44 »

Well technically, mine has the ability to skip the rest of checks in certain cases (i.e. if the first check is true x + w < x2, then it can return right away) in worst case scenario it should be just as fast as that method you post (which has to check all boundaries before returning true or false).

However... realistically, they are doing close to the same thing (also I didn't see a point in adding a check when I know that my rectangle bounds will always be above 0, not that having a check is costly) so the speed difference is very negligible.
Offline Cero
« Reply #6 - Posted 2011-08-04 16:39:56 »

Well technically, mine has the ability to skip the rest of checks in certain cases (i.e. if the first check is true x + w < x2, then it can return right away) in worst case scenario it should be just as fast as that method you post (which has to check all boundaries before returning true or false).

However... realistically, they are doing close to the same thing (also I didn't see a point in adding a check when I know that my rectangle bounds will always be above 0, not that having a check is costly) so the speed difference is very negligible.

I did some tests.

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  
long start = System.nanoTime()/1000l;
       Rectangle rect[][] = new Rectangle[500][500];
       Boolean resultOfIntersect1[][] = new Boolean[500][500];
       
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             rect[x][y] = new Rectangle(Util.getRandom(1, 9000), Util.getRandom(1, 9000), Util.getRandom(1, 9000),Util.getRandom(1, 9000));
          }
       }
       System.out.println("Random Rects ini took   "+((System.nanoTime()/1000l)-start)+"us");

       start = System.nanoTime()/1000l;
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             boolean r = rect[x][y].intersects(rect[0][0]);
             resultOfIntersect1[x][y] = r;
          }
       }
       


       System.out.println("My Intersects took      "+((System.nanoTime()/1000l)-start)+"us");
       
       
       
       start = System.nanoTime()/1000l;
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             boolean a = rect[x][y].intersects2(rect[0][0]);
             if (a != resultOfIntersect1[x][y]) System.out.println("Intersect1 for "+rect[x][y].toString()+" and "+rect[0][0].toString()+" is "+resultOfIntersect1[x][y]+" but intersects 2 said its "+a);
          }
       }

       
       System.out.println("Intersect2 took         "+((System.nanoTime()/1000l)-start)+"us");


 
1  
2  
3  
4  
5  
6  
7  
8  
9  
public static final boolean intersects2(int x, int y, int w, int h, int x2, int y2, int w2, int h2)
    {
        return !(x + w < x2 || x2 + w2 < x || y + h < y2 || y2 + h2 < y);
    }
   
    public boolean intersects2(Rectangle in)
    {
        return intersects2((int)this.x, (int)this.y, (int)this.width, (int)this.height, (int)in.x, (int)in.y, (int)in.width, (int)in.height);
    }


Intersects2, your intersects.  All the casting to int, I do for my intersect aswell.

Turns out yours is often slower, and more importantly incorrect.
When I did [100][100] rects, one error came up. Here I use 500x500 and like 15 come up.
Not that this much, but still incorrect sometimes.

Example:
1  
Intersect1 for Rect  [x=8215.0,y=5611.0,width=2504.0,height=1335.0] and Rect  [x=6732.0,y=6946.0,width=2714.0,height=5927.0] is false but intersects 2 said its true


Edit: Yours is sometimes faster, sometimes slower, I dont know.

Offline Cero
« Reply #7 - Posted 2011-08-04 16:45:20 »

1  
2  
3  
4  
5  
6  
Rectangle one = new Rectangle (6732, 6946, 2714, 5927);
       Rectangle two   = new Rectangle (8215, 5611, 2504, 1335);
       
       System.out.println("Intersect1 for "+one.toString()+" and "+two.toString()+" is \n"
             + "Intersects 1: "+two.intersects(one)+
             "\nIntersects 2: "+two.intersects2(one));


Result

1  
2  
3  
Intersect1 for Rect  [x=6732.0,y=6946.0,width=2714.0,height=5927.0] and Rect  [x=8215.0,y=5611.0,width=2504.0,height=1335.0] is 
Intersects 1: false
Intersects 2: true


seems like your algorithm says its true whever their borders lie on top of each other, and the java intersects doesn't.
Drawing on paper, FTW =D

Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #8 - Posted 2011-08-04 20:45:51 »

Moved to OP

"Experience is what you get when you did not get what you wanted"
Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #9 - Posted 2011-08-04 20:52:10 »

Thanks you very much for this article!  Kiss

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #10 - Posted 2011-08-04 22:08:36 »

Added deflection example and source code
See bottom of Original Post

Thanks all for the feedback and support so far!

I am hoping that these help some people who hate or are confused by collision detection.


I will continue to try and expand upon these for as long as I can.



"Experience is what you get when you did not get what you wanted"
Offline Cero
« Reply #11 - Posted 2011-08-04 23:44:20 »

I am hoping that these help some people who hate or are confused by collision detection.

Absolutely, I'm lazy as hell, and thus not very good at math.
So it helps a lot.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 12


Game Engineer


« Reply #12 - Posted 2011-08-05 23:06:05 »

Cool, this looks good. Smiley

See my work:
OTC Software
Offline counterp

Senior Member


Medals: 11



« Reply #13 - Posted 2011-08-06 14:25:49 »

Edit: Yours is sometimes faster, sometimes slower, I dont know.

Yeah, it depends on the rectangle. For example if you feed mine with the parameters (5, 5, 100, 100, 120, 5, 100, 100) mine should be faster, since the first clause will return true (x + w < x2).

Still, I'm surprised yours is faster in some cases, I thought they would at worst case be equal Tongue

And if you don't want borders included you would swap all < and > signs for <= and >=.
Offline Cero
« Reply #14 - Posted 2011-08-06 14:33:34 »

actually, I have tested a third method. The intersects method of Slick.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public boolean intersects(Rectangle other)
    {
       if (((int)x >= ((int)other.x + (int)other.width)) || (((int)x + (int)width) <= (int)other.x))
       {
         return false;
      }
       
      if (((int)y >= ((int)other.y + (int)other.height)) || (((int)y + (int)height) <= (int)other.y))
      {
         return false;
      }
     
        return true;
    }


and this is ALWAYS faster than the other two. (Note I added the = here too, this didnt check aswell)

Offline counterp

Senior Member


Medals: 11



« Reply #15 - Posted 2011-08-06 14:35:42 »

Sweet Cheesy I'll benchmark now

EDIT: This is only benchmark I did but it shows in this case mine is faster:

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  
public class Main {

   public static void main(String[] args) {
      long start, end;
      double total = 0;
      int trials = 10000000;

      for (int i = 0; i < trials; i++) {
         start = System.nanoTime();
         intersects(5, 5, 100, 100, 120, 5, 100, 100);
         end = System.nanoTime();
         total += end - start;
      }

      total /= trials;

      System.out.println("Average trial 1: " + total);

      total = 0;

      for (int i = 0; i < trials; i++) {
         start = System.nanoTime();
         intersects2(5, 5, 100, 100, 120, 5, 100, 100);
         end = System.nanoTime();
         total += end - start;
      }

      total /= trials;

      System.out.println("Average trial 2: " + total);
   }

   public static final boolean intersects(int x, int y, int w, int h, int x2, int y2, int w2, int h2) {
      if (x >= x2 + w2 || x + w <= x2) {
         return false;
      }
      if (y >= y2 + h2 || y + h <= y2) {
         return false;
      }
      return true;
   }

   public static final boolean intersects2(int x, int y, int w, int h, int x2, int y2, int w2, int h2) {
      return !(x + w < x2 || x2 + w2 < x || y + h < y2 || y2 + h2 < y);
   }

}
Offline Cero
« Reply #16 - Posted 2011-08-06 15:07:07 »

I tested your code and they were like the same, but yours was 3ms faster

Its' interesting because in my 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 static void main(String[] args) throws Exception
    {
       int times = 100;
       
       for(int i=0;i<times;i++)
       {
          doPerformanceTest(i);
       }
       
       System.out.println("Done it "+times+" times");
       
       
    }
   
    public static void doPerformanceTest(int i)
    {
       long start;
       long i1, i2, i3;
       Rectangle rect[][] = new Rectangle[500][500];
       
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             rect[x][y] = new Rectangle(Util.getRandom(1, 9000), Util.getRandom(1, 9000), Util.getRandom(1, 9000),Util.getRandom(1, 9000));
          }
       }

       start = System.nanoTime()/1000l;
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             rect[x][y].intersectsAWT(rect[0][0]);
          }
       }
       i1 = ((System.nanoTime()/1000l)-start);
       
       
       
       start = System.nanoTime()/1000l;
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             rect[x][y].intersects2(rect[0][0]);
          }
       }
       i2 = ((System.nanoTime()/1000l)-start);
       
       
       start = System.nanoTime()/1000l;
       for (int y=0;y<rect[0].length;y++)
       {
          for (int x=0;x<rect.length;x++)
          {
             rect[x][y].intersects(rect[0][0]);
          }
       }
       i3 = ((System.nanoTime()/1000l)-start);
       
       System.out.println("AWT Intersect took      "+i1+"us");
       System.out.println("Intersect2 took      "+i2+"us");
       System.out.println("Slick Intersect3 took      "+i3+"us");
       
       if (i3 > i1 || i3 > i2) System.out.println("#"+i+"  I3 was slower");
       else
       {
          long which = (Math.max(i2, i1));
          System.out.println("#"+i+"  I3 was "+(which-i3)+"us faster");
       }
    }


Slick intersect is always always faster than the other two.

Offline counterp

Senior Member


Medals: 11



« Reply #17 - Posted 2011-08-06 15:35:43 »

It's probably the random factor. And it's not 3ms faster. It's 3 NANO seconds faster Tongue really not a big deal
Offline Cero
« Reply #18 - Posted 2011-08-06 15:48:02 »

well whatever

just to note though: without the = all my collision logic doesnt work. people are getting stuck in the walls and stuff, its madness =D

Online Roquen
« Reply #19 - Posted 2012-03-07 17:07:37 »

Ah.  I was just gonna post an N2 separation test code pretty close to this.  Note:

1  
2  
3  
4  
5  
  Vector edge = new Vector(0,0);
  edge.x = v1.x - v0.x; // edge
 edge.y = v1.y - v0.y; // edge
     
  Vector axis = edge.perp(); // Separate axis is perpendicular to the edge


can be replaced by
1  
Vector axis = new Vector(v1.y - v0.y, v0.x - v1.x);
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.

xsi3rr4x (22 views)
2014-04-15 18:08:23

BurntPizza (17 views)
2014-04-15 03:46:01

UprightPath (31 views)
2014-04-14 17:39:50

UprightPath (15 views)
2014-04-14 17:35:47

Porlus (31 views)
2014-04-14 15:48:38

tom_mai78101 (57 views)
2014-04-10 04:04:31

BurntPizza (115 views)
2014-04-08 23:06:04

tom_mai78101 (214 views)
2014-04-05 13:34:39

trollwarrior1 (182 views)
2014-04-04 12:06:45

CJLetsGame (189 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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!