В настоящее время я работаю над физическим движком для игры в Java, в частности обнаружением столкновений.
В данный момент все работает так: я вставляю каждый объект в Quadtree при каждом обновлении. В расширенной фазе для каждого GameObject, который я хочу протестировать, я получаю список объектов из Quadtree, который содержит все объекты, с которыми он может столкнуться. Затем я выполняю столкновение AABB, чтобы определить, находятся ли объекты рядом с целью. В узкой фазе фактическое столкновение проверяется с помощью теоремы о разделительной оси.
Пока все хорошо, но я настроил некоторые тесты и обнаружил, что полное обнаружение столкновения занимает около 3 мс для 5000 объектов каждый обновление, которое занимает около 0,2 с каждую секунду, что составляет около 20% моего обновления и составляет бюджет 60 ударов в секунду. Предел составляет около 10000 объектов, когда я использую> 95% моего бюджета производительности при обнаружении столкновений, тогда я получаю только около 2 кадров в секунду.
Самая дорогая часть алгоритма (около 75% времени) является тестом, если два объекта находятся в диапазоне друг от друга после получения списка из Quadtree. Это всего лишь простой тест на столкновение прямоугольника, но в зависимости от «плотности» объектов его можно выполнить более миллиона раз за обновление с 5000 объектами.
5000 или более объектов могут звучать очень сильно, но игра, которую я пытаюсь сделать, будет содержать много объектов, таких как стены, плитки и т. д. c. и я действительно не хочу тратить столько производительности на обнаружение столкновений.
Объекты включают в себя игрока, мобов, снарядов и частиц, которые могут двигаться и вращаться, но в основном это настенные плитки и другие объекты окружающей среды, c. Сначала я подумал об использовании двух Quadtree, одного для подвижных и одного для stati c объектов, но я не знаю, как заставить их хорошо общаться.
Итак, я подумал, есть ли другая стратегия для улучшить мою эффективность помимо обнаружения Quadtree и Broad Phase.