Всего один шаг

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

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

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

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

Для начала, разберёмся, что такое физический объект. Физический объект обладает некой поверхностью, которой он может соприкасаться с другими. Обычно это шар, капсула, параллелепипед (бокс), но потенциально это может быть вообще любое множество, главное подобрать соответствующие алгоритмы обработки. А ещё физический объект обладает физическими свойствами типа массы и импульса. Для столкновения обязательно, чтобы оба объекта обладали поверхностью и хотя бы один массой, потому что для обработки столкновений нужно что-то двигать, а если нечего двигать, то предотвратить такое столкновение физическому движку невозможно.

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

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

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

Но что, если столкновение происходит дольше одного шага? Что если столкновение произошло, но в тот же шаг не удалось вытащить один объект из другого? Вся информация о прошлом положении объекта уже утеряна, как и его скорость уже изменилась. В каком положении его вытаскивать? Движок больше этого не знает, поэтому придётся угадывать. Чаще всего происходит выталкивание в ту сторону, куда объект быстрее всего вытолкнуть. Именно из-за этого в играх можно телепортироваться сквозь стены — они тонкие, легко случайно оказаться на другой стороне центра масс.

Это вынужденная мера. Потому что ну а как ещё? Хранить всю историю скоростей и положений объекта до столкновения? Ну так никакой памяти не хватит (по-крайней мере, раньше не хватало). Да и всё равно это ничего не гарантирует. Хотя, скорее всего, в современных движках, особенно шутерах, стабильность геймплея ценят больше, чем память, так что физические движки делают всё, лишь бы никаких лагов не происходило, чего бы им это не стоило.

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

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

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

Например, если у вас вращаются объекты, то вам сначала нужно будет найти такое положение, чтобы объекты находились друг другу параллельно. Сами объекты по волшебной палочке такое состояние не найдут, вместо этого находясь в бесконечном качании с одного угла на другой, как монетка, упавшая на стол. А после этого ещё и убедиться, что на них не действуют никакие будоражущие их силы.

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

А представьте, что у вас десятки таких объектов. И все их нужно проверять на столкновения. 10^2 уже 100, 20^2 уже 400, а эти вычисления нужно производить каждый такт, 60 кадров в секунду. Велико, да?

А 90% времени эти проверки даже не нужны, ведь объекты находятся друг от друга слишком далеко. Поэтому в движках есть возможность выбирать, по какому алгоритму объект будет обрабатывать столкновения: подробному или упрощённому. Упрощённый порядок обрабатывает столкновения только если объекты прямо пересекают друг друга, без каких-либо предсказаний. Такое годится только для достаточно больших и медленных объектов. Но вот снаряды нужно обрабатывать как следует, потому что им очень легко на диких скоростях даже за один такт пролететь сквозь стену и движок ничего не заметит.

Короче говоря, всё это очень тяжело, так что разработчиков физических движков можно только поблагодарить — это адский труд, хуже любого ИИ для врага или рейтрейсинга.

Думал написать всего три абзаца, но как же дико это всё растянулось. И это я очень упрощённо описывал, охватил примерно 10% проблематики. Поставьте лайк, что ли, а то новый месяц, надо обратно в топ.