Широкая фаза обнаружения столкновений

Как я уже писал выше, обнаружение коллизий между объектами – задача ресурсоемкая. Если попарно проверять все объекты сцены друг с другом на пересечение, то это займёт квадратичное время.

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

Популярной техникой для широкой фазы, является алгоритм Sweep and Prune. Идея заключается в том, чтобы построить проекции объектов на одну из координатных осей, отсортировать полученные границы объектов и затем перебрать отсортированный список, фиксируя все пересечения проекций. Таким образом, нам не придется проверять объекты каждый с каждым, поскольку встретив закрывающую границу проекции объекта, далее его можно не рассматривать. Что касается сортировки, то алгоритм опирается на то, что между итерациями игрового цикла, объекты не сильно меняют свои позиции, а значит массив проекций будет всегда почти отсортирован. Сортировка, которая лучше работает на частично отсортированном массиве будет выдавать сложность близкую к O(n). Например, сортировка вставками.

На самом деле я реализовал этот алгоритм уже довольно давно, но рассказывал про него только на своем выступлении на HolyJS, поэтому думаю стоит упомянуть об этом здесь отдельно перед тем как двигаться дальше. А двигаться есть куда, поскольку недавно я заметил, что из-за косяков в реализации алгоритма я избавился от N^2 не до конца. О своих ошибках я расскажу дальше.