В современной разработке игр одной из самых важных функций является тестирование столкновений. В двумерных играх, особенно в простых, наиболее часто используемым методом обнаружения столкновения является теорема о разделяющей оси. Но что такое теорема о разделяющей оси?
Теорема о разделении гиперплоскостей
Теорема о разделении гиперплоскостей — это теорема, которая говорит нам, что если у нас есть два выпуклых множества без пересечения, можно разделить эти два выпуклых множества гиперплоскостью. Гиперплоскость не является технически объектом с одним измерением, если не считать рабочего пространства. Например, если мы работаем с двухмерным пространством, гиперплоскость — это линия, но если мы работаем с трехмерным пространством, гиперплоскость — это плоскость.
Другой математический элемент, который нам нужно прокомментировать, — это выпуклое множество. Выпуклый набор не является технически обобщением выпуклого многоугольника для других векторных пространств (таких как трехмерное пространство, функциональные пространства и другие).
Один из примеров теоремы о разделении гиперплоскостей показан на изображении выше. Хорошо, теорема говорит, что можно разделить множества гиперплоскостью, но как это использовать на практике? Для этого существует Теорема о разделяющей оси (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:
И результат: