java - libgdx中的圆矩形碰撞边检测

Question

我花了几个小时寻找解决方案:我正在用libgdx开发一个自上而下的小游戏(也许这与我使用的引擎很重要)。现在，我必须在角色(圆形)和墙(矩形)之间实现碰撞检测。如果希望滑动，我希望角色在碰撞时沿着墙壁滑动。
让我解释:

• If i am moving 45 degrees right up i can collide with the down, the left or the corner of a wall.
• If i collide with the left i want to stop x-movement and move only up. If i leave the wall then i want to go on moving right up. The same with the down side (stop y-movement)
• If i collide with the Corner i want to stop movement (sliding not possible).

我实际上是在检查矩形的左线是否与我的圆相交。然后我检查墙的左线和我的圆和墙的底线和我的圆之间的交点。取决于发生哪个相交，我将圆的x/y位置设置回零并将x/y速度设置为0。问题是，大多数情况下不是碰撞 bt发生重叠。因此，即使实际上圆只会与右侧碰撞，底部检查也将返回true。在这种情况下，两个相交测试都将返回true，并且我将重设两个速度，例如在转角碰撞中。
我怎么解决这个问题？这是检测碰撞以及碰撞边或角的更好方法吗？
我不需要矩形的确切碰撞点。

编辑:
我要说的是，rects并不仅仅与x轴平行旋转。

Answer 1

您可以在下面找到有关圆/矩形碰撞的说明，但请注意，您可能不需要这种碰撞。例如，如果您的角色有一个矩形边界框，则该算法将更简单，更快。即使您使用的是圆形，也可能有一种更简单的方法足以满足您的目的。

我虽然为此编写了代码，但是会花费太长时间，因此这里仅作解释:

这是角色圈的示例运动，包括其最后一个(上一个)和当前位置。墙矩形显示在其上方。



这是相同的移动，虚线表示圆在此移动中扫过的区域。扫掠区域为胶囊状。



计算这两个对象的碰撞将很困难，因此我们需要以不同的方式进行。如果您查看上一张图片中的胶囊，您会发现它只是沿每个方向延伸圆弧半径的移动线。我们可以将“延伸”从移动线移动到矩形墙。这样，我们得到一个圆角矩形，如下图所示。



当且仅当胶囊与壁矩形碰撞时，移动线才会与该扩展的(圆形)矩形碰撞，因此它们在某种程度上是等效的并且可以互换。

由于此碰撞计算仍然是轻而易举且相对昂贵的，因此您可以首先在扩展的壁矩形(这次是非圆形的)与运动线的边界矩形之间进行快速碰撞检查。您可以在下面的图像中看到这些矩形-它们都被点缀。这是一种快速简便的计算方式，在您玩游戏时，可能不会与> 99％的时间的特定墙矩形发生重叠，并且碰撞计算将在此处停止。



但是，如果有重叠，则字符圈可能会与墙矩形发生冲突，但是不确定，这将在后面进行演示。

现在，您需要计算运动线本身(而不是其边界框)与扩展墙矩形之间的交点。您可能会找到一种算法，该算法如何在线执行此操作，搜索直线/矩形交点或直线/aabb交点(aabb =轴对齐边界框)。矩形是轴对齐的，这使计算更简单。该算法可以为您提供一个或多个交点，因为可能有两个-在这种情况下，您选择最接近直线起点的一个。以下是这种相交/碰撞的示例。



当您得到一个交点时，应该很容易计算出该交点位于扩展矩形的哪一部分。您可以在上面的图像中看到这些部分，这些部分用红线分隔并标有一个或两个字母(l-左，r-右，b-底部，t-顶部，tl-顶部和左侧等)。
如果相交在部分l，r，b或t(中间是单个字母的那一部分)上，则说明操作完成。字符圆和墙矩形之间肯定存在碰撞，您知道在哪一侧。在上面的示例中，它位于底部。您可能应该使用4个变量，例如isLeftCollision，isRightCollision，isBottomCollsion和isTopCollision。在这种情况下，您可以将isBottomCollision设置为true，而其他3个设置为false。

但是，如果相交在拐角处的两个字母部分，则需要进行额外的计算以确定字符圆与墙矩形之间是否存在实际碰撞。下图显示了拐角上的3个此类相交，但只有2个存在实际的圆角矩形碰撞。



为了确定是否发生碰撞，您需要找到运动线和以原始非延伸壁矩形的最近角为中心的圆之间的交点。该圆的半径等于字符圆的半径。同样，您可以在Google上搜索线/圆交点算法(甚至libgdx都可以)，它并不复杂，应该很难找到。
bl部分上没有线/圆的交集(也没有圆/矩形碰撞)，并且br和tr部分上没有交集/碰撞。
在br情况下，将isRightCollision，isBottomCollsion都设置为true，在tr情况下，将isRightCollision和isTopCollision都设置为true。

您还需要注意一种边缘情况，您可以在下图中看到它。



如果上一步的移动在扩展矩形的角上但在内部矩形角的半径之外(没有碰撞)，则可能发生这种情况。
要确定是否是这种情况，只需检查运动凝视点是否在扩展矩形内。
如果是这样，则在初始矩形重叠测试(延伸的壁矩形和运动线的边界矩形之间)之后，应跳过线/矩形相交测试(因为在这种情况下可能没有任何相交并且仍然存在圆/矩形碰撞) )，还可以简单地基于运动指示点确定您位于哪个角，然后仅检查与该角的圆的线/圆交点。如果存在相交，则存在字符圆/墙矩形碰撞，否则不存在。

毕竟，冲突代码应该很简单:

// x, y - character coordinates
// r - character circle radius
// speedX, speedY - character speed
// intersectionX, intersectionY - intersection coordinates
// left, right, bottom, top - wall rect positions

// I strongly recomment using a const "EPSILON" value
// set it to something like 1e-5 or 1e-4
// floats can be tricky and you could find yourself on the inside of the wall
// or something similar if you don't use it :)

if (isLeftCollision) {
    x = intersectionX - EPSILON;
    if (speedX > 0) {
        speedX = 0;
    }
} else if (isRightCollision) {
    x = intersectionX + EPSILON;
    if (speedX < 0) {
        speedX = 0;
    }
}

if (isBottomCollision) {
    y = intersectionY - EPSILON;
    if (speedY > 0) {
        speedY = 0;
    }
} else if (isTopCollision) {
    y = intersectionY + EPSILON;
    if (speedY < 0) {
        speedY = 0;
    }
}

[更新]

这是一个简单的方法，我相信有效地实现路段-aabb交集应该足以满足您的目的。这是经过稍微修改的Cohen-Sutherland algorithm。您也可以查看this answer的第二部分。

public final class SegmentAabbIntersector {

    private static final int INSIDE = 0x0000;
    private static final int LEFT = 0x0001;
    private static final int RIGHT = 0x0010;
    private static final int BOTTOM = 0x0100;
    private static final int TOP = 0x1000;

    // Cohen–Sutherland clipping algorithm (adjusted for our needs)
    public static boolean cohenSutherlandIntersection(float x1, float y1, float x2, float y2, Rectangle r, Vector2 intersection) {

        int regionCode1 = calculateRegionCode(x1, y1, r);
        int regionCode2 = calculateRegionCode(x2, y2, r);

        float xMin = r.x;
        float xMax = r.x + r.width;
        float yMin = r.y;
        float yMax = r.y + r.height;

        while (true) {
            if (regionCode1 == INSIDE) {
                intersection.x = x1;
                intersection.y = y1;
                return true;
            } else if ((regionCode1 & regionCode2) != 0) {
                return false;
            } else {
                float x = 0.0f;
                float y = 0.0f;

                if ((regionCode1 & TOP) != 0) {
                    x = x1 + (x2 - x1) / (y2 - y1) * (yMax - y1);
                    y = yMax;
                } else if ((regionCode1 & BOTTOM) != 0) {
                    x = x1 + (x2 - x1) / (y2 - y1) * (yMin - y1);
                    y = yMin;
                } else if ((regionCode1 & RIGHT) != 0) {
                    y = y1 + (y2 - y1) / (x2 - x1) * (xMax - x1);
                    x = xMax;
                } else if ((regionCode1 & LEFT) != 0) {
                    y = y1 + (y2 - y1) / (x2 - x1) * (xMin - x1);
                    x = xMin;
                }

                x1 = x;
                y1 = y;
                regionCode1 = calculateRegionCode(x1, y1, r);
            }
        }
    }

    private static int calculateRegionCode(double x, double y, Rectangle r) {
        int code = INSIDE;

        if (x < r.x) {
            code |= LEFT;
        } else if (x > r.x + r.width) {
            code |= RIGHT;
        }

        if (y < r.y) {
            code |= BOTTOM;
        } else if (y > r.y + r.height) {
            code |= TOP;
        }

        return code;
    }
}

这是一些代码示例用法:

public final class Program {

    public static void main(String[] args) {

        float radius = 5.0f;

        float x1 = -10.0f;
        float y1 = -10.0f;
        float x2 = 31.0f;
        float y2 = 13.0f;

        Rectangle r = new Rectangle(3.0f, 3.0f, 20.0f, 10.0f);
        Rectangle expandedR = new Rectangle(r.x - radius, r.y - radius, r.width + 2.0f * radius, r.height + 2.0f * radius);

        Vector2 intersection = new Vector2();

        boolean isIntersection = SegmentAabbIntersector.cohenSutherlandIntersection(x1, y1, x2, y2, expandedR, intersection);
        if (isIntersection) {
            boolean isLeft = intersection.x < r.x;
            boolean isRight = intersection.x > r.x + r.width;
            boolean isBottom = intersection.y < r.y;
            boolean isTop = intersection.y > r.y + r.height;

            String message = String.format("Intersection point: %s; isLeft: %b; isRight: %b; isBottom: %b, isTop: %b",
                    intersection, isLeft, isRight, isBottom, isTop);
            System.out.println(message);
        }

        long startTime = System.nanoTime();
        int numCalls = 10000000;
        for (int i = 0; i < numCalls; i++) {
            SegmentAabbIntersector.cohenSutherlandIntersection(x1, y1, x2, y2, expandedR, intersection);
        }
        long endTime = System.nanoTime();
        double durationMs = (endTime - startTime) / 1e6;

        System.out.println(String.format("Duration of %d calls: %f ms", numCalls, durationMs));
    }
}

这是我从执行此命令得到的结果:

Intersection point: [4.26087:-2.0]; isLeft: false; isRight: false; isBottom: true, isTop: false
Duration of 10000000 calls: 279,932343 ms

请注意，这是i5-2400 CPU上的台式机性能。在Android设备上，速度可能会慢得多，但我认为仍然绰绰有余。
我只是对此进行了表面测试，所以如果您发现任何错误，请告诉我。

如果使用此算法，我相信对于起点在扩展墙矩形的拐角处的情况，您不需要特殊处理，因为在这种情况下，您将获得直线起点处的交点以及碰撞检测程序将继续进行下一步(线-圆碰撞)。