Фон
Вместе с другом я работаю над 2D-игрой в космосе. Чтобы сделать его как можно более захватывающим и интерактивным, мы хотим, чтобы вокруг свободно плавали тысячи объектов, некоторые сгруппировались вместе, другие плыли в пустом пространстве.
Вызов
Чтобы разгрузить движок рендеринга и физики, нам нужно реализовать какое-то пространственное разбиение. Мы должны преодолеть две проблемы. Первая проблема заключается в том, что все движется, поэтому реконструкция / обновление структуры данных должно быть чрезвычайно дешевым, поскольку это должно быть сделано каждый кадр. Вторая проблема заключается в распределении объектов, как уже говорилось ранее, могут быть кластеры объектов вместе и огромные куски пустого пространства, и, что еще хуже, нет границы для пространства.
Существующие технологии
Я рассмотрел существующие методы, такие как BSP-Trees, QuadTrees, kd-Trees и даже R-Trees, но, насколько я могу судить, эти структуры данных не идеально подходят, так как обновление большого количества объектов, которые были перемещены в другие ячейки относительно дорого
Что я пробовал
Я решил, что мне нужна структура данных, которая больше ориентирована на быструю вставку / обновление, чем на возвращение наименьшего количества возможных попаданий по запросу. Для этого я сделал ячейки неявными, чтобы каждый объект, учитывая его положение, мог вычислить, в какой ячейке (ях) он должен быть. Затем я использую, HashMapкоторый отображает координаты ячейки в ArrayList(содержимое ячейки). Это работает довольно хорошо, поскольку на «пустых» ячейках не теряется память, и легко подсчитать, какие ячейки проверять. Однако создание всех этих ArrayLists (наихудший случай N) является дорогостоящим и поэтому увеличивается во HashMapмного раз (хотя это немного смягчается, если дать ему большую начальную емкость).
проблема
Итак, это работает, но все еще не очень быстро. Теперь я могу попробовать микрооптимизировать код JAVA. Однако я не ожидаю слишком многого от этого, поскольку профилировщик говорит мне, что большая часть времени уходит на создание всех тех объектов, которые я использую для хранения ячеек. Я надеюсь, что есть некоторые другие приемы / алгоритмы, которые делают это намного быстрее, поэтому вот как выглядит моя идеальная структура данных:
- Приоритет номер один - быстрое обновление / реконструкция всей структуры данных.
- Менее важно точно разделить объекты на ячейки одинакового размера, мы можем нарисовать несколько дополнительных объектов и сделать несколько дополнительных проверок столкновений, если это означает, что обновление происходит немного быстрее
- Память не очень важна (компьютерная игра)
источник
Ответы:
Техника, которую вы используете, очень похожа на технику вычислительной физики, называемую молекулярной динамикой, где траектории атомов (обычно сейчас в диапазоне частиц от 100k до 10M) следуют с очень маленькими временными шагами. Основная проблема заключается в том, что, чтобы измерить силу для одной частицы, вы должны сравнить ее положение с положением любой другой частицы, которая очень плохо масштабируется (n в квадрате).
Я могу предложить один трюк, который требует, чтобы вы выбрали максимальное расстояние, на которое вещи могут взаимодействовать. В качестве отправной точки я бы начал с примерно 1/10 длинного измерения вашего пространства и приспособился бы к вкусу (более длительное отсечение означает более точные, но более сложные вычисления).
Метод заключается в прохождении каждой частицы (i). (I) получает массив, где все частицы в диапазоне от i добавляются в массив. В итоге вы получите 2d массив, где i-я запись - это массив частиц в диапазоне i. Чтобы рассчитать силы для i, вам нужно только проверить записи в массиве i.
Искусством этого метода является выбор расстояния отсечки и дополнительное заполнение (например, 20%). Увеличение скорости состоит в том, что вам нужно только проверить несколько взаимодействий для каждой частицы, и вы пересчитываете соседей только каждые несколько шагов. Я бы предложил выбрать несколько быструю скорость и выяснить, сколько временных шагов потребуется, чтобы пересечь область «заполнения». Увеличение заполнения (50% или даже 100% отсечки) дает вам больше шагов между пересчетами соседей, но делает каждый шаг немного медленнее. Балансировка это компромисс.
Еще одна хитрость при расчете расстояний - это работать с d ^ 2 вместо d, удаляя кучу вызовов pow () и sqrt ().
Изменить: Трудно найти ссылку на ссылку, которая не является супер технической. Это единственный, кого я смог найти.
источник
Ваше собственное решение звучит довольно хорошо, если вы можете добиться построения структуры данных в o (n), тогда я бы сказал, что оптимизация должна быть сделана при выборе структуры данных, а не алгоритма.
У меня похожая реализация с некоторыми отличиями: Основная структура данных - это массив фиксированного размера (например, ArrayList), который лучше всего подходит для прямого доступа к элементу. Каждая ячейка массива содержит связанный список, который лучше всего подходит для вставок и так же хорош, как и список массивов для зацикливания. Позже нам потребуется удалить элементы из связанного списка, поэтому, чтобы сделать эту операцию очень быстрой, идея состоит в том, чтобы сохранить в каждом элементе списка итератор, который указывает на себя (вы сказали, что память не является проблемой, верно?)
Для инициализации каждая «частица» вставляется в конец связанного списка, который соответствует ячейке в массиве, которая соответствует его позиции в пространстве, при условии, что пространство разделено на тайлы фиксированного размера. Таким образом, у нас все еще есть сложность, но мы оптимизируем все это, используя контейнеры, более приспособленные для использования.
Каждая «частица» имеет ссылку на содержащий ее связанный список, чтобы обеспечить быстрый доступ к ее соседям.
В каждом кадре мы можем осуществлять взаимодействие между каждой частицей с ее списком соседей, и я бы сказал также с 8 окружающими плитками, чтобы избежать пороговых эффектов вблизи границ плиток.
Нет необходимости пересчитывать все разбиения в каждом кадре; нам нужно только удалить и снова поместить элемент, когда он перемещается больше, чем на заданное расстояние или, по соображениям безопасности, каждые X кадров. Идея может состоять в том, чтобы сохранить позицию каждого элемента в тот момент, когда он был вставлен в связанный список, и в каждом кадре сравнить текущую позицию со старой.
источник