Help With Seperating Axis Theorem

Started by chaucer, April 19, 2017, 11:01:18 pm

Previous topic - Next topic

chaucer

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. 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. ^^

Blizzard

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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

KK20

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.

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

chaucer

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.  :^_^\':

KK20

April 20, 2017, 10:49:55 pm #4 Last Edit: April 21, 2017, 02:45:08 am by KK20
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

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

chaucer

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!

chaucer

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


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

Blizzard

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. :)
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.