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

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

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

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

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

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

  • Сделать так чтобы при одинаковых вводных она работала на всех платформах и любых повторах абсолютно одинаково. А значит нужно избавиться от чисел с плавающей запятой. Если кому интересно может почитать статью: https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/
  • Отрефакторить так чтобы расчеты были не per-tick, а считался весь процесс и с минимальным размером данных выдавался такой результат по которым ее можно было воспроизвести (хотя это не обязательно, но лучше перевести)
  • Оптимизировать, ведь исходный алгоритм имеет сложность O(n^2). На тестовой сцене полный расчет длится 50мс на iPhone 15 pro и использует около 20000 вычислений корней уравнений 4-й степени. При переводе на целочисленную арифметику это время непременно вырастет.

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

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

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

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

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

Теперь небольшая оптимизация самой функции 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 но для самой игры. Но об этом в другой раз)

66
11
21 комментарий

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

1
Ответить
Автор

Доеду с работы до дома, сделаю. Спасибо 👍

1
Ответить

Не видел исходников, но сразу 2 момента (на стороне C#) - выделение происходит на куче, как я понял? может на стек перенести? И второй, может использовать небезопасный код с указателями для хотя бы какого повышения производительности?

1
Ответить

А что хранить в стеке?
Небезопасный код похерит детерминизм.

Ответить
Автор

достаточно было просто переиспользовать аллоцированную один раз память при инициализации солвера

Ответить

хотелось бы поподробнее конечно.
я тоже могу картинки сгенерить и ссылки на Вики дать будто я что-то делаю ;)

1
Ответить
Автор

С удовольствием почитаю) подробности не могу сейчас к сожалению, только после релиза. 1-2 месяца.

Ответить