Разрешение столкновений в случае столкновения с несколькими объектами

15

У меня есть статические и подвижные объекты. Столкновения обнаруживаются с использованием теоремы разделяющей оси.

Например, в этой ситуации у меня есть два статических объекта (красным):

введите описание изображения здесь

и подвижный объект между ними:

введите описание изображения здесь

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

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

введите описание изображения здесь

Обратите внимание, что я просто быстро нарисовал это в MSPaint, так что на этом рисунке фактически может быть так, что вектор минимального перевода выталкивает зеленый прямоугольник сверху, но я собираюсь предположить, что он выталкивает его влево / право на самом деле короче.

Общий способ решения этой проблемы - разрешить столкновение только по одному столкновению на кадр, а не по всем сразу. Но в моем случае это приведет к триггеру:

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

введите описание изображения здесь

Затем в следующем кадре он обнаруживает только одно столкновение, которое находится между левым красным прямоугольником и зеленым прямоугольником, и разрешает его:

введите описание изображения здесь

Как вы можете видеть, это на самом деле не разрешает столкновение (например, путем выталкивания зеленого прямоугольника вверх), а вместо этого просто бесконечно переключает провалы между двумя состояниями.

Как я могу решить это?

TravisG
источник
Вы используете прямоугольники в своем примере. Ваш алгоритм столкновения разрешает столкновение только по одной оси? Если это так, имеет смысл, что поведение, которое вы описываете, происходит.
хаосТехник
Нет, он может разрешить их с помощью любых форм на всех возможных осях (не только прямоугольники, их просто нарисовать с помощью MS paint: P), и он всегда найдет самый короткий вектор, который разделяет два объекта ,
TravisG
+1 Хороший вопрос. Я удалил (2D) «тег» из заголовка, это то, что вы должны избегать (см. Мета ).
bummzack

Ответы:

7

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

Вот подробности: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

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

Если вам нужно / нужно больше, вы можете приобрести его исходный код за (IIRC) $ 7.

Вот видео моей реализации в 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

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

Ольховский
источник
2

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

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

Михай Марусак
источник
Добавить небольшой случайный вектор с величиной около эпсилон * 10 к столкновениям? Арифметика с плавающей точкой должна делать все остальное.
Мартин Сойка
2
Да, это может работать, я думаю. Но это также может создавать дрожащие движения.
Михай Марусак
1
Я надеюсь, что все еще могу получить ответ на этот вопрос: вычисление результирующего исправляет проблему «бесконечного цикла», но вновь вводит проблему «трещины», когда движение при скольжении по стене, выполненной из плиток того же размера, заставляет тело получить застрял между "трещинами" плитки. Есть ли способ решить обе эти проблемы?
Витторио Ромео
Согласитесь ... нет лучшего «правильного ответа» для решения такого невозможного столкновения твердого тела, как это. Либо он дрожит, либо вы допускаете некоторую «мягкость» в одном или нескольких объектах.
Дэвид ван Бринк
0

Если вы внимательно посмотрите на это, то состояние объектов является (или должно быть) недостижимым ..

Пусть крайняя левая красная форма будет иметь форму R1, а крайняя правая красная форма будет иметь форму R2. Пусть зеленая форма будет G.

т.е. учитывая размер и геометрию всех трех объектов и учитывая, что все объекты не проницаемы:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

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

Если G проверяется на R1 после того, как проверяется на R2, то G, по-видимому, юридически находится справа от R1 (если G, скажем, приближается к R1 с направлением вектора <-1, -1> с произвольной величиной (или расстоянием) ), потому что проверка между R1 и G позволяет это, и забывает о проверке между R2 и G, которая была сделана ранее.

Решение, которое вы можете сделать, - это собрать все векторы минимального смещения в массив или любую другую структуру данных, которую вы хотите, и выбрать тот, который окажется допустимым для ВСЕХ объектов.

Обратите внимание, что в данном кадре объект (например, G) может иметь только ОДНО направление. (о человек, звучит как бойфренд ...)

Лю Мао Син
источник