Обработка столкновений

[s-andriano]

Сообщение от Granus

Может быть я чего-то недопонял. Скажем, столкновение нескольких AABB одновременно. Как Вы предлагаете его предотвратить?

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

[karuy]

http://isadateam.com/doc/phys1.htm - может окажется полезным. Пример прилагается.

[Гром]

Сообщение от s-andriano

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

Ню-ню.
Учитывая, что время в компьютерных симуляциях течет исключительно дискретно, проблема возникает очень часто и доставляет много хлопот.
В качестве примера возьмем, например, три круглых двумерных тела. Пусть начальные координаты первого - (0, 0), второго - (2, 0), третьего - (1, 1). Радиусы всех равны 0.5 (диаметры, значит, по единице). Скорости: (0.67, 0), (-0.67, 0), (0, -0.67). Если расположить прямо под ними шахматную доску, то первый будет находиться прямо над А1, второй - над С1, третий - над B2 (это для наглядности). В результате, через единицу времени из такой картины:

 О
О О

получается что-то вроде этого:

[Granus]

karuy, спасибо за материал.

Гром, большое спасибо. Именно о таких случаях речь и идет. А при наличии неподвижных объектов (стен, полов и т.д.) столкновение одновременно с десяточком объектов - не редкость. И как Вы такого рода столкновения обрабатываете?

[Kostia]

И как Вы такого рода столкновения обрабатываете?

Последовательно, сначала растолкаю красный и зеленый, затем красный* и синий.
красный* - красный в новой позиции.
Эффективнее, определить все проникновения красного в остальные, и правильно их растолкать исходя из глубины проникновения. Затем проникновение зеленого в синий и их тоже растолкать. Повторить несколько раз для всех объектов (расслабление системы).

[s-andriano]

Сообщение от Гром

Ню-ню.
Учитывая, что время в компьютерных симуляциях течет исключительно дискретно,

Это неверное утверждение.
Вполне вероятно, в некоторых примитивных случаях дело обстоит именно так, в общем же случае мы сами задаем, как должно течь время в нашем виртуальном мире.
Как сделаем, так и будет. Никакой фатальности здесь нет и быть не может.
Все эти "исключительно дискретно" происходят исключительно от недостатка квалификации разработчика.

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

Ну да, как обычно - сначала придумываем себе проблемы, а потом их мужественно решаем.

В качестве примера возьмем, например, три круглых двумерных тела. Пусть начальные координаты первого - (0, 0), второго - (2, 0), третьего - (1, 1). Радиусы всех равны 0.5 (диаметры, значит, по единице). Скорости: (0.67, 0), (-0.67, 0), (0, -0.67). Если расположить прямо под ними шахматную доску, то первый будет находиться прямо над А1, второй - над С1, третий - над B2 (это для наглядности). В результате, через единицу времени из такой картины:

Элементарные подсчеты показывают, что тела 1 и 2 столкнутся через 0.67. Именно в этот момент и нужно обрабатывать столкновение, не дожидаясь, пока пройдет полная единица времени.
Это - первое.

Теперь - второе.
Вы умышленно выбрали такие условия, что столкновения нескольких тел произойдет одновременно. В природе так не бывает. Значит, Ваш вариант не соответствует ни тому, что реально имеется в природе, ни тому, что можно нормально обработать (последовательное попарное столкновение объектов). Т.е. Вы умышленно искажаете ту картину, которая реально встречается в природе, и именно вследствие этого приобретаете проблемы.
Вы задаете координаты и скорости с точностью до 0.01. Добавьте ко всем данным по 0.01*(random - 0.5). Это самое простое, что можно предложить.

[Kostia]

s-andriano, вы неправы.

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

dt меньше чем машинный нуль взять не получится.

Элементарные подсчеты показывают, что тела 1 и 2 столкнутся через 0.67. Именно в этот момент и нужно обрабатывать столкновение, не дожидаясь, пока пройдет полная единица времени.

А для системы из 5 тысяч тел сложной формы?

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

Современные компьютеры неспособны обработать физику как она есть в реальном мире, поэтому в gamedev'е всегда упрощают модель реального мира, и после этих упрощений естественно столкнуться с проблемами которые в оном не встречаются. Но при правильной обработки различных исключительных ситуаций можно получить вполне приемлемую имитацию.

Вы задаете координаты и скорости с точностью до 0.01. Добавьте ко всем данным по 0.01*(random - 0.5). Это самое простое, что можно предложить.

o_O

Вот давно еще на Delphi 7 писал:

[Granus]

Это неверное утверждение.
Вполне вероятно, в некоторых примитивных случаях дело обстоит именно так, в общем же случае мы сами задаем, как должно течь время в нашем виртуальном мире.
Как сделаем, так и будет. Никакой фатальности здесь нет и быть не может.
Все эти "исключительно дискретно" происходят исключительно от недостатка квалификации разработчика.

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

[s-andriano]

Сообщение от Kostia

dt меньше чем машинный нуль взять не получится.

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

А для системы из 5 тысяч тел сложной формы?

Без разницы.
Законы природы для всех одинаковы.

Современные компьютеры неспособны обработать физику как она есть в реальном мире, поэтому в gamedev'е всегда упрощают модель реального мира, и после этих упрощений естественно столкнуться с проблемами которые в оном не встречаются. Но при правильной обработки различных исключительных ситуаций можно получить вполне приемлемую имитацию.

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

Сообщение от Granus

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

В принципе, со всеми тезисами согласен. Возможно, кроме некоторых акцентов.

Вы уверены, что плюсы второго перевесят расходы на него?

Это нужно решать в каждом конкретном случае.
Универсального решения пригодного на все случаи жизни не существует.

[Granus]

s-andriano, видимо, не до конца Вас понимаю. Вы сильно критикуете многое из того, что здесь пишут. Опишите целиком, как, по-вашему, должно все это происходить, по полочкам.