Обнаружение столкновений пушечных ядер со стеной и целью

Question

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

РЕДАКТИРОВАТЬ: я понятия не имею, какое решение является наилучшим, для расчета BSP на основе дерева или сетки, но моя реализация будет на JavaScript и управлении движущимися объектами на холсте, и пушечное ядро ​​будет уничтожено, если оно попадет по чему-то, поэтому я думаю, что для каждого выпущенного пушечного ядра требуется одно дерево BSP.

Answer 1

Я согласен, что идея злого цыпленка - лучшая. Я просто предлагаю другой подход все же.

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

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

Answer 2

Поскольку вы уже знаете местоположение статического объекта, вы можете закодировать его местоположение в BSP или kd-tree . Затем, когда местоположение шара движется, вы отслеживаете местоположение объекта в BSP или kd-дереве и сравниваете его только с объектами в тех же узлах дерева.

Общая идея состоит в том, чтобы создать двоичное дерево до того, как вы начнете выполнять свои тесты. Такая структура данных значительно упрощает поиск «близлежащих» объектов - поскольку вы сокращаете количество объектов, которые вы проверяете на столкновение, вы ускоряете обнаружение в целом.

Answer 3

Поскольку стена / цель не движутся, вы не сравниваете шары для столкновений друг с другом (верно?), И вы должны в любом случае перебирать каждый шар через каждый кадр, чтобы переместить его, лучше всего проверить каждый мяч для столкновения каждый кадр (если столкновение сложное, вы можете фильтровать по приблизительному расстоянию).

Это будет работать быстрее и будет легче писать, чем хранить дерево BSP.