3

我知道有很多关于碰撞检测的帖子，通常是针对在 2D 平面上移动的精灵，但我的问题略有不同。

我正在将圆圈插入 2D 平面。这些圆具有可变半径。我正在尝试优化我在平面内找到一个随机位置的方法，我可以在其中插入一个新圆圈，而不会与飞机上已经存在的任何其他圆圈发生碰撞。现在我正在使用一种非常“未优化”的方法，它只是在平面内生成一个随机点，然后将其与平面上的所有其他圆圈进行检查。

有没有办法优化这个？对于这个特定的应用程序，平面的边界一次只能容纳 20-25 个圆圈，通常存在 5-10 个。如您所料，当圆圈数接近可以容纳的最大值时，您必须测试许多点才能找到一个有效的点。它变得非常缓慢。

注意：safeDistance 是我要添加到平面的圆的半径。

这是代码：

- (CGPoint)getSafePosition:(float)safeDistance {
// Point must be far enough from edges
// Point must be far enough from other sprites

CGPoint thePoint;
BOOL pointIsSafe = NO;

int sd = ceil(safeDistance);

while(!pointIsSafe) {

    self.pointsTested++; // DEBUG

    // generate a random point inside the plane boundaries to test
    thePoint = CGPointMake((arc4random() % ((int)self.manager.gameView.frame.size.width - sd*2)) + sd, 
                           (arc4random() % ((int)self.manager.gameView.frame.size.height - sd*2)) + sd);

    if(self.manager.gameView.sprites.count > 0) {
        for(BasicSprite *theSprite in self.manager.gameView.sprites) {

            // get distance between test point and the sprite position
            float distance = [BasicSprite distanceBetweenPoints:thePoint b:theSprite.position];

            // check if distance is less than the sum of the min safe distances of the two entities
            if(distance < (safeDistance + [theSprite minSafeDistance])) {
                // point not safe
                pointIsSafe = NO;
                break;
            }

            // if we get here, the point did not collide with the last tested point
            pointIsSafe = YES;
        }
    }
    else {
        pointIsSafe = YES;
    }
}

return thePoint;
}
4

4 回答 4

3

w按h块细分您的窗口。您将维护一个w按h数组，dist. dist[x][y]包含可以以 (x, y) 为中心的最大圆的大小。（您可以将像素用作块，尽管我们将在放置每个圆圈时更新整个数组，因此您可能希望选择更大的块以提高速度，但会稍微降低包装密度。）

初始化

最初，将所有设置dist[x][y]为min(x, y, w - x, h - y)。这对作为窗口的边界框给出的限制进行编码。

更新程序

每次向窗口添加一个圆时，比如说一个位于(a, b)radius 的圆，您都r需要更新.dist

每个职位所需的更新(x, y)是：

dist[x][y] = min(dist[x][y], sqrt((x - a)^2 + (y - b)^2) - r);

（显然，^2这里的意思是平方，而不是 XOR。）基本上，我们是在说：“将 dist[x][y] 设置为到刚刚放置的圆的最小距离，除非情况已经比这更糟了。” dist刚刚放置的圆圈内的点的值将是负数，但这没关系。

寻找下一个位置

然后，当您想插入下一个半径圆时q，只需扫描dist查找dist值 >=的位置q。（如果要随机选择这样的位置，请找到有效位置的完整列表，然后随机选择一个。）

于 2009-05-17T16:59:34.623 回答
2

老实说，只有 20-25 个圆圈，通过使用更高级的算法或数据结构（例如四叉树或kd-tree） ，您不会获得太多的速度提升。对于小 n 来说，一切都很快。

您确定这是您的应用程序的瓶颈吗？你有简介吗？如果是，那么您要加快速度的方法是通过微优化，而不是通过高级算法。您是否因为大部分飞机不安全而通过 while 循环进行大量迭代？

于 2009-05-17T15:56:40.940 回答
0

只是一个大纲，因为这个解决方案相当复杂。

如果您想保证在可能的情况下总能找到放置圆圈的地方，您可以执行以下操作。考虑每个现有的圆 C。我们将尝试找到一个可以放置新圆的位置，使其与 C 接触。对于每个足够接近 C 的圆 D（除了 C），都会有一系列角度在 C 周围的其中一个角度放置一个新圆将使其与 D 相交。某些几何图形将为您提供该范围。类似地，对于足够接近 C 的四个边界中的每一个，都会有一系列角度，在其中一个角度放置一个新圆将使其与边界相交。如果所有这些区间都覆盖了 C 周围的所有 360 度，那么你不能在 C 附近放置一个圆圈，你将不得不尝试下一个圆圈，直到没有更多候选 C。

于 2009-09-11T06:06:43.080 回答
0

您可以将您的平面分割成许多小矩形（与四叉树略微相关）并保存哪些矩形被至少一个圆圈击中。当您寻找插入点时，您只需要寻找一些“空”的（不需要任何随机跳转并且可以在恒定时间内）。

矩形的数量和星座可以通过半径来计算。

于 2009-05-17T16:07:20.877 回答