Chaos Project

Game Development => Sea of Code => Topic started by: chaucer on April 19, 2017, 11:01:18 pm

Title: Help With Seperating Axis Theorem
Post by: chaucer on April 19, 2017, 11:01:18 pm
Hello, been a while since I've posted anything, I know this isn't specifically code related, and mostly math related, however recently I've been looking into seperating axis theorem, I've found several tutorials/explanations online, and to be honest, I cant exactly understand how all the math works(yet), but I do understand what it's doing. I've managed to successfully implement detection with rectangles, however I'm still having difficulties with a couple things, and I was hoping someone here could help give some insight into the situation. ^_^

My first problem is, for some reason I can't get collision between a circle and a square to work properly, I've found a tutorial which seems to cover it but whenever I try to implement it the results are incorrect, the tutorial can be found here. (https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169) The math for circle/square collision is at the very bottom, I also have the same issue with polygons, I've tested with a simple rectangle and a square and again, it seems the math just isn't there, you can find the code for circles and polygons below( please note the code used is ES6 ).

Rectangle  * Polygon collision.

collision( a, b ) {
      var collided, corners, axes;
      collided = true;
      corners = [ a.points, b.points ]; //push all the normals into an array.
      axes = this.getAxes( a ).concat( this.getAxes( b ) ); //get new axes based on the normals
      for ( let i = 0; i < axes.length; i++ ) { //iterate through the axes we need to test.
        let axis, p1, p2 = 0;
        axis = axes[i];
        p1 = this.getProjections( axis, corners[0] ); //projections along the new axis for our first shape.(an object with min and max value).
        p2 = this.getProjections( axis, corners[1] ); //projections along the new axis for second shape.
        if ( p1.max < p2.min ) collided = false;
        if ( p2.max < p1.min ) collided = false;
        if ( !collided ) break;
      };
      return collided;
    };

Rectange * Circle Collision.

rectCirCollision( a, b ) {
    //a = rectangle, b = circle
      let circle, max, corners;
      max = -Infinity;
      corners = a.points; // get all the normals of the rectangle.
      circle = new Vector( b.x - a.center.x, b.y - a.center.y ); //create a new vector with the angle between the rect & circle.

      for ( let i = 0; i < corners.length; i++ ) { //iterate through the normals.
        let v = new Vector( corners[i].x - a.center.x, corners[i].y - a.center.y ); //new vector with angle of the center of triangle to each corner.
        let proj = v.dot( circle.normalize() ); //get our projection based on the circle vector as a unit vector.
        max = proj > max ? proj : max; // set our max distance.
      };
      if ( circle.magnitude - max - b.radius > 0 && circle.magnitude > 0 ) { //not exactly sure whats going on here, got this code from the tutorial linked above. xD
        return false;
      };
      return true;
    };



My other question is I'm not entirely sure how to handle collisions once they happen. I didn't find much info on how to push the collided sprite outside of the collision area once it's collided. Anyone know a good tutorial that could help with this? or have any advice on the matter? :D any help is much appreciated. thanks in advance. If you need more code just let me know, if you'd like i can post all the code i've written thus far. ^^
Title: Re: Help With Seperating Axis Theorem
Post by: Blizzard on April 20, 2017, 02:36:07 am
I've written some collision detection code in Blizz-ABS. Look it up, maybe you can make some sense of it (since I left lots of comments there). xD I usually have to look this stuff up each time I have to implement it.
Title: Re: Help With Seperating Axis Theorem
Post by: KK20 on April 20, 2017, 04:24:50 am
The idea is to translate the second dimension into the first dimension (i.e. a single line). Regarding the equation
circle.magnitude - max - b.radius > 0 && circle.magnitude > 0

This is saying "take the distance from the center of the rectangle to the center of the circle, minus the length from the center of the square to one of its corners given that corner is closest to the circle, minus the radius of the circle."
If it's greater than zero, you still have some space in-between the shapes.

The code looks right, so maybe the functions you have used (dot, magnitude, etc) might not be implemented correctly. If those are built-in, then IDK.

As for handling collisions, that's for another subject entirely. You're dealing with actual physics so go find articles on that. As the article said, to find the exact penetration length between two objects, you'll need to calculate the unit vector of the projection, so that will help in determining how they should move. But you'll also need the frame before they collide to get their velocities and such.

Personally I find this collision equation better suited for things like hitboxes, not so much physical, interactable objects.
Title: Re: Help With Seperating Axis Theorem
Post by: chaucer on April 20, 2017, 10:03:55 pm
Thanks Blizz, and KK20 much appreciated, and thanks for the description of what was happening on that line, it's much clearer to me now. I'll be sure to double check my functions, I'm quite positive, the dot product, is working as intended, however I'll double check my code, I'm sure I've got something mixed up somewhere, I was questioning my noramlize method, as I wasn't entirely sure it was correct, so that may be it. Also thanks for the instructions on handling the collision I think I may have skipped this line in the tutorial somehow .-. but the way you put it it makes sense.

As for it's use, I'm not really even sure I'm planning to use it xD as I'm really mostly using this for learning purposes at this moment, I am hoping to implement more detailed collision system into my game though ^^ I appreciate your advice and I'll definitely keep this in mind, in reality square vs square is really all I was looking to use out of this, but I kinda got carried away with learning how it worked haha.  :^_^\':
Title: Re: Help With Seperating Axis Theorem
Post by: KK20 on April 20, 2017, 10:49:55 pm
Nothing wrong with learning :D
Have you looked into raycasting? That sounds more up your alley.

EDIT: Another article about SAT with the "what to do after a collision" explained
http://elancev.name/oliver/2D%20polygon.htm
Title: Re: Help With Seperating Axis Theorem
Post by: chaucer on April 21, 2017, 07:05:59 pm
Haha, after you said.
QuotePersonally I find this collision equation better suited for things like hitboxes, not so much physical, interactable objects.
.

I started thinking about different ways to detect collision, and i came across a video to do with line segments, and line collision( from dev tigris on youtube ), and it hit me, xD it's funny cause I've known of raycasting for so long, but never actually looked into it, or how to use it, but from what I watched on that video, it seems like that's exactly what I'm trying to accomplish, just much less math( and headache, haha ). I'm still intending on finishing my studies into SAT, however I think I may use raycasting for my game( but it's good have options ).

Also wow, this tutorial looks a lot more in-depth, I kinda just skimmed it for now, I'll have to sit down and read through over the weekend when I have some free time. Thanks for the link brother!
Title: Re: Help With Seperating Axis Theorem
Post by: chaucer on December 24, 2017, 04:30:53 am
Just wanted to stop by and say thanks again for the help everyone, I thought I'd post an update on my progression on this topic.

Spoiler: ShowHide
(https://i.imgur.com/JVecC68.gif)


I know it's not really perfect in terms of physics, however I still intend on continuing studying this path, I've also kind of developed my own method of collision detection for polygon x polygon collison, since none of the methods I'd found were to my liking, as I wanted the ability to use convex & concave shapes, I also didn't want to limit the shapes to be reliant on being clockwise/counter clockwise, so I managed to come up with my own form of collision. If anyones interested in the code( it's in javascript ), I'd be more than happy to share it. Infact I'd be interested in hearing what others with more experience haveto say about it. I know I more than likely wouldn't have been able to get this far without outside help, so again, big thanks for the help. :)

Also hope everyone has a great holiday weekend. :D
Title: Re: Help With Seperating Axis Theorem
Post by: Blizzard on December 26, 2017, 10:13:33 am
Usually concave polygons are done by combining convex ones and testing collision of groups since the calculations are performance heavy. Do test whether your method can handle a large number of polygons. :)