Быстрое обнаружение столкновений для вставки кругов в 2D-плоскость - PullRequest
Новая
       11

Быстрое обнаружение столкновений для вставки кругов в 2D-плоскость

3 голосов
/ 17 мая 2009

Я знаю, что есть много сообщений об обнаружении столкновений, как правило, для спрайтов, перемещающихся по 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 ]

3 голосов
/ 17 мая 2009

Разделите ваше окно на w на h блоки. Вы будете поддерживать массив w на h, dist. dist[x][y] содержит размер наибольшего круга, который может быть центрирован в (x, y). (Вы можете использовать пиксели в качестве блоков, хотя мы будем обновлять весь массив с каждым размещенным кружком, поэтому вы можете выбрать более крупные блоки для повышения скорости за счет небольшого уменьшения плотности упаковки.)

1009 * инициализация * Изначально установите все dist[x][y] на min(x, y, w - x, h - y). Это кодирует пределы, заданные ограничительной рамкой, являющейся окном. Процедура обновления

Каждый раз, когда вы добавляете в окно круг, скажем один, расположенный в (a, b) с радиусом 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. (Если вы хотите случайным образом выбрать такое местоположение, найдите полный список действительных местоположений, а затем случайным образом выберите одно.)

2 голосов
/ 17 мая 2009

Честно говоря, имея всего 20-25 кругов, вы не получите большого прироста скорости, используя более сложный алгоритм или структуру данных (например, quadtree или kd-tree ). Все быстро для маленьких n .

Вы абсолютно уверены, что это узкое место в вашем приложении? Вы профилировали? Если да, то способ ускорить это - микрооптимизация, а не продвинутые алгоритмы. Вы делаете много итераций в цикле while, потому что большая часть плоскости небезопасна?

0 голосов
/ 11 сентября 2009

Просто набросок, так как это решение довольно сложное.

Если вы хотите гарантировать, что всегда найдете место, где можно поставить кружок, если это возможно, вы можете сделать следующее. Рассмотрим каждый существующий круг C. Мы попытаемся найти место, где мы можем разместить новый круг так, чтобы он касался C. Для каждого круга D (кроме C), который достаточно близок к C, будет диапазон углов. где размещение нового круга под одним из этих углов вокруг C заставит его пересекаться с D. Некоторая геометрия даст вам этот диапазон. Точно так же для каждой из четырех границ, которые достаточно близки к C, будет диапазон углов, где размещение новой окружности под одним из этих углов будет пересекать ее с границей. Если все эти интервалы охватывают все 360 градусов вокруг C, то вы не можете поместить кружок рядом с C, и вам придется пробовать следующий круг, пока больше не будет кандидатов на C. Если вы найдете место для размещения нового круга Вы можете отодвинуть его на некоторое случайное расстояние от C, чтобы все ваши новые круги не обязательно были смежными с существующим кругом, если в этом нет необходимости.

0 голосов
/ 17 мая 2009

Вы можете разбить свою плоскость на множество маленьких прямоугольников (немного quadtree -related) и сохранить, какие прямоугольники будут поражены хотя бы одним из кругов. Когда вы ищете точку вставки, вам просто нужно искать некоторые «пустые» (которые не требуют случайных переходов и возможны в постоянное время).

Количество и созвездие прямоугольников можно вычислить по радиусу.

...