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

Question

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

EDIT: Я понятия не имею, какое решение является лучшим решением, вычислением BSP дерева или сетки, но моя реализация будет выполняться на JavaScript и управлять движущимися объектами в холсте, а пушечный шар будет уничтожен, если он что-то ударит, поэтому Я думаю, что каждый выстреленный пушечный мяч нуждается в одном дереве BSP.

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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