Что такое хороший, простой, 2D алгоритм обнаружения коллизий только для прямоугольников?
Я пошел бы с тем, что мне жаль, что я не знал сначала: простое поле MS-DOS и интегрированный ассемблер (отладка). Замечательно действительно изучить и понять основы того, чтобы говорить с компьютером.
, Если бы это не отпугивает ребенка, то я пошел бы "следующий, выравнивают" и представляют C. Это не должно быть твердо, учитывая, что фундаментальное понятие указателей, регистров и инструкций в целом хорошо понято к тому времени.
Однако я не совсем уверен, куда пойти затем. Возьмите большой переход к Lisp, Haskell или столь же абстрагированным языкам, или должны там быть ориентированные языки некоторого простого объекта (возможно, даже C++) быть добавленным, или это больше причинит боль, чем справка?
3 ответа
Одной из простых стратегий, ускоряющих обнаружение на ранних этапах простой 2D-игры, было ведение списка, отсортированного по более длинному измерению. Фаза столкновения состояла примерно из этого:
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
Вот простой алгоритм, который немного ускорит процесс и работает с прямоугольниками, выровненными по осям.
Выберите одну из осей в качестве «отсортированной оси». Для этого описания я скажу, что ось X отсортирована. Задайте каждый прямоугольник как два узла: узел «вход» и узел «выход» на отсортированной оси. Узлы входа всегда должны иметь меньшее значение на оси, чем узлы выхода.
Создайте отсортированный список всех точек входа и выхода.
Обходите отсортированный список. Когда вы нажимаете каждый узел "ввод", добавляйте его в список "введенных" прямоугольников, а затем выполните обнаружение столкновений методом перебора всех остальных узлов во «введенном» списке. Когда вы нажимаете каждый узел «выхода», удаляйте его из списка «введенных».
Затем вы можете провести читателя через упражнение, в котором «введенный» список сам сортируется по оси Y с помощью «ввода» и точки «выхода» на оси Y.
По моему опыту, все алгоритмы широкофазного обнаружения столкновений относительно тонки и трудны для понимания. Учитывая, насколько дешево тестирование столкновений прямоугольников, я бы структурировал урок, используя алгоритм n ^ 2, а затем в качестве дополнительного материала, возможно, представил бы идею пространственной индексации. С менее чем сотней прямоугольников, держу пари, тупой способ будет достаточно быстрым.
Quadtree подойдет для ваших целей, но помните, что когда вы имеете дело с не-точками, вы должны поместить прямоугольник в узел, содержащий все квадранты, которые он пересекает. Затем, при тестировании чего-то, что находится в нижнем узле, вы должны проверить все прямоугольники в этом узле и во всех его предках!
Вы также можете рассмотреть алгоритм сортировки и очистки, так как вы '