@thirteen_bit

Как грамотно остановить объект при столкновении?

Здравствуйте! Изучаю вопрос столкновения объектов, пишу простенький 2d-движок под html5 для этого. Есть два выпуклых многоугольника (в данном случае – прямоугольники), координаты задаются центром, стороны – векторами. На картинке ниже черный прямоугольник статичен, синий движется по направлению к нему с заданным вектором скорости.

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

604b139a829f7027814251.png
  • Вопрос задан
  • 266 просмотров
Пригласить эксперта
Ответы на вопрос 3
gbg
@gbg
Любые ответы на любые вопросы
Ваша проблема в том, что вы допускаете залезание объекта в препятствие, а потом не знаете, как его оттуда вынуть.

На каждой итерации, вам нужно проверять отрезок прямой, по которому ваш объект шагает и искать внутри этого отрезка такой параметр времени theta, при котором объект начинает касаться стенки.

После этого вам остается зафиксировать ваш объект в этом положении.

Поиск пересечения нужно делать аналитически, это быстрее.
Ответ написан
Комментировать
maaGames
@maaGames
Погроммирую программы
Сдвигать по нормали статичной поверхности. Во "взрослых" движках нельзя просто сдинуть, потому что это ломает всю непрерывную физику, поэтому вместо сдвига добавляется ускорение в ту сторону, куда надо сдвинуть. Этим объясняются прыгающие ящики и трупы и прочее - из-за погрешностей вычисления объекты постоянно проникают, выстреливют наружу и обратно проникают при падении.
Ответ написан
Комментировать
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Во-первых, если скорости маленькие и движение происходит на маленькие отрезки за итерацию, то можно выталкивать объект в любую сторону.

Если же шаги не настолько мелкие, то нужно, как уже подсказал Фокс Йовович, сдвигать до пересечения, а не впихивать объект в другой и выталкивать назад.

Есть концептуально простой но далеко не самый эффективный метод - бинарный поиск. Вот вы уже умеете определять, пересекаются ли 2 объекта. Изначально они не пересекались, после сдвигания на 1.0 едениц веремени они пересеклись. Делайте бинарный поиск по времени в отрезке (0, 1): посморите, есть ли пересечение при сдвиге на 0.5 единиц времени. Потом или 0.25 или 0.75 в зависимости от результата проверки. И так пока текущий отрезко в бинпоиске не станет достаточно мал. Но у этого метода большая проблема с большими скоростями - если за время итерации объекты пройдут сквозь друг друга - вы этого не заметите.

Более быстрый метод - это реально искать пересечение тракетории. Для этого пустите лучи из каждой вершины одного объекта параллельные его скорости движения относительно второго объекта. Потом пересеките каждый луч со вторым многоугольником и найдите кратчайший луч. Аналогично надо пустить лучи из всех вершин второго многоугольника в обратную сторону и пересечь их все с первым многоугольником (это если движущийся наткнется на вершину препятствия стороной). Нашли длину минимального луча - на нее и сдвигайтесь. Если задавать лучи параметрически в виде point+t*v, то фактически вы ищете минимальное значение параметра t при пересечении у всех лучей (тут v - вектор скорости за один квант времени,point - вектор координат точки, из который выпустили луч).

В этом методе не надо даже проверять, попадает ли после полного шага объект в препятствие. Нашли минимальное расстояние до пересечения (может быть и бесконечностью, если пересечений нет) - если оно больше сдвига за квант времени, то сдвигайтесь просто на квант времени. в параметрическом подходе, это значит, что сдвигаетесь вы на min(1.0, t).

Этот метод можно соптимизировать с квадратичного до линейного. Представьте, что вектор движения горизонтален (и направлен влево). Можно просто повернуть все точки каждого многоугольника вместе со всем пространством или применять векторные/скалярные произведения для определения, какая точка ниже/левее/правее.

Найдите в каждом многоугольнике самую нижнюю и самую верхнюю точку. Если эти промежутки по OY не пересекаются - то два объекта не столкнутся, можно останавливать проверки. Если промежутки по OY пересекаются, но второй обхект находится правее первого - то они отдаляются и опять можно дальше не проверять. Тут можно сравнить по одной любой точке с каждого объекта.

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

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

Можно его до сублинейного соптимизировать через бинарный поиск опять, но тут уже очень сложно. Можно низшую и высшую точки искать за логарифм бинпоиском, а не как выше полным перебором всех точек. Потом тернарным поиском перебираете значение координаты Y и считаете расстояние между двумя многоугольниками вдоль этого горизонтального отрезка. Для этого, опять же бинпоиском, находите 2 отрезка пересекающих эту горизонталь в обоих многоуголниках и пересекаете с горизонталью, чтобы найти 2 конца расстояния. Эта функция расстояния dist(y) будет выпуклой. Поэтому уможно найти ее минимум тернарным поиском.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы