В рамках подготовки к реализации условной игры Mage Rage мне понадобилось искать пересечения линий.
Нахождение точки пересечения линий – одна из краеугольных задач в играх. Она требуется в платформерах, шутерах, физических симуляциях, рендеринге.
Крайне важно иметь эффективный алгоритм определения пересечения. Поэтому их делят по типам. Например, пересечение двух произвольных линий вычислять сложнее, чем пересечение линии и прямоугольника. Если игровой уровень состоит из прямоугольных областей, то конечно следует использовать более простой метод.
Мой игровой уровень как раз состоит из клеток-квадратов.
Работа ведётся не с бесконечной линией, а с отрезком, у которого есть начало и конец. Прямоугольник также состоит из четырёх отрезков: двух вертикальных и друх горизонтальных. Отбрасывание ненужных вариантов происходит сразу: если наш отрезок целиком находится вне прямоугольника, то ничего дальше сравнивать не нужно.
В противном случае отрезок проверяется на пересечение с каждым из отрезков прямоугольника. Начнём с горизонтальных отрезков.
У горизонтального отрезка есть постоянная координата y. Если наш отрезок пересекается с ним, значит, в нём должна быть точка с такой же координатой y. Вычислив эту точку на нашем отрезке, мы вычислим и её координату x. А зная координату x, мы уже можем сказать, попадает она внутрь горизонтального отрезка или нет. Если попадает, значит наш отрезок пересекается с горизонтальным отрезком.
Как найти координаты точки пересечения на отрезке? Вспомним про уравнение линии: ax + by + c = 0. Но я не буду тут грузить никакой математикой, давайте просто на пальцах: у отрезка есть начальная точка и конечная точка. Чтобы из начальной точки попасть в конечную, координата x должна измениться на некоторое значение dx, а координата y должна измениться на некоторое значение dy. Эти значения, как правило, не равны.
Но между ними есть взаимосвязь: если по координате x мы прошли любое расстояние, то по координате y мы пройдём пропорциональное ему расстояние. Скажем, разница между концами отрезка: dx = 100, dy = 200. Если от первого конца мы пройдём по x 50 единиц, то по y мы должны пройти 100 единиц, так как dy в два раза больше чем dx, и нужно приращивать y в два раза быстрее, чтобы попасть в конечную точку одновременно с x. Иначе говоря, смещение по y это смещение по x, умноженное на dy/dx.
Если же мы смещаемся по y, то смещение по x рассчитывается аналогично, в обратной пропорции: x = y * (dx / dy)
Итак, чтобы найти пересечение с горизонтальным отрезком, нужно:
- Найти разницу между координатой y горизонтального отрезка и координатой y первой точки нашего отрезка. Эта разница является смещением по y для точки, лежащей на нашем отрезке.
- Зная смещение по y, вычислить смещение по x через пропорцию dx/dy и прибавить его к координате x первой точки нашего отрезка. Мы получили точку пересечения x.
- Сравнить точку пересечения x с координатами x концов горизонтального отрезка. Если наша точка находится между ними, то пересечение есть.
Проверив таким образом два горизонтальных отрезка, переходим к вертикальным. Там происходит то же самое, только x и y, dx и dy меняются местами.
Если на любом из отрезков случилось пересечение, можно уже возвращать результат. Или продолжать дальше, если нам нужны все пересечения, которые есть.
Я написал проверочный скрипт. Он генерирует случайные линии при каждом перезапуске и визуально показывает пересечения.
Посмотреть на него можно прямо в браузере.
Покончив с этой задачей, можно задаться философским вопросом: а надо ли было её решать? Полно игровых движков, в которые уже встроена проверка пересечений. Я вспомнил про один такой движок, Phaser, и решил посмотреть, как там дела. К моему удивлению, я обнаружил там код, абсолютно идентичный тому, что я написал.
Ну что ж, это значит, что я не один такой умный мог бы его и не писать, а взять готовый. Но у меня другие планы: так как мне нужно не просто пересечение, а пересечение с ближайшим объектом, то фактически я буду писать алгоритм "бросания лучей" (raycasting), да ещё и с собственными заморочками.
Вызов метода из Phaser будет в таком случае не оптимален – много накладных расходов. А написав определение пересечений самостоятельно, я как бы загрузил в свой мозг модель пересечений и теперь могу её свободно изменять, понимая, как и что там работает.
А вот подоспел и следующий выпуск, где я буду использовать Ray Casting.