Какую технику следует использовать для обрезки 2d коллизионных проверок?

С самого начала обнаружение столкновения похоже на проблему O (n ^ 2).

У вас есть куча объектов, и вам нужно проверить, сталкивается ли каждый объект с каким-либо другим объектом. Тем не менее, я знаю, что крайне неэффективно проверять каждый объект на всех других объектах. Почему относительно дорогостоящая проверка столкновения между двумя шарами, если они даже не близки друг к другу?

Вот пример моей простой программы, над которой я работаю:

Если у вас 1000 шариков, то если вы поехали с наивным обнаружением столкновения, у вас будет 1000 чеков на коллекцию (миллион)! Эта проверка столкновения быстро стала узким местом в моем приложении. Мне нужно выполнить некоторую широкую фазовую обрезку.

Какие методы следует использовать для обрезки коллизионных проверок при работе с 2d-круговыми объектами? Я читал о QuadTrees, BSP, пространственном хэшировании и т.д., Но трудно определить, какой метод наиболее подходит для этого варианта использования.

Кто-нибудь знает, что может сработать лучше всего?

Ответ 1

Пространственное хеширование. См. Страницу Хьюго Элиаса об этом.

Ответ 2

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

Вы можете поэкспериментировать с размером сетки, чтобы найти оптимальный. Вы можете обнаружить, что это зависит от того, сколько у вас шаров.

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

Ответ 3

Я второй метод Grid. 2D-моделирование шаров не принесет пользу QuadTrees (которые обычно используются, когда у вас сложная геометрия, например, персонажи и здания) или BSP (которые вы должны выбрать, если у вас очень неравномерная дисперсия/концентрация объектов, например, с высокой концентрацией областей и областей с низкой концентрацией, в многопользовательской или стратегической игре)