Как оптимизировать функцию расстояния?

Разрабатывая довольно простую RTS-подобную игру, я заметил, что мои расчеты расстояния влияют на производительность.

Всегда есть дистанционные проверки, чтобы узнать, находится ли юнит в пределах досягаемости от цели, если снаряд достиг своей цели, если игрок столкнулся с пикапом, общим столкновением и т. Д. Список продолжается, и проверка на наличие Расстояние между двумя точками используется много.

Мой вопрос именно об этом. Я хочу знать, какие альтернативы есть у разработчиков игр для проверки расстояний, кроме обычного подхода sqrt (x * x + y * y), который довольно трудоемкий, если мы выполняем его тысячи раз за кадр.

Я хотел бы отметить, что я знаю о манхэттенских расстояниях и квадратах сравнений расстояний (пропуская узкое место sqrt). Что-нибудь еще?

TL; DR; Ваша проблема не в выполнении функции расстояния. Ваша проблема заключается в выполнении функции расстояния так много раз. Другими словами, вам нужна алгоритмическая оптимизация, а не математическая.

[РЕДАКТИРОВАТЬ] Я удаляю первый раздел моего ответа, потому что люди ненавидят его. Заголовок вопроса спрашивал об альтернативных функциях расстояния до редактирования.

Вы используете функцию расстояния, где вы каждый раз вычисляете квадратный корень. Тем не менее, вы можете просто заменить это без использования квадратного корня и вычислить вместо этого квадрат в квадрате. Это сэкономит вам много драгоценных циклов.

Расстояние ^ 2 = х * х + у * у;

это на самом деле распространенный трюк. Но вам нужно соответствующим образом скорректировать свои расчеты. Его также можно использовать в качестве начальной проверки перед расчетом фактического расстояния. Так, например, вместо того, чтобы вычислять фактическое расстояние между двумя точками / сферами для теста на пересечение, мы можем вместо этого вычислить Квадрат расстояния и сравнить с квадратом радиуса вместо радиуса.

Edit, задолго до того, как @ Byte56 указал, что я не читал вопрос, и что вы знали об оптимизации квадрата расстояния

Что ж, в вашем случае, к сожалению, мы в компьютерной графике почти исключительно имеем дело с евклидовым пространством , и расстояние точно определяется как Sqrt of Vector dot itselfв евклидовом пространстве.

Квадрат расстояния - это лучшее приближение, которое вы получите (с точки зрения производительности), я не вижу ничего, превосходящего 2 умножения, одно сложение и задание.

Итак, вы говорите, что я не могу оптимизировать функцию расстояния, что мне делать?

Ваша проблема не в выполнении функции расстояния. Ваша проблема заключается в выполнении функции расстояния так много раз. Другими словами, вам нужна алгоритмическая оптимизация, а не математическая.

Дело в том, что вместо проверки пересечения игрока с каждым объектом на сцене каждый кадр. Вы можете легко использовать пространственную согласованность в своих интересах и проверять только те объекты, которые находятся рядом с игроком (которые наиболее вероятно попадут / пересекаются).

Это может быть легко сделано путем фактического хранения этой пространственной информации в структуре данных с пространственным разделением . Для простой игры я бы предложил Grid, потому что он в основном прост в реализации и прекрасно вписывается в динамическую сцену.

Каждая ячейка / блок содержит список объектов, которые ограничивающий прямоугольник сетки содержит. И легко отслеживать положение игрока в этих ячейках. А для расчета расстояния вы проверяете расстояние игрока только с этими объектами внутри одной или соседних ячеек, а не со всей сцены.

Более сложный подход заключается в использовании BSP или Octrees.

Если вам нужно что-то, что остается линейным на любом расстоянии (в отличие от distance^2) и все же выглядит неопределенно круглым (в отличие от квадратного чебышевского и алмазоподобного манхэттенского расстояния), вы можете усреднить последние два метода, чтобы получить приблизительное расстояние в форме восьмиугольника:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

dist = 0.5 * (dx + dy + max(dx, dy))

Вот визуализация (контурный график) функции, благодаря Wolfram Alpha :

А вот график ее функции ошибок по сравнению с евклидовым расстоянием (радианы, только первый квадрант):

Как видите, ошибка колеблется от 0% на осях до примерно + 12% на лепестках. Немного изменив коэффициенты, мы можем уменьшить его до +/- 4%:

dist = 0.4 * (dx + dy) + 0.56 * max(dx, dy)

Обновить

Используя вышеуказанные коэффициенты, максимальная ошибка будет в пределах +/- 4%, но средняя ошибка все равно будет + 1,3%. Оптимизированный для нулевой средней ошибки, вы можете использовать:

dist = 0.394 * (dx + dy) + 0.554 * max(dx, dy)

что дает ошибки от -5% до + 3% и среднюю ошибку + 0,043%

При поиске в Интернете имени этого алгоритма я нашел похожее восьмиугольное приближение :

dist = 1007/1024 * max(dx, dy) + 441/1024 * min(dx, dy)

Обратите внимание, что это, по сути, эквивалентно (хотя показатели имеют разные значения - они дают погрешность от -1,5% до 7,5%, но ее можно массировать до +/- 4%), поскольку max(dx, dy) + min(dx, dy) == dx + dy. Используя эту форму, можно использовать minи maxвызовы в пользу:

if (dy > dx)
    swap(dx, dy)

dist = 1007/1024 * dx + 441/1024 * dy

Это будет быстрее, чем моя версия? Кто знает ... зависит от компилятора и от того, как он оптимизирует каждый для целевой платформы. Я предполагаю, что было бы довольно трудно увидеть разницу.

Иногда этот вопрос может возникать не из-за затрат на выполнение расчетов расстояния, а из-за того, сколько раз производился расчет.

В большом игровом мире со многими актерами невозможно проверять расстояние между одним актером и всеми остальными. Чем больше игроков, НПЦ и снаряды входят в мир, число сравнений , которые должны быть сделаны будет расти квадратично с O(N^2).

Один из способов уменьшить этот рост - использовать хорошую структуру данных, чтобы быстро исключать нежелательных участников из расчетов.

Мы ищем способ эффективной итерации всех действующих лиц, которые могут находиться в пределах досягаемости, при этом исключая большинство участников, которые явно находятся вне диапазона .

Если ваши актеры довольно равномерно распределены по всему мировому пространству, то подходящей структурой должна быть сетка ведер (как предполагает принятый ответ). Сохраняя ссылки на актеров в грубой сетке, вам нужно только проверить несколько соседних сегментов, чтобы охватить всех актеров, которые могут быть в пределах досягаемости, игнорируя остальных. Когда актер движется, вам может понадобиться переместить его из его старого ведра в новое.

Для актеров, которые распределены менее равномерно, квадри может быть лучше для двумерного мира, либо октрие подойдет для трехмерного мира. Это структуры более общего назначения, которые могут эффективно разделять большие области пустого пространства и небольшие области, содержащие множество действующих лиц. Для статических акторов существует разделение двоичного пространства (BSP), которое очень быстро искать, но слишком дорого обновлять в реальном времени. BSP разделяют пространство, используя плоскости, чтобы многократно разрезать его пополам, и могут быть применены к любому количеству измерений.

Конечно, накладные расходы на поддержание ваших актеров в такой структуре, особенно когда они перемещаются между разделами. Но в большом мире с множеством действующих лиц, но с небольшим диапазоном интересов, затраты должны быть намного ниже, чем те, которые несет наивное сравнение со всеми объектами.

Рассмотрение того, как увеличивается стоимость алгоритма при получении большего количества данных, имеет решающее значение для разработки масштабируемого программного обеспечения. Иногда достаточно просто выбрать правильную структуру данных . Затраты, как правило , описывается с помощью Big O обозначения .

(Я понимаю, что это не прямой ответ на вопрос, но он может быть полезен для некоторых читателей. Мои извинения, если я потратил впустую ваше время!)

Как насчет чебышевской дистанции? Для точек p, q это определяется следующим образом:

Таким образом, для точек (2, 4) и (8, 5) расстояние Чебышева равно 6, так как | 2-8 | > | 4-5 |.

Кроме того, пусть E - евклидово расстояние, а C - чебышевское расстояние. Затем:

Верхняя граница, вероятно, не очень полезна, так как вам придется вычислять квадратный корень, но нижняя граница может быть полезной - когда расстояние Чебышева достаточно велико, чтобы выйти за пределы диапазона, евклидово расстояние тоже должно быть, спасая вас от необходимости рассчитывать это.

Конечно, компромисс заключается в том, что если расстояние Чебышева находится в пределах диапазона, вам все равно придется вычислять евклидово расстояние, тратя время впустую. Есть только один способ узнать, будет ли это чистый выигрыш!

Очень простая локальная оптимизация - сначала просто проверить одно измерение.

То есть :

distance ( x1, y1 , x1, y2) > fabs (x2 - x1)

Так что просто проверка fabs (x2 - x1)в качестве первого фильтра может дать заметный выигрыш. Сколько будет зависеть от размера мира по сравнению с соответствующими диапазонами.

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

Если все соответствующие объекты отсортированы в списке в порядке координат x, то соседние объекты должны быть рядом в списке. Даже если список выходит из строя из-за того, что он не поддерживается полностью по мере перемещения объектов, тогда, учитывая известные пределы скорости, вы все равно можете уменьшить участок списка, в котором нужно искать близлежащие объекты.

В прошлом были предприняты усилия для оптимизации sqrt. Хотя это больше не относится к современным машинам, вот пример из исходного кода Quake, который использует магическое число 0x5f3759df :

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

Подробное объяснение того , что происходит здесь , можно найти в Википедии.

Короче говоря, это несколько итераций метода Ньютона (численный алгоритм, который итеративно улучшает оценку), с магическим числом, используемым для получения разумной начальной оценки.

Как указывает Трэвис, этот вид оптимизации больше не используется в современных архитектурах. И даже если бы это было так, это могло бы обеспечить только постоянное ускорение работы для вашего узкого места, в то время как алгоритмическая модернизация могла бы достичь лучших результатов.