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.
poly to rect makes no difference in my opinion, an unnecessary optimisation unless necessary for some reason.
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.
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:
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:
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? :’(
Here is some debug info of whats going on when I get the false positive.
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
okay I needed to calcualte edges, but now that I’ve done that it’s still giving false posititves.
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:
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:
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]);
}
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.
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.
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.
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.
Vector2f.sub in slick doesn’t return a vector, so I had to make the code like this:
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.
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;
}
}