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;
}