sabato 17 marzo 2012

Collision detection challange

Me and the math are not friends, but now that I need some math equations to reach my scopes, finally I understand his importance. On last week I worked on some collision detection algorithms between circles and rectangles and after some reading of my high school books I found some solutions. Between rectangles simply I check the angle points: with a fast algorithms simply I compare 8 points (4 from the two rectangles). Between a circle and a rectangle the algorithms make a square that cover the entire circle and if the rectangle is inside this square, it checks if every pixel's border of the rectangle is on the circumference or inside the circle using the equation of the circle; I made this techniques to reduce the CPU use.

My dilemma now is that I want to check when two circles collides or how to write the algorithm that checks the collisions between rotated rectangles. On the engine that I'm working for Sonic The Hedgehog HD I need to rotate the sprites between 0° and 360° and I need also to work on rotated collisions but how? I tried to imagine 4 lines with the classic formula y=m*x+q, assign m converting the angle value with arctan but I can't realize how to write the code. But this isn't the only problem. If I decide to define a rectangle collision that won't rotate with the sprite (I'm assuming that the sprite is like a square and not a long/high rectangle) I can have other problems; the sprite can be rotated using any point of the space as center point but the collision will not rotate. Maybe some pictures can give more sense:
This is my sprite defined to the center of the space:
This is the same sprite with the same center, but with a rotation of 135°:
The sprite can be rotated without problems and without to rotate also the collision.
Now I take the same sprite but I move his center point:

But if I want to rotate the sprite by 135° from that point?
The result is weird. The sprite is rotate correctly, but the collision is fixed to that point.
Assuming to use my algorithm that checks the 4 angles from the first rect and the 4 angles from the second rect, if I rotate the collision, the detection will fail giving me wrong results. So I need to check the borders as a line defined from an equation, but how I can edit the equation if the lines will rotate using a specific point as center? And how I can check if a line cross another line when them has two limit points? I need to check pixel per pixel?  

8 commenti:

  1. I highly doubt you need to check pixel per pixel, that would use to much CPU power. Also, why would you even need to set the collisions for an object that is not centered? If so you just need to specify the area where the sprite is before-hand.

    1. Try to imagine an arm that rotate ( or something that oscillates trough a rope. The only way to have that effect is to move the center point.

  2. Hm, qual'è la tua email Xeeynamo? Non riesco a trovarla da nessuna parte, vorrei discuture con te un pò sull'hacking di Sonic CD 2011 perchè anch'io mi era intrapreso. :) La mia email è Ciao!

  3. Regarding to 2 circles collision detection, simply compute the square of the euclidean distance between the two circles centers and compare it with the sum of the 2 radiuses squared (this way you prevent your code to compute the square root).
    if distance < sum they collide
    if distance = sum they touch each other in 1 point
    else there is no collision.

    1. I did the same thing recently :) it was easy. If (SQRT(|C1X-C2X|^2 + |C1Y-C2Y|^2) <= R1+R2) the collision flag is true. C1 and C2 are the two circles, R1 and R2 is the radius. The problem is the rotated squares D:. If a line y=mx+q limited by two end points A(x1, y1) and B(x2, y2) cut or touch a square/circle, the collision comes, so with a rectangle I need to check four lines. I know also the formula to get the m from the angle, but I don't know the correct formula to check if a line cut a shape...

  4. mmm I didn't get what you need to do. Comunque se non ho capito male sei italiano :P.

  5. Hello Xeeynamo. I'd like to contact you, I have some questions about Kingdom Hearts 2 Final Mix (about the ISO itself and its editing) BTW Thanks for the patch. I know this post is not about the KH Patch but I don't think you're going to read the comments from the patch post.
    If you need mi email or another way of talking with me (for example, here) you can tell me, no problem.
    Thanks in advance,