logo标签列表

使用分离轴定理实现碰撞检测需要帮助

c++collision-detectionvector
5

经过反复搜索和阅读，我发现使用SAT检测碰撞的基本过程如下:

for each edge of poly A
    project A and B onto the normal for this edge
    if intervals do not overlap, return false
end for

for each edge of poly B
    project A and B onto the normal for this edge
    if intervals do not overlap, return false
end for

然而，无论我尝试以多少种方式在代码中实现它，我都无法使其检测到碰撞。我的当前代码如下：

for (unsigned int i = 0; i < asteroids.size(); i++) {
    if (asteroids.valid(i)) {
        asteroids[i]->Update();

        // Player-Asteroid collision detection
        bool collision = true;
        SDL_Rect asteroidBox = asteroids[i]->boundingBox;

        // Bullet-Asteroid collision detection
        for (unsigned int j = 0; j < player.bullets.size(); j++) {
            if (player.bullets.valid(j)) {
                Bullet b = player.bullets[j];

                collision = true;
                if (b.x + (b.w / 2.0f) < asteroidBox.x - (asteroidBox.w / 2.0f)) collision = false;
                if (b.x - (b.w / 2.0f) > asteroidBox.x + (asteroidBox.w / 2.0f)) collision = false;
                if (b.y - (b.h / 2.0f) > asteroidBox.y + (asteroidBox.h / 2.0f)) collision = false;
                if (b.y + (b.h / 2.0f) < asteroidBox.y - (asteroidBox.h / 2.0f)) collision = false;

                if (collision) {
                    bool realCollision = false;

                    float min1, max1, min2, max2;

                    // Create a list of vertices for the bullet
                    CrissCross::Data::LList<Vector2D *> bullVerts;
                    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));
                    // Create a list of vectors of the edges of the bullet and the asteroid
                    CrissCross::Data::LList<Vector2D *> bullEdges;
                    CrissCross::Data::LList<Vector2D *> asteroidEdges;
                    for (int k = 0; k < 4; k++) {
                        int n = (k == 3) ? 0 : k + 1;
                        bullEdges.insert(new Vector2D(bullVerts[k]->x - bullVerts[n]->x,
                                                bullVerts[k]->y - bullVerts[n]->y));
                        asteroidEdges.insert(new Vector2D(asteroids[i]->vertices[k]->x - asteroids[i]->vertices[n]->x,
                                                    asteroids[i]->vertices[k]->y - asteroids[i]->vertices[n]->y));
                    }

                    Vector2D *vectOffset = new Vector2D(asteroids[i]->center.x - b.x, asteroids[i]->center.y - b.y);

                    for (unsigned int k = 0; k < asteroidEdges.size(); k++) {
                        Vector2D *axis = asteroidEdges[k]->getPerpendicular();
                        axis->normalize();
                        min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]);
                        for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) {
                            float test = axis->dotProduct(asteroids[i]->vertices[l]);
                            min1 = (test < min1) ? test : min1;
                            max1 = (test > max1) ? test : max1;
                        }
                        min2 = max2 = axis->dotProduct(bullVerts[0]);
                        for (unsigned int l = 1; l < bullVerts.size(); l++) {
                            float test = axis->dotProduct(bullVerts[l]);
                            min2 = (test < min2) ? test : min2;
                            max2 = (test > max2) ? test : max2;
                        }
                        float offset = axis->dotProduct(vectOffset);
                        min1 += offset;
                        max1 += offset;
                        delete axis; axis = NULL;
                        float d0 = min1 - max2;
                        float d1 = min2 - max1;
                        if ( d0 > 0 || d1 > 0 ) {
                            realCollision = false;
                            break;
                        } else {
                            realCollision = true;
                        }
                    }

                    if (realCollision) {
                        for (unsigned int k = 0; k < bullEdges.size(); k++) {
                            Vector2D *axis = bullEdges[k]->getPerpendicular();
                            axis->normalize();
                            min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]);
                            for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) {
                                float test = axis->dotProduct(asteroids[i]->vertices[l]);
                                min1 = (test < min1) ? test : min1;
                                max1 = (test > max1) ? test : max1;
                            }
                            min2 = max2 = axis->dotProduct(bullVerts[0]);
                            for (unsigned int l = 1; l < bullVerts.size(); l++) {
                                float test = axis->dotProduct(bullVerts[l]);
                                min2 = (test < min2) ? test : min2;
                                max2 = (test > max2) ? test : max2;
                            }
                            float offset = axis->dotProduct(vectOffset);
                            min1 += offset;
                            max1 += offset;
                            delete axis; axis = NULL;
                            float d0 = min1 - max2;
                            float d1 = min2 - max1;
                            if ( d0 > 0 || d1 > 0 ) {
                                realCollision = false;
                                break;
                            } else {
                                realCollision = true;
                            }
                        }
                    }
                    if (realCollision) {
                        player.bullets.remove(j);

                        int numAsteroids;
                        float newDegree;
                        srand ( j + asteroidBox.x );
                        if ( asteroids[i]->degree == 90.0f ) {
                            if ( rand() % 2 == 1 ) {
                                numAsteroids = 3;
                                newDegree = 30.0f;
                            } else {
                                numAsteroids = 2;
                                newDegree = 45.0f;
                            }
                            for ( int k = 0; k < numAsteroids; k++)
                                asteroids.insert(new Asteroid(asteroidBox.x + (10 * k), asteroidBox.y + (10 * k), newDegree));
                        }
                        delete asteroids[i];
                        asteroids.remove(i);
                    }
                    while (bullVerts.size()) {
                        delete bullVerts[0];
                        bullVerts.remove(0);
                    }
                    while (bullEdges.size()) {
                        delete bullEdges[0];
                        bullEdges.remove(0);
                    }
                    while (asteroidEdges.size()) {
                        delete asteroidEdges[0];
                        asteroidEdges.remove(0);
                    }

                    delete vectOffset; vectOffset = NULL;
                }
            }
        }
    }
}

bullEdges是子弹边缘的向量列表，asteroidEdges类似，bullVerts和asteroids[i].vertices显然是分别表示相应子弹或小行星的每个顶点的向量列表。

说实话，我并不需要代码纠正，只需要一双新鲜的眼睛。

问题到底是什么？realCollision 总是为 false 吗？你的边界框测试是否有效？我没有看到任何明显的问题，你应该将碰撞检测分离成一个单独的方法，这样你就可以进行单元测试。 - Keith Randall
边界框碰撞可以工作，但是真实碰撞几乎总是为false。 - Eddie
更新了最新的代码，又读了一篇文章并且按照其中的步骤进行了操作。 - Eddie
5个回答
2
原来我的定理数学理解是完全正确的。问题在于我没有将多边形的中心点包括在顶点向量中。
感谢大家抽出时间阅读。
0

除了整个偏移量的问题有点错误之外，算法的其余部分似乎都没问题。你试过跟踪它来找出问题吗？

另外，有几个风格怪癖使得代码一眼难以阅读：

  • 为什么到处都是指针，而不是在堆栈上分配所有这些临时的Vector2D？
  • 为什么使用CrissCross::Data::LList而不是“老好”的std::vector？
  • 肯定Vector2D有重载运算符-吧？

这里是一个快速而简单的自包含实现算法。我已经进行了一些测试，但不能保证完全正确：

#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);
}
object1是顶点还是边的向量？ - Eddie
顶点。通过减去连续的顶点来构造边缘（Vector2D edge = object1[(i+1)%nume] - object1[i];）。 - user168715
此外，如果不清楚的话，最终要使用的方法是isColliding，通过传递两个顶点列表（在您的情况下，每个列表有四个顶点）。checkCollisionOneSided只是一个辅助方法。 - user168715
是的，看起来是这样。我基本上重新实现了你的代码，但是以一种自包含的方式，以便我可以编译和测试它。您可以尝试从游戏内同时调用我的代码和您的代码，并比较答案；如果它们对于某个输入不一致，则您可以手动检查具体的测试用例。如果它们都同意并且游戏仍然有错误，那么您可能需要查看其他代码中的错误（例如，边界框或中心点未正确计算）。 - user168715
是的，我正在添加你的函数。 - Eddie
好的，你的函数已经替换了我的旧函数，但它仍然出现问题，这意味着问题出在其他地方。 - Eddie
0

你添加了这个 vectOffset 部分，这是错误的 - 你的陨石和子弹坐标系是相同的，对吧？（如果边界框测试有效的话，它必须是这样的。）

你的陨石是正方形吗？如果是，那么边界框测试将始终是精确的，realCollision 和 collision 应该始终是相同的。如果不是，那么你没有正确构建 asteroidEdges - 你需要迭代顶点的数量，而不是4。

但是，说真的，把这段代码作为一个单独的方法，并为它编写一个单元测试，这是我能运行你的代码并查看发生了什么的唯一方法。

小行星都有四个顶点，但不是正方形。 - Eddie
0

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));

看起来你正在创建一个类似于小行星的克隆游戏，如果是这样，你会期望子弹被旋转，但是这段代码总是把子弹当作完全直立的。这可能是你的问题吗？

我没有想到那个，我会看看我能做什么。 - Eddie
取消那个，子弹永远不会旋转。 - Eddie
嗯，在这种情况下，除了我（和Keith一样）不理解vectOffset的作用之外，我找不到你代码中的任何问题。你尝试过注释掉float offset = ...这一行和其后的两行代码吗？ - Dave Kilian
我已经删除了偏移量，但它没有任何作用。这个项目今天就要交，所以从这一点上来说，我真的没有太多其他的办法可做了。幸运的是，这是一个十年级的三角学课程，而不是一群会注意到碰撞检测差异的程序员（实际上，我只需要解释定理，但展示一下也不错）。 - Eddie
0

有时候，将子弹变成点可能会帮助找到问题所在。这可能会揭示代码其他部分的问题。此外，如果您的点发生碰撞但子弹没有，那么您将得到一些具体的东西来查看。

换句话说，简化您的问题，直到出现解决方案。 ;)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接