Поведение толпы по-простому: от стай скворцов до тысячи юнитов в кадре

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

На этой неделе в телеграм-канале я постил три коротких поста про симуляцию толпы — вступительный про то, что у тысячи NPC нет тысячи AI, про три правила Рейнольдса и про то, почему наивный поиск соседей убивает FPS уже на пятистах юнитах. И, собственно, давно хотел собрать это всё в один большой материал, в котором каждая идея — интерактив в браузере, который можно покрутить пальцами на телефоне.

Сталкивались ли вы с ситуацией, когда у вас в игре уже двести юнитов, а FPS почему-то уехал, хотя визуально на сцене ничего особенного нет? Или с тем, что хочется сделать настоящую орду — плотную, с реакцией на стрельбу, обтекающую укрытия — а получается стайка эгоистов, которые либо разбегаются как пыль, либо слипаются в один шарик и едут им по всей карте?

Чтож, давайте по порядку. Как это устроено у настоящих скворцов в Риме и причём тут код, какие именно три правила Рейнольдса и как они балансируются весами, как сетка побеждает O(N²) и где она сама ломается, что такое ORCA и как она решает встречные потоки в коридоре, как steering behaviors дают цель и обход препятствий, что вообще лежит между симуляцией и пикселем на экране в виде GPU instancing — и что под капотом конкретных шипнутых игр от Assassin's Creed Unity до World War Z.

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

Часть 1. Биологический заход: что не так со словом «AI у каждого юнита»

Прежде чем лезть в код, посмотрим, как это устроено в природе. Не потому, что мне нравится биология (хотя и поэтому тоже), а потому, что у нас программистов есть привычка слово «толпа» начинать осмыслять с фразы «у каждого юнита есть behavior tree». Это, как мы сейчас увидим, не единственно возможный способ — и на самом деле у живых стай это так не работает.

Murmurations: что мы вообще видим

Если ввести в поиск слово murmuration, вы увидите чёрно-белые гифки гигантских стай скворцов (Sturnus vulgaris), которые осенью над крышами европейских городов — и особенно над Римом — образуют огромные жидкие облака из тысяч птиц. Стая изгибается, делится, сливается обратно, реагирует на сокола за доли секунды. На видео это выглядит так, будто у всей стаи есть один общий мозг.

Самый интересный вопрос это — а нет ли там действительно общего сигнала? Может, передний скворец что-то «командует»? Может, есть «вожак»? Конечно же нет. Никакого центрального управления в стае нет. Каждая отдельно взятая птица не знает, что делает стая в целом, и не получает приказов сверху. Это и есть та самая эмерджентность, о которой я говорю — групповое поведение возникает не из общего мозга, а из локальных взаимодействий между соседями.

Reynolds (1987): «они летают по локальным правилам»

В 1987 году на SIGGRAPH вышла короткая статья Craig W. Reynolds — «Flocks, herds and schools: A distributed behavioral model» (Computer Graphics 21(4):25–34). Это и есть та самая работа, в которой впервые формально были описаны boids — «bird-oid objects», искусственные птицы, которые на экране ведут себя как стая. Сам термин «boids» придумал автор как сокращение для «bird-oid», и оно прижилось так, что вы его сейчас встретите в любом туториале по симуляции толпы.

Идея в одной строке: каждый агент видит только своих соседей в локальной окрестности и применяет три простых правила. Никакого общего «мозга». Никакой передачи сообщений между птицами. Никакого глобального плана движения.

Это была гипотеза. Reynolds показал, что если так запрограммировать виртуальных птиц, на экране получается что-то очень похожее на настоящую стаю. Был ли это реальный механизм, по которому летают живые скворцы? Этот вопрос оставался открытым ещё двадцать лет.

Ballerini (2008): а как работает живая стая

В 2008 году вышла статья итальянских физиков и биологов — Ballerini et al., «Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study» (PNAS 105(4):1232–1237). Команда отвечала за биологию (Andrea Cavagna, Irene Giardina и др.), направление называется «Statistical and Biological Physics».

Что они сделали — это, собственно, самое интересное. Над римскими крышами поставили несколько синхронизированных стереокамер. Сняли реальные стаи скворцов в полёте. Триангулировали 3D-координаты каждой отдельной птицы в каждом кадре. Получили датасет из тысяч стереоснимков с реконструкцией трёхмерных позиций всех птиц в стае.

И задали один конкретный вопрос: соседи, на которых реагирует каждая птица — это соседи по расстоянию (метрические) или соседи по числу (топологические)? То есть «все, кто ближе двух метров» или «семь ближайших, неважно как далеко»?

Топологические соседи (~7) — ключевой результат

Ответ: топологические. По данным Ballerini, каждая птица в стае реагирует примерно на 6–7 ближайших соседей, и это число почти не зависит от плотности стаи в данный момент. Когда стая сжимается под атакой хищника — соседи становятся ближе физически, но их всё равно семь. Когда расходится в более просторное построение — соседи дальше, но опять же соседей примерно семь.

Почему это важно для нас. Reynolds в 1987 году предположил метрический радиус видимости — «все, кто в радиусе R». Это работало визуально, но Ballerini показал, что у реальных скворцов механизм другой. Топологическое правило биологически объясняется лучше: оно устойчиво к плотности и обеспечивает стае целостность даже при сильном сжатии — что критично, когда сокол атакует и стая сжимается.

В играх и индустриальных симуляциях по сей день почти все реализации — метрические. Это сознательное упрощение: метрика дешевле считается, особенно с spatial hash, который мы разберём в части 3. Визуально разница есть, но она не критичная для большинства задач. Хотите аутентичности — берёте топологический вариант (k-ближайших соседей). Хотите скорости — метрический. В демке ниже у нас именно топологический вариант, чтобы вы могли покрутить число соседей k и посмотреть, где стая ощущается как настоящая, а где — нет.

Honest hedge: а у рыб тоже так?

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

Связь с играми

В играх массовка нужна постоянно. Толпы в открытом мире, орды в roguelike-боевиках, юниты в RTS, стаи рыб в океанических локациях, птицы в небе как ambient detail. На каждый из этих случаев в индустрии используется один и тот же базовый паттерн — локальные правила на каждом агенте, без глобального «AI толпы». Конкретные нюансы — в Части 7, где мы разберём, что лежит под капотом конкретных тайтлов.

Интерактив 1: Murmuration toy

В демке ниже летают «птички» по тому же принципу, что и в работе Ballerini — каждый агент видит ровно k ближайших соседей (топологически, не метрически), и применяет к ним три правила Рейнольдса. По умолчанию k=7 — то самое число из реальных стай. Слайдером N можно менять размер стаи.

Покрутите слайдер. На k=1 стая распадается на цепочки и пары. На k=7 ощущается живой стаей с характерными волнами. На k=15–30 слипается в монолит, реагирующий как один большой объект. А если нажать кнопку «тревога» — в случайном месте на пару секунд возникнет «сокол», и стая разделится-сольётся, как настоящая.

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

Часть 2. Три правила Рейнольдса: separation, alignment, cohesion

Парадокс настоящей стаи я уже проговорил в предыдущем разделе — все летят согласованно, но никто никем не управляет. Откуда тогда согласованность? Ответ Рейнольдса: каждый агент одновременно решает три локальные задачи. Не наступить соседу на хвост. Лететь примерно в ту же сторону, что соседи. Не отставать от группы. Эти три задачи противоречат друг другу, и балансом противоречий получается то, что мы видим как стаю.

Давайте по порядку, каждое правило — векторная поправка к скорости агента, потом всё складывается с весами в одну итоговую силу.

Separation: «не наступай на ноги»

Для каждого соседа j, который оказался слишком близко (расстояние меньше sepRadius), добавляем отталкивающий вектор. В простом виде он направлен от соседа к нам, и его длина обратно пропорциональна квадрату расстояния. То есть чем ближе сосед, тем сильнее отталкивание.

Технически это записывается как (self.pos - j.pos) / dist² или, что то же самое — normalize(self.pos - j.pos) / dist.

Alignment: «смотри, куда смотрят соседи»

Считаем среднюю скорость соседей в радиусе видимости. Целевая корректировка — avg.vel - self.vel, то есть «подтяни свою скорость к средней». Без alignment стая летит, но не направлена — это просто облака точек, которые шевелятся. С alignment стая получает общий heading, и появляется чёткое ощущение «куда летим».

Cohesion: «не отставай»

Считаем центр масс соседей. Целевая корректировка — (avg.pos - self.pos), вектор от агента к центру масс. Это «тянись к группе». Без cohesion стая не сцеплена и быстро распадается на пары и одиночек, которых уносит в стороны.

Единый цикл (C#, Unity-style)

Все три правила в одном проходе по соседям. Тот же код, что в пятничном посте телеграм-канала, но с одним нюансом — раскрою его дальше.

Vector3 sep = Vector3.zero, ali = Vector3.zero, coh = Vector3.zero;
int count = 0;

foreach (var other in neighbors) {
    Vector3 d = transform.position - other.position;
    float dist = d.magnitude;
    if (dist > 0f && dist < sepRadius)
        sep += d.normalized / dist;   // ближе → сильнее
    ali += other.velocity;
    coh += other.position;
    count++;
}

if (count > 0) {
    ali = (ali / count) - velocity;
    coh = (coh / count) - transform.position;
}

velocity += wSep * sep + wAli * ali + wCoh * coh;
velocity = Vector3.ClampMagnitude(velocity, maxSpeed);
transform.position += velocity * Time.deltaTime;

Один нюанс, на который часто не обращают внимания — это d.normalized / dist. По форме это то же самое, что d / dist². Просто разные способы записи одного и того же вектора. Используют первую запись потому, что она яснее показывает физический смысл: «единичный вектор от соседа, поделённый на расстояние». Если у вас в проекте есть дешёвый sqrMagnitude и вы хотите сэкономить sqrt — пишите через квадрат, результат тот же.

Радиусы видимости: один или три

В классическом коде Рейнольдса 1987 года — три разных радиуса: sepRadius, aliRadius, cohRadius. Обычно sepRadius < aliRadius ≈ cohRadius. Логика: separation должна срабатывать только когда сосед уже очень близко, а alignment и cohesion — на всём радиусе видимости.

В упрощённой версии (это то, что в большинстве туториалов и в нашем коде выше) — один общий радиус r, а sepRadius — внутренняя константа меньше него. Это, собственно, достаточно для всех практических задач в инди-играх. В AAA-системах чаще берут три разных радиуса, плюс ещё «угол обзора» — агент не видит то, что строго сзади, и это важно для авиационных моделей: реальная птица не видит другую птицу прямо за хвостом, и игнорировать это — сильное упрощение.

Где это в играх

• Стаи рыб в Subnautica. Каноническая иллюстрация чистых boids в современной игре. Видно, как косяк сходится и расходится, реагирует на игрока как на репеллер.
• Птицы в Far Cry и RDR2. Окружающая фауна — птицы, выводки уток, орлы — на boids поверх spline-патрулей.
• Half-Life: Alyx, рои headcrabs. Hostile boids с дополнительным правилом seek к игроку — об этом в Части 5.
• Total War-серия. Отряды внутри отряда — модифицированные boids поверх строевой формации с slot-based позициями.

Во всех перечисленных играх ванильных boids в чистом виде, конечно же, нет. Поверх лежат флоу-филды для глобальной навигации, FSM для смены поведений, иногда — отдельные солверы для тесной толпы. Но базовый слой — именно эти три правила.

Где boids ломаются и зачем нам остальные разделы

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

Узкие коридоры. Два встречных потока залипают — separation не успевает разрулить встречное движение. Это к Части 4 (ORCA).

Большое количество агентов. Наивный поиск соседей O(N²) убивает FPS уже на 500 юнитах, и мы этого даже не дотягиваем до проблем масштаба «толпа в AC Unity». Это к Части 3 (spatial hash).

Нужно идти к конкретной цели. Чистые boids цели не знают — это локальное правило, без глобального плана. Это к Части 5 (steering behaviors).

Интерактив 2: Boids playground

Покрутите ползунки. Кнопка freeze — пауза, чтобы можно было рассмотреть, кто куда смотрит. Чекбокс «показать радиусы» подсвечивает одного агента (красного) и рисует вокруг него области видимости.

Чтобы понять, как работают три правила вместе, покрутите веса в четырёх режимах:

Только wSep, остальные ноль. Толпа рассыпается. Каждый агент отскакивает от соседей и больше ничего не делает. Никакого общего движения, никакой стаи — просто разлетающаяся пыль. Это, кстати, полезный режим для дебага: если у вас в проекте что-то не так с separation, нужно сначала отключить два других правила и убедиться, что хотя бы отталкивание работает.

Только wAli. Толпа идёт стройно, но не сцеплена. Агенты движутся параллельно, но не реагируют на то, что часть отстала. Похоже на парад, а не на стаю.

Только wCoh. Толпа схлопывается в точку. Все притягиваются к центру, по дороге наступают друг другу на ноги (separation выключен), и получается «один большой шарик», который пульсирует.

Все три в балансе. Живая стая. Та самая, которую мы хотим. По умолчанию в playground'е стоят равные wSep=1.0, wAli=1.0, wCoh=1.0 — все три нормированы в единичные векторы, и веса работают в одной шкале. Дальше можно подкручивать под свою задачу.

Слайдер N я не просто так сделал до числа 500. Дальше — почему так, и как сделать чтобы было нормально и на пяти тысячах.

Часть 3. O(N²), uniform spatial hash и где они ломаются

Окей. Правила работают, веса крутятся, стая мутится. Идём дальше — посмотрим, сколько это всё стоит.

Что мы считаем

В каждом кадре для каждого агента нужно знать, кто его соседи — без этого правила Рейнольдса просто не работают. Самое наивное — пройтись по всем остальным агентам и проверить расстояние. Это O(N²) проверок на кадр. Прикинем цифры. N=100 — десять тысяч проверок. N=500 — четверть миллиона. N=1000 — миллион. N=5000 — двадцать пять миллионов проверок дистанции на каждый кадр, при шестидесяти кадрах в секунду — полтора миллиарда в секунду. И это до того, как мы посчитали что-либо ещё — рендер, физику, обработку ввода.

Я сознательно не привожу конкретных бенчмарков в миллисекундах — это очень сильно зависит от языка, движка, версии JS-движка в браузере, кэширования и десятка других вещей. Но порядок понятен: на современном CPU миллион простых проверок дистанции — это примерно несколько миллисекунд в JS-однопоточном цикле, и около миллисекунды в нативном C# или C++ с приличным cache-friendly кодом. При бюджете на кадр в 16.7 миллисекунд (это 60 FPS), миллион проверок — это уже значимая доля.

Идея сетки: соседи всегда рядом

Простое наблюдение: если радиус видимости r равен, скажем, пятидесяти пикселям, то агент в углу canvas физически не может видеть агента в противоположном углу. Проверять их пару — пустая трата.

Разбиваем мир на регулярную сетку клеток размером cellSize × cellSize. Каждый агент попадает в свою клетку — туда, где он сейчас находится. Когда нам нужно найти соседей агента, мы смотрим только в его клетку и восемь соседних — итого девять клеток в 2D. В 3D это уже двадцать семь клеток, но идея та же.

При равномерной плотности агентов в каждой клетке лежит фиксированное среднее количество — допустим, десять штук. Тогда поиск соседей одного агента занимает порядка ста проверок (девять клеток × десять агентов в каждой) вместо девятисот девяноста девяти (все, кроме самого себя, на сцене из тысячи). При N=5000 разница уже не на порядок, а на два — сто vs пять тысяч.

Размер клетки: главная настройка

Базовое правило: cellSize = r (радиус видимости). Это потому, что в радиусе r от агента точно лежат все клетки, до которых от него меньше одного cellSize по любой оси — а это и есть его 9 клеток.

Если cellSize сделать меньше радиуса видимости, придётся смотреть не 3×3 клетки, а 5×5 или 7×7 — иначе часть соседей в радиусе просто потеряется. Проверок становится больше, выгода тает. Если же cellSize сделать больше — клетки получаются «жирные», в каждую набивается слишком много кандидатов, и spatial hash вырождается обратно к brute force внутри клетки.

На практике cellSize подбирается под среднюю плотность сцены так, чтобы в одной клетке оказывалось 5–20 агентов — это и есть «sweet spot»«sweet spot» (англ. — «золотая точка», «точка максимума») — диапазон параметра, в котором система работает оптимально: до неё эффект слабый, после неё — преимущество исчезает или превращается в накладные расходы.. Меньше одного агента на клетку — клетки слишком мелкие, и накладные расходы на саму структуру данных съедают выигрыш. Сто агентов на клетку — клетки слишком большие, и внутри каждой переполненной клетки spatial hash локально вырождается обратно в O(N²).

Код (Unity / C#)

// build: один раз в начале кадра, после движения всех агентов
var grid = new Dictionary<Vector2Int, List<Boid>>();
foreach (var b in boids) {
    var cell = new Vector2Int(
        Mathf.FloorToInt(b.position.x / cellSize),
        Mathf.FloorToInt(b.position.z / cellSize));
    if (!grid.TryGetValue(cell, out var list))
        grid[cell] = list = new List<Boid>();
    list.Add(b);
}

// query: на каждого агента, для каждого правила
List<Boid> Neighbors(Boid b) {
    var result = new List<Boid>();
    var c = CellOf(b);
    for (int dx = -1; dx <= 1; dx++)
        for (int dy = -1; dy <= 1; dy++) {
            if (!grid.TryGetValue(c + new Vector2Int(dx, dy), out var list))
                continue;
            foreach (var other in list)
                if ((b.position - other.position).sqrMagnitude < r * r)
                    result.Add(other);
        }
    return result;
}

Что мы получили в цифрах. Дорогая проверка дистанции (sqrMagnitude < r*r) теперь делается только для кандидатов из девяти клеток вокруг агента, а не для всей сцены. Поиск соседей одного агента стоит O(K), где K — среднее число агентов в этих девяти клетках. Поиск по всей сцене — O(N·K). И ключевое: при равномерной плотности K от N не зависит, поэтому общая сложность падает с O(N²) до эффективного O(N).

Происхождение spatial hash

Spatial hashing — старая идея, её разные формулировки применяются с 70-х в графике и с 80-х в молекулярной динамике. В контексте игр и collision detection ключевая опорная работа — Teschner et al. (2003), «Optimized Spatial Hashing for Collision Detection of Deformable Objects» (VMV 2003). У Teschner'а подробно разобран хеш-вариант, при котором сетка может быть бесконечной — ключ клетки получается хешированием её координат, а не индексацией в массив. Это критично для открытых миров, где у вас нет известных заранее границ.

Базовая идея, которую мы используем, проще чем у Teschner'а, но из той же серии: пространственная хеш-таблица, ключ — клетка, значение — список объектов в клетке.

Почему Dictionary в проде заменяют

В JavaScript / TypeScript эту конструкцию мы пишем как Map<number, Array<Boid>>, и в браузере она работает совершенно нормально: память выделяется дёшево, встроенный хеш приличный, код читается без оговорок.

В Unity C# тот же код в hot pathHot path — участок кода, который исполняется десятки или сотни раз за кадр (внутренние циклы апдейта, broad-phase коллизий, поиск соседей). Именно тут любая аллокация и любой лишний вызов виртуального метода превращаются в просадку FPS, поэтому в продакшне hot path вычищают от GC и кэшируют ссылки. ведёт себя иначе. Каждый новый List, каждый новый элемент Dictionary — это GC-аллокация. На каждый кадр их сотни, и при N > 1000 сборщик мусора начинает срабатывать раз в несколько кадров, выдавая заметные провалы FPS.

Стандартный продакшн-вариант — два плоских массива фиксированного размера. Первый, cellHead[], для каждой клетки хранит индекс «первого» боида в ней. Второй, next[], для каждого боида — индекс следующего боида в той же клетке. Получается интрузивный связанный список через индексы, без единого new в кадре. Код многословнее, но в Unity это легко даёт пятикратный-десятикратный прирост за счёт нуля аллокаций и плотной упаковки в кэш.

Альтернативы сетке: когда плотность неравномерная

Uniform grid хорош, когда плотность примерно равномерная. Если у вас половина юнитов в одном углу карты, а вторая половина равномерно по миру — почти все юниты попадут в одну переполненную клетку, и spatial hash вырождается обратно в O(N²) на эту клетку. Не на всю сцену, но локально — будет проседать.

Альтернатив три, в зависимости от того, что именно у вас неравномерное:

• KD-tree. Бинарное разбиение пространства, перестраивается каждый кадр или раз в несколько кадров. Хорошо для неоднородных плотностей. Тяжелее в реализации, дороже в построении, но даёт логарифмическое время поиска даже в плохих случаях.
• Quadtree (2D) / Octree (3D). Иерархическая сетка с переменным размером клетки. Часто используется в широких open-world сценах, где плотность сильно варьируется по разным участкам карты.
• BVH. Bounding volume hierarchy. Чаще для статичной геометрии и препятствий, чем для подвижных агентов. Перестраивать BVH каждый кадр дорого, а для агентов uniform grid обычно лучше. Для статичных коллайдеров — наоборот, BVH рулит.

В Unity Job System / DOTS и Unreal Mass AI используют разные комбинации этих структур. Готового рецепта «вот вам KD-tree, копируйте» в моих статьях не будет — для большинства задач uniform grid достаточно, и это тот случай, когда простое решение лучше. Если вы реально упёрлись в неравномерность — это уже отдельный разговор, и без профиля конкретной сцены любой совет тут будет пальцем в небо.

Интерактив 3: Spatial hash visualizer

В демке ниже — до двух тысяч агентов с переключаемым между brute force и spatial hash поиском соседей. Под canvas — FPS и общее число проверок на кадр. Это, собственно, главная цифра.

Покрутите слайдер N. На две тысячи и brute force — ваш браузер начнёт проседать (на ноутбуке у меня уезжает в район 5–15 FPS). Включите spatial hash — те же две тысячи держат шестьдесят. Это и есть та самая разница.

И слайдер cellSize. По умолчанию 50 — близко к радиусу видимости и оптимально. Если ставите 200 — клетки слишком большие, выигрыш частично теряется. Если 10 — клетки слишком мелкие, среднее количество в клетке падает до нуля-одного, агент не находит соседей в радиусе и стая визуально распадается. Это, кстати, демонстрация того, что cellSize — параметр, который влияет не только на скорость, но и на корректность.

Чтож, искать соседей научились. Теперь — следующая проблема. Two boids enter a corridor, one boid leaves.

Часть 4. ORCA: почему separation одного мало в узком коридоре

Это, собственно, самый математический раздел статьи. Я попробую разобрать его так, чтобы он не пугал — за ORCA стоит конкретная геометрическая конструкция, которую можно увидеть на пальцах. И результат этой конструкции — именно тот, который вы видите в любой современной RTS, где толпа юнитов плотным потоком проходит через узкий проход и не залипает.

Что не вытягивает separation

Возьмём два встречных агента в узком коридоре шириной в полтора их диаметра. Оба идут навстречу друг другу. Separation у каждого подключится, только когда они окажутся в пределах sepRadius. Но к этому моменту они уже на встречном курсе вплотную, и отталкивание направлено вдоль линии между ними — то есть против их собственного движения. Оба тормозят, скорость падает почти до нуля, обойти друг друга им просто нечем: стены коридора рядом, шарахаться в стороны некуда.

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

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

Velocity Obstacles (1998)

В 1998 году Paolo Fiorini и Zvi Shiller предложили принципиально другой подход — «Motion planning in dynamic environments using velocity obstacles» (International Journal of Robotics Research 17(7):760–772). Идея, которая лежит в основе всей последующей линии работ — рассуждать не в физическом пространстве, а в пространстве скоростей.

В каждый момент времени у агента есть текущая позиция и выбираемая скорость (мы сами решаем, как двигаться). Для каждого препятствия — другого агента или статического объекта — можно построить в пространстве скоростей подмножество тех скоростей, при которых столкновение случится в ближайшие t секунд. Это подмножество и называется velocity obstacle (VO).

Геометрически в 2D это конус, исходящий из точки относительной скорости соседа. Точные формулы тут не критичны для понимания — главное, что эта область вычисляется в замкнутой форме за O(1) на пару, и проверка «безопасна ли моя скорость» сводится к проверке «лежу ли я внутри конуса».

Reciprocal Velocity Obstacles (2008)

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

В 2008 году группа из UNC Chapel Hill — Jur van den Berg, Ming Lin, Dinesh Manocha — опубликовала «Reciprocal Velocity Obstacles for real-time multi-agent navigation» (ICRA 2008). Главная идея: каждый агент берёт на себя половину работы по уклонению. Это и есть reciprocal в названии.

Геометрически это выражается в смещении исходной точки velocity obstacle. Вместо полного VO мы рассматриваем половину — «мою половину обязанности», и предполагаем, что симметричную половину возьмёт сосед. Это уже работает в реальном времени для десятков агентов. Тот же RVO, который потом стал частью Unity NavMeshAgent — внутри NavMeshAgent сидит вариант RVO-подобного локального avoidance. Документация Unity описывает параметры (avoidancePriority, radius, obstacleAvoidanceType), но конкретные алгоритмические детали проприетарны.

ORCA (2011): почему линейное программирование

В 2011 году та же группа опубликовала развитие — Optimal Reciprocal Collision Avoidance: «Reciprocal n-body collision avoidance», van den Berg, Guy, Lin, Manocha (Robotics Research, Springer Tracts in Advanced Robotics 70:3–19). Это и есть ORCA, которой пользуется значительная часть индустрии.

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

Шаг первый. Для каждого соседа j вокруг агента i строится полуплоскость в пространстве скоростей. Эта полуплоскость отделяет «безопасные» скорости от «опасных» — тех, что приведут к столкновению с j в ближайшие tau секунд. С учётом reciprocal-смещения, разумеется.

Шаг второй. Безопасное множество для агента i — это пересечение всех таких полуплоскостей от всех соседей. Геометрически это выпуклый многоугольник в пространстве скоростей. Внутри многоугольника — все скорости, безопасные относительно всех соседей одновременно.

Шаг третий. Выбираемая скорость — это ближайшая к preferred velocity точка из безопасного множества. Preferred velocity — это то, как агент хотел бы двигаться, если бы соседей не было (например, прямо к своей цели). Задача «найти ближайшую точку в выпуклом многоугольнике к заданной точке» — это линейное программирование с двумя переменными.

Почему именно LP, а не градиентный спуск

Сначала коротко, что вообще такое LP. Linear programming, линейное программирование — это класс задач оптимизации, в которых нужно минимизировать (или максимизировать) линейную функцию при наборе линейных ограничений-неравенств. Геометрически — найти точку внутри выпуклого многоугольника (это и есть множество, заданное неравенствами), на которой целевая функция минимальна. Слово «программирование» здесь — устаревший термин из 1940-х (программа в смысле «план действий»), к программированию в современном смысле отношения не имеет. Для ORCA это в точности наша задача: множество — выпуклый многоугольник безопасных скоростей, целевая функция — «расстояние до preferred velocity».

У нас всего две переменные (vx, vy) и десяток-другой линейных ограничений — по одному на соседа. LP с двумя переменными решается за O(K) времени при K ограничений (результат Megiddo, 1984). Это копеечная задача, реально измеряемая в наносекундах на современном CPU.

Градиентный спуск был бы итеративным, не дал бы гарантии оптимальности, был бы чувствителен к настройке шага и мог бы застревать в плохих случаях. LP — детерминирован, стабилен, прозрачен и дёшев. Именно поэтому индустрия выбрала LP, и именно поэтому ORCA работает в продакшне.

Где это в проде

• Unity NavMeshAgent. Внутри сидит локальный avoidance, концептуально близкий к RVO/ORCA. Работает «из коробки» для большинства Unity-проектов и хорошо тянет десятки-сотни агентов. Если у вас в проекте уже используется NavMeshAgent, поздравляю — у вас уже есть ORCA-подобное решение.
• Recast / Detour Crowd. Открытая C++-библиотека Mikko Mononen (бывший Crytek, потом Unity) для навигации и crowd-симуляции на навмешах. Crowd-модуль Detour реализует ORCA-подобный локальный avoidance. Используется в Unreal Engine, в Godot, во множестве инди-движков. Это де-факто open-source стандарт. Репозиторий — recastnavigation/recastnavigation на GitHub.
• RVO2 Library. Прямо от авторов оригинальной статьи (UNC Chapel Hill) — C++/C# библиотека на gamma.cs.unc.edu/RVO2/. Это эталонная реализация ORCA, по которой проверяются все остальные.

Когда ORCA ломается

Несколько ситуаций, в которых ORCA даёт сбои.

Сверхплотные толпы. Когда безопасное множество пусто или почти пусто, ORCA вырождается в «не двигаюсь». Толпа замирает. Решение в проде — fallback в softer-режим или комбинирование с flow fields для глобальной навигации, чтобы агенты в принципе не оказывались в безвыходных позициях.

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

Большие массовки (тысячи агентов). На N=5000 решение LP для каждого агента — это уже 5000 LP в кадр. Не катастрофа, но добавляется к бюджету. В этом случае комбинируют LOD AI: дальние агенты только по boids, ближние — через ORCA.

Что в моей демке

Поскольку полная реализация ORCA с linear programming — это не маленький объём кода (репозиторий RVO2 — несколько тысяч строк), в интерактиве ниже используется упрощённая ORCA-подобная схема. Для каждого соседа я считаю время до столкновения через квадратное уравнение, и если оно меньше горизонта tau — добавляю силу избегания, перпендикулярную линии будущего контакта. Reciprocal-half заложен как множитель 0.5. Это не строгий ORCA с гарантиями, но визуально воспроизводит главный эффект — встречные потоки обтекают друг друга, а не залипают.

Если вы хотите потом перенести это в Unity «по-настоящему» — используйте либо NavMeshAgent (там уже всё внутри), либо порт RVO2 для C#, который тоже доступен публично.

Интерактив 4: ORCA в коридоре

Две группы по двадцать агентов идут навстречу через коридор. Слайдером можно менять его ширину в диаметрах агента — посмотреть, как одно и то же поведение проходит на 4 диаметрах, начинает буксовать на 2.5 и тонет на 2. Когда обе группы дошли до концов, они респаунятся обратно — это бесконечный цикл. Avoidance внутри — упрощённый ORCA-like алгоритм с боковым смещением и tau-предвидением, описанные выше.

Окей, столкновения разрулили. Осталось научить толпу к чему-то идти, а не просто крутиться. И обходить препятствия, которые не другие агенты.

Часть 5. Цель и препятствия: steering behaviors

К этому моменту у нас есть три правила Рейнольдса (Часть 2), быстрый поиск соседей через spatial hash (Часть 3) и гарантия отсутствия столкновений через ORCA (Часть 4). Чего не хватает? Цели. Boids в чистом виде не знают, куда идти — они знают только, как двигаться согласованно с соседями. В реальной игре этого недостаточно: юниты должны идти на штурм, рыбы — плыть к корму, NPC — патрулировать заданный маршрут.

Reynolds 1999: расширение базовых правил

В 1999 году Reynolds выступил на GDC с докладом «Steering Behaviors for Autonomous Characters». Это уже не про стаи, а про отдельных автономных персонажей, и про набор переиспользуемых «строительных кирпичей» поведения. Канонический набор — seek, flee, arrive, wander, pursue, evade. Документация и красивые схемы лежат на red3d.com/cwr/steer/.

Эти behaviors задают preferred velocity агента — желаемую скорость, как если бы соседей и препятствий не было. А дальше поверх работают alignment, cohesion из boids и avoidance через ORCA. Это слой над слоем, не замена.

Базовые behaviors

Seek(target). Самое простое — тянуть агента к точке.

Vector3 desired = (target - transform.position).normalized * maxSpeed;
Vector3 steering = desired - velocity;

Желаемая скорость направлена к цели и равна по модулю maxSpeed. Steering — это разница между желаемой и текущей скоростью. Сложите её с другими силами, ограничьте по модулю и обновите позицию.

Flee. Обратное seek — desired = (pos - threat).normalized * maxSpeed. Полезно для зайца, убегающего от лисы, или для NPC, которые должны бежать от взрывов.

Arrive(target). Как seek, но desired масштабируется по дистанции до цели — близко к цели агент тормозит. Лечит «дёрганый стоп» в финальной точке. Без arrive агент пролетает через цель, разворачивается, опять пролетает — и осциллирует.

float d = (target - transform.position).magnitude;
float speed = d < slowingRadius
    ? maxSpeed * (d / slowingRadius)
    : maxSpeed;
Vector3 desired = (target - transform.position).normalized * speed;

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

Pursue / Evade. Seek и flee, но к предсказанной будущей позиции цели. Используется упреждение — линейная экстраполяция позиции цели на основе её скорости. Это, кстати, тот же самый алгоритм упреждения, что в шутерной статье — там для пули, тут для агента. Геометрически — одно и то же квадратное уравнение.

Slot-based formations: строй как «забронированные места»

Для отрядов в RTS, Total War, или любой военной стратегии boids недостаточно — нужно, чтобы юниты строились в формацию (линия, клин, каре). Подход slot-based: формация определяется как набор «слотов» — координат относительно центра отряда. При движении отряда каждый юнит назначен на свой слот и стремится в него через arrive.

Boids поверх этого: separation мягко сглаживает мелкие касания между юнитами. Alignment поверх slot не нужен — он уже задан построением. В Total War слоты пересчитываются динамически при поворотах строя и при потерях — это, безусловно, более сложная инженерия, чем чистый boids.

Обход препятствий: раздельно от ORCA

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

Более продвинутый — представить препятствия как поле расстояний (SDF — про это есть отдельная статья). В крауд-симуляции SDF используется для того, чтобы быстро понять «насколько близко я к ближайшей стене» — и это сэмпл из 3D-текстуры, O(1), очень дёшево.

В Unity и Unreal препятствия обычно интегрированы прямо в навмеш, и avoidance происходит на уровне NavMeshAgent / Detour Crowd — отдельной подсистемы для статики писать в большинстве случаев не нужно.

Как steering behaviors сшиваются с boids и ORCA

Это важный момент, который часто упускают в туториалах. Порядок такой, для каждого агента на каждый кадр:

1. Steering behavior даёт preferred velocity — куда бы я хотел двигаться (в seek-цель, по wander, по slot).
2. Boids поправки (separation/alignment/cohesion от соседей) корректируют preferred velocity. На уровне векторной суммы с весами.
3. ORCA (или другой local avoidance) берёт скорректированную preferred velocity и отсекает её к ближайшей безопасной точке в пространстве скоростей.
4. Кэп по maxSpeed и обновление позиции.

Что тут упрощено

На практике в продакшне между шагами вставляются доп-фильтры: smoothing скорости (чтобы агент не дёргался от шумных сил), мягкий поворот с угловой скоростью (а не мгновенное изменение heading'а), priority overrides (бегущий от страха агент ломает обычную логику и игнорирует часть правил).

Веса между boids-поправками и steering — это, кстати, не обязательно фиксированные числа. В некоторых системах они адаптивные: на свободном пространстве усилен seek, в плотной толпе — усилена separation. Это называется context-aware steering, есть отдельная серия работ в AI Game Programming Wisdom — но для большинства задач хватает фиксированных весов, подобранных под конкретную игру.

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

Интерактив 5: Steering behaviors playground

В демке ниже — тридцать агентов и несколько препятствий (красные кружки), которые можно тащить мышью. Кликом задаётся цель (фиолетовый крест). Чекбоксы переключают комбинации: seek, arrive, wander, obstacle avoidance.

Попробуйте по очереди.

• Только seek. Агенты добегают до цели, проскакивают её на максимальной скорости, разворачиваются и снова летят через цель. Получается орбита вокруг точки. Это классический симптом «забыли про arrive».
• Seek + arrive. Тот же seek, но с тормозом на подходе: внутри slowingRadius агент масштабирует желаемую скорость пропорционально расстоянию. У цели агенты чисто останавливаются.
• Wander. Цель не используется вовсе. Агенты бесцельно блуждают по сцене — это полезный режим для ambient-фауны: рыбок в аквариуме, бабочек на лужайке, фоновых птиц над лесом.
• Obstacle avoidance. Включает рейкаст-проверку препятствий впереди по курсу. Красные кружки можно тащить мышью — агенты в реальном времени переориентируются и обтекают их.

На этом инженерный набор симуляции собран. Boids задают групповое поведение, spatial hash делает поиск соседей дешёвым, ORCA разруливает встречные потоки, steering ведёт агента к цели и обходит препятствия. Дальше — отдельный слой, про который часто забывают: рендер. Тысячу юнитов мало посчитать, их надо ещё и нарисовать так, чтобы видеокарта не легла.

Часть 6. Рендер тысячи юнитов: GPU instancing и compute shaders

Эту часть я сначала писать не собирался, потому что симуляция и рендер в индустрии — это разные подсистемы, которыми обычно занимаются разные команды. Предыдущие пять частей — про симуляцию: что юнит делает, куда шагает, как избегает столкновений. Эта — про рендер. Без неё статья остаётся незакрытой: симуляцию мы посчитали, а как это всё нарисовать на экране, когда юнитов тысяча, — вопрос отдельный.

Сразу честно — это короткий раздел без интерактива. Полноценный туториал по GPU instancing с примерами в Unity — материал ещё одной отдельной статьи. Тут я обозначу основные точки, чтобы у вас была карта.

Симуляция и рендер: как они сшиваются

На уровне инженерии симуляция пишет в буфер позиций и ориентаций, рендер этот буфер читает. Между ними — либо CPU memory (с пересылкой на GPU каждый кадр), либо общий GPU buffer (если симуляция на GPU). Это два варианта, между ними есть гибриды.

Главная инженерная задача рендера тысячи юнитов в одном предложении — минимизировать число draw calls. Чем меньше — тем больше юнитов влезает в кадр. И из этого следует всё остальное.

Наивный подход в Unity: 1000 GameObject = 1000 draw calls

Прямой способ, как делают новички — Instantiate(prefab) на каждый юнит. У каждой копии — свой MeshRenderer, свой Material instance, своя матрица трансформации. На сотне юнитов это работает. На тысяче — нет.

Каждый MeshRenderer без instancing — это отдельный draw call к GPU. CPU тратит время на подготовку команды (запись в command buffer, валидация state'а), драйвер делает context switch между объектами. На тысяче объектов оверхед накапливается до нескольких миллисекунд CPU-side. На мобиле — катастрофически больше.

Современные API (Vulkan, DX12, Metal) с этим борются за счёт command lists и batching на стороне драйвера. И Unity вытаскивает что может через dynamic / static batching. Но если разработчик ничего сам не делает — это работает до сотен объектов, не тысяч. Чтобы перейти к тысячам, нужно явно использовать instancing.

GPU instancing: один меш, тысяча матриц

Идея в одну строку — если у всех юнитов один меш и один материал, GPU умеет нарисовать их все одной командой. Драйвер получает: «вот меш, вот массив матриц длиной тысяча — нарисуй». Один draw call, тысяча инстансов.

Per-instance данные (позиция, ориентация, цвет, индекс анимации) пакуются в отдельный буфер, шейдер читает их по SV_InstanceID (в DX) или gl_InstanceID (в GL/Vulkan). CPU-оверхед сжимается до константы, GPU прекрасно параллелит — это и есть то, для чего GPU вообще нужны.

Главное условие — общий меш и общий материал. Если у каждого юнита уникальная сетка — instancing не сработает напрямую. Лечится тремя способами. Первый — объединение нескольких разных мешей в один атлас. Второй — texture array плюс per-instance индекс текстуры, и тогда визуальные различия достигаются через разные текстуры на одной геометрии. Третий — MaterialPropertyBlock или structured buffer с дескрипторами, который позволяет передать в шейдер дополнительные параметры на каждый инстанс.

Unity: конкретные API

• Graphics.DrawMeshInstanced(mesh, submesh, material, matrices) — старое API, по-прежнему рабочее. Синхронный вызов в Update(). Передаёт массив матриц (до 1023 за вызов) прямо в драйвер. Простое решение для случая «нарисовать N одинаковых кубиков».
• Graphics.RenderMeshInstanced (Unity 2022.1+) — современный API с явным RenderParams, поддержкой URP/HDRP и batching без ограничения в 1023 инстанса.
• Graphics.DrawMeshInstancedIndirect — для случая, когда количество инстансов и сами матрицы лежат в GPU buffer'е, и CPU вообще не знает, сколько юнитов на экране. Это нужно, когда симуляция целиком на GPU — об этом дальше.
• GPU Instancing checkbox на материале — обязательно. Без галочки шейдер не сгенерит instanced-вариант, и API будет работать в один draw call на инстанс.
• DOTS / Entities Graphics / BatchRendererGroup — современный рекомендованный путь Unity для тысяч уникальных по данным юнитов. Каждый агент — Entity, его трансформации читает BatchRendererGroup, который батчит их по материалам. Документация — docs.unity3d.com/Manual/batch-renderer-group.html. Тяжёлая инженерия с переездом игры на ECS, но даёт лучшие цифры в Unity-мире.

Compute shaders: симуляция целиком на GPU

Логичное расширение мысли — если рендер мы делаем на GPU одной командой, может, и симуляцию туда же?

Позиции и скорости юнитов лежат в StructuredBuffer<float4> на GPU. На каждом тике запускается compute shader, который для каждого юнита считает соседей, применяет boids-правила, обновляет позиции. Рендер — через DrawMeshInstancedIndirect, который читает позиции из того же buffer'а. CPU вообще не касается данных юнитов между фреймами.

На современных дискретных GPU прекрасно тянутся десятки тысяч агентов в реальном времени. Это уже не «сотня» и не «тысяча» — это совсем другой порядок.

Spatial hash на GPU становится отдельным навыком. Простого аналога Dictionary<Vector2Int, List<Boid>> на compute нет: сетка строится через atomic-операции (atomic add на счётчик клетки) и параллельный prefix sum для упаковки в плоский массив. Это, безусловно, сложнее, чем CPU-вариант из Части 3. Туториалов с открытым кодом достаточно — например, Sebastian Lague, Coding Adventure: Boids на YouTube, реализация с нуля на compute. Дебажить шейдеры, кстати, тоже отдельная боль — нужны PIX или RenderDoc, потому что обычный отладчик в коде шейдера не работает.

VFX Graph и Niagara: готовый instrument

Если писать compute самим не хочется, в Unity есть VFX Graph, в Unreal — Niagara. Это node-based редакторы для систем частиц и эффектов. Под капотом у них сидит ровно та же конструкция, что я только что описал — симуляция на GPU плюс DrawMeshInstancedIndirect для рендера. Просто без необходимости писать .compute файлы руками.

Тянут десятки тысяч частиц или агентов без боли. Для боидов, стай рыб, листьев, искр — рабочий инструмент.

Минус — VFX Graph и Niagara это системы для VFX, не для AI. Если ваши юниты должны участвовать в игровой логике — стрелять, наносить урон, иметь HP, реагировать на event'ы — придётся прокидывать мост между VFX-симуляцией на GPU и игровой логикой на CPU. Этот мост — отдельная инженерия: либо readback буферов (медленно), либо ECS-промежуточный слой (сложно).

AAA: GPU-driven rendering

Самые большие массовки в AAA-играх рендерятся через GPU-driven pipelines. Вся сцена кодируется в GPU buffer'ах, GPU сам генерит команды отрисовки через ExecuteIndirect в DX12 или vkCmdDrawIndirectCount в Vulkan. CPU почти не участвует в render loop, его время тратится на гейм-логику и подготовку данных, а не на render API.

Из публичных материалов на эту тему — доклады Sebastian Aaltonen и Ulrich Haar, разбросанные по SIGGRAPH advances in real-time rendering и GDC за последние лет восемь. Если копать рендер тысячи юнитов в AAA-формате — копать туда. Конкретные URL'ы должны быть в advances.realtimerendering.com.

Для инди и mid-tier Graphics.RenderMeshInstanced или DOTS Entities Graphics закрывают 95% случаев. GPU-driven pipeline — это уже про тысячи типов объектов и десятки тысяч инстансов одновременно. В большинстве задач он не нужен.

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

GPU instancing — это не «бесплатно сделать тысячу юнитов». У каждого подхода свои ограничения. Instancing требует общего меша. Compute требует переноса симуляции на GPU. DOTS требует переписывания игры под ECS. VFX Graph требует моста до игровой логики.

В Big finale из Части 7 рендер — это обычные вызовы canvas 2D API (ctx.fillRect, ctx.arc), и GPU instancing там не демонстрируется в принципе — 2D canvas работает совсем по другой схеме, никакого батчинга инстансов в нём нет. Честный интерактив про GPU instancing потребовал бы WebGL2 с собственным шейдером и буфером инстансов, а в идеале — ещё и Unity / Unreal проект рядом для сравнения. В этой статье я сознательно остался на 2D, чтобы все интерактивы открывались на любом телефоне без оговорок про драйверы и поддержку WebGL2.

Если хотите вживую увидеть GPU instancing — посмотрите Sebastian Lague на YouTube или откройте Unity HDRP / URP Sample проект с VFX Graph. В формате веб-интерактива в браузере я это буду делать очень долго, и по моему опыту написания статей бессмысленно.

Что это меняет для архитектуры

На уровне статьи симуляция из Частей 1–5 плюс рендер из Части 6 — это полная end-to-end архитектура, которая тянет тысячи юнитов от поведения до пикселя на экране. На уровне студии эти два слоя обычно ведут разные люди: AI-программисты отвечают за boids, ORCA и навигацию, графика и тех-арт — за шейдеры и rendering pipeline. Связка между ними чисто инженерная — общий буфер данных (StructuredBuffer / ComputeBuffer), куда симуляция пишет позиции и состояния, а рендер их читает.

Это, по сути, то место, где у статьи кончаются «формулы для индивидуального юнита» и начинается «как это собрать в один pipeline». Дальше — командная работа и проектные решения, которые универсально пересказать в туториале невозможно.

У нас есть симуляция и есть рендер. Теперь — посмотрим, что лежит под капотом конкретных шипнутых игр.

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

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

Assassin's Creed Unity (Ubisoft Montreal, 2014)

Что точно известно. На GDC 2015 был доклад от Ubisoft про массовку в AC Unity — «Massive Crowd on Assassin's Creed Unity: AI Recycling» (материалы доступны на gdcvault.com, доклад от команды AC Unity). Содержание: в Париже эпохи Революции на сцене одновременно до десяти тысяч NPC, для этого используется агрессивный LOD AI с recycling — NPC «переиспользуются», выгружаются за камерой, появляются заново в зоне видимости. Behavior tree у близких NPC полноценный, у дальних — упрощённые статистические правила, иногда вообще без индивидуальной симуляции, просто скриптовая толпа-биллборд.

Что разумная догадка. Локальное движение в толпе — на основе локальных правил с avoidance. Используется что-то близкое к ORCA-подобному avoidance — но я это утверждать как факт не буду, потому что точные параметры (cellSize spatial hash, форма avoidance, пороги LOD) в публичный доклад не вошли.

Days Gone (Bend Studio, 2019)

Что точно известно. На GDC и в более ранних интервью разработчики Bend описывали систему орды Freakers. Орда — это до пятисот индивидуально симулируемых зомби в кадре, и главная инженерная задача — заставить их плавно двигаться по 3D-локациям без застревания. Использовался AI Director, управляющий «настроением» орды (агрессия, голод, паника), и локальные правила движения с avoidance.

Что разумная догадка. Точная конструкция avoidance внутри орды публично не описана детально. Учитывая ландшафтную сложность открытого мира с холмами, машинами и заборами, там почти наверняка комбинация flow fields для глобального движения и какой-то локальный avoidance — но конкретная реализация (ORCA-вариант, своя система, или гибрид) — это моя догадка.

World War Z (Saber Interactive, 2019)

Что точно известно. Saber Interactive публично представляли свой «Swarm Engine» в нескольких интервью и пресс-материалах. Заявленная фишка — поддержка тысяч зомби в кадре, при этом зомби текут по уровню как жидкость, обтекают укрытия и сжимаются в дверных проёмах. Это позиционировано как ключевая технология, отличающая игру от других кооп-шутеров про зомби.

Что разумная догадка. Поведение визуально совместимо с комбинацией boids плюс flow fields плюс ORCA-подобный avoidance. Какие конкретно структуры данных и LOD используются — публично не раскрыто.

They Are Billions (Numantian Games, 2017–2019)

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

Что разумная догадка. Для такого количества юнитов почти наверняка используется uniform grid или близкая структура для поиска соседей. Avoidance — упрощённый, вероятно без полноценной ORCA для каждого юнита: на десятках тысяч ORCA даст серьёзный CPU-бюджет, и более простые эвристики там практичнее.

Vermintide 2 (Fatshark, 2018)

Что точно известно. Fatshark на GDC и в интервью описывали, что орды крыс — Skaven Slaves — это до 60–80 одновременных AI, и каждый получает упрощённую версию полноценного combat AI игры. Поведение в орде — гибрид seek (к игроку), boids-подобной локальной координации между крысами и avoidance относительно героев.

Что разумная догадка. Конкретный вариант avoidance в Vermintide публично не раскрыт детально. Видно, что крысы умеют обтекать героев в плотных столкновениях, но это может быть как ORCA-подобный механизм, так и более простая эвристика.

RTS обобщённо: StarCraft 2, Supreme Commander, Planetary Annihilation

Что точно известно. В современных RTS повсеместно используется flow fields для глобальной навигации больших отрядов. Это покрыто в публичных GDC-докладах — Elijah Emerson по Supreme Commander 2, Mike Lewis по Planetary Annihilation. Flow fields для тысяч юнитов — стандартное индустриальное решение. Локальный avoidance — отдельная подсистема поверх flow fields.

Что разумная догадка. Что в конкретном тайтле avoidance — это именно ORCA, я утверждать не буду. У каждой студии свой набор оптимизаций, и в RTS часто используются упрощённые эвристики, которые быстрее ORCA, но дают похожий визуальный результат на средних плотностях.

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

Архитектурный паттерн один и тот же: глобальная навигация (flow fields или навмеш), плюс поиск соседей (spatial hash или эквивалент), плюс локальные правила движения (boids-family), плюс локальный avoidance (ORCA-family или эвристика), плюс LOD AI (упрощения для дальних и невидимых агентов).

Конкретные реализации у каждой студии свои, и полную схему симуляции толпы никто наружу не выкладывает — это инженерное ноу-хау, в которое вложены человеко-годы и которым одна студия отличается от другой. И мы как разработчики получаем из этого важный вывод: тот же базовый набор кирпичей, который мы разобрали в Частях 1–5 этой статьи, реально лежит под капотом игр с массовкой. С нюансами, упрощениями и LOD'ом — но это не магия и не закрытое искусство. Это то, что вы сами можете собрать.

Интерактив 6: Big finale

И финал. До тысячи юнитов на сцене одновременно. Цель — позиция курсора (или последний touch на мобиле). Все три слайдера весов из Части 2. Слайдер cellSize из Части 3. Тогл [spatial hash] — попробуйте выключить и посмотреть, как FPS уезжает. Тогл [ORCA] — выключите и посмотрите, как в плотных группах появляются залипания. Кнопка drop obstacles — раскидывает по сцене тридцать препятствий, через них толпа обтекает (avoidance из Части 5).

Это, собственно, «статья на одном экране». Все концепции работают одновременно, и можно крутить и смотреть.

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

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

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

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

Реальные ссылки — только то, что я могу подтвердить URL'ом или DOI.

• Reynolds, C. W. (1987). Flocks, herds and schools: A distributed behavioral model. SIGGRAPH '87, Computer Graphics 21(4):25–34. Каноническая статья о boids. Доступна на сайте автора — red3d.com/cwr/papers/1987/boids.html.
• Reynolds, C. W. (1999). Steering Behaviors for Autonomous Characters. GDC 1999. Опорный материал по steering behaviors — red3d.com/cwr/steer/.
• Ballerini et al. (2008). Interaction ruling animal collective behavior depends on topological rather than metric distance. PNAS 105(4):1232–1237. Топологические соседи у скворцов. DOI 10.1073/pnas.0711437105.
• Fiorini, P., Shiller, Z. (1998). Motion planning in dynamic environments using velocity obstacles. IJRR 17(7):760–772. Первый VO.
• van den Berg, J., Lin, M., Manocha, D. (2008). Reciprocal Velocity Obstacles for real-time multi-agent navigation. ICRA 2008.
• van den Berg, J., Guy, S. J., Lin, M., Manocha, D. (2011). Reciprocal n-body collision avoidance. Robotics Research, Springer Tracts in Advanced Robotics 70:3–19. ORCA. Также страница библиотеки — gamma.cs.unc.edu/RVO2/.
• Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., Gross, M. (2003). Optimized Spatial Hashing for Collision Detection of Deformable Objects. VMV 2003. Spatial hashing для collision detection.
• Mikko Mononen, recastnavigation. Open-source библиотека Recast/Detour с реализацией Crowd на ORCA-подобной модели. Репозиторий — github.com/recastnavigation/recastnavigation.
• Coding Train (Daniel Shiffman), Nature of Code, глава 5 «Autonomous Agents». Доступно бесплатно как HTML-книга. Лучший пошаговый туториал по boids и steering на p5.js для самостоятельной игры.
• Sebastian Lague, Coding Adventure: Boids на YouTube. Боиды на compute shader, реализация с нуля. Лучший публичный туториал по GPU-стороне.

Что осталось за скобками

• Flow fields для глобальной навигации. Тема большая, заслуживает отдельной статьи. Реальная архитектура crowd-симуляции в современных RTS — это не один слой, а сэндвич из flow fields плюс локальных правил плюс ORCA плюс LOD AI. Я разобрал верхние слои; нижний слой — материал для следующего раза.
• Compute shaders для симуляции boids на GPU. В Части 6 идея и API на уровне «что и зачем», но пошаговый туториал — материал отдельной статьи. Spatial hash на GPU через atomic plus prefix sum, indirect dispatch для динамического числа агентов, дебаг compute через PIX или RenderDoc — всё это отдельные большие темы.
• GPU-driven rendering в AAA. ExecuteIndirect, GPU culling, instanced rendering на уровне всей сцены — это уже инженерия рендера, не симуляции. Доклады Aaltonen и Haar на SIGGRAPH advances — туда копать дальше.
• LOD AI на массовке AAA-уровня. Recycling агентов, статистические марионетки вместо полноценной симуляции на дальних дистанциях, инстансинг анимации для тысяч NPC одновременно — это уже инженерия рендера и анимации, не симуляции движения.
• ML и RL для координации. Активная research-тема (DeepMind, OpenAI, академия). В продакшне игр в 2025–2026 пока почти не используется — это будущее, не настоящее.
• Толпа как геймплейный механизм. Hitman, где толпа — это укрытие. Watch Dogs, где толпа — это интерактивный объект. Sense-of-place в open world. Это уже геймдизайн, не симуляция, и заслуживает отдельного разговора.

Заключение

Надеюсь, статья была полезна. Шесть интерактивов, семь разделов, и базовый набор кирпичей, на которых стоит вся современная индустриальная симуляция толпы. Этого достаточно, чтобы собрать что-то рабочее в своём проекте и понимать, что лежит под капотом чужих.

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

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