Правильный выбор структуры данных для системы столкновений

Question

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

Первая идея - это грубая сила на границе (или, возможно, не такая граница)).Я бы сохранил два списка объектов столкновения в системе столкновения.Один список будет динамическими объектами, другой будет включать как динамические, так и статические объекты (каждый динамический элемент будет в обоих списках).В каждом кадре я бы проходил через динамический список и передавал каждому объекту больший список, чтобы он мог найти все, с чем может столкнуться.Это потребует большого количества ненужных вычислений для любой загруженной области разумного размера, но я использую ее как своего рода базовую линию, потому что это было бы очень легко реализовать.

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

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

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

Answer 1

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

Вы еще не сказали, каково представление ваших объектов, но в любом случае вы, скорее всего, получите в итоге типичную "широкую фазу" и "узкую фазу"(как физический движок) - «широкая фаза», состоящая из ложных срабатываний «что может пересекаться?»запрос и «узкая фаза» грубой вытеснения результирующих потенциальных пересечений.Если вы не используете такие вещи, как деревья разделения двоичного пространства для многоугольных форм, вы не получите однофазное решение.

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

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

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

Итак: когда вы обновляете объекты, обновляйтесетки, в которых они, вероятно, находятся. (Опять же, достаточно просто использовать ограничивающий прямоугольник - например, квадрат или прямоугольник вокруг объекта.) Добавьте объект в хеш-таблицу для каждой ячейки, в которой он находится. (Например, если выв ячейке 5,4, которая хэширует к 17-й записи хеш-таблицы. Добавьте ее в эту запись хеш-таблицы и отбросьте данные 5,4.) Затем, чтобы проверить столкновения, пройдите соответствующие ячейки в хэше.таблицу (например, ценность ячеек всего экрана, если это то, что вас интересует) и посмотрите, какие объекты внутри каждой ячейки сталкиваются с другими объектами внутри каждой ячейки.

По сравнению с решениями выше:

• Обратите внимание, что грубое форсирование занимает меньше времени.
• Это имеет некоторое сходство с упомянутым методом "2D-массив", потому что, в конце концов, мы навязываем "сетку" (или 2D-массив)однако в представленном пространстве мы делаем это способом, менее подверженным ошибкам точности (поскольку он используется только для широкой фазы, которая является консервативной).Кроме того, требования к памяти уменьшаются благодаря усердному сокращению данных в хеш-таблицах.
• kd, сфера, X, BSP, R и другие "TLA" -деревья почти всегда довольно нетривиальны для правильной реализации, тестирования идаже после всех этих усилий может оказаться гораздо медленнее, чем вы ожидаете.Вам не нужно такого рода сложности для нескольких сотен объектов обычно .

Замечание по реализации:Каждый узел в пространственной хеш-таблице в конечном итоге будет связанным списком. Я рекомендую написать свой собственный связанный список с осторожным распределением. Каждый узел должен занимать более 8 байт (если вы используете C / C ++) и должен иметь схему объединенного распределения, чтобы вы почти никогда не выделяли или не освобождали память. Полагаясь на встроенный распределитель, вероятно, снизит производительность.

Answer 2

Во-первых, я всего лишь новичок, я пробираюсь через видео 3dbuzz xna extreme 101, и мы только сейчас рассказываем о системе, которая использует статические списки для каждого другого типа объектов, когда обновляете только один объект. проверьте список (ы) вещей, с которыми он должен столкнуться. Таким образом, вы проверяете только столкновения противника с игроком или пулями игроков, а не с другими противниками и т. Д.

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

извините, если неясно, что я имею в виду, я все еще нахожусь в ногах