Author Topic: Help With Seperating Axis Theorem  (Read 719 times)

Offline chaucer

  • Transcended Spirit
  • ***
  • Posts: 151
  • LV: 13
  • Gender: Male
    • View Profile
Help With Seperating Axis Theorem
« on: April 20, 2017, 05:01:18 AM »
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.
Code: [Select]
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.
Code: [Select]
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. ^^

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19916
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: Help With Seperating Axis Theorem
« Reply #1 on: April 20, 2017, 08: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.
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


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

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

Offline KK20

  • Master Scripter Fixer
  • Global Moderator
  • Lexima Warrior
  • ****
  • Posts: 2988
  • LV: 369
  • Gender: Male
  • Bringer of Salt
    • View Profile
Re: Help With Seperating Axis Theorem
« Reply #2 on: April 20, 2017, 10:24:50 AM »
The idea is to translate the second dimension into the first dimension (i.e. a single line). Regarding the equation
Code: [Select]
circle.magnitude - max - b.radius > 0 && circle.magnitude > 0This 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 AceUpgrade RMXP to RMVXA performance!
XPA TilemapTilemap rewrite with many features, including custom resolution!


NNID: KK20-CP
Discord: KK20 Tyler#8901
Join the CP Discord Server

Offline chaucer

  • Transcended Spirit
  • ***
  • Posts: 151
  • LV: 13
  • Gender: Male
    • View Profile
Re: Help With Seperating Axis Theorem
« Reply #3 on: April 21, 2017, 04:03:55 AM »
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.  :^_^\':

Offline KK20

  • Master Scripter Fixer
  • Global Moderator
  • Lexima Warrior
  • ****
  • Posts: 2988
  • LV: 369
  • Gender: Male
  • Bringer of Salt
    • View Profile
Re: Help With Seperating Axis Theorem
« Reply #4 on: April 21, 2017, 04:49:55 AM »
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
« Last Edit: April 21, 2017, 08:45:08 AM by KK20 »



Other Projects
RPG Maker XP AceUpgrade RMXP to RMVXA performance!
XPA TilemapTilemap rewrite with many features, including custom resolution!


NNID: KK20-CP
Discord: KK20 Tyler#8901
Join the CP Discord Server

Offline chaucer

  • Transcended Spirit
  • ***
  • Posts: 151
  • LV: 13
  • Gender: Male
    • View Profile
Re: Help With Seperating Axis Theorem
« Reply #5 on: April 22, 2017, 01:05:59 AM »
Haha, after you said.
Quote
Personally 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!