Как я создал собственную мини-Вселенную

Сегодня в 18:10 Прокомментировать Просмотры: 19

Приветствую, уважаемый читатель!

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

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

Всё зародилось из стремления промоделировать зарождение космических систем. Первоначальный прототип я набросал на Python. Всё шло неплохо, пока не уперлось в критический недостаток интерпретируемого языка — катастрофически низкое быстродействие. Осознав это после завершения базовой реализации, я решил мигрировать на C++, с которым на тот момент был знаком поверхностно, активно привлекая искусственный интеллект для помощи в репортаже кода. Перенос занял всего сутки, и результат превзошел ожидания: во-первых, всё заработало с первой попытки, а во-вторых, колоссальный прирост производительности полностью оправдал затею.

Архитектура системы

Проект состоит из следующих ключевых модулей:

Набор физических законов — инкапсулированы в пространстве имён Laws в виде отдельных функций;
Ядро движка — класс PhysicsEngine, управляющий массивом частиц и последовательным применением законов;
Графический модуль — отвечает за рендеринг посредством библиотеки SFML;
Утилиты — FrameSaver для экспорта последовательности кадров в PNG и ConfigLoader для инициализации параметров из текстовой конфигурации.

Жизненный цикл симуляции

Инициализация пространства: рождается заданное или псевдослучайное множество частиц с уникальными характеристиками.
С фиксированным временным шагом dt последовательно вычисляются актуальные взаимодействия для каждого элемента: гравитационные силы, инерция, столкновения, диссипация энергии…
Этап визуализации: на экран выводятся частицы (оттенок отражает массу), векторы скоростей (цвет сигнализирует о динамике) и активные ячейки гексагональной сетки, о которой пойдет речь далее 😉

Динамика трения и упругие столкновения

Ниже представлены две демонстрации: в первой смоделирован упругий удар с минимальным коэффициентом трения, во второй — режим с повышенным сопротивлением среды:

Вектор оптимизации

Создание физических симуляций неизбежно упирается в проблему производительности. Если на 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 из самих объектов на каждом шаге и позволившая эффективно оперировать текущим счетчиком цикла.

Итоговые показатели производительности

Сравнительные тесты времени расчистки кадра для выборок из 1000 и 5000 элементов до и после оптимизационных процедур дали следующие цифры:

Частиц	Без сетки	С HexGrid
1 000	~2 мс	~1 мс
5 000	~55 мс	~7 мс

Ну и какой же проект без стресс-теста «на прочность» железа 🙂 Сразу оговорлюсь: на иллюстрации ниже отключена гравитация, поскольку глобальные дальнодействующие силы разрушают изоляцию ячеек, сводя эффект сетки на нет.

Расчёт 1000 000 частиц — Расчёт 1 000 000 частиц

Нереализованные идеи

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

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

Заключение

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

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

Благодарю за уделенное чтению время! Буду искренне рад конструктивной критике, мнениям и идеям в комментариях.

Полезные ссылки

GitHub-репозиторий: https://github.com/FRIMIDOVO/Your-Univerce
Telegram-канал: https://t.me/chumarno — оперативные инсайды и новости разработки публикую там гораздо чаще.

Источник