Толпа без AI: сотни юнитов на трёх правилах

По голосованию победитель очевиден. Так что начнём. У парижан в Assassin's Creed Unity нет интеллекта. У каждого крысака в Vermintide и зомби из World War Z — тоже. Когда в кадре одновременно сотни персонажей, если бы у каждого крутилось полноценное behavior tree, FPS умер бы.

Так что там — не AI, а несколько локальных правил: «не наступай на ноги соседям», «иди примерно туда же, куда соседи», «не отставай». Собственно, это и есть толпа в играх — эмерджентность. Крейг Рейнольдс описал это в 1986 году и назвал boids.

Дальше начинается инженерия. Days Gone крутит орду из сотен Freakers. World War Z — Swarm Engine с зомби, текущими по уровню как жидкость. Под капотом везде одно и то же: boids, spatial hashing, ORCA, плюс LOD AI на дальних юнитах.

На неделе разберём: три формулы Рейнольдса, почему наивная реализация умирает на 500 юнитах, как ORCA не даёт юнитам сталкиваться в узких местах. 🔥

#мат_геймдев #МатРазбор #AI #algorithms

Boids: три правила стаи

Когда вы смотрите на стаю скворцов на закате, кажется, что это один организм с общей волей. На самом деле там нет лидера: каждая птица следит примерно за семью ближайшими соседями — независимо от того, как далеко они оказались. Это измерили Ballerini и соавторы в 2008 году по стереосъёмкам стай над Римом (PNAS).

Сам алгоритм старше. Крейг Рейнольдс собрал три правила ещё в 1987-м (SIGGRAPH '87). Само слово boids — от bird-oid object:

— separation — отталкивайся от того, кто оказался слишком близко.
— alignment — подстраивай свою скорость под среднюю скорость соседей.
— cohesion — тянись к их центру масс.

Собственно, в Unity это делается так:

Vector3 sep = Vector3.zero, ali = Vector3.zero, coh = Vector3.zero;
int count = neighbors.Count;

foreach (var other in neighbors) {
  Vector3 d = transform.position - other.position;
  if (d.sqrMagnitude < sepRadius * sepRadius) sep += d.normalized;
  ali += other.velocity;
  coh += other.position;
}

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

Магия — в балансе весов. Большой wSep — юниты разлетаются в пыль. Большой wCoh — слипаются в шарик и стоят. Всё интересное — где-то между.

В играх это стаи в Subnautica, орда Freakers в Days Gone, Swarm Engine в World War Z. Конечно же, в боевой реализации есть ещё seek к цели и avoidance препятствий — но базовая стая держится на этих трёх правилах. 🔥

#мат_геймдев #МатРазбор #AI #biomimicry

Толпа без AI: как три правила, хеш-сетка и ORCA делают массовку живой
https://dev-math.ru/articles/crowd/

Вы просили про толпу. Ну держитесь 🙂 Семь разделов, шесть интерактивов и тысяча юнитов в одном экране браузера. Я заморочился — получилось так объёмно, что статьи скоро можно сшивать в книжку (Поэтому немного задержался. Хотел в пятницу, а получилось в субботу). Жду огоньков и репостов друзьям 🔥

Симуляция массовки упирается в две проблемы: общий behavior tree «толпа делает X» не масштабируется, а наивный поиск соседей даёт O(N²) и кладёт сцену уже на пятистах юнитах. В статье разбираю архитектуру по слоям: три правила Рейнольдса для группового движения, uniform spatial hash для поиска соседей за O(N), упрощённый ORCA для встречных потоков в коридоре, steering behaviors для целей и обхода препятствий, плюс отдельная часть про GPU instancing для рендера тысячи юнитов одним draw call'ом. В финале — разбор под капотом AC Unity, World War Z, They Are Billions, Vermintide 2 и RTS-обобщённо.

#мат_геймдев #МатРазбор #algorithms #AI

Flow fields: один расчёт вместо тысячи A*

Тысяча юнитов идёт к одной точке. Если для каждого считать A* — тысяча независимых поисков за кадр. Дороговато.

Как нам сделать меньше расчётов? По своей сути, идея проста. Можно сделать один расчёт вместо тысячи. Посчитали поле — все юниты просто читают из него «куда идти из своей клетки».

Разбиваем карту на сетку. От цели обратной волной (Dijkstra) в каждой клетке считаем дистанцию до цели и записываем вектор на соседа — это и есть flow field. Юниту достаточно прочитать вектор из своей клетки. O(1) на запрос, без зависимости от длины пути и количества юнитов.

«А если цель движется?» В RTS — почти никогда. Клик в точку, поход к зданию — цель статична, поле живёт минутами. При движущейся цели перерсчитать получается в любом случае не так дорого. Одну дейкстру пустить по карте не так долго, как для каждого юнита считать А*. Тем более с шумом от boids там не обязательно моментальная реакция на пользовательский ввод или триггеры.

Проблема возникает если много юнитов и у каждого своя цель — A* снова в выигрыше. Flow fields — это про движение толпы к общей цели. Канонический разбор — Elijah Emerson, AI Game Programming Wisdom 5 (2008).

#мат_геймдев #МатРазбор #algorithms #AI