Какой хороший, простой 2D-алгоритм обнаружения столкновений?

Question

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

Требования очень просты. Мир 2D и содержит только прямоугольники (произвольных размеров). BSP и даже quadtrees кажется, что это будет излишним (опять же, акцент делается на простоте), но мне хотелось бы что-то более эффективное, чем грубое форсирование через все n (n-1)/2 возможных столкновений.

2D, прямоугольники только и простые.

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

EDIT: Кроме того, прямоугольники никогда не будут повернуты (я держу их простыми). И чтобы дать вам представление о том, в каком масштабе я работаю, будет порядка нескольких сотен прямоугольников, работающих на вашем типичном пользовательском ноутбуке/настольном компьютере (менее 5 лет), реализованном в Python с Pygame.

Answer 1

По моему опыту, все алгоритмы обнаружения столкновений в широком диапазоне относительно тонкие и трудно понятны. Учитывая, насколько дешевым является испытание на прямоугольник-столкновение, я бы структурировал урок, используя алгоритм n^2, а затем как бонус материал, возможно, представит идею пространственного индексирования. Имея менее сотни прямоугольников, я готов поспорить, что тупой способ достаточно быстрый.

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

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

Answer 2

Одна простая стратегия, ускорило обнаружение на ранней попытки простой 2D игры было поддерживать список отсортированный по длинной фазе столкновения dimension.The состоял из чего-то вроде этого:

for i in 0..n 
    j = i+1 
    while rect[j].left < rect[i].right 
     check for collision in y 
     j=j+1 
    endwhile 
endfor 

Answer 3

Вот простой алгоритм, который немного ускорит работу и будет работать с прямоугольниками, выровненными по оси.

Выберите одну из осей как «отсортированную ось». Для этого описания я скажу, что ось X отсортирована. Задайте каждый прямоугольник как два узла, узел «ввести» и узел «exit» на отсортированной оси. Узлы ввода должны всегда иметь меньшее значение на оси, чем выходные узлы.

Создайте отсортированный список всех точек входа и выхода.

Пройдите отсортированный список. Когда вы нажмете каждый узел «ввести», добавьте его в список «введенных» прямоугольников, а затем выполните обнаружение столкновений грубой силы против всех других узлов в «введенном» списке. Когда вы нажмете на каждый «выход» узел, удалите его из «введенного» списка.

После этого вы можете пройти читателя через упражнение, в котором сам «введенный» список сортируется по оси Y с точками «enter» и «exit» на оси Y.