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

Теорема о разделении гиперплоскостей

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

Другой математический элемент, который нам нужно прокомментировать, — это выпуклое множество. Выпуклый набор не является технически обобщением выпуклого многоугольника для других векторных пространств (таких как трехмерное пространство, функциональные пространства и другие).

Один из примеров теоремы о разделении гиперплоскостей показан на изображении выше. Хорошо, теорема говорит, что можно разделить множества гиперплоскостью, но как это использовать на практике? Для этого существует Теорема о разделяющей оси (SAT).

Теорема о разделяющей оси

В теореме о разделяющей оси, если у нас есть два выпуклых многоугольника, нам нужно получить ортогональную ось ко всем граням двух многоугольников и спроецировать два многоугольника на все эти оси. Если проекции пересекаются на всех этих осях, то и многоугольники пересекаются, но если на одной из ортогональных осей проекции не пересекаются, то мы можем добавить гиперплоскость или линию в этом пространстве, чтобы разделить два выпуклых множества (выпуклые многоугольники). Один из примеров этого виден на изображении ниже (два разделенных полигона).

Реализация в JavaScript

Реализация на JavaScript будет создана с использованием элемента Canvas Html5 (для справки мы используем Html5 Canvas Handbook). Во-первых, мы создаем две функции, одну для создания векторов в направлении ребер, а другую для получения расстояния двух интервалов.

Первая функция будет проходить по всем вершинам (получая две на две вершины) и вычислять вектор в том же направлении, что и текущее ребро (две вершины), буквально, если у нас есть вершины A и B, вектор в направлении ребра равен B-A. Вторая функция получает значение расстояния между двумя интервалами. Если интервалы перекрываются, то расстояние меньше или равно 0.

Теперь мы создаем структуру многоугольника, чтобы получить вершины и создать другую необходимую информацию и функции:

Функция смещения — это всего лишь функция для суммирования dx и dy с x и y соответственно всех вершин полигона:

Функция рендеринга — это метод рисования (обводки) многоугольника с использованием контекста Html5 Canvas Context2D:

Теперь самое важное в этой структуре — это проектInAxis и метод testWith. ProjectInAxis проецирует полигон по определенной оси. testWith проверяет столкновение полигона с другим полигоном.

Чтобы спроецировать многоугольник на ось, мы используем скалярное произведение геометрии, чтобы получить длину проекции:

Нам нужно спроецировать все вершины и определить, кто является минимальной проекцией, а кто максимальной проекцией (краями многоугольника):

Теперь нам нужно создать функцию testWith. Эта функция получает все ребра двух многоугольников, а затем создает векторы ортогональных осей для всех ребер, а затем проецирует многоугольник на эту ось и проверяет интервальное расстояние:

Тестирование реализации

Для тестирования этой реализации теоремы о разделяющей оси мы добавляем код из приведенных выше шагов в файл с именем sat.js и создаем новый файл с именем game.js в папке assets/scripts и создаем index.html в корневой папке для этого проекта. В файле game.js есть небольшой пример использования приведенных выше кодов:

index.html имеет только включение скриптов и пустой элемент canvas Html5:

И результат: