Self-made физика и ее оптимизация

Года два назад написал физику для игры на языке C# которую можно использовать одновременно и на сервере и на клиенте. И вот пришло время достать ее из долгого ящика, и попутно из прототипа превратить уже в финальный алгоритм.

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

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

Для доведения до релизного состояния необходимо:

Беремся за дело.

Для начала переписал алгоритм, теперь он за вызов производит сразу все расчеты и прогнал его через юнитевый профайлер. Который показал что самая тяжелая функция вызывается QSolver.SolveBiQuadsEquation порядка 20тыс раз и суммарно весь расчет генерит 20мб аллокаций. Тут ничего особенного: было много аллокаций массивов - аллоцируем 1 раз и дальше переиспользуем, постоянные аллокации различных небольших классов - переводим на структуры и тд. В результате вместо 20мб теперь всего 100кб. При таких оптимизациях не забываем про потенциальную многопоточность, те аккуратнее со static полями.

Можно и еще меньше сделать, но это уже не имеет существенного значения.

Теперь небольшая оптимизация самой функции QSolver.SolveBiQuadsEquation. Ее задача - решение уравнений 4й степени. Поменяем алгоритм, избавляемся от комплексных чисел и будем использовать Ferrari's solution (https://en.wikipedia.org/wiki/Quartic_equation#Ferrari's_solution_in_the_special_case_of_real_coefficients).

Пришло время заменить double на что нибудь целочисленное. Выбор был между r128 (https://github.com/fahickman/r128/blob/main/r128.h) и soft_double (https://github.com/ckormanyos/soft_double). Первое - это число с фиксированной запятой с размеренностью 128 бит. Второе - это софтовая реализация double и 64-bit. В итоге выбор пал на soft double. Портируем на C#, поправили в нем пару багов, и в итоге производительность упала сразу в 6 раз. Но это нормально. Наша цель - стабильность расчетов.

Последний этап (хотя его лучше делать первым, но избавиться от аллокаций и перевод на soft double все равно нужно было): снижаем сложность алгоритма и уменьшаем количество вызовов вычислений. Тут конечно пришлось хорошенько подумать над тем как реально двигаются все объекты, как и когда они реально пересекаются.

Самое простое это попробуем добавить баунды на движение. Все объекты в системе двигаются по функциям второй степени: p(t)=p0 + v0 * t + a * t^2 / 2. Разложив все функции движения по всем осям и проведя анализ каждой параболы можно высчитать min/max зависящие от времени. Кэшируем баунды. В итоге всего 800 расчетов уравнений вместо 20тыс.

Как итог время вычисления на тестовой системе стало порядка 16 мс. Те исходно 50 мс. Перевели на soft_double оно выросло до 300мс. И в результате анализа физики и ее доработок стало 16мс (!). Цель достигнута и дальше можно не тратить время.

Решил еще портировать все на C++ и сравнил в итоге с тем C++ который получается из C# с помощью юнитевого ill2cpp. Сначала результаты были такие что C++ физика работала быстрее в 2 раза. Но потом оказалось что нужно еще правильно тестировать ибо на процессоре есть как производительные ядра, так и эффективные. Немного переделав методику тестирования оказалось разница не в 2 раза а всего порядка 5-10 процентов. Что уже не принципиально.

Теперь занимаемся самой игрой используя прекрасный паттерн MVVM уже не только для UI но для самой игры. Но об этом в другой раз)

#gamedev