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

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

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


algorithm collision-detection
person joetsuihk    schedule 04.06.2010    source источник
comment
Имейте в виду, что если мяч летит слишком быстро, он может пройти сквозь стену, не касаясь ее в каждом кадре, в котором вы рассчитываете столкновения, и, таким образом, не сталкиваясь, хотя и должен.   -  person ANeves thinks SE is evil    schedule 08.06.2010

Ответы (3)


arrow_upward
1
arrow_downward

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

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

person wickedchicken    schedule 04.06.2010

arrow_upward
1
arrow_downward

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

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

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

person MAK    schedule 04.06.2010

arrow_upward
0
arrow_downward

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

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

person BlueRaja - Danny Pflughoeft    schedule 04.06.2010