间歇性碰撞检测

Question

间歇性碰撞检测

4

我一直在研究如何检测游戏中两个物体之间的碰撞。目前所有物体都是垂直移动的，但我希望保持其他运动方式的选择。这是一个经典的2D垂直空间射击游戏。

目前，我会循环遍历每个物体，检查是否发生碰撞：

for(std::list<Object*>::iterator iter = mObjectList.begin(); iter != mObjectList.end();) {
    Object *m = (*iter);
    for(std::list<Object*>::iterator innerIter = ++iter; innerIter != mObjectList.end(); innerIter++ ) {
            Object *s = (*innerIter);

            if(m->getType() == s->getType()) {
                break;
            }

            if(m->checkCollision(s)) {
                m->onCollision(s);
                s->onCollision(m);
            }
        }
    }

这是我检测碰撞的方法：

bool checkCollision(Object *other) {
        float radius = mDiameter / 2.f;
        float theirRadius = other->getDiameter() / 2.f;
        Vector<float> ourMidPoint = getAbsoluteMidPoint();
        Vector<float> theirMidPoint = other->getAbsoluteMidPoint();

        // If the other object is in between our path on the y axis
        if(std::min(getAbsoluteMidPoint().y - radius, getPreviousAbsoluteMidPoint().y - radius) <= theirMidPoint.y &&
            theirMidPoint.y <= std::max(getAbsoluteMidPoint().y + radius, getPreviousAbsoluteMidPoint().y + radius)) {

                // Get the distance between the midpoints on the x axis
                float xd = abs(ourMidPoint.x - theirMidPoint.x);

                // If the distance between the two midpoints
                // is greater than both of their radii together
                // then they are too far away to collide
                if(xd > radius+theirRadius) {
                    return false;
                } else {
                    return true;
                }

        }
        return false;
}

问题在于它会随机正确检测到碰撞，但有时却完全没有检测到。这不是if语句从对象循环中脱离的问题，因为这些对象确实具有不同的类型。对象距屏幕顶部越近，检测到碰撞的几率就越大。靠近屏幕底部，检测到碰撞的几率就越小甚至根本没有。然而，这些情况并不总是发生。对象的直径很大（10和20）以查看是否存在问题，但帮助不大。

编辑-更新代码

bool checkCollision(Object *other) {
    float radius = mDiameter / 2.f;
    float theirRadius = other->getDiameter() / 2.f;
    Vector<float> ourMidPoint = getAbsoluteMidPoint();
    Vector<float> theirMidPoint = other->getAbsoluteMidPoint();

    // Find the distance between the two points from the center of the object
    float a = theirMidPoint.x - ourMidPoint.x;
    float b = theirMidPoint.y - ourMidPoint.y;

    // Find the hypotenues
    double c = (a*a)+(b*b);
    double radii = pow(radius+theirRadius, 2.f);

    // If the distance between the points is less than or equal to the radius
    // then the circles intersect
    if(c <= radii*radii) {
        return true;
    } else { 
        return false;
    }
}

- rcapote

你是否已经按照Beta最新答案中建议的更改进行了修改（即不再将半径之和平方两次）？如果这解决了你的问题，你应该接受Beta的答案。如果没有解决，你应该说明仍然存在的问题。 - Gareth McCaughan

3个回答

2

这个逻辑是错误的：

if(std::min(getAbsoluteMidPoint().y - radius, getPreviousAbsoluteMidPoint().y - radius) <= theirMidPoint.y &&
        theirMidPoint.y <= std::max(getAbsoluteMidPoint().y + radius, getPreviousAbsoluteMidPoint().y + radius))
{
  // then a collision is possible, check x
}

花括号内的逻辑也是错误的，但这应该会产生假阳性而不是假阴性。检查在时间间隔内是否发生了碰撞可能很棘手；我建议首先在当前时间检查碰撞，并使其正常工作。当您检查碰撞（现在）时，不能独立地检查x和y，必须查看对象中心之间的距离。

编辑：

修改后的代码仍然不完全正确。

// Find the hypotenues
double c = (a*a)+(b*b); // actual hypotenuse squared
double radii = pow(radius+theirRadius, 2.f); // critical hypotenuse squared

if(c <= radii*radii) { // now you compare a distance^2 to a distance^4
    return true; // collision
}

应该是这样的：

这应该是这样的：

double c2 = (a*a)+(b*b); // actual hypotenuse squared
double r2 = pow(radius+theirRadius, 2.f); // critical hypotenuse squared

if(c2 <= r2) {
    return true; // collision

}

或者这样：

double c2 = (a*a)+(b*b); // actual hypotenuse squared
double c = pow(c2, 0.5); // actual hypotenuse
double r = radius + theirRadius; // critical hypotenuse

if(c <= r) {
    return true; // collision

}

- Beta

谢谢您的建议。我回去修改了y轴上的检测，使用了与x轴相同的方法，但是结果仍然相同。有时候会正确地检测到碰撞，而有时候则完全没有检测到。这是否表明问题可能出现在其他地方？ - rcapote

-1

你的内部循环需要从mObjectList.begin()开始，而不是iter。

内部循环需要遍历整个列表，否则在外部循环进展更远时会错过碰撞候选项。

- Aatif Khan

谢谢，但问题仍然存在。 :( - rcapote

我的第一个答案是错误的。我假设你正在比较两个不同的列表，而不是列表本身。你尝试过使用相同的碰撞标准来检查x和y坐标吗？我认为x坐标检查是正确的，应该用于y坐标。我不明白为什么你需要先前的y坐标。 - Aatif Khan

我使用之前的坐标是因为我认为碰撞是由于移动步骤而出现问题。如果我的精灵移动12个像素，而其他对象只有10个像素，则可能无法检测到碰撞。 - rcapote

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- anatolyg · Accepted Answer

当两个圆形物体的中心距离足够小时，它们会发生碰撞。您可以使用以下代码来检查此情况：

double distanceSquared =
    pow(ourMidPoint.x - theirMidPoint.x, 2.0) +
    pow(ourMidPoint.x - theirMidPoint.x, 2.0);
bool haveCollided = (distanceSquared <= pow(radius + theirRadius, 2.0));

为了检查两个时间点之间是否发生了碰撞，可以在时间间隔的开始和结束时检查碰撞；然而，如果物体移动得非常快，碰撞检测可能会失败（我猜你已经遇到了这个问题，对于屏幕底部速度最快的掉落物）。

以下方法可能使碰撞检测更可靠（虽然仍不完美）。假设物体以恒定速度移动，则它们的位置是时间的线性函数：

our_x(t) = our_x0 + our_vx * t;
our_y(t) = our_y0 + our_vy * t;
their_x(t) = their_x0 + their_vx * t;
their_y(t) = their_y0 + their_vy * t;

现在你可以将它们之间的（平方）距离定义为时间的二次函数。找到它最小值的时间（即其导数为0），如果这个时间属于当前时间区间，计算最小值并检查是否发生碰撞。

这应该足以几乎完美地检测碰撞；如果您的应用程序与自由落体物体密切相关，您可能需要将运动函数细化为二次函数：

our_x(t) = our_x0 + our_v0x * t;
our_y(t) = our_y0 + our_v0y * t + g/2 * t^2;