Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Поток Геймдев доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 55
Простой и увлечённый технический пост о переносе математической симуляции с Python на C++ для получения высокой частоты кадров при просчёте большого количества объектов. Автору респект, молодца!
Проект шикарный, одно замечание -- вы в гитхабе в репозиторий закинули ярлыки, аа не конфиги)
Видимо следующие пару месяцев буду переносить физику своего фентези рассказа на виртуальный движок. Спасибо за вдохновение.
Пишете фэнтези? Я больше фантастику и мистику. плюс там много философии и психологии. Переносить нечего, отдельные законы не изобретал. :) Но вообще данный пост действительно вдохновляет... :) Вам тоже удачи!
Я в основном пишу научную фантастику. Но решил сделать один фэнтезийный рассказ для отдыха, ну и потому что хотел попробовать продумать свою физику, анатомию, как бы работал мир с другими физическими явлениями и как бы там развивалась эволюция. Может отдалённо его тоже можно назвать научным, но что бы никого не путать решил называть фэнтезийным
Мне очень приятно, что кого-то это вдохновило! Не могли бы вы поделиться, что за фэнтези рассказ, если это не секрет? Очень интересно было бы:)
Я его пишу по наитию, только на законах физики заостряю большое внимание. Боги для своих целей создали сверх сильного мага, но потом он им оказался не нужен, он проиграл и почти умер в самой важной битве. Рассказ начинается через 7 лет после этой битвы. Гг лишили полностью магии, все на него злы так как думаю что из за него битва проигранна, единственное для чего его создали боги он больше сделать не может
Я думаю дальнейшее понятно. Где то там в мини-вселенной есть программист, который пишет свою микро-вселенную, а в той потом появится программист, который создаст кроха-вселенную...
Ну тогда согласно теории Ника Бострома нас тоже кто-то довольно таки активно симулирует вместе со всеми физическими законами, числами пи, блекджеками и прочими распутными девами.)
Найти бы этого двоечника
нас тоже кто-то довольно таки активно симулирует
Так это почти доказано... :)
https://erichware.name/mysli/simulator.htm
"ТВОЙ БЫДЛОКОД НАС ОГОРЧАЕТ" (c)
Главное чтобы этот микро-программист не начал майнить крипту в своей мини-вселенной, иначе наш хост просто сгорит от перегрева)
Так нельзя же тупо смотреть только на соседние ячейки. Гравитация так не работает. Так можно делать только для локальных взаимодейсвий вроде столкновений.
Есть честные O(n log n) методы для просчета гравитации. Например Barnes-Hut. Там, конечно, тоже есть неточности, но не настолько ужасные. Там тоже использутеся сетка, но все далекие объекты в далеких ячейках групперуются и заменяются точечной массой и все-таки учитываются хотя бы аггрегированно.
Если же к этой идее приложить еще и жесткую математику, то получается O(n) метод для просчета гравитации глобально (fast multipole method). В отличии от вашего хака, там есть далекое взаимодействие и точность можно приближать сколь угодно близко к идеальной.
О! Игра "жизнь" уже не та. Респект автору, красиво получилось.
Вспомнилась старая книжка "Этюды для программистов". Там в том числе описывалось моделирование гравитационного взаимодействия большого числа звёзд на слабых компах. Чем-то сиё напомнило.
Как думаете, стоит ли прочесть данную книгу?🤔
Да. Она старая, проблемы местами уже решены (всё-таки в компах уже не десятки кб памяти, к примеру), но читать было интересно.
Хорошо, я обязательно найду время, чтобы прочесть её, вы меня заинтересовали.
https://publ.lib.ru/ARCHIVES/U/UEZERELL_Charl’z/_Uezerell_Ch..html — я, похоже, ошибся в названии. Эта книга тоже хороша и я её читал, но я не нахожу там задачи про гравитацию.
Нашел-таки. Книга называется "Жемчужины программирования".
https://publ.lib.ru/ARCHIVES/B/‘‘Biblioteka_programmista’’_(seriya)/%c1%e5%ed%f2%eb%e8%20%c4%e6._%20%c6%e5%ec%f7%f3%e6%e8%ed%fb%20%ef%f0%ee%e3%f0%e0%ec%ec%e8%f0%ee%e2%e0%ed%e8%ff.(2002).pdf
Судя по всему, читал ещё первое издание.
Оптимизация на 5к частиц это круто, но настоящая боль начнется при многопотоке. Попробуй распараллелить расчеты хотя бы на пару ядер, вот там узнаешь что такое настоящие гонки данных в масштабах вселенной))
О, да, это классная тема. Но там, как и везде свои нюансы, которые надо изучать. Я думал перенести некоторые расчёты на видюху, но у меня почему-то не устанавливалась Cuda от Nvidia. Пробовал распаралелить на ядра процессора, особо ничего не изменилось, скорее всего я что-то не так делал, но я не знаю что именно.
Да не, в этой задаче все просто. Если уж тут все взаимодействия происходят парочками, то можно и все импульсы считать независимо. И потом их все применить к скоростям. Надо только их аккуратно аггрегировать. Тут достаточно atomic<double> v_x; v_x += imp_x; использовать.
А Большой Взрыв там будет? Черные дыры? Аттракторы? Хотя бы схематично. А так глядишь кто-то из ученых найдет этот проект и придумает гениальную гипотезу, которая обьясняет вот прям всё! Маловероятно конечно, ну а вдруг.
Кто знает, кто знает;) Я конечно себе всё это в голове изначально и представлял, но очень непросто оказалось такое сделать. Например даже если просто сделать тор-образное пространство, уже будет надо очень много чего пересмотреть: гравитацию, пространственную сетку, визуализацию.
Посмотрите в сторону игрушки powder toy. Там и гравитация (в тч черные дыры) и взаимодействие 100500 частиц, взрывчатка, песок, ветер и даже атомный взрыв с некоторой условностью можно сделать. Физика там конечно довольно своеобразна но это детали. Советую также обратить внимание на механизм встроенного в игру захвата экрана, неважно с какой скоростью все эмулируется но игра генерирует один кадр за проход и сохраняет его в изображение. Затем это можно с "нормальной" скоростью преобразовать в видео и просто посмотреть видеоролик, как оно там что происходит.
Теперь смотрите в сторону CUDA. :)
классно у вас получается, на реддите видел и походу какую-то вселенную, и такую вселенную (почему бы нет как визуализация контекстов так сказать ) )
Создал пустую вселенную на листке бумаги - познал дзен.
Какая скорость в итоге
вы показали кстати! 1000-5000, дальше можно отвязаться от stl(vector, hashmap) и попытаться наколбасить своё управление памятью.... я может не прав, но со своим аллокатором(который связан интрузивно с кор подсистемой памяти будет) и подсчетом байт удобнее чем с вектором, но отлаживать гемор(хотя кому как наверно), попробуйте посмотреть в сторону интрузивных счетчиков ссылок, как итог ваши буферы станут чуточку удобнее и тесты можно будет проводить на 10к-100к(тоесть в 3д уходить наверно не знаю в обьём(кубики или другие примитивы, тут я не знаю, но там тоже есть SpatialHashGrid/SpatialGrid/BVH(за счет того что ваши частички вроде не уникальны это можно будет отрисовывать через MultiDrawElementsIndirect закидывая матрицы в ssbo, за 1 вызов типо считайте сами какой прирост...) или еще что поидее)) наверно, плюс можно на С++ наколбасить свой модуль по SIMD(берете спецификацию файла симд по 4.1/4.2 и пишите бинды свои! в модуле именно в модуле .cppm), плавно переходящий в свои расчеты типо.... всё это конечно гемор....
ну и так по мелочи модули(именно модули .cppm). конечно, на любителя, на алгоритмы я последнее время в последнюю очередь смотрю, щас приоритет на архитектуру с кор системы...
Скрытый текст
у меня щас так выглядит все .cppm это модули, и скрипт свой на сборку проекта
Спасибо большое, что делитесь ценным опытом! Он очень мне пригодится, как во время улучшения этого проекта, так и в будущем:)
Не очень активно прислушивайтесь к этому комментатору, он весьма своеобразный. Писать свои аллокаторы - это терминальная стадия синдрома "это плохо, потому что сделано не тут". В вашей демке вообще аллокаций во время работы не должно происходить. Перед симуляцией выделили массивы и все. Выбором алгоритмов и структур данных вы гораздо больше пользы получите.
Безусловно, я буду оценивать, нужны ли те или иные изменения ради оптимизации, и будет ли вообще от них польза.
По факту, да, во время работы программы, пока что, у меня вообще не изменяется массив с частицами, поэтому ускорять нечего. Но в принципе мне будет полезно знать, что такое вообще можно сделать.
Спасибо, что даёте возможность оценить ситуацию с разных сторон.
Чтобы понять, нужно ли вообще заменять vector из STL на что-то другое, нужно профилировать программу и посмотреть, какие куски исполняются дольше всего. А то можно ускорить в 10 раз то, что исполняется 1% времени, и толку никакого не будет.
Выше давали совет распараллелить код и исполнять его в нескольких потоках одновременно - ИМХО, вот это может действительно серьезно ускорить программу.
Согласен, в первую очередь стоит распараллеливать и пробовать переносить какую-то нагрузку на видеокарту.
В первую очередь эффективные алгоритмы.
Кстати, по данной теме я бы предложил посмотреть в исходники с тематики демосцены. Там похожие задачи эффективно решены.
ИМХО, здесь вообще все можно на видеокарте делать. И в ней тоже есть распараллеливание.
вот демка бесшовная с тестовыми инстансами простыми пока без потоков,
эта демка на библиотеках, я нигде не копался, тут одни вектора и хеш мапы как понимаем, суть в том, что под стриминг нужно определенное поведение вектора, да ниже приведу сразу профайл с рендердока чтоб было нагляднее....
можно итак оставить, но под Indirect вектор же не удобен, нужна именно система памяти поудобнее же.... хотя может оно и пофиг конечно не знаю..... я в дилемме, там мне удобно с управлением, а под прототип, всё колбасить своё сложно конечно тут соглашусь....
почему пишут другое поведение вектора, потомучто там идёт снизу вверх управление памятью с трекинком и передаче ссылки на общего владельца более удобным способом, как я понимаю, это нагляднее и удобнее поидее(мини зиг подход, есть аллокатор и аллокации видно явно типо..., с владельцами ресурсов не надо напрягаться в голове держать где копировать где не копировать 1 раз написал считалку и удобно, на анимациях можно будет выдыхать будет 1 владелец ничо не прокопируется ваще красота....), плюс у себя можно сделать так чтобы регионХ9 держался без перевыделений же. на векторе самом с шринк_ту_фит это может быть проблематично, но реально, кстати точно такая же ситуация и с клоном майнкрафта, ровно 1 в 1 ситуация, просто на расте сенд/ресив из коробки, и владелец памяти каналы. Но всё равно там тоже шринк всё портит на скоко помню....
техника мега-буфера - подразумевает многопоточность в том числе, от вектора можете не избавляться, но как вы предлагаете управлять памятью? автоматически от вектора...
переиспользование(архитектура) - будет подразумевать написание своей архитектуры всё равно, чтобы не писать то, что исследовано по новой. от симда не уйти перемножать матрицы быстрее на ней, от BVH/ускоряющейструктуры не уйти, так что как не крути, чтобы приблизиться к вулкану по скорости это gl4.5+, и управление памятью(модули в проекте это просто удобство для создания кода и ускорения компиляции как не крути).
просто если щас у вас 1-5 хакатонов/прототипов/побыстреесделать, вам категорически запрещается думать об этом, скачайте библиотек или анриал енжин с нанитами проку больше будет...
итоги - мои тейки сложно пробить )
~ https://github.com/erincatto/box3d вот получается то*** , что вы хотели частично или движок(Анриал).
*(частично, модули всё еще нужны, другие ускорялки тоже наверно, библиотеки всякие или движки как там всё это организовать ) кароче как не крути путь долгий )...
**ну и еще парочка пейперов придётся почитать, потомучто всё это исследовать проверять надо помимо профилирования...
лично у меня всё вокруг этого закрутилось
Скрытый текст
int main() {
Window window(" Spatial Grid Visualizer",3,3,800,600);//
glEnable(GL_DEPTH_TEST);
// unsigned int brick=;
Alloca::Ref myAllocator = Alloca::create();
HashMap<const char*,Texture::Ref> textures(myAllocator);
TextureCache textureCache(&textures);
//textureCache.InsertTexture("Brick","assets/texture/brick1.tga");
textureCache.InsertTexture("Brick","assets/texture/brick1.tga");
HashMap<const char*, GameObject::Ref> objs2D(myAllocator);
HashMap<const char*, GameObject::Ref> objs(myAllocator);
HashMap<const char*, Shader::Ref> shade(myAllocator);
Camera camera(glm::vec3(0.0f, 1.0f, 10.0f), 45.0f,800.0f,600.0f, 800.0f/600.0f);
//Quad2D quad2d(1.f,1.f,0.f,0.f);
Quad3D quad3d(1.f,1.f,0.f,0.f,0.f,Anchor::CENTER);
Scene scene(&objs, &shade,&objs2D,&camera);
scene.Add2DObject("Quad0",
new GameObject(
new Mesh(quad3d.getVertices(), quad3d.getSizeofVertices(), quad3d.getIndices(), 6),
textureCache.GetTexture("Brick"),
Transform3D { glm::vec3(100.0f,100.0f,0.0f),glm::vec3(0.0f),glm::vec3(200.5f) } ) );
scene.AddObject("Quad1",
new GameObject(
new Mesh(quad3d.getVertices(), quad3d.getSizeofVertices(), quad3d.getIndices(), 6),
textureCache.GetTexture("Brick"),
Transform3D{ glm::vec3(0.0f),glm::vec3(0.0f),glm::vec3(1.0f) }));
scene.AddShader("Base", new Shader("assets/shaders/vertex.glsl","assets/shaders/fragment.glsl"));
while (window.running) {
SDL_Event event;
while (SDL_PollEvent(&event)) {
if (event.type == SDL_QUIT) window.running = false;
if (event.type == SDL_WINDOWEVENT) {
if (event.window.event == SDL_WINDOWEVENT_RESIZED) {
window.updateSize(event.window.data1, event.window.data2);
scene.camera->UpdateAspect(event.window.data1, event.window.data2,window.getAspect());
}
}
}
const uint8_t* state = SDL_GetKeyboardState(NULL);
scene.camera->ProcessKeyboard(state);
ClearColorWindow();
scene.Render();
EnableBlenWindow();
scene.Render2D();
DisableBlenWindow();
window.updateContext();
}
return 0;
}*так как у меня контроль памяти свой, я делаю нью всё равно да) я до конца не изучил этот нюанс, но трекинг памяти работает...
=== СБОРКА В РЕЖИМЕ DEBUG ===
[2/2] Linking app
--- Запуск (Debug) ---
Bytes Allocated: 1049344 Counter Allocs: 2
Bytes Free: 1048576 Counter Free: 1
Add Brick
Bytes Allocated: 1051648 Counter Allocs: 5
Bytes Free: 1049344 Counter Free: 2
Bytes Allocated: 1051648 Counter Allocs: 5
Bytes Free: 1050112 Counter Free: 3
Bytes Allocated: 1051648 Counter Allocs: 5
Bytes Free: 1050880 Counter Free: 4
[Texture] Удалена из GPU, ID: 1
Bytes Allocated: 1051648 Counter Allocs: 5
Bytes Free: 1051648 Counter Free: 5может кто-то скажет это переусложнение, но уже хз, и вот кстати когда осознал зачем управлять памятью, сразу все книги по С++ пригодились, а до этого реально не понимал, почему всё это надо(небольшой спойлер - всё вокруг управления ресурсами все эти архитектуры, сложный подход в кодинге и пр.)
вообще этот подход классный все пробросы от системы на самом низу, в файле coreSystem.cppm - это реально удобная магия пирога архитектуры, ну да статичная, но пока пофиг, это не мега крутой релиз для бизнеса, это изучать/исследовать десятилетиями...... этот подход тоже интересен ващето
Спасибо за подробные разъяснения и примеры из своего кода! Я наверное больше не ради оптимизации, а ради интереса всё это пишу, а такой глубокий бэкенд контроль мне в целом интересен:)
И за ссылку на box3d отдельное спасибо! Полезно будет посмотреть, как устроено всё в других более серьёзных проектах.
да ничего, в 3д если вам интересно, можно начинать с базового бвх в нём коробки ААББ(просто визуализируете коробки эти, делаете физику солверов контактов типо, по началу можно инстансом, потом лучше через ссбо), хотя у вас спатиал это делает, просто я смотрел у себя на бвх, задолго до вызода бкс3д, и смотрел без многопотока, ну кароче там по техникам просто вы настроите MDI+SSBO+multithreading там дорожная карта если попутно читать - вникать в gl всё понятно станет... как я считаю(просто когда приступите к прототипу держите в голове что кусок памяти должен быть 1 через MDI, а подгрузка должна быть многопоточной в него, но пока на момент прототипа тестов ElementsDraw хватает, но поитогу если сидеть с профайлером RenderDoc вы поймёте, что еффективнее рисовать без переключений драйвера и накладных расходов, а это MDI+SSBO, или полностью отрисовка в шейдерах всего - но до сюда доходят только те кто реально знает почему ему надо отрисовывать всё в шейдере. www.scratchapixel.com/index.html - тут тоже что-то есть по инфе...)
вообще как я это узнал, просто сделал клон-майнкрафт многопотоковый бесконечный локальный, вот там реально наглядно видно всю технику около ААА(почему около? потомучто это проверка гипотезы, это компиляция техник и управления памятью.... можете делать ответвление в клон майнкрафта, чтобы понять все техники для около идеальной отрисовки) - отсюда ответ откуда я тейкаю за управление памятью - всё дело в том, что я проверял техники эти на Расте просто.... в С++ просто через время, я вернулся, потомучто с указателями попроще жить чтоли если проще выражаться....
ну можно впринципе и в zig смотреть, как вы знаете там аллокаторы не придётся изобретать, кароче у зиг - аллокаторы и симд из каробки удобные...
смотрите пример, сразу не рвите на многопоток, подкину вам идейку,
предположим у вас есть буфер частичек, предположим есть окно и перспектива(projection*view)
тогда одна отрисовка пучков будет такой +-, я сейчас террейн рисую как раз так.
Скрытый текст
void BigRegion::render(const Frustum& cameraFrustum,const std::vector<Plane>& sp) {
m_countArray.clear();
m_indicesArray.clear();
m_baseVertexArray.clear();
int count=0;
// Проверяем каждый микро-чанк индивидуально
for (int i = 0; i < 256; ++i) {
// Если коробка микро-чанка пересекает пирамиду видимости камеры
if (cameraFrustum.isAABBInFrustum(m_microChunks[i].getBounds(),sp)) {
count++;
m_countArray.push_back(6144); // Рисуем все 6144 индекса чанка
m_indicesArray.push_back(nullptr); // Общий EBO
m_baseVertexArray.push_back(i * 1089); // Смещение вершин чанка в VBO региона
}
}
// Если весь регион 512х512 остался позади камеры, выходим и экономим Draw Call
if (m_countArray.empty()) return;
// std::cout<<"count chunks: "<<count<<std::endl;
// ОДИН вызов отрисует только то, что игрок реально видит!
glBindVertexArray(m_VAO);
glMultiDrawElementsBaseVertex(
GL_TRIANGLES,
m_countArray.data(),
GL_UNSIGNED_INT,
m_indicesArray.data(),
m_countArray.size(),
m_baseVertexArray.data()
);
}у меня регион 512х512 он состоит из 32х32(тайлик - 32х32) их таких тайлов 16х16 - это будет равно 512х512 юнитов(квадов(размера 1)), вот вам приближение простейшее к вопросу, ну конечно сюда можно писать в интервал адреса из потоков, вы сами это видите.... наверно
ой тут у меня не индирект, но там до него рукой уже подать на самом .... как раз для индирект для комманд нужно будет смещение индексного буфера и вершинного(и тут как раз поехала основная идея есть строка - буфер предположим её интервалы каждый 4ой а элементов 128) получается такую строку по смещению можно заполнять будет потоками типо(по-сути так и делают, просто задачка со строкой и смещением более так сказать наглядная...)....
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я создал свою мини‑Вселенную