Лучшее решение для двухмерной окклюзии

Question

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

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

Я рассмотрел несколько структур данных, которые могут решить мою проблему:

• квадрадерево

Это было первое, что я рассмотрел, однако проблема в том, что это заставило бы мои сцены иметь фиксированный размер. (Приемлемо для статических, но не для динамических объектов)

• Динамическое дерево AABB

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

• Пространственный хеш

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

В целом, мои критерии хорошего решения этой проблемы:

• Динамический размер: решение не должно ограничивать размер сцены или требовать значительных перерасчетов для изменения размера

• Хорошая производительность запросов (для камеры)

• Хорошая поддержка очень динамичных объектов: вычисления, необходимые для обработки объектов с постоянно меняющейся позицией, должны быть хорошими:

Максимальное вменяемое количество динамических объектов в моей игре за один раз, вероятно, составляет 5000. Учтите, что все они меняют свое положение в каждом кадре. Есть ли даже структура данных, которая может быть быстрее, учитывая частые вставки и удаления, чем сравнивать AABB объектов с камерой каждый кадр?

Answer 1

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

• Деревья квадратов явно подходят для статической геометрии с фиксированными границами.

• Пространственные хеши идеально подходят для наборов объектов с одинаковыми размерами
  (системы частиц, например).

• Динамические деревья AABB AFAIK редко используются для отбора окклюзии, их основное назначение - широкая фаза обнаружения столкновений.

• И, как вы заметили, отбор грубой силы является нормальным для динамических объектов, если их число не очень велико.

статическая геометрия уровня, разбросанная по всей сцене

Если ваша сцена очень разреженная, вы можете разделить ее на острова, то есть создать список частей сцены с "хорошей плотностью".