Улучшение функции O (N ^ 2) (все объекты повторяются по всем другим объектам)

21

Немного предыстории, я пишу эволюционную игру с другом на C ++, используя ENTT для системы сущностей. Существа ходят по 2D-карте, едят зелень или других существ, размножаются, и их черты видоизменяются.

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

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

Пример скриншота игры

Если оно хочет есть, существо, изображенное в центре, должно осмотреть себя в радиусе 149,64 (расстояние обзора) и решить, какую пищу ему следует искать, исходя из питания, расстояния и типа (мясо или растение) ,

Функция, отвечающая за нахождение каждого существа, его пища съедает около 70% времени выполнения. Упрощение того, как это написано в настоящее время, выглядит примерно так:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

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

О(N2) , но я не знаю, возможно ли это вообще.

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

РЕДАКТИРОВАТЬ: Спасибо всем за ответы! Я реализовал разные вещи из разных ответов:

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

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

Наконец, после исследования разделения пространства и рассмотрения BVH и quadtree, я выбрал последнее, так как я чувствую, что это намного проще и лучше подходит для моего случая. Я реализовал это довольно быстро, и это значительно улучшило производительность, поиск продуктов почти не занимал времени!

Теперь рендеринг - это то, что замедляет мой темп, но это проблема для другого дня. Спасибо вам всем!

Александр Родригес
источник
2
Вы экспериментировали с несколькими потоками на нескольких процессорных ядрах, работающих одновременно?
Эд Марти
6
Сколько существ у вас в среднем? Судя по снимку, он не такой высокий. Если это всегда так, разделение пространства не очень поможет. Рассматривали ли вы не запускать эту функцию на каждом тике? Вы можете запустить его каждые, скажем, 10 тиков. Результаты моделирования не должны качественно меняться.
Турмс
4
Вы выполнили какое-либо подробное профилирование, чтобы выяснить самую дорогостоящую часть оценки продуктов питания? Вместо того, чтобы смотреть на общую сложность, возможно, вам нужно посмотреть, есть ли какие-то конкретные вычисления или доступ к структуре памяти, которые душат вас.
Харабек
Наивное предложение: вы можете использовать квадродерево или связанную структуру данных вместо O (N ^ 2), как вы это делаете сейчас.
Сейрия
3
Как предложил @Harabeck, я бы покопался глубже, чтобы увидеть, где в цикле тратится все это время. Например, если для вычисления расстояния используется квадратный корень, вы можете сначала сравнить координаты XY, чтобы предварительно исключить множество кандидатов, прежде чем выполнять дорогостоящий sqrt для оставшихся. Добавление if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue;должно быть проще, чем реализация «сложной» структуры хранения, ЕСЛИ она достаточно производительная. (Связано: это может помочь нам, если вы разместите немного больше кода во внутреннем цикле)
AC

Ответы:

34

Я знаю, что вы не воспринимаете это как столкновение, однако то, что вы делаете, сталкивается с кругом, сосредоточенным на существе, со всей едой.

Вы действительно не хотите проверять еду, которая, как вы знаете, далека, только то, что рядом. Это общий совет по оптимизации столкновений. Я хотел бы призвать искать методы для оптимизации коллизий, и не ограничивать себя C ++ при поиске.


Существо в поисках пищи

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

Примечание : вы могли бы сделать меньшие ячейки, что означало бы, что круг, который вы ищете, будет выходить за пределы непосредственных соседей, что потребует от вас итерации там. Однако, если проблема заключается в том, что пищи слишком много, меньшие клетки могут означать итерации по меньшему количеству пищевых объектов, что в какой-то момент оказывается в вашу пользу. Если вы подозреваете, что это так, проверьте.

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

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

Вы можете работать с квадратом расстояния (иначе не делать sqrt), сравнивая, чтобы найти ближайший. Меньше sqrt операций означает более быстрое выполнение.


Добавлена ​​новая еда

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

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

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

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


Пропуск симуляции

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

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

Перейти к этому моменту. Вам не нужно имитировать движущихся существ.

Theraot
источник
1
"И искать только там." и ячейки, являющиеся непосредственными соседями, то есть всего 9 ячеек. Почему 9? Потому что, если существо находится прямо в углу клетки.
UKMonkey
1
@UKMonkey "Сделайте ячейки, по крайней мере, радиусом кругов, с которыми вы хотите столкнуться", если сторона ячейки - это радиус, а существо находится в углу ... ну, я полагаю, вам нужно искать только четыре в этом случае. Однако, конечно, мы можем сделать клетки меньше, что может быть полезно, если есть слишком много еды и слишком мало существ. Изменить: я уточню.
Theraot
2
Конечно - если вы хотите потренироваться, если вам нужно искать в дополнительных клетках ... но с учетом того, что у большинства клеток не будет еды (из данного изображения); это будет быстрее просто искать 9 ячеек, чем определить, какие 4 вам нужно искать.
UKMonkey
@UKMonkey, поэтому я не упомянул об этом изначально.
Theraot
16

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

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

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

Вы также можете использовать библиотеку AABB.cc.

оцелот
источник
1
Это действительно уменьшило бы сложность до N log N, но это также было бы дорогостоящим, чтобы сделать разделение. Учитывая, что мне нужно было бы выполнять разбиение каждого тика (поскольку существа перемещаются на каждый тик), это все равно стоило бы? Существуют ли решения, которые помогут разделить реже?
Александр Родригес
3
@AlexandreRodrigues вам не нужно перестраивать целое дерево каждый тик, обновлять только движущиеся части, и только когда что-то выходит за пределы конкретного контейнера AABB. Чтобы еще больше повысить производительность, вы можете захотеть откармливать узлы (оставляя некоторое пространство между дочерними элементами), чтобы вам не приходилось перестраивать целую ветвь при обновлении листьев.
Оцелот
6
Я думаю, что BVH здесь может быть слишком сложным - единая сетка, реализованная в виде хэш-таблицы, достаточно хороша.
Стивен
1
@Steven, внедрив BVH, вы можете легко расширить масштаб симуляции в будущем. И вы ничего не потеряете, если сделаете это для небольшого моделирования.
Оцелот
2

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

Ваша проблема в том, что вы продолжаете опрашивать данные. Это немного похоже на то, как если бы дети на заднем сиденье спрашивали в тысячный раз, «мы там еще», то нет необходимости делать то, что водитель сообщит, когда вы там.

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

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

Также в качестве очень низко висящего плода рассмотрите возможность отделить свои процедуры рисования от симуляции. Даже несмотря на то, что ваша симуляция проста, есть некоторые накладные расходы на рисование вещей. Хуже того, драйвер дисплея может ограничивать вас до x обновлений в секунду, в то время как на самом деле ваши процессоры могут делать вещи в 100 раз быстрее. Это подчеркивает необходимость профилирования.

joojaa
источник
@ Theraot Мы не знаем, как структурированы рисунки. Но да, вызовы станут узкими местами, как только вы все равно
станете
1

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

Так называемый алгоритм Фортуны делает это за вас в Nlog (N), а на вики-странице он содержит псевдокод для его реализации. Я уверен, что есть также реализации библиотек. https://en.wikipedia.org/wiki/Fortune%27s_algorithm

набла
источник
Добро пожаловать в GDSE и спасибо за ответ. Как именно вы примените это к ситуации ОП? Описание проблемы говорит о том, что организация должна рассмотреть всю еду на расстоянии своего обзора и выбрать лучшую. Традиционный Вороной исключал бы в ассортименте еду, которая была ближе к другой сущности. Я не говорю, что Voronoi не будет работать, но из вашего описания не очевидно, как OP должен использовать один для описанной проблемы.
Пикалек
Мне нравится эта идея, я хотел бы видеть ее расширенной. Как вы представляете диаграмму Вороного (как в структуре данных памяти)? Как вы запрашиваете это?
Theraot
@ Тебе не нужна диаграмма вороноя, просто идея того же плана.
Джуджаа
-2

Самым простым решением будет интеграция физического движка и использование только алгоритма обнаружения столкновений. Просто создайте круг / сферу вокруг каждой сущности, и позвольте физическому движку вычислить столкновения. Для 2D я бы предложил Box2D или Бурундук , и Bullet для 3D.

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

  • Обнаружение широкой фазы: цель этого этапа - как можно быстрее получить список возможных пар объектов, которые могут столкнуться. Два распространенных варианта:
    • Подметать и подрезать : сортируйте ограничивающие прямоугольники вдоль оси X и отметьте те пары объектов, которые пересекаются. Повторите для каждой другой оси. Если пара кандидатов проходит все тесты, она переходит к следующему этапу. Этот алгоритм очень хорош в использовании временной когерентности: вы можете хранить списки отсортированных объектов и обновлять их каждый кадр, но так как они почти отсортированы, это будет очень быстро. Он также использует пространственную когерентность: поскольку объекты сортируются в возрастающем пространственном порядке, когда вы проверяете наличие столкновений, вы можете остановиться, как только объект не столкнется, потому что все последующие будут дальше.
    • Структуры данных пространственного разделения, такие как квадродерево, октреи и сетки. Сетки просты в реализации, но могут быть очень расточительными, если плотность объектов мала, и их очень трудно реализовать для неограниченного пространства. Статические пространственные деревья также просты в реализации, но их трудно сбалансировать или обновить на месте, поэтому вам придется перестраивать их каждый кадр.
  • Узкая фаза: пары кандидатов, найденные в широкой фазе, дополнительно тестируются с использованием более точных алгоритмов.
Хосе Франко Кампос
источник