При написании игр, нередко, можно столкнуться с проблемой: вот есть мой персонаж, который представляет из себя сложную форму, совсем не похожую на прямоугольник; и есть другой персонаж, тоже совсем не похожий на прямоугольник. И они, в какой-то момент, пересекаются - и как же определить, что факт пересечения наступил? Эту прикладную задачу и рассмотрим в статье.
Обозначение проблемы
Изначально о простом: определить пересечение двух прямоугольников просто, а двух многоугольников - нет. Но "не просто" не значит невозможно, однако всё упирается в цену вопроса: если для определения факта пересечения двух игровых объектов надо будет тратить слишком много процессорного времени, игра начнёт тормозить и удовольствие от процесса быстро сменится раздражением и разочарованием.
Но что делать, если наш персонаж - треугольник, а его враг - ромб? Вписав их в прямоугольники, частично, задачу можно решить, но решение будет неудовлетворительной. Довольно легко представить, как треугольник и ромб находятся рядом друг с другом, не пересекаясь, а вот их "описывающие прямоугольники" - пересекаются и обрабатывается соприкосновение, которого, по факту, нет.
Метод разделяемой оси
И вот тут нам на помощь приходит метод разделяемой оси. Давайте представим, что наш треугольник проецируется на оси X и Y - и отображается там в виде отрезков (школьный курс геометрии).
В то же время, ромб, также, проецируется на оси X и Y.
И тут наступает магия: оказывается, что если на обеих осях отрезки пересекаются, значит и фигуры пересекаются. Просто и элегантно. К сожалению, только для прямоугольников. Для многоугольников чуть сложнее: нужно проверить проекции этих многоугольников на оси, перпендикулярные КАЖДОЙ стороне (ребру) ОБЕИХ фигур. То есть, если у нас есть треугольник (3 стороны) и ромб (4 стороны), то для проверки нужно взять 3 оси от треугольника и 4 оси от ромба (всего 7 осей).
Вуаля, и мы отказываемся от большинства сложных математических вычислений, а можем брать фигуры совершенно любых форм и определять факт их пересечения.
Но постойте, мы рассматривали выпуклые фигуры. А что если противником треугольника будет не ромб, а злодей, формой напоминающей букву "S"? Нетрудно представить, как треугольник и "с" пересекаются на осях, но не имеют пересечения в реальности.
Пересечение не выпуклых фигур
К счастью, эта задача тоже решаема, хоть и более ресурсоёмкая. Для этого нам надо нашу не-выпуклую фигуру разделить на несколько выпуклых. И для этого существует алгоритм т.н. триангуляция методом "ушей", который применим к простым многоугольникам без отверстий (да, все круглые поверхности придётся немного упростить до многоугольников, но это ведь не так трудно). Он выполняется в 3 шага:
- Поиск "уха": "ухом" в многоугольнике называется треугольник, образованный двумя соседними сторонами многоугольника и диагональю, лежащей внутри многоугольника.
- Удаление "уха": после нахождения "уха", его удаляют, заменяя на диагональ, и продолжают процесс для оставшейся части многоугольника.
- Повторение: процесс повторяется, пока не останется один большой треугольник или пока не будет достигнуто необходимое количество треугольников.
А вот вполне себе выпуклые треугольники, из которых состоит "вражеская фигура" - можно сравнивать со своей выпуклой фигурой. А если своя фигура не выпуклая, то её можно превратить по тому же алгоритму в набор выпуклых фигур и сравнить все со всеми.
Ресурсоёмко? Пожалуй. Но некоторые вычисления надо провести только один раз, да и никто не мешает избегать использования таких вот сложных фигур.
Заключение
Не знаю как вам, но мне предложенный метод кажется эдакой "серебряной пулей" в мире определения столкновений. Метод очень универсальный (хоть и не такой быстрый как AABB), позволяющий вообще не думать о многих трудностях, понятных лишь разработчикам движков, а в совокупности с упомянутым AABB, гарантирующим отличную производительность.
Но главное, данный метод вообще не ограничен 2д - его можно использовать и в 3д, просто осей для проверки будет больше. Такие дела.