Лучшее решение для двухмерной окклюзии - PullRequest
Новая
       90

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

7 голосов
/ 08 августа 2011

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

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

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

  • Quadtree

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

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

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

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

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

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

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

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

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

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

1 Ответ

4 голосов
/ 07 ноября 2011

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

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

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

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

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

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

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

...