Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (723)
Games in Android Showcase (216)
games submitted by our members
Games in WIP (790)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Having problems implementing SAT (Separating Axis Theorem)  (Read 471 times)
0 Members and 1 Guest are viewing this topic.
Offline kingAree

Senior Newbie


Exp: 4-6 months



« Posted 2017-04-15 13:59:11 »

I have tried to follow a few guides explaining the theory behind Sat but this implementation is not working for me, Could I get some help?

here is my class with my SAT code, its part of the DevEntity class, every object that I want to implement SAT extends this class, and the vertex points are set in those classes.


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
   
   protected Vector2[] vertices = new Vector2[4];
   protected Vector2[] axis;

        public void obtainEdges(){
      axis  = new Vector2[vertices.length];
      for(int i = 0; i < vertices.length; i++){
         
         Vector2 e1 = vertices[i];
         
         Vector2 e2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
         
         Vector2 edge = e1.subtract(e2);
         
         Vector2 perp = edge.perp(edge);

         axis[i] = perp;
      }
   }
   
   public Vector2 projectAxis(Vector2 axis){
      float min = axis.dot(vertices[0]);
      float max = min;
     
      for(int i = 1; i < vertices.length; i++){
         Vector2 norm = axis.normalize(axis);
         float proj = norm.dot(new Vector2(x + vertices[i].x, y + vertices[i].y));
         
         if(proj < min){
            min = proj;
         }
         
         if(proj > max){
            max = proj;
         }
      }
     
      return new Vector2(min, max);
   }
   
   public boolean separatingAxisTheorem(){
     
      for(DevEntity e : handler.getDevWorld().getDevM().getDevEntities()){
         Vector2[] axes1 = axis;
         Vector2[] axes2 = e.axis;
     
         obtainEdges();
         if(e.equals(this))
            return false;

         for(int i = 0; i < axes1.length; i++){
            Vector2 axis = axes1[i];
           
            Vector2 p1 = projectAxis(axis);
            Vector2 p2 = e.projectAxis(axis);
           
            if(!p1.overlap(p2)){
               return false;
            }
         }
         
         for(int i = 0; i < axes2.length; i++){
            Vector2 axis = axes2[i];
           
            Vector2 p1 = projectAxis(axis);
            Vector2 p2 = e.projectAxis(axis);
           
            if(!p1.overlap(p2)){
               return false;
            }
         }
         
      }
      return true;
   }


here's my Vector Class

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
package shapegame.engine;

import java.util.Vector;

public class Vector2 {
   
   public float x, y;

   
   
   public Vector2(float x, float y){
      this.x = x;
      this.y = y;

   }
   
   public Vector2(Vector2 vec){
      this.x = vec.x;
      this.y = vec.y;

   }
   
   public float dot(Vector2 b){
      return x * b.x + y * b.y;
   }
   
   public Vector2 normalize(Vector2 vec){
      float mag = (float) Math.sqrt(vec.x * vec.x + vec.y * vec.y);
      Vector2 b = new Vector2(vec.x/mag, vec.y/mag);
      return b;
   }
   
   public Vector2 subtract(Vector2 vec){
      return new Vector2(x - vec.x, y - vec.y);

   }
   
   public Vector2 perp(Vector2 vec){
      Vector2 p = new Vector2(-vec.y, vec.x);
      return p;
   }
   
   public boolean overlap(Vector2 vec){
         if(y < vec.x || vec.y < x){
            return false;
         }
      return true;
   }

   

}


Offline bmanmcfly
« Reply #1 - Posted 2017-04-17 16:59:56 »

I had struggled with implementing a SAT algorithm, some time ago, I wound up using the algorithm supplied by libgdx (intersector)... and even once I got the premade algorithm there were still issues.

Without scrutinizing the specific code you laid out, beyond that it seems correct, even with the SAT algorithm, what I found I had to do to get it to work without tunneling was:
- copy the current position
- get the new position
- run the sat on the new position
- test the MTV to ensure that it's going to send you to the right edge
- if that test fails, then from each point on the first object make a line from each point + the movement vector and test that line for intersection.
- move the object to the coordinates of the shortest line that intersected

in that way I prevented tunneling even when movement was pushed to absurd speeds.

Good luck.

Offline kingAree

Senior Newbie


Exp: 4-6 months



« Reply #2 - Posted 2017-04-18 14:10:29 »

Thanks for the reply, I guess I'll have to do way more testing in general as the SAT method is boolean and it won't change from false no matter what I seem to do, tunnelling isn't a problem for me yet.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline bmanmcfly
« Reply #3 - Posted 2017-04-18 21:27:00 »

Thanks for the reply, I guess I'll have to do way more testing in general as the SAT method is boolean and it won't change from false no matter what I seem to do, tunnelling isn't a problem for me yet.

Unfortunately, when I tried to write the SAT algorithm for myself, it did not go well... this was the one that finally worked, but even that took some work.

https://github.com/libgdx/libgdx/blob/master/gdx/src/com/badlogic/gdx/math/Intersector.java

Unfortunately, I'm a bit too much of a noob to offer much better advice than to go through the process of drawing the lines and stepping through.

What I can do is bring up some of the factors that were holding me back:
- I was not using translated polygons, so, while I was drawing the polygons correctly, the actual polygons were at a different position.
- I was not properly calculating the projection vector, this was tricky and I didn't realize it until I started drawing all the results (that was right before I gave up on writing my own, because I realized I was just working the math wrong)
- Once I got the algorithm, I had trouble calculating the MTV, which was partly because while I was adding the speed I wasn't scaling to deltaT for the MTV calculation...

There's a lot of things that can go wrong, and I do wish I could offer better help, but I also remember how there weren't many implementations of SAT that people would share, except in c# or c++, that I could find online.  At least with the example, you can compare code that definitely does work with what you have... good luck.
Offline kingAree

Senior Newbie


Exp: 4-6 months



« Reply #4 - Posted 2017-04-20 15:45:59 »

I think drawing my axes and projections onto the screen will be the best way to help me figure this out, I definitely think that visualising these problems is one of the best ways of dealing with this, currently I am not using Polygon's, instead my shapes are just classes with the vertices defined in an array, I then draw the image/shape to the screen.

I'll have a good browse through your code, thanks for posting it.
Offline bmanmcfly
« Reply #5 - Posted 2017-04-20 17:59:10 »

I think drawing my axes and projections onto the screen will be the best way to help me figure this out, I definitely think that visualising these problems is one of the best ways of dealing with this, currently I am not using Polygon's, instead my shapes are just classes with the vertices defined in an array, I then draw the image/shape to the screen.

I'll have a good browse through your code, thanks for posting it.

Since a polygon is just an array of vertices either way, that shouldn't be an issue...

Just to be clear, that's not code that I've written, that is the intersector class that is included in libgdx.  Part of why I didn't want to risk troubleshooting the code you supplied at the top, it looks similar, and the process sounds the same, but since I struggled with the same even after having code that works, I didn't want to take many chances there.

Let us know how the visualizations work out, I suspect it will help to highlight the part that's not working.
Offline kingAree

Senior Newbie


Exp: 4-6 months



« Reply #6 - Posted 2017-04-21 09:09:34 »

I was wondering why you said you were a noob! that code was impressive, I'll post my findings back here for sure.

and true about the Polygons just being vertices although it seems creating an actual Polygon object has benefits due to being able to use AffineTransforms.
Offline bmanmcfly
« Reply #7 - Posted 2017-04-21 15:50:15 »

I was wondering why you said you were a noob! that code was impressive, I'll post my findings back here for sure.

and true about the Polygons just being vertices although it seems creating an actual Polygon object has benefits due to being able to use AffineTransforms.

I wish I could take credit for that one... I had nothing to do with it.

No, that was the people who contributed to libgdx that wrote all that, I just put it up for you because I know it's a working class and made use of it for a project I've yet to finish (even to a point where putting it as a WIP would not be embarrassing).

Pages: [1]
  ignore  |  Print  
 
 

 
buddyBro (188 views)
2017-04-05 03:38:00

CopyableCougar4 (618 views)
2017-03-24 15:39:42

theagentd (611 views)
2017-03-24 15:32:08

Rule (662 views)
2017-03-19 12:43:22

Rule (636 views)
2017-03-19 12:42:17

Rule (640 views)
2017-03-19 12:36:21

theagentd (652 views)
2017-03-16 05:07:07

theagentd (586 views)
2017-03-15 22:37:06

theagentd (426 views)
2017-03-15 22:32:18

theagentd (355 views)
2017-03-15 22:31:11
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-03-02 06:37:51
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!