Привет, читатель!

Однажды, после просмотра ролика про эволюцию Вселенной, я загорелся идеей создать свою, со своими правилами. В итоге я написал собственный физический движок на С++, и в этой статье я расскажу про него, историю создания, и разные нюансы.

День, который всё изменил

Началось всё с желания создать вселенную со своими правилами, посмотреть на её эволюцию. Начал писать я на Python, и всё бы ничего, если бы не его скорость, а она совсем не велика. Понял я это не сразу, а после того, как написал уже рабочую версию движка, поэтому код я переносил советуясь с нейронкой, тем более язык С++ для меня пока новый. Транспортировал проект я за 1 день и был очень рад: во-первых тем, что оно вообще работает, во-вторых скоростью - то, ради чего я и затеял это.

Как это устроено

В общем существуют:

• Набор законов — все в отдельном пространстве имён Laws в виде функций;

• Сам движок — PhysicsEngine, хранит список частиц и просчитывает все законы;

• Визуализатор — рисует на SFML;

• Вспомогательные штуки — FrameSaver для сохранения кадров в PNG, ConfigLoader для подгрузки настроек из txt.

Как это работает

1. В пространстве создаются частицы, каждая со своими свойствами(заданными или случайными в диапазоне).

2. С определённым шагом dt, просчитывается набор из правил для списка всех частиц, такие как: гравитация, инерция, коллизия, трение...

3. После расчётов — визуализация: частицы(цвет зависит от массы), векторы скорости(цвет зависит от скорости), активные ячейки гексагональной сетки, про которую я расскажу чуть подробнее ниже;)

Трение и эластичные столкновения

Вот две симуляции, где в одной столкновение эластичное и с маленьким трением, а во второй трение увеличено:

Оптимизация

Ну куда же в программировании физики без оптимизации. На Python 50 частиц уже предел, на C++ получилось сдвинуть порог до ~5000 частиц, но на этом я не хотел останавливаться, поэтому стал рыться в этой теме.

Алгоритмическая сложность

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

• Линейная сложность — O(N) — время растёт пропорционально числу частиц.

• Квадратичная сложность — O(N²) — время растёт как квадрат числа частиц.

Так, например, для 10 000 частиц разница в количестве операций будет колоссальной: 10 000 против 100 000 000.

Что было сначала

Изначально у меня была квадратичная сложность O(N²) для всех законов. В коде это выглядело как вложенный цикл:

for (size_t i = 0; i < particles.size(); ++i) {
    for (size_t j = i + 1; j < particles.size(); ++j) {
        // проверяем взаимодействие каждой пары
    }
}

Каждая частица "смотрела" на все остальные. Это самый медленный из возможных вариантов для парных взаимодействий.

Частично решить эту проблему мне помогла пространственная сетка!

Пространственная сетка

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

Математика перевода из декартовых координат в аксиальные(с округлением в кубических) и назад:

Hex HexGrid::pixel_to_hex(const Vec2& pos) const {
    float q = pos.x * inv_hex_D + pos.y * inv_hex_D_sqrt3;
    float r = -2 * pos.y * inv_hex_D_sqrt3;

    float& x = q;
    float& z = r;
    float y = -x -z;

    int rx = round(x);
    int ry = round(y);
    int rz = round(z);

    float dx = abs(rx -x);
    float dy = abs(ry -y);
    float dz = abs(rz -z);

    if (dx > dy && dx > dz) {
        rx = -ry -rz;
    } else if (dy > dx && dy > dz) {
        ry = -rx -rz;
    } else if (dz > dy && dz > dx) {
        rz = -rx - ry;
    }

    return Hex(rx, rz);
}

Vec2 HexGrid::hex_to_pixel(const Hex& hex) const {
    float x = hex_D * (hex.q + hex.r * 0.5f);
    float y = -hex_R * 1.5f * hex.r;
    return Vec2(x, y);
}

Я сначала это всё на листочке расписывал даже, что бы максимально понять:)

Преимущества гексагональной сетки:

• Каждая ячейка равноудалена от соседей — равномерное заполнение.

• Минимальное количество соседей.

• Изотропность расчётов (одинаковость во всех направлениях).

Суть работы сетки

Основная суть — не просчитывать взаимодействия между всеми частицами, а "смотреть" только в соседние ячейки, что снижает сложность до линейной.

Данный фокус работает только с близкими взаимодействиями, по типу трения, столкновений. Гравитация в свою очередь дальнодействующая, поэтому такая сетка здесь ничем не поможет. Есть способы её оптимизации, но у меня она всё ещё имеет квадратичную сложность.

Я храню в классе сетки словарь:
хэш_адреса_ячейки(отдельная структура данных): список_индексов_партиклов_в_этой_ячейке

И записываю партикл в ячейку при его малейшем пересечении описанного вокруг шестиугольника круга. Затем в функции не просчитываю взаимодействие между всеми частицами, а только каждую с соседями(кроме гравитации). Чпок — и всё!

p.s. Я немного костылю, тем что записываю не id а индексы партиклов, но оно работает и пофиг как-то. А делаю так, потому что... не помню, но чёт сложно или затратно было доставать id из каждой частицы, а брать просто i из самого же цикла норм было.

Какая скорость в итоге

Я сравнил скорость расчётов физики при 1000 и 5000 элементах до и после оптимизации и получил такие циферки:

Ну и куда без нагрузки пк до максимума:) Если что здесь без гравитации.

Не добавленные фишки

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

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

Заключение

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

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

Спасибо, что прочитали эту статью, пишите в комментариях свои мнения, идеи. Буду рад обратной связи!

Ссылки

• GitHub: https://github.com/FRIMIDOVO/Your-Univerce

• Telegram: https://t.me/chumarno — тут я выкладываю новости по проектам чаще.