2D-код обнаружения столкновения

Question

Кто-нибудь знает очень простой физический движок или просто набор основных функций, которые могут выполнять следующие задачи: Простая детекция столкновений точек, линий и прямоугольников? Я посмотрел на Box2D, но это слишком продвинуто для того, что я делаю. Мне просто нужен простой код. Заранее спасибо!

Answer 1

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

Как примечания к комментариям GMan, вы должны помнить, что точка будет двигаться. Таким образом, у вас будет текущая позиция точки (назовем ее A) и возможное новое положение точки (B). Вам нужно выяснить, если, когда точка переместится с A на B, она столкнется с линией.

Назовем начальную и конечную точки линии C и D. Столкновение произойдет только в том случае, если линии AB и CD пересекаются.

Опишем строку AB с использованием стандартного уравнения Ux + Vy + W = 0. После некоторой алгебры, уравнение выходит как:

(ay - by) x + (bx - ax) y + ax by - bx ay = 0 

Мы можем описать линию CD с точки зрения параметра t и константы X Y U V:

x = X + Ut 
y = Y + Vt 

Это полезно, если мы устанавливаем t=0 в точке C, и t=1 в точке D. Рассматривая t=0, мы можем разработать X и Y. И, рассмотрев t=1, мы можем разработать U и V.Это дает

x = cx + (dx - cx) t 
y = cy + (dy - cy) t 

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

(ay - by) (cx + (dx - cx) t) + (bx - ax) (cy + (dy - cy) t) + ax by - bx ay = 0 

Это сводится к

t = (ax by - bx ay + bx cy - cx by + cx ay - ax cy)/q 

где Q = (ay - by)(cx - dx) - (ax - bx)(cy - dy)

• Если q равно нулю, линии параллельны и не встречаются.
• Если 0 < t < 1, то линия, экстраполированная с AB, пересекает CD.

Но мы все еще не знаем, что это пересечение фактически находится между точками A и B. Поэтому нам нужно повторить все предыдущие шаги, заменив AB и CD, и написать строку AB с точки зрения параметра s. Это дает:

s = (cx dy - dx cy + dx ay - ax dy + ax cy - cx ay)/q 

• Если 0 < s < 1 то линия экстраполированы CD пересекает AB.

Всё. Итак, в вашем коде вы начинаете с вычисления q. Если q равно нулю, то линии параллельны. В противном случае перейдите к t и s. Если 0 < t < 1 и 0 < s < 1, то произойдет столкновение. Чтобы найти место столкновения, замените t или s обратно в исходные уравнения для CD.

Для дополнительной скорости вы можете удалить деления на q - можно проверить, находится ли верхняя половина каждой фракции в правильном диапазоне, и тогда для каждой проверки требуется только 10 операций умножения.

Answer 2

Если вам нужно простое обнаружение столкновения 2d, это очень просто и доступно множество обучающих программ для игр, см., Например, http://www.gamedev.net/reference/articles/article735.asp.

Answer 3

Есть ли причина, по которой вы не можете использовать базовую геометрию для этого?

Две точки сталкиваются, когда их координаты совпадают.

Точка пересекается с линией, когда ее положение является решением уравнения для линии.

Точка пересекает прямоугольник, когда точка ограничена прямоугольником.

Более сложные составные корпуса могут быть построены путем составления этих случаев. Вы почему-то искали библиотеку по какой-то причине?