В моей 2D-игре есть статические и динамические объекты. Камер может быть несколько. Моя проблема: Определить объекты, которые пересекаются с прямоугольником обзора текущей камеры.
В настоящее время я просто перебираю все существующие объекты (не обращая внимания на динамические или статические) и выполняю проверку AABB с прямым обзором камеры на них. Это кажется приемлемым для очень динамических объектов, но не для статических объектов, где их могут быть десятки тысяч (геометрия статического уровня разбросана по всей сцене).
Я изучил несколько структур данных, которые могли бы решить мою проблему:
- Quadtree
Это было первое, что я подумал, однако проблема в том, что это заставит мои сцены иметь фиксированный размер. (Допустимо для статических, но не для динамических объектов)
- Динамическое дерево AABB
Вроде бы хорошо, но накладные расходы на ребалансировку кажутся слишком большими для многих динамических объектов.
- Пространственный хеш
Основная проблема здесь для меня заключалась в том, что если вы сильно уменьшили масштаб с помощью камеры, приходилось запрашивать огромное количество в основном несуществующих пространственных хэш-сегментов, что приводило к низкой производительности.
В целом, мои критерии хорошего решения этой проблемы:
Динамический размер: решение не должно приводить к ограничению размера сцены или требованию серьезного пересчета для изменения размера.
Хорошая производительность запросов (для камеры)
Хорошая поддержка очень динамичных объектов: вычисления, необходимые для обработки объектов с постоянно меняющейся позицией, должны быть хорошими:
Максимальное разумное количество динамических объектов в моей игре за один раз, вероятно, составляет 5000. Учтите, что все они меняют свое положение каждый кадр. Существует ли даже структура данных, которая может быть быстрее, учитывая частые вставки и удаления, чем сравнение AABB объектов с камерой каждый кадр?
