碰撞检测问题

Question

我在游戏中的碰撞检测系统中遇到了一些问题。游戏中有几个结构物相互连接，但是当它们之间有其他结构物时，它们不应该连接。

但是，由于某种奇怪的原因，有时候直接相邻的结构物之间无法连接，而在它们后面的直线上有另一个结构物。很少情况下会产生其他奇怪的连接。

图片如下：

红色标记的节点应该被连接。

代码如下：

public void drawConnections(Graphics g) {
    ArrayList<EnergyContainer> structurecopy = (ArrayList<EnergyContainer>) Mainclass.structures.clone(); //all structures in a list
    structurecopy.remove(this); //as we are member of the list
    structurecopy.removeIf(t -> (!hasStructureInRangeWithoutObstaclesInBetween(t))); 
    structurecopy.removeIf(t -> !t.receivesEnergyfromNeighbors()); //unimportant check if it is allowed to connect (its working)
    structurecopy.forEach(t -> drawConnectionTo(t, g)); //also works fine 
}

public boolean hasStructureInRangeWithoutObstaclesInBetween(Structure structureWhichShouldBeInRange) {
    // if in Range
    if (getRange() >= Math.hypot(structureWhichShouldBeInRange.getX() - getX(),
            structureWhichShouldBeInRange.getY() - getY())){ //checks if structure is in range
        ArrayList<EnergyContainer> structureclone = (ArrayList<EnergyContainer>) Mainclass.structures.clone();
        structureclone.remove(this); //again removes itself from the list
        structureclone.remove(structureWhichShouldBeInRange); //also removes target - so it doesn't block itself
        structureclone.removeIf(t -> !t.collidesWithLine(this.getX(), structureWhichShouldBeInRange.getX(),
                this.getY(), structureWhichShouldBeInRange.getY())); //removes it when it does not collide
        return structureclone.size() == 0; //returns true when no collisions are found
    }
    return false;
}

public boolean collidesWithLine(int x1, int x2, int y1, int y2) {
    // Line Segment - Circle Collision Detection
    double dx = x2 - x1;
    double dy = y2 - y1;
    double a = dx * dx + dy * dy; //this is the distance
    double b = 2 * dx * (x1 - getX()) + 2 * dy * (y1 - getY());
    double c = getX() * getX() + getY() * getY() + x1 * x1 + y1 * y1 - 2 * (getX() * x1 + getY() * y1)
            - getCollisionRadius() * getCollisionRadius();
    double discriminant = b * b - 4 * a * c;
    return discriminant >= 0; // no intersection -> discriminant <0

}

有人能告诉我哪里出了问题吗？

- kleopi

---

我真的需要至少一个提示...而且我不想造成重复，所以... - kleopi

https://stackoverflow.com/help/no-one-answers - halfer

也许这有点宽泛。你能解释一下你使用的数学知识以及你认为问题可能出在哪里吗？ - halfer

我的建议是为 collidesWithLine() 编写单元测试，以查明是否错放了运算符。很难看出计算实际上在做什么，因此很容易混淆 '+' 和 '*'。除此之外，您的片段还没有展示完整的情况。在 collidesWithLine() 的作用域中，this 是什么？Javadoc 注释也可以帮助解决这个问题。 - SME_Dev

两点之间的距离公式为：sqrt((x2-x1)^2 + (y2-y1)^2)，但是你计算的距离没有开平方。这是我能轻易发现的问题，代码中可能还存在其他缺陷。 - ahoxha

我们可以看到 getX()、getY() 和 getCollisionRadius() 的具体内容吗？如果我们不知道这些函数返回的值是什么，就很难判断哪里出了问题。 - Uchiha Itachi

Answer 1

这里可能存在几个问题：

首先：正如Marat所述：b可能会返回0的值。如果您的getX()和getY()返回x1和y1，就会出现这种情况。如果是这样，您实际上正在执行以下操作：(2dx * 0) + (2dy * 0)。如果是这种情况，它可能会对您后面的方程式产生负面影响。

其次：很可能由于您的最终方程式，您总是返回true：

double discriminant = b * b - 4 * a * c;
//This breaks down to discriminant = b^2 * 4ac

即使此时b为0，只要a或c中有一个值大于0，return discriminant >= 0;就是真的；我强烈建议在我提到的两个部分设置断点，并检查代码执行前后的值，以便了解数学运算的情况。此外，Unity API还具有碰撞检测函数，您应该进行调查。希望这有所帮助。https://docs.unity3d.com/Manual/PhysicsSection.html。

- Uchiha Itachi

Answer 2

假设： 1. 如果我理解正确，这些是某个结构类的方法。 2. hasStructureInRangeWithoutObstaclesInBetween 是 collidesWithLine 的唯一调用者，或者至少是问题的表述方式。

因为 (2)，b 总是 0。我有一种感觉，这不是你的意图。请重新审视你的 collidesWithLine 方法。

- Marat Asadurian

---

它是同一个类。结构描述了游戏中的“建筑物”，因此是提供的图片上显示的节点之一。collidesWithLine 应该检查结构本身是否在该线上。因此，结构具有圆形“命中框”，而该线由参数给出。 - kleopi

另一种方法实际上是在两个结构之间绘制一条线，并检查每个其他结构是否在该线上。如果除了明确在该线上的起始和结束对象之外，任何对象都在该线上，则将此连接视为阻塞。 - kleopi

你注意到b始终为0了吗？ - Marat Asadurian

除非getX()和getY()返回x1和y1，否则b永远不会为0... 如果不知道这些函数返回的一些值，很难确定问题出在哪里。 - Uchiha Itachi

给Geoff：在这里呈现的代码中，x1始终是GetX()。 解释：函数的唯一调用在第16行。在此调用中，x1 = this.GetX()，y1 = this.GetY()。在第28行中，我们计算b。如果我们用传递的值替换x1和y1，我们得到b始终为0。 - Marat Asadurian