Allegro.cc Forums » Programming Questions » Collision Detection (SAT)

 Collision Detection (SAT)
someone972
Member #7,719
August 2006

I read this tutorial about the Separating Axis Theorem. I understand the theory, I just don't know how to implement the axis checking.??? If anyone could help me out it would be greatly appreciated.

EDIT: Nevermind, I finally figured it out.

Update:
How to do polygon-polygon collision detection:

Hopefully this helps anyone who comes across this post, I used the information in this tutorial, modifying the code to make it work, and the explanation of SAT in the link above.
It is necessary to understand the theory if you want to understand the code, or you can just use the code if you don't need any modifications.

Take note that this only detects a collision, it doesn't provide any response, and it is only for polygon-polygon collisions, round objects have a different implementation.

First we want an object that holds an x-y coordinate:

```class vector2d
{
public:
int x,y;
};
```

We then need to create an object that will hold the polygon data:

```class polygon2d
{
public:
std::vector<vector2d> verticies; //this can be replaced with another
//type of container if necessary
int num_verticies;
};
```

So far this should be pretty straight forward. Now we need the function that checks for collisions, it will be explained at the end:

 1 int collision_detect(polygon2d& p1, polygon2d& p2) 2 { 3 vector2d axis; 4 double tmp,minA,maxA,minB,maxB; 5 6 for(int i = 0; i < p1.num_verticies;i++) 7 { 8 if(i == 0) 9 { 10 axis.x = p1.verticies[p1.num_verticies-1].y - p1.verticies[0].y; 11 axis.y = p1.verticies[0].x - p1.verticies[p1.num_verticies-1].x; 12 } 13 else 14 { 15 axis.x = p1.verticies[i-1].y - p1.verticies.y; 16 axis.y = p1.verticies.x - p1.verticies[i-1].x; 17 } 18 minA = maxA = p1.verticies[0].x * axis.x + p1.verticies[0].y * axis.y; 19 for(int i = 1; i < p1.num_verticies; i++) 20 { 21 tmp = p1.verticies.x * axis.x + p1.verticies.y * axis.y; 22 if (tmp > maxA) 23 maxA = tmp; 24 else if (tmp < minA) 25 minA = tmp; 26 } 27 minB = maxB = p2.verticies[0].x * axis.x + p2.verticies[0].y * axis.y; 28 for(int i = 1; i < p2.num_verticies; i++) 29 { 30 tmp = p2.verticies.x * axis.x + p2.verticies.y * axis.y; 31 if (tmp > maxB) 32 maxB = tmp; 33 else if (tmp < minB) 34 minB = tmp; 35 } 36 if (maxA < minB || minA > maxB) 37 return 0; 38 } 39 for(int i = 0; i < p2.num_verticies;i++) 40 { 41 if(i == 0) 42 { 43 axis.x = p2.verticies[p2.num_verticies-1].y - p2.verticies[0].y; 44 axis.y = p2.verticies[0].x - p2.verticies[p2.num_verticies-1].x; 45 } 46 else 47 { 48 axis.x = p2.verticies[i-1].y - p2.verticies.y; 49 axis.y = p2.verticies.x - p2.verticies[i-1].x; 50 } 51 minA = maxA = p1.verticies[0].x * axis.x + p1.verticies[0].y * axis.y; 52 for(int i = 1; i < p1.num_verticies; i++) 53 { 54 tmp = p1.verticies.x * axis.x + p1.verticies.y * axis.y; 55 if (tmp > maxA) 56 maxA = tmp; 57 else if (tmp < minA) 58 minA = tmp; 59 } 60 minB = maxB = p2.verticies[0].x * axis.x + p2.verticies[0].y * axis.y; 61 for(int i = 1; i < p2.num_verticies; i++) 62 { 63 tmp = p2.verticies.x * axis.x + p2.verticies.y * axis.y; 64 if (tmp > maxB) 65 maxB = tmp; 66 else if (tmp < minB) 67 minB = tmp; 68 } 69 if (maxA < minB || minA > maxB) 70 return 0; 71 } 72 return 1; 73 };

This function returns 1 if there was a collision, 0 if there wasn't.

And now on to explaining it.

First:

```vector2d axis;
double tmp,minA,maxA,minB,maxB;
```

Axis is the coordinate that all the sides are projected onto. MinB, maxB, minA and maxA are the points that are projected the farthest apart, this is explained better later on.

http://www.allegro.cc/files/attachment/593933

Next:

```for(int i = 0; i < p1.num_verticies;i++)
{
...
}
```

This will loop through all the sides of the polygon, if you read the information on the page linked at the very top, you will know that all these sides need to be colliding for a collision to occur.

http://www.allegro.cc/files/attachment/593934

Next:

```if(i == 0)
{
axis.x = p1.verticies[p1.num_verticies-1].y - p1.verticies[0].y;
axis.y = p1.verticies[0].x - p1.verticies[p1.num_verticies-1].x;
}
else
{
axis.x = p1.verticies[i-1].y - p1.verticies<i>.y;
axis.y = p1.verticies<i>.x - p1.verticies[i-1].x;
}
```

These lines of code will determine the axis from the side being suppiled from the for loop.

http://www.allegro.cc/files/attachment/593935

To be continued...

______________________________________
As long as it remains classified how long it took me to make I'll be deemed a computer game genius. - William Labbett
Theory is when you know something, but it doesn't work. Practice is when something works, but you don't know why. Programmers combine theory and practice: Nothing works and they don't know why. -Unknown
I have recklessly set in motion a chain of events with the potential to so-drastically change the path of my life that I can only find it to be beautifully frightening.

 De Baimbo Member #8,944 August 2007 Interesting tecnique, but why should I create a new class "vector2d" instead of using a normal array, e.g. coords[2], to store the x and y coordinates of a vertex?I'm almost a newbie so that question may sound stupid, but so far arrays worked well for my collisions.
 nonnus29 Member #2,606 August 2002 The choice on how represent vectors is completely arbitrary. You'll see different projects do it with arrays or structs of individual coordinates. It does make interoperating with things difficult at times; like if you want to use ODE (open dynamics engine) with your code and you've coded math one way and they've done it another.Nice pictures by the way, did you make them?
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads