Реакция столкновения 2D-игры: SAT & минимальное смещение вдоль заданной оси?

13

Я пытаюсь внедрить систему столкновений в 2D-игру, которую я делаю. Теорема о разделяющей оси (как описано в учебнике по столкновению с metanet ) кажется эффективным и надежным способом обработки обнаружения столкновений, но мне не совсем нравится метод реагирования на столкновения, который они используют. При слепом смещении вдоль оси наименьшего перекрытия алгоритм просто игнорирует предыдущую позицию движущегося объекта, что означает, что он не сталкивается со стационарным объектом так сильно, как входит в него и затем отскакивает.

Вот пример ситуации, когда это будет иметь значение:

пример

Согласно методу SAT, описанному выше, прямоугольник просто выпадет из треугольника, перпендикулярного его гипотенузе:

SAT-Style Response

Однако реально, прямоугольник должен остановиться в нижнем правом углу треугольника, так как это будет точка первого столкновения, если он будет непрерывно двигаться вдоль своего вектора смещения:

Реалистичный ответ

Теперь, это может на самом деле не иметь значения во время игры, но я хотел бы знать, есть ли способ эффективно и вообще добиться точных перемещений таким образом. Последние несколько дней я ломал голову над этим, и пока не хочу сдаваться!

(Перекрестная публикация от StackOverflow, надеюсь, это не противоречит правилам!)

Archagon
источник
Это против правил. Не кросспост
AttackingHobo
Да, удалите его из StackOverflow и сохраните здесь: P
TravisG
gamedev.stackexchange.com/questions/9144/… Я ответил на ваш конкретный вопрос здесь.
ультифинит
Удалено из СО.
Archagon
Начните щедрость, аркагон: P В противном случае мне, возможно, придется. Этот вопрос действительно интересен, и было бы здорово увидеть ответ, который не просто перечисляет несколько ссылок.
TravisG

Ответы:

11

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

На рисунках ниже синий объект движется, а красный объект неподвижен. 1 Шаг 1: Для каждого многоугольника найдите две самые дальние точки вдоль проекции этого многоугольника на линию, перпендикулярную вектору движения. 2 Шаг 2: Разделите каждый многоугольник вдоль линии, соединяющей эти точки. Половина многоугольника, которая обращена к другому многоугольнику вдоль вектора движения, является "передней оболочкой". Это единственная часть многоугольника, которая может столкнуться. 3 Шаг 3:Спроецируйте вектор из каждой точки "передней оболочки" каждого многоугольника вдоль вектора движения в направлении противоположного многоугольника и проверьте его на предмет пересечения с каждым ребром "передней оболочки" противоположного многоугольника. (Возможно, медленный, но в наше время компьютеры работают довольно быстро - верно?) (Извините за наклонную стрелку. Все стрелки должны быть параллельны.) 4 Шаг 4: Возьмите кратчайший вектор. Это точное расстояние столкновения. 5 Шаг 5: Вуаля! 6

Archagon
источник
2
Это довольно впечатляюще. Вы случайно не сравнивали скорость вашего алгоритма с простой (4x или 8x) мультисэмплинг?
TravisG
К сожалению нет.
Archagon
Впечатляет, и я уверен, что математика не слишком сложна / интенсивна. +1
you786
7

Проверьте этот похожий вопрос: разрешение столкновений

А также с http://www.metanetsoftware.com/technique/tutorialA.html#section5 (на которую вы разместили ссылку :))

РАЗДЕЛ 5: Быстро движущиеся объекты

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

Если они абсолютно необходимы, есть два распространенных метода для работы с небольшими и / или быстродвижущимися объектами: тесты с быстрым столкновением и мультисэмплинг.

- = тесты подметания = -

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

Основная идея описана в [Gomez], для круговых круговых и AABB-AABB тестов развертки.

- = мультисэмплинг = -

Гораздо более простой альтернативой кратким тестам является мультисэмплинг; вместо того, чтобы выполнять один статический тест в новой позиции объекта, выполните несколько тестов в нескольких позициях, расположенных между предыдущей и новой позицией объекта. Эта техника была использована для столкновения тряпичной куклы в N.

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

РЕДАКТИРОВАТЬ

В итоге и AFAIK, есть несколько решений

  1. Ограничьте свою игру, чтобы никогда не иметь маленький и / или быстро движущийся объект, который может даже вызвать это
  2. Внедрить систему, которая предотвращает возникновение коллизий, как описано в первой ссылке, которую я разместил
  3. Увеличьте частоту дискретизации для быстрых и / или небольших движущихся объектов.
  4. ... возможно больше, но я не эксперт.
you786
источник
1

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

Альтернатива использованию SAT:

Только в случае линейного можно навести луч на разность Минковского двух полигонов от начала координат в направлении дельта-линейной скорости объектов.

Если луч достигнет MD, два объекта столкнутся, и точка попадания сообщит вам время t, в которое они столкнулись.

Теперь, если объекты движутся и вращаются это становится сложнее, но вы все равно можете использовать аналогичную технику. Консервативное продвижение позволит вам разобраться с этим делом. Эта техника итеративна; каждая итерация будет генерировать новый MD и приближать вас к моменту пересечения.

Вот оригинальный проект документа по консервативному продвижению:

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Я написал статью, объясняющую технику в некоторых деталях здесь:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Надеюсь, что это поможет!

wildbunny
источник