Как вычислить наличие препятствий на пути в 2d мире?

Question

[Вячеслав Слинько]

Есть массив 2d объектов (в основном прямоугольники и квадраты).

Нужно вычислить есть ли на пути движения снаряда один из объектов.

Сейчас я проверяю наличие объектов в треугольнике ABC, где медиана AM — и есть путь движения снаряда.
За угол А я взял 30°.

Проблема в том, что объекты двухмерные и имеют различную ширину и длину.
Алгоритм ошибается в ситуации когда объект слишком широкий, но его центр выходит за площадь треугольника.

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

Как правильно решить данную задачу?

Comments

[Вячеслав Слинько]

У объектов есть следующие полезные свойства:
x, y — координаты центра объекта в пространстве
angle — угол относительно оси x
width, height — размеры

Если некоторые полезные методы
get_angle_to_unit — вычеслить угол от направления движения до объекта

[Вячеслав Слинько]

Как я вычисляю сейчас.
Если obstacles пустой — препятствий нет.

Answer 1

[Вячеслав Голованов]

Смотря как они заданы. Возможно, наипростейший способ — посчитать, пересекается ли отрезок «начало полета снаряда — конец полета снаряда» с каждой из сторон 2d-объектов. Если пересекается, то кирдык. Надо только решить, что делать, если этот отрезок пересекает вершину препятствия.
Нужно взять уравнение прямой отрезка полёта снаряда, и проверить, не лежит ли какая-то из сторон многоугольников, ограничивающих 2d-препятствия, в разных полуплоскостях от этой прямой. Если да, то есть пересечение.
По-моему это перемножением векторов делается, но могу и ошибаться, надо погуглить.

Comments

[Вячеслав Слинько]

Способ очень интересный.
С моим количеством объектов (до 20) это вполне пойдет.

P.S. Дополнил вопрос.

[Вячеслав Голованов]

Необходимо уточнить — все-таки, «в основном» прямоугольники, или все они прямоугольники (если учесть, что квадраты — подмножество прямоугольников)?
Наверно, все, т.к. другие фигуры только шириной и высотой задавать вряд ли получится.

[Вячеслав Слинько]

Если учесть, что квадраты — подмножество прямоугольников, то только прямоугольники.

[Вячеслав Голованов]

На самом деле, всё проще — надо для каждого препятствия вычислить координаты вершин, и если все они лежат в одной полуплоскости от прямой пролёта снаряда, значит препятствие не затронуто.
Для уменьшения количества вычислений можно хранить координаты вершин вместо указанных параметров препятствий.
Это будет 8 чисел вместо 5, зато вычислять их не надо каждый раз.

[Вячеслав Слинько]

1. Препятствия могут двигаться.
2. По специфике программы объекты пересоздаются каждый ход (тик).

К тому же можно проверять только две параллельные грани объекта — при пересечении одной стороны пересекается и вторая.

[Вячеслав Слинько]

Большое спасибо за помощь.

[zeksa]

в физических движках применяется техника raycasting.
вы можете посмотреть конкретные примеры

Answer 2

[EndUser]

Можно и collision detection, наверное. Сначала проверка столкновения с «конвертом», затем с самим объектом.