Продолжаем работу над обнаружением коллизий

Рассказывая про обнаружение и обработку столкновений в игре, я обмолвился о простенькой физической системе, добавленной чтобы как-то разруливать эти самые коллизии. Я практически ничего про это не рассказал потому что практически ничего и не сделал. Да движок научился отвечать на вопрос пересекаются ли два игровых объекта или нет. Но этого было недостаточно. Чтобы грамотно разрешить коллизию нужны детали: насколько глубоко объекты проникли друг в друга, какие грани или вершины участвуют в контакте и тому подобное.

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

Эта проблема стала особенно заметной, когда я добавил в игру ИИ. Игроки перемещались хаотично и то и дело собирались в кучу. Выбраться из неё получалось не всегда. К примеру, если ты пытался выбежать из этой толпы и кто-то из игроков делал то же самое, то ничего не выходило у обоих. Вы постоянно догоняли и врезались друг в друга, что приводило к своеобразному deadlock-у. Пришлось даже научить ИИ оценивать обстановку вокруг, и в случае столпотворения искать брешь чтобы выбраться. Стало лучше, но полностью проблема не решилась.

Я долго откладывал эту проблему, но теперь пришло время с ней разобраться.

Объем информации, которую можно получить из коллизии зависит от используемого алгоритма. К примеру, некоторые из них в рамках теста на пересечение позволяют определить так называемый MTV (Minimum Translation Vector). Это вектор, определяющий направление и минимальное расстояние на которое нужно растолкнуть объекты, чтобы разрешить коллизию.

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

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

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

Но это ещё далеко не конец. Преодолев одну вершину, я обнаружил следующую.

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

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

Но поскольку нет предела совершенству я решил отложить решение этой проблемы чтобы заняться чем-нибудь более важным. Текущая реализация – это уже большой шаг вперёд. Все перечисленные в начале проблемы были решены, поэтому будем двигаться дальше.