Я ищу хороший алгоритм, обнаруживающий, если движущийся шар касается или статической стены или статической цели. Классическая игровая логика Увольнения. Кто-либо замеченный хороший алгоритм кроме просто циклично выполняет их всех?
Править: Я понятия не имею, который является лучшим решением, BSP древовидное или основанное на сетке вычисление, но моя реализация будет на JavaScript и управляющий движущимися объектами в холсте, и пушечное ядро будет уничтожено, если это поразит что-то, таким образом, я думаю, что каждому выпущенному пушечному ядру нужно одно дерево BSP.
Я согласен, что идея Wickedchicken самая лучшая. Я все же предлагаю другой подход.
Когда я кодировал похожую игру (много лет назад), я разделил игровую область на сетку N * N. Теперь, чтобы проверить, происходит ли столкновение, я просто проверил только те объекты, которые были в том же квадрате сетки, что и мяч, или в любом из 8 квадратов, смежных с этим квадратом. Тщательный выбор значения N может сделать это довольно быстро.
Конечно, это дает хорошие результаты только в том случае, если все объекты распределены более или менее равномерно по игровой зоне. Но в то время этот подход казался мне проще, чем кодирование более сложной структуры данных (я еще учился в старшей школе и только изучал программирование).
Поскольку вы уже знаете местоположение статического объекта, вы можете закодировать его местоположение в BSP или kd-tree . Затем по мере перемещения мяча вы отслеживаете местоположение объекта в BSP или kd-дереве и сравниваете только с объектами в тех же узлах дерева.
Общая идея состоит в том, чтобы построить двоичное дерево до того, как вы начнете выполнять свои тесты. Эта структура данных значительно упрощает поиск «ближайших» объектов - поскольку вы сокращаете количество объектов, которые вы тестируете на столкновение, вы в целом ускоряете обнаружение.
Поскольку стена / цель не движутся, вы не сравниваете шары на предмет столкновений друг с другом (верно?), И вы должны в любом случае перебирать каждый шар в каждом кадре, чтобы переместить его, вы лучше всего проверять каждый шар на предмет столкновения в каждом кадре (если столкновение сложное, вы можете отфильтровать его по приблизительному расстоянию).
Это будет работать быстрее, и его будет проще написать, чем хранить дерево BSP.