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

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

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

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

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

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

И тут резонный вопрос: а нет ли там действительно общего сигнала? Может, передний скворец что-то командует? Может, есть вожак? Никакого центрального управления в стае нет. Отдельно взятая птица вообще не знает, что делает стая целиком, и не получает приказов сверху. Это и есть та самая эмерджентность: групповое поведение возникает не из общего мозга, а из локальных взаимодействий между соседями.

 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», и он прижился так, что вы его теперь встретите в любом туториале по толпе.

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

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

Ответ дала статья 2008 года — Ballerini et al., «Interaction ruling animal collective behavior depends on topological rather than metric distance» (PNAS 105(4):1232–1237). Итальянские физики и биологи поставили над римскими крышами несколько синхронизированных стереокамер, сняли реальные стаи в полёте и триангулировали 3D-координаты каждой отдельной птицы в каждом кадре. И задали один конкретный вопрос: соседи, на которых реагирует птица, — это соседи по расстоянию (метрические) или по числу (топологические)? То есть «все, кто ближе двух метров» или «семь ближайших, неважно как далеко»?

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

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

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

У рыб в косяке и у саранчи похожие модели работают, но механизм у них другой: у рыб помимо зрения есть боковая линия — орган, который ловит гидродинамическое поле от соседей в воде (этим, кстати, много занимается Iain Couzin в Принстоне). А человеческая толпа — вообще отдельная история, со своей социальной динамикой, личным пространством и тысячей других вещей. Так что boids — это про птиц и абстрактных юнитов, а не универсальная физика любой толпы.

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

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

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

Separation — «не наступай на ноги». Для каждого соседа, который оказался слишком близко, добавляем отталкивающий вектор от него к нам. Чем ближе сосед — тем сильнее. Технически это (self.pos - j.pos) / dist², или, что то же самое, normalize(self.pos - j.pos) / dist.

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

Cohesion — «не отставай». Считаем центр масс соседей и тянемся к нему: avg.pos - self.pos. Без cohesion стая не сцеплена и быстро рассыпается на пары и одиночек.

Все три правила нужно посчитать в одном проходе по соседям. 

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², просто разные записи одного вектора. Первую используют потому, что она яснее показывает смысл: «единичный вектор от соседа, поделённый на расстояние».

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

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

• Только alignment. Толпа идёт стройно, но не сцеплена. Параллельные курсы, но никто не реагирует на отставших. Похоже на парад, а не на стаю.

• Только cohesion. Толпа схлопывается в точку. Все притягиваются к центру, по дороге наступают друг другу на ноги (separation-то выключен), получается один пульсирующий шарик.

• Все три в балансе. Живая стая. Та самая, которую мы хотим.

Хорошая отправная точка по весам — равные wSep = wAli = wCoh = 1.0, при условии что все три поправки нормированы и живут в одной шкале. Дальше крутите под свою задачу.

Где это встречается в играх? Косяки рыб в Subnautica — каноническая иллюстрация почти чистых boids: видно, как стая сходится-расходится и шарахается от игрока. Птицы и прочая ambient-фауна в Far Cry и RDR2 — boids поверх spline-патрулей. Отряды в Total War — модифицированные boids поверх строевых формаций. Конечно же, ванильных boids в чистом виде там нет: поверх лежат flow fields для глобальной навигации, FSM для смены поведений, иногда отдельные солверы для тесной толпы. Но базовый слой — именно эти три правила. И если у вас в проекте «boids не работают» — в девяти случаях из десяти это либо кривые веса, либо слишком маленький радиус видимости, либо одно из правил молча отвалилось из-за бага.

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

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

Окей. Правила работают, веса крутятся, стая мутится. Посмотрим, сколько это стоит.

В каждом кадре для каждого агента нужно знать, кто его соседи, — без этого правила Рейнольдса просто не считаются. Самое наивное — пройтись по всем остальным агентам и проверить расстояние. Это O(N²) проверок на кадр.

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

Конкретные миллисекунды я приводить не буду — слишком сильно зависит от языка, движка, кэширования и десятка других вещей. Но порядок понятен: при бюджете кадра в 16.7 мс (это и есть 60 FPS) миллион простых проверок — уже заметная доля. А мы ведь хотим тысячи юнитов, а не сотни.

Идея решения простая. Если радиус видимости r — это, скажем, пятьдесят пикселей, то агент в одном углу карты физически не может видеть агента в противоположном. Проверять их пару — пустая трата. Так что разбиваем мир на регулярную сетку клеток размером cellSize × cellSize. Каждый агент попадает в свою клетку. Когда ищем соседей агента — смотрим только его клетку и восемь соседних, итого девять клеток в 2D (в 3D их двадцать семь, но идея та же).

При равномерной плотности в каждой клетке лежит фиксированное среднее число агентов — допустим, десяток. Тогда поиск соседей одного агента стоит порядка сотни проверок (девять клеток по десять) вместо девятисот девяноста девяти. При N=5000 разница уже не на порядок, а на два: сотня против пяти тысяч. И ключевое — при равномерной плотности это «среднее на клетку» от N не зависит, поэтому общая сложность падает с O(N²) до эффективного O(N).

Главная настройка тут — размер клетки. Базовое правило: cellSize = r. Если сделать клетку меньше радиуса — придётся смотреть не 3×3, а 5×5 или 7×7, иначе часть соседей потеряется, и выгода тает. Если больше — клетки «жирные», в каждую набивается слишком много кандидатов, и spatial hash вырождается обратно в brute force внутри клетки. На практике cellSize подбирают так, чтобы в клетке оказывалось 5–20 агентов. Меньше одного на клетку — структура данных съедает больше, чем экономит. Сотня на клетку — внутри переполненной клетки снова локальный O(N²).

Код на 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;}

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

В JS/TypeScript эта конструкция пишется как Map<number, Array<Boid>> и в браузере работает нормально. А вот в Unity C# тот же код в hot path ведёт себя иначе: каждый новый List, каждый новый элемент Dictionary — это GC-аллокация. На кадр их сотни, и при N > 1000 сборщик мусора начинает срабатывать раз в несколько кадров, выдавая заметные провалы FPS. Стандартный продакшн-вариант — два плоских массива фиксированного размера: cellHead[] хранит для каждой клетки индекс первого боида, next[] — для каждого боида индекс следующего в той же клетке. Интрузивный связанный список через индексы, без единого new в кадре. Кода больше, но в Unity это легко даёт пяти-десятикратный прирост за счёт нуля аллокаций и плотной упаковки в кэш.

Uniform grid хорош, когда плотность примерно равномерная. Если половина юнитов сбилась в один угол карты — почти все попадут в одну переполненную клетку, и сетка локально выродится обратно в O(N²). На такие случаи есть KD-tree, quadtree/octree и BVH (последний — скорее для статичной геометрии, чем для подвижных агентов). Но готового рецепта «копируйте KD-tree» я не дам: для подавляющего большинства задач uniform grid достаточно, и это тот случай, когда простое решение лучше. Если вы реально упёрлись в неравномерность — это уже разговор под профиль конкретной сцены.

ORCA: почему одного separation мало в узком коридоре

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

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

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

В 1998 году Paolo Fiorini и Zvi Shiller предложили смотреть на задачу иначе — «Motion planning in dynamic environments using velocity obstacles» (IJRR 17(7):760–772). Идея, на которой стоит вся последующая линия работ: рассуждать не в физическом пространстве, а в пространстве скоростей. У агента есть текущая позиция и выбираемая скорость. Для каждого соседа можно построить в пространстве скоростей множество тех скоростей, при которых столкновение случится в ближайшие t секунд, — это и есть velocity obstacle (VO). Геометрически в 2D это конус, и проверка «безопасна ли моя скорость» сводится к «лежу ли я внутри конуса» — O(1) на пару.

У наивного 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, и оно уже работает в реальном времени для десятков агентов. Кстати, именно вариант RVO-подобного локального avoidance сидит внутри Unity NavMeshAgent.

А в 2011 году та же группа (van den Berg, Guy, Lin, Manocha) опубликовала развитие — ORCA, Optimal Reciprocal Collision Avoidance (Robotics Research, Springer Tracts 70:3–19). Это то, чем пользуется значительная часть индустрии. Конструкция в три шага:

1. Для каждого соседа строится полуплоскость в пространстве скоростей, отделяющая безопасные скорости от опасных — с учётом reciprocal-сдвига.

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

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

А вот «найти ближайшую точку в выпуклом многоугольнике к заданной точке» — это задача линейного программирования (LP) с двумя переменными. Тут резонный вопрос: почему LP, а не какой-нибудь градиентный спуск? У нас всего две переменные (vx, vy) и десяток-другой линейных ограничений — по одному на соседа. LP с двумя переменными решается за O(K) (результат Megiddo, 1984) — копеечная задача, реально измеряемая в наносекундах. Градиентный спуск был бы итеративным, без гарантии оптимальности, чувствительным к шагу и склонным застревать в плохих случаях. LP детерминирован, стабилен, прозрачен и дёшев. Поэтому индустрия и выбрала именно его.

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

Recast/Detour Микко Мононена — открытый C++ де-факто стандарт, его Crowd-модуль используют Unreal, Godot и куча инди-движков.

Но есть где ORCA ломается. В сверхплотной толпе безопасное множество становится пустым, и агенты просто замирают — в проде это лечат softer-режимом и flow fields, чтобы юнит в принципе не попадал в безвыходную позицию. Против невменяемого соседа, который не играет в reciprocal (например, разъярённого игрока), ORCA даёт консервативную, «застенчивую» оценку. А на тысячах агентов 5000 LP в кадр — это уже дорого, и его срезают через LOD AI: дальние идут по boids, ближние — через ORCA.

Цель и препятствия: steering behaviors

К этому моменту у нас есть три правила, быстрый поиск соседей и avoidance встречных потоков. Чего не хватает? Цели. Чистые boids не знают, куда идти, — они умеют только двигаться согласованно с соседями. А юнитам надо идти на штурм, рыбам — плыть к корму, NPC — патрулировать маршрут.

Это закрыл сам Рейнольдс в 1999 году докладом на GDC «Steering Behaviors for Autonomous Characters». Это уже не про стаю, а про отдельных автономных персонажей и набор переиспользуемых кирпичиков поведения: seek, flee, arrive, wander, pursue, evade. Важная мысль: эти behaviors задают preferred velocity агента — а поверх неё всё так же работают boids-поправки и avoidance через ORCA. Это слой над слоем.

Скажем seek, тянуть агента к точке:

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

Желаемая скорость направлена к цели, steering — разница между желаемой и текущей. Складываете с остальными силами, ограничиваете по модулю, двигаете. Flee — это seek наоборот. Arrive — как seek, но у цели агент тормозит: желаемую скорость масштабируем по дистанции, и внутри slowingRadius она падает к нулю. Без 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, но к предсказанной будущей позиции цели, через линейное упреждение по её скорости. Тот же приём упреждения, что и для пули в шутерах, — геометрически одно и то же квадратное уравнение.

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

И ещё момент— обход препятствий. ORCA отвечает за уклонение подвижных агентов друг от друга. Стены, дома, скалы — это отдельная подсистема. Базово — рейкаст по направлению движения и перпендикулярная поправка, если впереди препятствие. Поинтереснее — представить препятствия полем расстояний (SDF): тогда «насколько я близко к ближайшей стене» — это один сэмпл из 3D-текстуры, O(1). В Unity и Unreal препятствия обычно зашиты прямо в навмеш, и для статики отдельную систему чаще писать не нужно.

Собственно, вот как все слои сшиваются — порядок на каждый кадр для каждого агента:

1. Steering даёт preferred velocity — куда я хочу (в seek-цель, по wander, в slot).

2. Boids-поправки (separation/alignment/cohesion) корректируют её векторной суммой с весами.

3. ORCA берёт скорректированную скорость и отсекает её к ближайшей безопасной точке.

4. Кэп по maxSpeed и обновление позиции.

В проде между шагами вставляют ещё фильтры: сглаживание скорости, плавный поворот с угловой скоростью вместо мгновенной смены heading’а, priority overrides (бегущий в панике агент ломает обычную логику). И, если честно, простая толпа собирается за пару часов на чистых boids, а вот «продакшн-толпа» без артефактов — это недели тонкой настройки. Тратятся эти недели, как правило, не на алгоритмы, а на крутку коэффициентов и фикс граничных случаев.

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

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

World War Z (Saber Interactive, 2019). Saber публично представляли свой Swarm Engine — заявленная фишка в том, что тысячи зомби текут по уровню как жидкость, обтекают укрытия и сжимаются в дверных проёмах. Визуально это совместимо с комбинацией boids + flow fields + ORCA-подобный avoidance, но конкретные структуры данных и LOD наружу не раскрыты.

Похожая картина и у остальных: Days Gone (Bend, 2019) симулирует орду до пятисот зомби с AI Director, управляющим её «настроением»; Vermintide 2 (Fatshark, 2018) держит 60–80 одновременных крыс, каждая с упрощённой версией боевого AI; They Are Billions (Numantian) гоняет десятки тысяч нежити на самописном движке с GPU-рендером. А в RTS — StarCraft 2, Supreme Commander, Planetary Annihilation — для глобальной навигации больших отрядов повсеместно используют flow fields (это покрыто публичными GDC-докладами), а локальный avoidance идёт отдельной подсистемой поверх.

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

Что в итоге и куда копать дальше

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

Если коротко по практике: нужна симуляция тысячи юнитов в Unity без жёстких требований по железу — берите NavMeshAgent с включённым avoidance и Job System, это закроет процентов восемьдесят случаев. Требования жёсткие или мобила — DOTS + Burst + собственный spatial hash на плоских массивах. Полноценный ORCA с нуля писать почти никогда не нужно.

Что почитать дальше:

• Reynolds, C. W. (1987). Flocks, herds and schools. 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, red3d.com/cwr/steer/.

• Ballerini et al. (2008). PNAS 105(4):1232–1237, топологические соседи у скворцов, DOI 10.1073/pnas.0711437105.

• Fiorini & Shiller (1998). IJRR 17(7):760–772, первый Velocity Obstacle.

• van den Berg et al. (2008, 2011). RVO (ICRA 2008) и ORCA (Springer Tracts 70:3–19), библиотека — gamma.cs.unc.edu/RVO2/.

• Teschner et al. (2003). Optimized Spatial Hashing, VMV 2003.

• Mikko Mononen, recastnavigation — github.com/recastnavigation/recastnavigation.

• Daniel Shiffman, Nature of Code, гл. 5 — лучший пошаговый туториал по boids и steering для самостоятельной игры. И Sebastian Lague, Coding Adventure: Boids на YouTube — лучший публичный разбор GPU-стороны.

Надеюсь, статья была полезна. Если хочется покрутить все шесть демок руками, а не смотреть на статичные кадры, — интерактивная версия со всеми интерактивами тут. А ещё у меня есть телеграм-канал «математика в геймдеве по-простому», где я разбираю такие штуки. Заходите, если интересно.

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