Толпа на максималках: flow fields, GPU и десятки тысяч юнитов в кадре

Всем привет! Меня зовут Гриша Дядиченко, и я технический директор и основатель White Label Games. Уже больше десяти лет работаю с компьютерной графикой, AR/VR и компьютерным зрением — в основном заказная разработка, иногда собственные прототипы по выходным.

В прошлый раз мы остановились на тысяче юнитов в кадре и честно оставили четыре вещи за скобками — flow fields, compute-боидов на GPU, GPU-driven rendering и LOD AI. Это продолжение той статьи, и если вы её не читали — там разобран весь CPU-стек симуляции толпы: три правила Рейнольдса, топологические соседи, spatial hash, ORCA и steering behaviors. Здесь я на них буду ссылаться как на уже знакомые кирпичи, так что при желании можно сначала сходить туда.

Тысяча юнитов на CPU — это разминка. А вот Париж с толпой на улицах, битва на пару полков в Total War или орда жуков, заливающая весь экран — это уже не «та же симуляция, только побольше». Это другая архитектура.

И устроена она как сэндвич из четырёх слоёв. Первый: глобальный путь перестаёт быть тысячей независимых A* и становится одной сеткой направлений — flow field. Второй: симуляция самих агентов переезжает с 8–16 ядер CPU на тысячи дорожек GPU — compute shaders и StructuredBuffer. Третий: рендер перестаёт быть draw call'ом на агента и становится indirect draw, где команды отрисовки генерит сам GPU. И четвёртый: то, что не видно вблизи, не симулируется честно — LOD AI и recycling.

Чтож, давайте по порядку. Как одно поле направлений заменяет тысячу путей, что такое StructuredBuffer и почему compute shader перемалывает толпу быстрее цикла for, как из десяти тысяч draw call'ов получается один, и что под капотом у Planetary Annihilation, AC Unity, Total War и Helldivers 2. Четыре интерактива в браузере прилагаются — покрутите прямо со страницы.

Если интересна тема — добро пожаловать.

Часть 1. Потолок: почему большая толпа — это другая архитектура

Быстрый рекап, на чём мы закончили в прошлый раз. Весь CPU-стек толпы — это: локальные правила Рейнольдса (разделение, выравнивание, сплочение), spatial hash вместо перебора всех пар, ORCA для гарантированного обхода столкновений и steering behaviors для целей и обхода препятствий. Всё это крутится на нескольких ядрах процессора и спокойно тянет толпу в духе той, на которой мы закончили в прошлый раз. На таком масштабе сцена уже выглядит как настоящая толпа, и при этом ничего экзотического не нужно.

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

Масштаб, на котором становится интересно

В Assassin's Creed Unity Ubisoft делали толпу революционного Парижа — и это, наверное, самый известный публично разобранный кейс. На GDC 2015 Франсуа Курнуайе из Ubisoft в докладе «Massive Crowd on Assassin's Creed Unity: AI Recycling» рассказывал, что на сцене одновременно бывало до десяти тысяч NPC — и держалось это не на честной симуляции каждого, а на хитром recycling'е (к нему вернёмся в Части 6).

Total War — другой жанр, та же боль: на поле одновременно тысячи солдат, и они должны держать строй, а не толпиться кашей. Тамаш Рабель, ведущий graphics-программист Creative Assembly, в разборе движка Total War на GPUOpen прямо пишет про «тысячи юнитов на экране» и тысячи уникальных матриц для скининга — то есть это официально подтверждённый порядок.

Где именно не справляется CPU

А не справляется он в трёх местах одновременно, и это не одна большая проблема, а три разные.

Путь. Если толпа идёт к одной точке и каждый юнит строит свой A* — это N независимых поисков пути в кадр, по одному на агента. A* сам по себе недешёвый, а целая пачка таких подряд — уже серьёзная доля кадрового бюджета. И чем больше карта, тем длиннее каждый путь, тем дороже.

Симуляция. Боиды, соседи, avoidance — всё это считается на CPU. Даже со spatial hash это десятки операций на агента в кадр, и крутится оно на 8–16 ядрах в лучшем случае. Современный процессор — это единицы-десятки потоков, и каждый поток грызёт агентов по очереди.

Рендер. Наивно каждый юнит — это свой draw call. Сколько юнитов, столько вызовов отрисовки — и тут упирается уже не GPU, а CPU, который эти вызовы готовит и шлёт драйверу.

И вот ключевая мысль всей статьи: на большой массовке эти три проблемы решаются не «оптимизацией того же кода», а сменой слоя. Путь становится одной сеткой направлений на всех. Симуляция переезжает на GPU. Рендер становится одним indirect-вызовом. А лишнее — перестаёт считаться вообще.

К этому моменту у нас есть карта боли: путь, симуляция, рендер. Давайте чинить по очереди, и начнём с самого наглядного — с пути.

Часть 2. Flow field: одна сетка направлений вместо N путей

Итак, проблема номер один. Тысяча юнитов идёт к одной цели. Наивно — это тысяча независимых A*: каждый юнит сам ищет себе путь по карте, сам разворачивает очередь, сам перебирает клетки. И вот что обидно: они все идут в одно и то же место. Тысяча почти одинаковых вычислений, результат которых процентов на девяносто совпадает.

Идея: считать не путь юнита, а путь к цели

Переворачиваем задачу с ног на голову. Вместо «откуда и куда идёт каждый юнит» спросим один раз: «из любой точки карты — куда шагнуть, чтобы приблизиться к цели?». Ответ на этот вопрос не зависит от того, сколько у нас юнитов — хоть один, хоть сто тысяч. Это свойство карты и цели.

Считаем его один раз. Дальше каждый юнит в каждом кадре просто смотрит в свою клетку и читает оттуда готовый вектор «иди туда». Это O(1) на запрос. Ни поиска, ни очереди, ни зависимости от длины пути.

Как это строится: волна, стоимость, направление

Три шага, и все три простые.

Шаг первый — сетка. Бьём карту на клетки. Часть клеток — стены (непроходимо).

Шаг второй — cost field. Запускаем волну от цели наружу. Это обычный ДейкстраАлгоритм Дейкстры — поиск кратчайших путей от одной вершины до всех остальных во взвешенном графе. Для сетки с равными весами вырождается в волну в ширину (BFS); с диагоналями — даёт честную стоимость с шагом 1 по стороне и √2 по диагонали. (или волна в ширину, если все шаги равны), только стартуем не из юнита, а из точки назначения. В каждой клетке записываем стоимость дойти до цели. Получается «карта высот»: у цели — ноль, чем дальше — тем больше, стены волна обтекает.

// обратная волна от цели — один раз на всё поле
var cost = new float[cols * rows];
Array.Fill(cost, float.PositiveInfinity);
cost[Index(goal)] = 0f;

var frontier = new MinHeap();           // приоритет — текущая стоимость
frontier.Push(goal, 0f);
while (frontier.Count > 0) {
    var c = frontier.Pop();
    foreach (var nb in Neighbors8(c)) {
        if (walls[Index(nb)]) continue;
        float nc = cost[Index(c)] + StepCost(c, nb);  // 1 по стороне, √2 по диагонали
        if (nc < cost[Index(nb)]) {
            cost[Index(nb)] = nc;
            frontier.Push(nb, nc);
        }
    }
}

Шаг третий — flow field. Превращаем стоимость в направление. В каждой клетке смотрим на соседей и берём вектор на того, у кого стоимость меньше. То есть «вниз по склону» к цели.

// в каждой клетке — направление на соседа с наименьшей стоимостью
var flow = new Vector2[cols * rows];
foreach (var c in AllCells()) {
    if (walls[Index(c)]) continue;
    var best = c;
    foreach (var nb in Neighbors8(c))
        if (cost[Index(nb)] < cost[Index(best)]) best = nb;
    flow[Index(c)] = ((Vector2)(best - c)).normalized;
}

И всё. Теперь юнит в кадре делает вот это:

// каждый юнит — просто читает свою клетку. O(1), без поиска.
Vector2 dir = flow[Index(CellOf(unit.position))];
unit.velocity += dir * accel * dt;

Почему это дёшево

Стоимость построения поля — это O(числа клеток), и она не зависит ни от длины пути, ни от числа юнитов. Построили один раз — и амортизировали на всю толпу. Тысяча юнитов или сто тысяч — поле то же самое, разница только в том, сколько раз его прочитали, а чтение это O(1).

По сути мы заменили «тысячу дорогих вопросов» на «один дорогой вопрос плюс тысячу дешёвых ответов». И вот это та самая смена слоя, про которую я говорил в Части 1: не «A* стал быстрее», а «A* больше не нужен на каждого».

Honest hedge: одна цель — да, пятьсот разных — нет

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

Как только у вас пятьсот юнитов с пятьюстами разными целями — магия исчезает. Строить пятьсот отдельных полей не дешевле, чем пятьсот A*, а скорее дороже. В этом случае старый добрый A* (или Detour из recastnavigation) на каждого — снова правильный инструмент. Так что flow field — это не «замена A*», а инструмент под конкретный сценарий.

Интерактив 1: Flow field playground

Ниже — сетка со стенами. Кликните по ней — поставите цель. Сразу же построится cost field (это фон-heatmap: ярко-мятный у цели, тёмно-синий далеко) и flow field (стрелки «куда идти»). Слайдером накидайте агентов — они потекут к цели по стрелкам.

Главное — тумблер A* на каждого / flow field. Под сценой два числа: время пересчёта при смене цели и «работа» — сколько клеток алгоритм реально перебрал. Переключите на A* на каждого и подвигайте цель: каждый агент пересчитывает свой путь, и «работа» подскакивает в тысячи раз. Переключите обратно на flow field — одно поле на всех. И да, миллисекунды тут честные, но это ваш браузер, а не игровая консоль — цифры иллюстрируют разницу подходов, а не перформанс конкретного движка.

Поле строится — отлично. Но в проде оно живёт не в вакууме: цель двигается, карта огромная, а само направление «в общем к цели» ещё не разводит юнитов между собой. Разберём нюансы.

Часть 3. Нюансы, без которых flow field в проде не живёт

Поле направлений в вакууме — это красиво, но в игре оно сразу обрастает оговорками. Разберём три самые частые, потому что без них демка остаётся демкой.

Цель двигается. И что теперь?

В RTS цель чаще всего статична. Вы кликнули в точку — поле построилось и живёт, пока юниты идут. Отряд топает к зданию — здание не убегает. Поле спокойно живёт секундами, а это сотни кадров на один пересчёт. Когда цель реально сдвинулась — пересчитываем, но раз в N сотен миллисекунд, а не каждый кадр.

А стоит ли это вообще пугаться из-за движения цели? Дейкстра на сетке 64×64 — это порядок единиц миллисекунд. Раз в несколько сотен миллисекунд это незаметно. А короткие, дёрганые сдвиги цели вообще не доходят до пересчёта поля — их гасит локальный слой, о котором ниже.

Карта огромная. Иерархические тайлы

Если карта — это не 64×64, а здоровенный открытый мир, строить одно поле на всю карту при каждом сдвиге цели уже накладно: клеток миллионы. Решение — иерархия.

Карту режут на тайлы. Между тайлами считают грубый путь (на уровне «через какие тайлы идти к цели»), а внутри тайла строят полноценный flow field — но только для тех тайлов, что лежат на грубом пути. Это классика, и опорная работа здесь — глава Элайджи Эмерсона «Crowd Pathfinding and Steering Using Flow Field Tiles» из сборника Game AI Pro (CRC Press, 2013). Эмерсон описывает именно тайловую схему — она выросла из работы над Supreme Commander, и PDF лежит в открытом доступе, можно почитать первоисточник.

Сшивка слоёв: «в общем туда» плюс «не наступай на соседа»

Вот ключевой момент, который многие пропускают. Flow field говорит юниту направление в общем — «вон туда, к цели». Но он ничего не знает про то, что рядом ещё триста таких же юнитов, и если все тупо пойдут по стрелке, они слипнутся в один пиксель.

Поэтому архитектура — двухслойная. Глобальный слой (flow field) даёт цель. Локальный слой (boids + ORCA из прошлой статьи) разводит юнитов между собой. Складываются они примерно так:

// глобальный слой: куда идти «в общем» — читаем поле за O(1)
Vector2 global = flow[Index(CellOf(unit.position))];

// локальный слой: разведение с соседями — boids + ORCA из прошлой статьи
Vector2 local = Separation(neighbors) + OrcaAvoidance(neighbors);

// сумма с весами — и поехали
unit.velocity += (global * wGlobal + local * wLocal) * dt;

Собственно, вот и весь сэндвич: глобальный слой решает «куда», локальный — «как не толкаться по дороге». Flow field не отменяет boids и ORCA — он встаёт над ними и снимает с них задачу глобальной навигации.

Где это в RTS

Flow fields в стратегиях — это давно индустриальный стандарт. Supreme Commander 2 — тот самый кейс Эмерсона с тайлами. Planetary Annihilation — отдельный любопытный случай: бой идёт на сфере, поэтому сетка навигации натянута на поверхность планеты, а не на плоскость. Пасфайндер там, по словам разработчика Форреста Смита, воксельный и поддерживает сферические планеты и тысячи юнитов — про это будет подробнее в Части 7. Современные RTS в той или иной форме все живут на этой схеме: грубый глобальный слой плюс локальное разведение.

Интерактив 2: размер клетки и компромисс

Покрутите слайдер размера клетки. Сиреневая линия — путь, который выдаёт поле из левого-нижнего угла к цели. Сделайте клетку крупной: число клеток падает, «работа поля» под сценой падает вместе с ним — но путь становится блочным, угловатым, хуже огибает стены. Сделайте мелкой: путь гладкий и аккуратный, но клеток (и работы) кратно больше.

Вот этот компромисс — «грубее сетка дешевле, но путь хуже» — иерархия тайлов и снимает: далеко планируем грубо, локально уточняем мелко.

К этому моменту у нас есть глобальная навигация на всю толпу, которая дёшево строится, переживает движущуюся цель и масштабируется на большие карты. Но симуляция каждого агента — боиды, соседи, avoidance — всё ещё крутится на CPU. Пора переезжать.

Часть 4. Симуляция на GPU: StructuredBuffer и compute shaders

Ну хорошо, глобальный путь мы удешевили до одного поля. Но стоимость симуляции самого агента никуда не делась: разгон по направлению, чтение соседей, локальный avoidance — это всё ещё надо посчитать для каждого юнита в каждом кадре. И считается оно на CPU.

А CPU — это единицы-десятки потоков. Восемь, шестнадцать ядер в хорошем случае. Дискретная видеокарта — это тысячи дорожек, заточенных ровно под одно: сделать одно и то же простое действие над кучей данных разом. Симуляция толпы — это буквально оно: «возьми тысячи агентов и обнови каждого по одному правилу». Идеальная работа для GPU.

Что и зачем (без глубокого нырка)

Идея на пальцах. Позиции и скорости всех агентов кладём не в массив объектов на CPU, а в StructuredBufferStructuredBuffer — типизированный буфер в видеопамяти, к которому compute/вершинный шейдер обращается по индексу как к массиву. RW-вариант (RWStructuredBuffer) доступен и на чтение, и на запись из шейдера. Это основной способ держать данные агентов на GPU. прямо в видеопамяти — например, float4 на агента, где xy это позиция, а zw это скорость. Дальше пишем compute shaderCompute shader — программа на GPU, не привязанная к графическому конвейеру. Запускается «диспатчем» на сетке потоков, разбитой на thread groups (группы потоков). Внутри группы потоки могут делить общую память и синхронизироваться., который одним тиком обновляет всех агентов параллельно.

Выглядит примерно так:

// все агенты — в буфере. одна dispatch — тысячи потоков разом.
RWStructuredBuffer<float4> Positions;   // xy = позиция, zw = скорость
StructuredBuffer<float2>   Flow;        // тот самый глобальный flow field

[numthreads(256, 1, 1)]
void CSUpdate(uint3 id : SV_DispatchThreadID) {
    if (id.x >= AgentCount) return;          // хвост за границей буфера
    float4 a = Positions[id.x];
    float2 dir = Flow[CellIndex(a.xy)];      // читаем поле за O(1)
    a.zw += dir * Accel * DeltaTime;         // разгон по направлению
    a.xy += a.zw * DeltaTime;                // шаг
    Positions[id.x] = a;
}

А со стороны C# это один вызов на весь кадр — не цикл по агентам, а «запусти ядро на стольких-то группах»:

// один Dispatch — и GPU обновляет всех агентов сразу
int groups = Mathf.CeilToInt(agentCount / 256f);
compute.SetBuffer(kernel, "Positions", positionsBuffer);
compute.SetFloat("DeltaTime", Time.deltaTime);
compute.Dispatch(kernel, groups, 1, 1);

[numthreads(256,1,1)] — это размер группы: 256 потоков работают пачкой. Сколько таких групп нужно — считаем как agentCount / 256, округлив вверх. GPU раскидывает группы по своим вычислительным блокам и молотит их параллельно. Лучший публичный разбор того, как собрать compute-боидов с нуля — ролик Себастьяна Лага «Coding Adventure: Boids»: он гоняет очень большую стаю на compute shader и показывает каждый шаг.

А поиск соседей?

В прошлой статье spatial hash на CPU был обычным Dictionary (или Map в браузере). На GPU так нельзя — там нет удобных хеш-таблиц с динамическими списками. Поиск соседей делают иначе: считают, сколько агентов попало в каждую клетку (атомарный инкремент счётчика клетки), затем параллельным префиксным сложением (prefix sum) превращают счётчики в смещения, и наконец раскладывают агентов по клеткам в один плоский массив. Звучит как три простых шага, но каждый — отдельная dispatch, и отлаживать это заметно сложнее, чем Map в пару строк.

Цена вопроса

Честно: это не бесплатно по нервам.

• Дебажить compute — это не дебажить C#. Брейкпоинт не поставишь, Debug.Log из шейдера не выведешь. Инструменты — PIX, RenderDoc, и это отдельный навык.
• Spatial hash на GPU (atomic + prefix sum) — это десятки строк нетривиального кода против пары строк с Map.
• Данные живут в видеопамяти, и каждый раз гонять их туда-сюда между CPU и GPU — дорого. Хочется, чтобы агенты жили на GPU и там же рендерились (про это — Часть 5).

Окупается это всё на десятках тысяч агентов. На тысяче — не трогайте GPU, CPU-стек из прошлой статьи и проще, и отлаживается легко. Это ровно тот случай, когда сложное решение оправдано масштабом, а не желанием поиграть с шейдерами.

Honest hedge: миллион в демо ≠ миллион в геймплее

В техдемках и research-статьях встречаются красивые числа — сотни тысяч, миллионы агентов на одной видеокарте. Это правда, но с оговоркой: в демо у агента логика на три инструкции, и больше в кадре нет ничего — ни геймплея, ни анимации, ни физики, ни звука, ни остального ИИ. В реальной игре GPU и CPU делят между десятком систем, и «миллион боидов» из техдемо превращается в куда более скромные числа в проде. Так что демо-числа — это потолок физики железа, а не обещание для вашего геймплея. Не выдавайте одно за другое.

Интерактив 3: CPU vs GPU как модель параллелизма

Сразу предупреждаю: это модель-иллюстрация, а не бенчмарк. Никаких выдуманных миллисекунд — мы считаем «шаги». Слева CPU: один цикл for, агенты обрабатываются по очереди, один за шаг. Справа GPU: одна dispatch, агенты красятся пачками по числу дорожек. Покрутите число дорожек и посмотрите на счётчики шагов внизу: CPU тратит N шагов, GPU — около N / дорожки. На реальной GPU дорожек тысячи (и есть свои оговорки — дивергенция веток, доступ к памяти), но порядок именно такой: вместо очереди — один широкий проход.

Агенты теперь живут и считаются на GPU. Логично, чтобы они там же и рисовались — иначе мы упрёмся в третью проблему из Части 1. Идём в рендер.

Часть 5. Рендер: от draw call на агента к indirect draw

Третья проблема из Части 1, и самая коварная, потому что она не про GPU. Наивно каждый юнит рисуется своим вызовом отрисовки — draw call. Десять тысяч юнитов — десять тысяч draw call'ов. И тормозит тут CPU: он готовит каждый вызов, проверяет состояние, шлёт команду драйверу. GPU в это время скучает. Классический случай, когда видеокарта простаивает, а игра лагает.

Лечится это в три ступени — от простого к хардкору.

Ступень 1: GPU instancing

Если все юниты — это один и тот же меш (а в толпе обычно так и есть, ну плюс-минус несколько вариаций), то нет смысла слать команду на каждого. Шлём один меш и массив трансформаций — «нарисуй вот это вот столько раз, вот по этим матрицам».

// один меш, массив матриц, один логический вызов на всю пачку
Graphics.DrawMeshInstanced(mesh, 0, material, matrices, count);

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

Ступень 2: DrawMeshInstancedIndirect

У instancing'а есть потолок: матрицы всё ещё готовит и передаёт CPU. А мы только что в Части 4 положили позиции агентов на GPU. Гонять их обратно на CPU, чтобы собрать матрицы, и снова на GPU — это бессмысленно.

Indirect-вызов убирает CPU из уравнения. И число инстансов, и сами матрицы лежат в GPU-буфере. CPU говорит лишь «рисуй по этому буферу аргументов» — а сколько именно и с какими трансформациями, читается прямо из видеопамяти:

// число инстансов и матрицы — в GPU-буфере. CPU их даже не трогает.
// argsBuffer хранит {indexCount, instanceCount, startIndex, ...}
Graphics.DrawMeshInstancedIndirect(mesh, 0, material, bounds, argsBuffer);

Теперь compute shader из Части 4 может сам дописать в буфер аргументов, сколько агентов рисовать — и рендер подхватит это без участия процессора. В вебе этого уже нет: WebGL2 не умеет ни indirect-вызовов, ни compute-шейдеров, которыми такой буфер заполняют. Появляется это только в WebGPU.

Ступень 3: полноценный GPU-driven pipeline

Хардкор. GPU не просто рисует по буферу — он сам решает, что рисовать. Делает GPU cullingGPU culling — отсев невидимого (за камерой, за другими объектами, слишком мелкого) силами самого GPU, через compute shader, без участия CPU. Результат — компактный список того, что реально надо нарисовать, тут же скармливается indirect-вызову. (отсекает то, что за камерой или перекрыто), формирует список видимого и сам же его рисует. На уровне API это ExecuteIndirect в DX12 или vkCmdDrawIndirectCount в Vulkan, плюс persistent-буферы, которые живут между кадрами. В вебе — мимо: ни GPU-culling через compute, ни ExecuteIndirect WebGL2 не поддерживает (есть только расширение WEBGL_multi_draw — несколько диапазонов одним вызовом, но число и аргументы всё равно готовит CPU). По-настоящему это уже WebGPU, Vulkan и DX12.

Опорный материал тут — доклад Ульриха Хаара и Себастьяна Аалтонена «GPU-Driven Rendering Pipelines» с SIGGRAPH 2015 (курс Advances in Real-Time Rendering). Там подробно про mesh cluster rendering и culling силами GPU — это первоисточник. Подобные подходы (кластерный culling, GPU-driven отрисовка) живут в id Tech и других AAA-движках. UE5 Nanite — это вообще соседняя вселенная той же идеи «GPU сам разбирается, что и в каком детализации рисовать», но это отдельная большая тема, я её только упоминаю.

И к слову про Total War: Тамаш Рабель из Creative Assembly в разборе их движка описывает ровно эту боль — тысячи уникальных инстансов, тысячи матриц для скининга, и как они оптимизировали загрузку буфера инстансов в DX12, читая upload-кучу прямо с GPU, чтобы убрать лишние барьеры синхронизации на каждый draw call. Это то самое, только в проде и про скелетную анимацию.

Интерактив 4: instancing на three.js, честный замер

Здесь без моделек-иллюстраций. Поднимается настоящая 3D-сцена на three.js (WebGL2): пол-чертёж, стены и оранжевое кольцо цели (как goal-маркер из Demo 1), а толпа мятных человечков бежит к цели через стены, читая тот же flow field из Части 2. Каждый человечек — капсула плюс гранёная голова, слитые в одну геометрию (чтобы инстансинг считался честно, одним вызовом). Камеру можно вращать и приближать колесом, цель — перенести кнопкой. Тумблер наивно / instancing. Слайдер до 20 000 агентов. Все цифры в подписи — реальные: draw calls берётся из renderer.info.render.calls прямо после кадра, FPS — измеренный в браузере, а не нарисованный для красоты.

База сцены — пол, стены и кольцо цели — это ~3 draw call'а в любом режиме. К ним прибавляется отрисовка юнитов. В режиме наивно это N штук THREE.Mesh с общими geometry и material — renderer.info.render.calls ≈ N + 3. На паре тысяч агентов CPU уже захлёбывается готовить вызовы, а GPU простаивает, и FPS послушно проседает. Переключите тумблер на instancing — те же N юнитов рисуются одним THREE.InstancedMesh, draw call'ов становится ~4 на всю сцену, FPS возвращается к 60.

Чтобы толпа выглядела живой, а не ползла слипшимся комом, поверх flow field накручены boids — те самые три правила Рейнольдса (расталкивание, выравнивание курса, сплочение) из классики про стаи. Flow остаётся главным: он ведёт к цели, boids лишь добавляет локальную жизнь — люди держат дистанцию, выстраиваются в общие ручьи и огибают углы не строем. Соседей для флокинга ищем через uniform-grid с кэпом, иначе на 20 000 это честное O(N²) повесило бы вкладку. Снимите галочку boids (стая) — и живые ручьи рассыпаются в равномерную «крупу», где каждый сам по себе и все налезают друг на друга: вот это и есть вклад флокинга.

Маленькая оговорка: «draw call» здесь — это вызов отрисовки WebGL, как его считает three.js. У всех мешей выключен frustumCulled, чтобы счётчик не «помогал» нам сбоку и не выкидывал из подсчёта юнитов, которых не видно из текущего ракурса. Полноценный indirect-вызов (тот, что в DX12/Vulkan убирает CPU из уравнения совсем) в WebGL честно не показывается — он живёт ступенью выше и остаётся текстом этой части.

Теперь у нас агенты считаются на GPU и рисуются почти без участия CPU. Осталась последняя, четвёртая идея — и она про то, чтобы вообще не делать лишнюю работу.

Часть 6. LOD AI и recycling: не симулировать то, чего не видно

Три предыдущие части мы делали работу дешевле: путь, симуляцию, рендер. Четвёртая идея радикальнее — не делать работу вообще.

Логика простая до наглости. Игрок физически не может уследить за десятью тысячами NPC одновременно. Он смотрит в свою сторону, видит десятки, ну сотни персонажей вблизи. Всё остальное — фон. Так зачем честно симулировать поведение того, кого никто не разглядывает?

Уровни детализации, только для мозгов

LOD AILOD AI — Level of Detail для искусственного интеллекта. По аналогии с графическим LOD (далёкие модели рисуют грубее) — далёкие и невидимые агенты получают всё более грубую логику: от полного дерева поведения вблизи до статистической «массовки» вдали. — это тот же принцип, что и графический LOD, только не про полигоны, а про поведение. Вблизи NPC получает полноценное дерево поведения: реагирует, уворачивается, живёт свою маленькую жизнь. Подальше — упрощённые правила. Ещё дальше — статистическая «марионетка»: не индивидуальная симуляция, а массовка, которая в среднем ведёт себя похоже на толпу, но без честных мозгов у каждого. Совсем далеко — выгружается вовсе.

И тут вступает recycling. NPC не удаляют и не создают заново (это дорого) — их переиспользуют. Ушёл за спину игрока — выгрузился из пула, появился впереди уже «другим» персонажем. Анимацию для тысяч NPC тоже упрощают и инстансят. По сути, толпа — это небольшой пул честных агентов плюс облако дешёвых статистов, и фокус в том, чтобы игрок никогда не поймал момент подмены.

Главный публичный кейс — AC Unity

Это ровно то, на чём держится Париж из Части 1. В докладе Франсуа Курнуайе «Massive Crowd on Assassin's Creed Unity: AI Recycling» (GDC 2015) описана как раз такая схема: при лимите порядка 40 «настоящих» AI и 120 высокодетализированных моделей на сцене ухитрялись держать до десяти тысяч NPC в кадре. Достигалось это пулом, который незаметно для игрока подменял низкодетализированных NPC на высокодетализированных по мере приближения. Вблизи — полное поведение, вдали — статистическая толпа, за камерой — выгрузка и переиспользование.

То есть «десять тысяч в Париже» — это не десять тысяч честных симуляций. Это сорок честных, сто двадцать «нарядных» и девять с лишним тысяч статистов, и вся инженерия — в том, чтобы стык был невидим. Именно LOD AI делает большую массовку вообще возможной: честно считается только то, что игрок реально разглядывает.

Honest hedge: почему тут нет интерактива

В отличие от первых четырёх частей, здесь нет демки — и это сознательно. LOD AI и recycling — это не один алгоритм, который можно крутить слайдером, а ворох продакшн-решений: пулы, пороги дистанций, бюджеты на «честных» агентов, тайминги подмены, инстансинг анимации. Честно показать это в браузере, не нафантазировав цифр, не выйдет.

К этому моменту у нас собрана вся архитектура: flow field для пути, GPU для симуляции, indirect draw для рендера, LOD AI чтобы не делать лишнего. Давайте посмотрим, что из этого реально подтверждено по конкретным играм, а что — наша догадка.

Часть 7. Под капотом: что мы знаем и не знаем про большие толпы

Planetary Annihilation (Uber Entertainment, 2014)

Бой в PA идёт на сфере — на поверхности процедурной планеты, а не на плоскости. Навигацию для этого писал Форрест Смит, и в своём портфолио он формулирует прямо: «я написал наш воксельный пасфайндер; он поддерживает сферические планеты, тысячи юнитов, разные размеры юнитов и разные типы движения». То есть сфера, тысячи юнитов и единый пасфайндер — это подтверждённый факт от автора. Сам подход «одно глобальное решение на большую толпу» Uber публично показывали в дев-материалах.

Supreme Commander 2 (Gas Powered Games, 2010)

Это канонический кейс flow field tiles. Элайджа Эмерсон описал тайловую схему в главе «Crowd Pathfinding and Steering Using Flow Field Tiles» (Game AI Pro, CRC Press, 2013), и выросла она из его работы над Supreme Commander 2. Глава лежит в открытом доступе — там разобрано всё, что мы обсуждали в Частях 2 и 3: тайлы, грубый путь между ними, локальный flow внутри.

Assassin's Creed Unity (Ubisoft Montreal, 2014)

Доклад Франсуа Курнуайе на GDC 2015 «Massive Crowd on Assassin's Creed Unity: AI Recycling»: recycling и LOD AI, порядка 40 «настоящих» AI и 120 высокодетализированных моделей, до десяти тысяч NPC в кадре, незаметная подмена low/high-res по дистанции. Есть и сопутствующий доклад Кристин Блондо про системные события в толпе того же года. Всё это разобрано в Части 6.

Total War (Creative Assembly)

На поле тысячи солдат, и держат они строй — это сама суть жанра. По рендеру есть отличный первоисточник: Тамаш Рабель, ведущий graphics-программист CA, в серии «Anatomy of the Total War Engine» на GPUOpen разбирает DX12, инстансинг тысяч юнитов и тысячи матриц для скелетной анимации — ровно то, о чём была Часть 5.

They Are Billions (Numantian Games, 2017–2019)

Движок самописный, и одна из его главных задач — одновременная симуляция и рендер десятков тысяч юнитов нежити. Разработчики в блоге и интервью говорили про кастомный pipeline с GPU-рендерингом для отрисовки орды и многопоточную логику.

Helldivers 2 (Arrowhead, 2024)

Игра сделана на Autodesk Stingray — движке, выросшем из Bitsquid, который Autodesk закрыл ещё в 2018-м. Это подтверждал публично сам Arrowhead (вплоть до CEO): студия тянула Stingray через несколько игр и допиливала его сама, без поддержки вендора. Так что про движок мы знаем, а вот про толпу термидов — нет.

Что объединяет все эти примеры

Паттерн один и тот же — тот самый сэндвич из четырёх слоёв: глобальная навигация (flow fields или навмеш), поиск соседей (spatial hash или аналог, на CPU или GPU), локальные правила и avoidance (boids/ORCA-семейство или эвристика), и сверху LOD AI, который выкидывает лишнее. Конкретные реализации у каждой студии свои, и полную схему никто наружу не выкладывает — это человеко-годы инженерии. Но кирпичи везде те же, и собрать из них рабочую толпу можете вы сами.

Эпилог: что мы получили и куда копать дальше

Соберём в одно место. Глобальный путь стал одним полем. Симуляция уехала на GPU. Рендер стал indirect-вызовом. А невидимое перестало считаться честно.

Сводная таблица слоёв

Что почитать и посмотреть дальше

• Elijah Emerson. «Crowd Pathfinding and Steering Using Flow Field Tiles». Game AI Pro: Collected Wisdom of Game AI Professionals, CRC Press, 2013, глава 23. Первоисточник по тайловым flow fields, PDF в открытом доступе — gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf.
• Treuille, A., Cooper, S., Popović, Z. (2006). Continuum Crowds. ACM Transactions on Graphics 25(3):1160–1168. Академический референс «толпы как непрерывного поля», математика поверх flow-field-идеи. DOI 10.1145/1141911.1142008.
• Sebastian Lague, Coding Adventure: Boids на YouTube. Боиды на compute shader с нуля — лучший публичный разбор GPU-стороны симуляции.
• Ulrich Haar, Sebastian Aaltonen. «GPU-Driven Rendering Pipelines». SIGGRAPH 2015, курс Advances in Real-Time Rendering. Mesh cluster rendering и GPU culling — опорный материал по indirect-рендеру.
• Francois Cournoyer. «Massive Crowd on Assassin's Creed Unity: AI Recycling». GDC 2015. Recycling и LOD AI на массовке Парижа.
• Forrest Smith — портфолио. Автор пасфайндера Planetary Annihilation: воксельный пасфайндер на сферических планетах, тысячи юнитов.
• Tamas Rabel. «Anatomy of the Total War Engine». AMD GPUOpen, 2016. Инстансинг тысяч юнитов и DX12-кухня от ведущего graphics-программиста Creative Assembly.
• Helldivers 2 на Autodesk Stingray — материал PC Gamer с публичными словами Arrowhead про движок.
• Mikko Mononen, recastnavigation. Recast/Detour с Detour Crowd — готовый ORCA-подобный локальный слой, связка с прошлой статьёй.

Заключение

Надеюсь, статья была полезна. Четыре интерактива, семь частей — и полная архитектура большой толпы: flow field для пути, GPU для симуляции, indirect draw для рендера, LOD AI чтобы не делать лишнего. Вместе с кирпичами из прошлой статьи этого достаточно, чтобы понимать, что лежит под капотом массовки в чужих играх, и собрать свою.

У меня есть телеграм-канал «математика в геймдеве по-простому», где я разбираю такие вещи короче и чаще. Заходите, если интересно.

Как обычно, моё решение не единственное, и в каждой студии — свои солверы, свои хаки и свои нюансы, которые наружу не выходят. Если у вас есть свой опыт с большими толпами в продакшне или наблюдения по конкретным играм — буду рад обсудить в комментариях.