Толпа без AI: сотни юнитов на трёх правилах
По голосованию победитель очевиден. Так что начнём. У парижан в Assassin's Creed Unity нет интеллекта. У каждого крысака в Vermintide и зомби из World War Z — тоже. Когда в кадре одновременно сотни персонажей, если бы у каждого крутилось полноценное behavior tree, FPS умер бы.
Так что там — не AI, а несколько локальных правил: «не наступай на ноги соседям», «иди примерно туда же, куда соседи», «не отставай». Собственно, это и есть толпа в играх — эмерджентность. Крейг Рейнольдс описал это в 1986 году и назвал boids.
Дальше начинается инженерия. Days Gone крутит орду из сотен Freakers. World War Z — Swarm Engine с зомби, текущими по уровню как жидкость. Под капотом везде одно и то же: boids, spatial hashing, ORCA, плюс LOD AI на дальних юнитах.
На неделе разберём: три формулы Рейнольдса, почему наивная реализация умирает на 500 юнитах, как ORCA не даёт юнитам сталкиваться в узких местах. 🔥
#мат_геймдев #МатРазбор #AI #algorithms
По голосованию победитель очевиден. Так что начнём. У парижан в Assassin's Creed Unity нет интеллекта. У каждого крысака в Vermintide и зомби из World War Z — тоже. Когда в кадре одновременно сотни персонажей, если бы у каждого крутилось полноценное behavior tree, FPS умер бы.
Так что там — не AI, а несколько локальных правил: «не наступай на ноги соседям», «иди примерно туда же, куда соседи», «не отставай». Собственно, это и есть толпа в играх — эмерджентность. Крейг Рейнольдс описал это в 1986 году и назвал boids.
Дальше начинается инженерия. Days Gone крутит орду из сотен Freakers. World War Z — Swarm Engine с зомби, текущими по уровню как жидкость. Под капотом везде одно и то же: boids, spatial hashing, ORCA, плюс LOD AI на дальних юнитах.
На неделе разберём: три формулы Рейнольдса, почему наивная реализация умирает на 500 юнитах, как ORCA не даёт юнитам сталкиваться в узких местах. 🔥
#мат_геймдев #МатРазбор #AI #algorithms
❤🔥18🔥13👍1
Толпа на сетке: несколько клеток, а не миллион проверок
В boids каждому юниту нужны его ближайшие соседи — без них не сработают ни separation, ни alignment, ни cohesion. Наивный ответ — пройтись по всем и проверить расстояние:
Считаем по головам. 100 юнитов — 10 000 проверок за кадр. 500 — 250 000. 1000 — миллион. И всё это 60 раз в секунду.
Итак, spatial hash. Соседи по определению рядом — значит, проверять надо только тех, кто в той же зоне пространства. Разбиваем сцену на клетки фиксированного размера, раскладываем юнитов по клеткам и смотрим рядом:
Размер клетки чаще всего берут равными радиусу видимости соседей.
По сути алгоритм boids — это часть задачи. Ещё часть — найти соседей достаточно быстро. Без этого игры с сотнями юнитов на экране просто не существовали бы. 🔥 Кроме того их надо отрендерить, а об этом уже поговорим позже.
#мат_геймдев #МатРазбор #algorithms #optimization
В boids каждому юниту нужны его ближайшие соседи — без них не сработают ни separation, ни alignment, ни cohesion. Наивный ответ — пройтись по всем и проверить расстояние:
// плохо: O(N²) на каждом кадре
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) continue;
if ((boid[i].position - boid[j].position).sqrMagnitude < r * r) {
// учесть соседа
}
}
}
Считаем по головам. 100 юнитов — 10 000 проверок за кадр. 500 — 250 000. 1000 — миллион. И всё это 60 раз в секунду.
Итак, spatial hash. Соседи по определению рядом — значит, проверять надо только тех, кто в той же зоне пространства. Разбиваем сцену на клетки фиксированного размера, раскладываем юнитов по клеткам и смотрим рядом:
// каждый кадр пересобираем
var grid = new Dictionary<Vector2Int, List<Boid>>();
foreach (var b in boids) {
var cell = new Vector2Int(
(int)(b.position.x / cellSize),
(int)(b.position.z / cellSize));
if (!grid.TryGetValue(cell, out var list))
grid[cell] = list = new List<Boid>();
list.Add(b);
}
Размер клетки чаще всего берут равными радиусу видимости соседей.
По сути алгоритм boids — это часть задачи. Ещё часть — найти соседей достаточно быстро. Без этого игры с сотнями юнитов на экране просто не существовали бы. 🔥 Кроме того их надо отрендерить, а об этом уже поговорим позже.
#мат_геймдев #МатРазбор #algorithms #optimization
🔥12
Толпа без AI: как три правила, хеш-сетка и ORCA делают массовку живой
https://dev-math.ru/articles/crowd/
Вы просили про толпу. Ну держитесь 🙂 Семь разделов, шесть интерактивов и тысяча юнитов в одном экране браузера. Я заморочился — получилось так объёмно, что статьи скоро можно сшивать в книжку (Поэтому немного задержался. Хотел в пятницу, а получилось в субботу). Жду огоньков и репостов друзьям 🔥
Симуляция массовки упирается в две проблемы: общий behavior tree «толпа делает X» не масштабируется, а наивный поиск соседей даёт O(N²) и кладёт сцену уже на пятистах юнитах. В статье разбираю архитектуру по слоям: три правила Рейнольдса для группового движения, uniform spatial hash для поиска соседей за O(N), упрощённый ORCA для встречных потоков в коридоре, steering behaviors для целей и обхода препятствий, плюс отдельная часть про GPU instancing для рендера тысячи юнитов одним draw call'ом. В финале — разбор под капотом AC Unity, World War Z, They Are Billions, Vermintide 2 и RTS-обобщённо.
#мат_геймдев #МатРазбор #algorithms #AI
https://dev-math.ru/articles/crowd/
Вы просили про толпу. Ну держитесь 🙂 Семь разделов, шесть интерактивов и тысяча юнитов в одном экране браузера. Я заморочился — получилось так объёмно, что статьи скоро можно сшивать в книжку (Поэтому немного задержался. Хотел в пятницу, а получилось в субботу). Жду огоньков и репостов друзьям 🔥
Симуляция массовки упирается в две проблемы: общий behavior tree «толпа делает X» не масштабируется, а наивный поиск соседей даёт O(N²) и кладёт сцену уже на пятистах юнитах. В статье разбираю архитектуру по слоям: три правила Рейнольдса для группового движения, uniform spatial hash для поиска соседей за O(N), упрощённый ORCA для встречных потоков в коридоре, steering behaviors для целей и обхода препятствий, плюс отдельная часть про GPU instancing для рендера тысячи юнитов одним draw call'ом. В финале — разбор под капотом AC Unity, World War Z, They Are Billions, Vermintide 2 и RTS-обобщённо.
#мат_геймдев #МатРазбор #algorithms #AI
🔥23❤🔥1❤1
Тысяча юнитов в кадре — это, конечно, эффектно. Но в AAA это только начало.
Давайте пройдемся до конца по толпе тогда (по результатам опроса). А потом уже пойдем либо к лутбоксам, либо к ELO и MMR.
В прошлой статье мы разобрали, как оживляют тысячу юнитов через boids + spatial hash на CPU. При этом в Assassin's Creed Unity на улицах Парижа — до 10 000 NPC одновременно. В массовых битвах Total War: Warhammer 2 — тоже десять тысяч, у каждого свой коллайдер и анимация. В Helldivers 2 — плотные волны термидов на одного игрока. They Are Billions — название говорит за себя.
По сути, любая CPU-архитектура решения из прошлой статьи на этом масштабе отвалится. У проблемы два слоя, которые мы не разобрали — глобальная навигация через flow fields (много готовых реализаций, но для такой задачи уже лучше написать свою) и перенос симуляции на GPU (compute shaders + indirect rendering).
Разберем на этой неделе. Всё как обычно со статьей в конце недели. Данная тема прикольна ещё тем, что если углублятся в детали реализации (особенно рендера), то станет понятнее как работает та же Nvidia Flex и подобные технологии.
Ну и делимся постами, ставим реакции, пишем чего хотелось бы ещё в комменты. Короче статьи, больше каких-то примеров. Хочется понимать, что интересно, а что нет. А то по SDF статью посмотрело меньше народу, чем даже по толпе, а вышла она уже неделю как.
#мат_геймдев #МатРазбор #algorithms #performance
Давайте пройдемся до конца по толпе тогда (по результатам опроса). А потом уже пойдем либо к лутбоксам, либо к ELO и MMR.
В прошлой статье мы разобрали, как оживляют тысячу юнитов через boids + spatial hash на CPU. При этом в Assassin's Creed Unity на улицах Парижа — до 10 000 NPC одновременно. В массовых битвах Total War: Warhammer 2 — тоже десять тысяч, у каждого свой коллайдер и анимация. В Helldivers 2 — плотные волны термидов на одного игрока. They Are Billions — название говорит за себя.
По сути, любая CPU-архитектура решения из прошлой статьи на этом масштабе отвалится. У проблемы два слоя, которые мы не разобрали — глобальная навигация через flow fields (много готовых реализаций, но для такой задачи уже лучше написать свою) и перенос симуляции на GPU (compute shaders + indirect rendering).
Разберем на этой неделе. Всё как обычно со статьей в конце недели. Данная тема прикольна ещё тем, что если углублятся в детали реализации (особенно рендера), то станет понятнее как работает та же Nvidia Flex и подобные технологии.
Ну и делимся постами, ставим реакции, пишем чего хотелось бы ещё в комменты. Короче статьи, больше каких-то примеров. Хочется понимать, что интересно, а что нет. А то по SDF статью посмотрело меньше народу, чем даже по толпе, а вышла она уже неделю как.
#мат_геймдев #МатРазбор #algorithms #performance
👍17🔥4
Flow fields: один расчёт вместо тысячи A*
Тысяча юнитов идёт к одной точке. Если для каждого считать A* — тысяча независимых поисков за кадр. Дороговато.
Как нам сделать меньше расчётов? По своей сути, идея проста. Можно сделать один расчёт вместо тысячи. Посчитали поле — все юниты просто читают из него «куда идти из своей клетки».
Разбиваем карту на сетку. От цели обратной волной (Dijkstra) в каждой клетке считаем дистанцию до цели и записываем вектор на соседа — это и есть flow field. Юниту достаточно прочитать вектор из своей клетки. O(1) на запрос, без зависимости от длины пути и количества юнитов.
«А если цель движется?» В RTS — почти никогда. Клик в точку, поход к зданию — цель статична, поле живёт минутами. При движущейся цели перерсчитать получается в любом случае не так дорого. Одну дейкстру пустить по карте не так долго, как для каждого юнита считать А*. Тем более с шумом от boids там не обязательно моментальная реакция на пользовательский ввод или триггеры.
Проблема возникает если много юнитов и у каждого своя цель — A* снова в выигрыше. Flow fields — это про движение толпы к общей цели. Канонический разбор — Elijah Emerson, AI Game Programming Wisdom 5 (2008).
#мат_геймдев #МатРазбор #algorithms #AI
Тысяча юнитов идёт к одной точке. Если для каждого считать A* — тысяча независимых поисков за кадр. Дороговато.
Как нам сделать меньше расчётов? По своей сути, идея проста. Можно сделать один расчёт вместо тысячи. Посчитали поле — все юниты просто читают из него «куда идти из своей клетки».
Разбиваем карту на сетку. От цели обратной волной (Dijkstra) в каждой клетке считаем дистанцию до цели и записываем вектор на соседа — это и есть flow field. Юниту достаточно прочитать вектор из своей клетки. O(1) на запрос, без зависимости от длины пути и количества юнитов.
«А если цель движется?» В RTS — почти никогда. Клик в точку, поход к зданию — цель статична, поле живёт минутами. При движущейся цели перерсчитать получается в любом случае не так дорого. Одну дейкстру пустить по карте не так долго, как для каждого юнита считать А*. Тем более с шумом от boids там не обязательно моментальная реакция на пользовательский ввод или триггеры.
Проблема возникает если много юнитов и у каждого своя цель — A* снова в выигрыше. Flow fields — это про движение толпы к общей цели. Канонический разбор — Elijah Emerson, AI Game Programming Wisdom 5 (2008).
#мат_геймдев #МатРазбор #algorithms #AI
👍11🔥3
Толпа на максималках: flow fields, GPU и десятки тысяч юнитов в кадре
https://dev-math.ru/articles/crowd-gpu/
Помните прошлую статью про толпу? Я остановился на тысяче юнитов и оставил четыре вещи «на потом» — flow fields, симуляцию на GPU, indirect draw и LOD AI. Обещал продолжение, да и вы за него проголосовали — и вот оно 🙂 Четыре интерактива (один — честная 3D-сцена на three.js, с реальным счётчиком draw call'ов), и снова получилось так объёмно, что впору сшивать в книжку. Жду огоньков и репостов друзьям 🔥
Тысяча юнитов на CPU — это разминка. Десятки тысяч в кадре (Париж в AC Unity, битвы Total War, орды нежити) — уже другая архитектура из четырёх слоёв. Глобальный путь перестаёт быть тысячей независимых A* и становится одним flow field — сеткой направлений на всю толпу за O(1). Симуляция агентов уезжает с ядер CPU на тысячи дорожек GPU (compute shaders + StructuredBuffer). Рендер перестаёт быть draw call'ом на агента и становится indirect draw, где команды отрисовки генерит сам GPU. А то, что не видно вблизи, не считается честно — LOD AI и recycling. В финале — разбор под капотом Planetary Annihilation, Supreme Commander 2, AC Unity, Total War, They Are Billions и Helldivers 2.
Первая часть, если пропустили: https://dev-math.ru/articles/crowd/ Думаю на этом тема толп в играх раскрыта окончательно :)
#мат_геймдев #МатРазбор #algorithms #GPU
https://dev-math.ru/articles/crowd-gpu/
Помните прошлую статью про толпу? Я остановился на тысяче юнитов и оставил четыре вещи «на потом» — flow fields, симуляцию на GPU, indirect draw и LOD AI. Обещал продолжение, да и вы за него проголосовали — и вот оно 🙂 Четыре интерактива (один — честная 3D-сцена на three.js, с реальным счётчиком draw call'ов), и снова получилось так объёмно, что впору сшивать в книжку. Жду огоньков и репостов друзьям 🔥
Тысяча юнитов на CPU — это разминка. Десятки тысяч в кадре (Париж в AC Unity, битвы Total War, орды нежити) — уже другая архитектура из четырёх слоёв. Глобальный путь перестаёт быть тысячей независимых A* и становится одним flow field — сеткой направлений на всю толпу за O(1). Симуляция агентов уезжает с ядер CPU на тысячи дорожек GPU (compute shaders + StructuredBuffer). Рендер перестаёт быть draw call'ом на агента и становится indirect draw, где команды отрисовки генерит сам GPU. А то, что не видно вблизи, не считается честно — LOD AI и recycling. В финале — разбор под капотом Planetary Annihilation, Supreme Commander 2, AC Unity, Total War, They Are Billions и Helldivers 2.
Первая часть, если пропустили: https://dev-math.ru/articles/crowd/ Думаю на этом тема толп в играх раскрыта окончательно :)
#мат_геймдев #МатРазбор #algorithms #GPU
🔥18
Матчмейкинг по-простому: Сигнал и шум
https://dev-math.ru/articles/matchmaking/
В этот раз пост наоборот пораньше, так как много дел на выходных. Одна из самых "математичных" статей получилась. Так как я в целом люблю тервер и статистические процессы, то даже интересно было писать и редактировать. Постарался максимально простым языком объяснить сложные математические понятия. Хотя на самом деле математика всего лишь "язык", который многих пугает, хотя он просто описывает различные процессы.
Главная мысль — на все полвека одна. Истинный скилл это скрытый сигнал, который нельзя увидеть напрямую. Один матч — шумная однобитная выборка из него. А рейтинг — это фильтр, который оценивает и сам сигнал, и собственную неуверенность в нём. Вся эволюция ELO → Glicko → TrueSkill ровно про это: как сделать фильтр умнее. ELO — фиксированное доверие к одному матчу (тот самый K) и логистическая сигмоида, откуда берётся «400 очков = ×10 шансов». Glicko добавляет второе число RD — адаптивный K, который сам понимает, про кого мы знаем мало. TrueSkill описывает скилл целым гауссовым колоколом N(μ, σ) и раздаёт его по команде через factor graph. В финале — кто это крутит в проде: Chess.com и Lichess на Glicko, Rocket League, Halo на TrueSkill.
Не забываем делиться статьей с друзьями, если она понравится — это помогает развитию канала. Больше подписчиков богам подписчиков. Ну и ставим огоньки естественно. Автор работает за классы :) Я стараюсь в одиночку на пару с клодом делать качественные материалы и хочется чтобы их увидело как можно больше людей.
Небольшая ремарка. На самом деле такая математика больше про геймдизайн, чем про разработку. Обычно геймдизайнеры подобные системы отдают на интеграцию. Но это геймдизайнеры математического баланса, которые есть не в каждой студии, да и самому быть осведомленным в таких вещах довольно полезно.
#мат_геймдев #МатРазбор #algorithms #matchmaking
https://dev-math.ru/articles/matchmaking/
В этот раз пост наоборот пораньше, так как много дел на выходных. Одна из самых "математичных" статей получилась. Так как я в целом люблю тервер и статистические процессы, то даже интересно было писать и редактировать. Постарался максимально простым языком объяснить сложные математические понятия. Хотя на самом деле математика всего лишь "язык", который многих пугает, хотя он просто описывает различные процессы.
Главная мысль — на все полвека одна. Истинный скилл это скрытый сигнал, который нельзя увидеть напрямую. Один матч — шумная однобитная выборка из него. А рейтинг — это фильтр, который оценивает и сам сигнал, и собственную неуверенность в нём. Вся эволюция ELO → Glicko → TrueSkill ровно про это: как сделать фильтр умнее. ELO — фиксированное доверие к одному матчу (тот самый K) и логистическая сигмоида, откуда берётся «400 очков = ×10 шансов». Glicko добавляет второе число RD — адаптивный K, который сам понимает, про кого мы знаем мало. TrueSkill описывает скилл целым гауссовым колоколом N(μ, σ) и раздаёт его по команде через factor graph. В финале — кто это крутит в проде: Chess.com и Lichess на Glicko, Rocket League, Halo на TrueSkill.
Не забываем делиться статьей с друзьями, если она понравится — это помогает развитию канала. Больше подписчиков богам подписчиков. Ну и ставим огоньки естественно. Автор работает за классы :) Я стараюсь в одиночку на пару с клодом делать качественные материалы и хочется чтобы их увидело как можно больше людей.
Небольшая ремарка. На самом деле такая математика больше про геймдизайн, чем про разработку. Обычно геймдизайнеры подобные системы отдают на интеграцию. Но это геймдизайнеры математического баланса, которые есть не в каждой студии, да и самому быть осведомленным в таких вещах довольно полезно.
#мат_геймдев #МатРазбор #algorithms #matchmaking
🔥16