ansaurus

Question

Need help with implementing collision detection using the Separating Axis Theorem

Answer 1

A:

You've added this vectOffset part which is wrong - both your asteroids' and bullets' coordinate systems are the same, right? (It must be, if the bounding box test is working.)

Are your asteroids squares? If so, then the bounding box test will always be exact, and realCollision and collision should always be identical. If not, then you're not building asteroidEdges properly - you need to iterate over the number of vertices, not 4.

But seriously, make this code a separate method and write a unit test for it, it's the only way I can run your code to see what is going on.

Keith Randall 2010-06-01 03:17:45

The asteroids are all 4 vertices, but not squares.

Eddie Ringle 2010-06-01 03:30:09

Answer 2

A:

bullVerts.insert(new Vector2D(b.x - b.w / 2.0f, b.y + b.h / 2.0f)); bullVerts.insert(new Vector2D(b.x - b.w / 2.0f, b.y - b.h / 2.0f)); bullVerts.insert(new Vector2D(b.x + b.w / 2.0f, b.y - b.h / 2.0f)); bullVerts.insert(new Vector2D(b.x + b.w / 2.0f, b.y + b.h / 2.0f));

It looks like you're creating an asteroids clone, in which case you'd expect the bullet to be rotated, but this code always treats the bullet as though it is fully upright. Could that be your problem?

Dave Kilian 2010-06-01 03:18:30

I hadn't thought of that, I'll see what I can do.

Eddie Ringle 2010-06-01 03:30:45

Scratch that, the bullets are never rotated.

Eddie Ringle 2010-06-01 03:33:10

hmm, in that case I can't find anything wrong with your code, other than that I (like Keith) don't understand what vectOffset is supposed to do. Have you tried commenting out the `float offset = ...` line and the two lines after that?

Dave Kilian 2010-06-01 04:41:27

I've since removed the offset, and it does nothing. This is a project due today, so there really isn't much else I can do from this point. Luckily it's a 10th grade trig class and not a class of programmers who will notice the difference in collision detection (really, I just need to explain the theorem, but showing it would have been nice too).

Eddie Ringle 2010-06-01 09:54:48

Answer 3

A:

Something that may help find the problem is to make the bullet a point. It might illuminate problems with other parts of your code. Plus, then if your point makes a collision but the bullet does not you will get something concrete to look at.

In other words, simplify your problem until a solution emerges. ;)

dash-tom-bang 2010-06-01 18:57:35

No collisions using points either. :(

Eddie Ringle 2010-06-01 19:37:31

Answer 4

A:

Besides the whole offset thing, which is buggy, the rest of the algorithm seems OK. Have you tried tracing through it to spot the problem?

BTW, there are several stylistic quirks that make the code hard to read at a glance:

Why the pointers everywhere, instead of allocating all of those temporary Vector2Ds on the stack?
Why CrissCross::Data::LList instead of "good old" std::vector?
Surely Vector2D has an overloaded operator-?

Here's a quick-and-dirty self-contained implementation of the algorithm. I've somewhat tested it, but make no guarantees:

#include <vector>
#include <limits>

using namespace std;

class Vector2D
{
public:
  Vector2D() : x(0), y(0) {}
  Vector2D(double x, double y) : x(x), y(y) {}

  Vector2D operator-(const Vector2D &other) const
  {
    return Vector2D(x - other.x, y - other.y);
  }

  double dot(const Vector2D &other) const
  {
    return x * other.x + y*other.y;
  }

  Vector2D perp() const
  {
    return Vector2D(-y, x);
  }

  double x,y;
};

bool checkCollisionOneSided(vector<Vector2D> &object1, vector<Vector2D> &object2)
{
  int nume = object1.size();
  for(int i=0; i<nume; i++)
    {
      Vector2D edge = object1[(i+1)%nume] - object1[i];
      Vector2D normal = edge.perp();

      double min1 = numeric_limits<double>::infinity();
      double min2 = min1;
      double max1 = -numeric_limits<double>::infinity();
      double max2 = max1;

      for(int j=0; j<object1.size(); j++)
    {
      double dot = normal.dot(object1[j]);
      min1 = std::min(min1, dot);
      max1 = std::max(max1, dot);
    }
      for(int j=0; j<object2.size(); j++)
    {
      double dot = normal.dot(object2[j]);
      min2 = std::min(min2, dot);
      max2 = std::max(max2, dot);
    }

      if(min2 > max1 || min1 > max2)
    return false;
    }
  return true;
}

bool isColliding(vector<Vector2D> &object1, vector<Vector2D> &object2)
{
  return checkCollisionOneSided(object1, object2) && checkCollisionOneSided(object2, object1);
}

2010-06-01 20:03:25

Is object1 a vector of vertices or edges?

Eddie Ringle 2010-06-01 22:03:08

Vertices. From it the edges are constructed by subtracting consecutive vertices (Vector2D edge = object1[(i+1)%nume] - object1[i];)

2010-06-01 22:05:51

Also, in case it wasn't clear, the final method to use is isColliding, by passing it two lists of vertices (in your case, four vertices each). checkCollisionOneSided is just a helper method.

2010-06-01 22:06:54

So then am I creating my list of edges correctly?

Eddie Ringle 2010-06-01 22:08:07

Yep, looks like it. I basically reimplemented youe code, but in a way that is self-contained so that I could compile if they disagree for a certain input, you have a concrete test case you can check by hand. If they both agree and the game is still buggy, you might look into the bug being in other code (e.g. the bounding boxes or centers are not being computed correctly.)

2010-06-01 22:13:19

Yeah, I'm in the process of adding your functions now.

Eddie Ringle 2010-06-01 22:58:18

Okay, your functions have replaced my old ones, and it's still acting up, which means it is elsewhere.

Eddie Ringle 2010-06-02 00:09:27

Answer 5

+1 A:

Turns out my mathematical understanding of the theorem was perfectly fine. Instead, the problem lay in the fact that I was not including the center points of the polygons in the vertice vectors.

Thank you everyone for their time.

Eddie Ringle 2010-06-02 01:13:18

ansaurus

tags:

views:

answers:

Need help with implementing collision detection using the Separating Axis Theorem

related questions