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.问题是，大多数时候不是 碰撞 bt 重叠 发生.所以底部检查返回真，即使实际上圆圈只会与右边发生碰撞.在这种情况下，两个交叉点测试都将返回 true，并且我将重置两个速度，就像在拐角碰撞时一样.我怎么解决这个问题?有没有更好的方法来检测碰撞和碰撞侧面或角落?我不需要矩形侧面的确切碰撞点.
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 = Axis Aligned Bounding Box).矩形是轴对齐的，这使得计算更简单.该算法可以为您提供一个或多个交点，因为可能有两个 - 在这种情况下，您选择最接近线起点的一个.下面是这个交叉点/碰撞的一个例子.
当你得到一个交点时，应该很容易计算出这个交点位于扩展矩形的哪个部分.您可以在上图中看到这些部分，由红线分隔并标有一个或两个字母(l - 左，r - 右，b - 下，t - 上，tl - 上和左等).
如果交叉点位于 l、r、b 或 t 部分(中间的单个字母)，那么您就完成了.字符圆和墙矩形肯定有碰撞，你知道在哪一边.在上面的示例中，它位于底部.您可能应该使用 4 个变量，例如 isLeftCollision、isRightCollision、isBottomCollision 和 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 个发生了实际的圆矩形碰撞.
要确定是否发生碰撞，您需要找到移动线与以原始非延伸墙矩形最近角为中心的圆之间的交点.这个圆的半径等于字符圆的半径.同样，您可以搜索线/圆相交算法(甚至可能 libgdx 也有)，它并不复杂，应该不难找到.
bl 部分没有线/圆相交(也没有圆/矩形碰撞)，br 和 tr 部分有相交/碰撞.
在 br 情况下，您将 isRightCollision、isBottomCollision 都设置为 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).
相关文章