Ive been trying to build a collision detection algorithm that would work for my needs, since I had to pull box2d out of the project I was working on, since there were issues that were creating more grief than was being solved.
So, I looked at a few different options, I thought AABB collisions would be simplest, but I intend to have ramps / slopes in a platform game and so simple AABB collisions won’t cut it.
After, I tried to use the intersector class with LibGDX, except that, for some reason it would not detect the collision until after the player was contained in the terrain polygon.
So, I looked around and found a bunch of sources, which I tried to convert to implement a SAT algorithm, its not 100% complete, but it seems complete enough to determine IF a collision is being detected.
http://www.dyn4j.org/2010/01/sat/
http://www.metanetsoftware.com/technique/tutorialA.html
http://www.gamedev.net/topic/619029-separating-axis-theorem/
These all seem to work out to the same…
A few things, is there a way to ensure that the polygons vectors are actually alligned to be able to compare overlap?
Could it be that I’m not getting the correct normal?
Anyway, here’s the relevant code, I’ve been trying with the debugger, and was hoping to get some insights into anything that sticks out that I’m not seeing.
In the meantime, I’ll be making an effort to draw out the tests because just looking at the numbers spitting out doesn’t seem very helpful since no matter what’s going on its not registering an overlap…
public boolean collides(Polygon poly1, Polygon poly2){
boolean check = true;
minMax1.isZero();
minMax2.isZero();
Array<Vector2> points1 = getPoints(poly1);
Array<Vector2> points2 = getPoints(poly2);
Array<Vector2> normal1 = getNormals(points1);
Array<Vector2> normal2 = getNormals(points2);
Vector2 edgeNormal;
int edgeCountA = points1.size;
int edgeCountB = points2.size;
for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
if (edgeIndex < edgeCountA) {
edgeNormal = normal1.get(edgeIndex);
} else {
edgeNormal = normal2.get(edgeIndex - edgeCountA);
}
// edgeNormal.nor();
projA = ProjectPolygon(edgeNormal, points1);
projB = ProjectPolygon(edgeNormal, points2);
if (!projA.overlap(projB)) {
Gdx.app.log("Gap detected", "no collision");
check = false;
break;
}
Gdx.app.log("If you made it this far", "There is a overlap");
}
return check;
}
private Projection ProjectPolygon(Vector2 edge, Array<Vector2> polyPoints){
// To project a point on an axis use the dot product
float dotProduct = edge.dot(polyPoints.first());
float min = dotProduct;
float max = dotProduct;
for (int i = 0; i < polyPoints.size; i++) {
dotProduct = polyPoints.get(i).dot(edge);
if (dotProduct < min) {
min = dotProduct;
} else {
if (dotProduct > max) {
max = dotProduct;
}
}
}
return new Projection(min, max);
}
public Array<Vector2> getPoints(Polygon shape){
float[] vertices = shape.getVertices();
// float[] vertices = shape.getTransformedVertices();
int numVertices = shape.getVertices().length;
Array<Vector2> points = new Array<Vector2>();
for (int i = 0; i < numVertices / 2; i++){
float x = vertices[i * 2];
float y = vertices[i * 2 + 1];
points.add(new Vector2(x,y));
}
return points;
}
public Array<Vector2> getNormals(Array<Vector2> edges) {
for (int j = 0; j < edges.size; j++){
//get the current vertex
Vector2 p1 = edges.get(j);
//get the next vertex
Vector2 p2 = edges.get(j + 1 == edges.size ? 0 : j + 1);
//subtract the two to get the edge between them
Vector2 edge = p1.sub(p2);
//The perpendicular vector is the normal
Vector2 normal = new Vector2(-edge.y, edge.x); //edge.rotate90(1);
//if the polygons are determined counter clockwise, then get the normal by shifting the
//edge 90 degrees clockwise
edges.set(j, normal);
}
return edges;
}
this is the main code, it gets used by sending the player polygon and iterating through the terrain polygons defined in tiled and loaded in the map parser.
Let me know if anything extra might be needed to help you help me, any pointers would be appreciated.
