Simplified Advanced Collision Detection (SAT)(v2.1) (updated 8/4/2011)

Shared Code
#1

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. :’(

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. ;D

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.

Separating Axis Theorem Collision Detection

Basic Collision Check Version 1.1
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.

http://code.newrog.com/examples/TouchnoTouch.png

I start with with 2 sets of Bodies. :persecutioncomplex: :point:
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

http://code.newrog.com/examples/sat.png

From Wikipedia

Extract Example from inside 1 polygon:


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” :smiley:

SAT Version 2.1: Displacement

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.

http://code.newrog.com/examples/compare.png

#2

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

#3

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

#4

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):

	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.

#5

This is a copy from the Java.awt.Rectangle which I have copied into my code:

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 ?

#6

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.

#7

I did some tests.

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");

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:

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.

#8 
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

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

#9

Moved to OP

#10

Thanks you very much for this article! :-*

#11

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.

#12

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

#13

Cool, this looks good. :slight_smile:

#14

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 :stuck_out_tongue:

And if you don’t want borders included you would swap all < and > signs for <= and >=.

#15

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

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)

#16

Sweet :smiley: I’ll benchmark now

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


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);
	}

}
#17

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

Its’ interesting because in my code

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.

#18

It’s probably the random factor. And it’s not 3ms faster. It’s 3 NANO seconds faster :stuck_out_tongue: really not a big deal

#19

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

#20

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


  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

Vector axis = new Vector(v1.y - v0.y, v0.x - v1.x);