libgdx中的Circle-Rectangle碰撞侧检测 [英] Circle-Rectangle collision side detection in libgdx
问题描述
我花了几个小时寻找解决方案：我正在用libgdx开发一个小型自上而下的游戏（也许这对我使用的引擎很重要）。现在我必须在我的角色（圆圈）和墙（矩形）之间实现碰撞检测。如果可以滑动，我希望角色在碰撞时沿着墙壁滑动。
让我解释一下：
I have spent hours looking for the solution to this: I am developing a little top-down game with libgdx (maybe it matters what engine i am using). Now i have to implement the collision detection between my character (circle) and the wall (rectangle). I want the character to slide along the wall on collision, if sliding is possible. Let me explain:
- 如果我向上移动45度，我可以与向下，
左边或墙角。
- 如果我与左边相撞，我想停止x移动并向上移动。如果我离开墙壁，那么我想继续前进。相同的
与下方（停止y移动）
- 如果我与角落碰撞我想停止移动（滑动不可能）。
我实际上要做的是检查矩形的左边是否与我的圆相交。然后我检查左边的墙和我的圆圈以及墙的底线和我的圆圈之间的交叉点。根据哪个交点发生，我设置了我的圆圈的x / y，并将x / y速度设置为0.问题是，大多数情况下不是碰撞而是重叠发生。所以底部检查返回true，即使实际上圆圈只会与右边碰撞。在这种情况下，两个交叉点测试都将返回true，我将重置两个速度，就像在Corner碰撞中一样。
我该如何解决这个问题？是否有更好的方法来检测碰撞和碰撞的侧面或角落？
我不需要在矩形的一侧确切的碰撞点。
What i am doing actually is to check if the left line of the rectangle intersects my circle. Then i check intersection between the left line of wall and my circle and the bottom line of wall and my circle. Depending on which intersection occuret i set back x/y possition of my circle and set x/y Speed to 0. The Problem is, that most times not a collision bt an overlap occures. So the bottom check returns true, even if in reality the circle would only collide with the right. In this case both intersection test would return true and i would reset both speeds like on the Corner collision. How can i solve this Problem? Is ther a better way to detect collision and collision side or corner? I don't Need the exact Point of collision just the side of the rectangle.
编辑：
我不得不说，rects不会与x轴平行旋转。
I have to say, that the rects aren't rotated just parallel to the x-axis.
推荐答案
您可以在下面找到圆/矩形碰撞的解释，但请注意，这种类型的碰撞可能不是您的需要所必需的。例如，如果您的角色有一个矩形边界框，则算法会更简单，更快捷。即使您使用的是圆圈，也可能有一种更简单的方法可以满足您的需要。
You can find an explanation for circle/rectangle collision below, but please note that this type of collision might not be necessary for your needs. If, for example, you had a rectangle bounding box for your character the algorithm would be simpler and faster. Even if you are using a circle, it is probable that there is a simpler approach that is good enough for your purposes.
我虽然为此编写代码，但是这需要太长时间，所以这里只是一个解释：
I though about writing the code for this, but it would take too long so here is only an explanation:
这是你的角色圈的一个示例运动，其最后（前一个）和当前位置。墙上方显示墙面矩形。
¥
这是相同的动作，虚线表示圆圈在此移动中扫过的区域。扫掠区域是胶囊形状。
$
$
计算这两个对象的碰撞是很困难的，因此我们需要采用不同的方式。如果你看一下上一张图像上的胶囊，你会看到它只是通过圆的半径在每个方向上延伸的运动线。我们可以将扩展从移动线移动到墙矩形。这样我们得到一个圆角矩形，如下图所示。
当且仅当胶囊与墙壁碰撞时，移动线将与此扩展（圆角）矩形碰撞矩形，所以它们在某种程度上是等价和可互换的。
Here is a example movement of your character circle, with its last (previous) and current positions. Wall rectangle is displayed above it.
Here is that same movement, dotted lines represent the area the circle sweeps in this move. The sweep area is capsule shaped.
It would be difficult to calculate the collision of these two object, so we need to do this differently. If you look at the capsule on the previous image, you will see that it is simply the movement line extended in every direction by the radius of the circle. We can move that "extension" from the movement line to the wall rectangle. This way we get a rounded rectangle like on the image below.
The movement line will collide with this extended (rounded) rectangle if and only if the capsule collides with the wall rectangle, so they are somehow equivalent and interchangeable.
由于这个碰撞计算仍然是非常重要且相对昂贵的，你可以先在扩展墙之间进行快速碰撞检查矩形（这次是非圆形的）和运动线的边界矩形。您可以在下面的图像上看到这些矩形 - 它们都是点缀的。这是一个快速简便的计算，当您玩游戏时，可能不会与特定的墙矩形重叠> 99％的时间，碰撞计算将在此处停止。
¥
$
如果有重叠，可能是角色圆与墙矩形发生碰撞，但它不确定，稍后将会证明。
Since this collision calculation is still non-trivial and relatively expensive, you can first do a fast collision check between the extended wall rectangle (non-rounded this time) and the bounding rectangle of the movement line. You can see these rectangles on the image below - they are both dotted. This is a fast and easy calculation, and while you play the game there will probably NOT be an overlap with a specific wall rectangle >99% of the time and collision calculation will stop here.
If however there is an overlap, there is probably a collision of the character circle with wall rectangle, but it is not certain as will be demonstrated later.
现在你需要计算运动线本身（不是它的边界框）和扩展墙矩形之间的交点。您可以找到一个算法如何在线执行此操作，搜索线/矩形交点或线/ aabb交点（aabb =轴对齐边界框）。矩形是轴对齐的，这使计算更简单。该算法可以为您提供一个或多个交叉点，因为有两个可能是交叉点 - 在这种情况下，您可以选择最接近该线的起点。以下是此交叉/碰撞的示例。
$
$
当你得到一个交叉点时，应该很容易计算这个交叉点的扩展矩形的哪个部分位于。您可以在上面的图像上看到这些部分，用红线分隔并标有一个或两个字母（l - 左，r - 右，b - 底部，t - 顶部，tl - 顶部和左侧等）。
如果交叉点在l，r，b或t部分（中间的单字母），那么你就完成了。字符圆和墙矩形之间肯定存在碰撞，你知道在哪一边。在上面的例子中，它位于底部。您应该使用4个变量，例如 isLeftCollision ， isRightCollision ， isBottomCollsion 和 isTopCollision 。在这种情况下，您将 isBottomCollision 设置为true，而其他3将保持为false。
Now you need to calculate the intersection between the movement line itself (not its bounding box) and the extended wall rectangle. You can probably find an algorithm how to do this online, search for line/rectangle intersection, or line/aabb intersection (aabb = Axis Aligned Bounding Box). The rectangle is axis-aligned and this makes the calculation simpler. The algorithm can give you intersection point or points since it is possible that there are two - in this case you choose the closest one to the starting point of the line. Below is an example of this intersection/collision.
When you get an intersection point, it should be easy to calculate on which part of the extended rectangle this intersection is located. You can see these parts on the image above, separated by red lines and marked with one or two letters (l - left, r - right, b - bottom, t - top, tl - top and left etc).
If the intersection is on parts l, r, b or t (the single letter ones, in the middle) then you are done. There is definitely a collision between character circle and wall rectangle, and you know on which side. In the example above, it is on the bottom side. You should probably use 4 variables called something like isLeftCollision, isRightCollision, isBottomCollsion and isTopCollision. In this case you would set isBottomCollision to true, while the other 3 would remain at false.
但是，如果交叉点位于角上，在两个字母的部分上，需要进行额外的计算以确定字符圆和墙矩形之间是否存在实际碰撞。下图显示了角落上的3个这样的交叉点，但是只有2个实际的圆形 - 矩形碰撞。
¥
要确定是否存在碰撞，您需要找到移动线与居中的圆圈之间的交点在原始非延伸墙矩形的最近角落。该圆的半径等于字符圆的半径。再一次，你可以google for line / circle intersection算法（甚至可能是libgdx有一个），它并不复杂，不应该很难找到。
没有行/圆交集（没有bl部分上有圆/矩形碰撞，并且br和tr部分有交叉/碰撞。
在br情况下你设置 isRightCollision ， isBottomCollsion 为true，在tr情况下，您设置 isRightCollision 和 isTopCollision 为真。
However, if the intersection is on the corner, on the two-letter sections, additional calculations are needed to determine if there is an actual collision between character circle and wall rectangle. Image below shows 3 such intersections on the corners, but there is an actual circle-rectangle collision on only 2 of them.
To determine if there is a collision, you need to find an intersection between the movement line and the circle centered in the closest corner of the original non-extended wall rectangle. The radius of this circle is equal to the radius of character circle. Again, you can google for line/circle intersection algorithm (maybe even libgdx has one), it isn't complex and shouldn't be hard to find.
There is no line/circle intersection (and no circle/rectangle collision) on bl part, and there are intersections/collisions on br and tr parts.
In the br case you set both isRightCollision, isBottomCollsion to true and in the tr case you set both isRightCollision and isTopCollision to true.
您还需要注意一个边缘情况，您可以在下图中看到它。
$
$
如果上一步的移动在扩展矩形的角落结束，但在内部矩形角的半径（没有碰撞）。
要确定是否是这种情况，只需检查移动凝视点是否在扩展矩形内。
如果是，在初始矩形重叠测试之后（在扩展墙矩形和移动线的边界矩形之间），你应该跳过线/矩形交叉测试（因为在这种情况下可能没有任何交叉并且仍然是圆/矩形碰撞），并且还可以简单地根据移动指示点确定您所在的角落，然后仅检查与该角落圆圈的直线/圆形交点。如果有交叉点，则会出现字符圆/墙矩形碰撞，否则不会。
There is also one edge case you need to look out for, and you can see it on the image below.
This can happen if the movement of previous step ends in the corner of the the extended rectangle, but outside the radius of the inner rectangle corner (there was no collision).
To determine if this is the case, simply check if movement staring point is inside the extended rectangle.
If it is, after the initial rectangle overlap test (between extended wall rectangle and bounding rectangle of movement line), you should skip line/rectangle intersection test (because in this case there might not be any intersection AND still be a circle/rectangle collision), and also simply based on movement stating point determine which corner you are in, and then only check for line/circle intersection with that corner's circle. If there is intersection, there is a character circle/wall rectangle collision, otherwise not.
完成所有这些后，碰撞代码应该很简单：
After all of this, the collision code should be simple:
// 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算法。您还可以查看此答案的第二部分。
Here is a simple and I believe efficient implementation of segment-aabb intersection that should be good enough for your purposes. It is a slightly modified Cohen-Sutherland algorithm. Also you can check out the second part of 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;
}
}
以下是一些代码示例用法：
Here is some code example usage:
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));
}
}
这是我从执行此操作得到的结果：
This is the result I get from executing this:
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设备上它可能会慢很多，但我相信仍然绰绰有余。
我只是在表面上测试过，所以如果你发现任何错误，请告诉我。
Please note that this is desktop performance, on an i5-2400 CPU. It will probably be much slower on Android devices, but I believe still more than sufficient.
I only tested this superficially, so if you find any errors, let me know.
如果您使用此算法，我相信您不需要特殊处理，因为起始点位于扩展墙矩形的角落，因为在这种情况下，您将获得行的交叉点开始，碰撞检测程序将继续下一步（线圆碰撞）。
If you use this algorithm, I believe you don't need special handling for that case where starting point is in the corner of the extended wall rectangle, since in this case you will get the intersection point at line start, and the collision detection procedure will continue to the next step (line-circle collision).
这篇关于libgdx中的Circle-Rectangle碰撞侧检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
