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

Немного предыстории, я пишу эволюционную игру с другом на 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)
}

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

$O(N^2)$ , но я не знаю, возможно ли это вообще.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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