Стаи и толпы в играх: как программируют реалистичное стайное поведение

В видеоиграх при создании реально больших скоплений существ или NPC нельзя просто запрограммировать логику поведения одного из них, а потом напичкать локацию его клонами. Игра захлебнётся тормозами, пытаясь провести вычисления для каждого. Поэтому разработчикам приходится идти на определённые хитрости, которые позволяют повысить производительность, но при этом выдают максимально естественный результат. Рассмотрим, как они добиваются этого.

Истоки симуляции стайного поведения

В фильме Тима Бёртона «Бэтмен возвращается» была сцена, в которой на жителей Готэма напала стая летучих мышей, а также сцена с марширующими пингвинами. Их воплотили на экране при помощи компьютерной графики, а вот за естественность стайного поведения отвечал алгоритм, разработанный экспертом по компьютерной графике Крейгом Рейнольдсом — он известен также тем, что приложил руку к фильму «Трон». Алгоритм этот называется Boids.

Крейг Рейнольдс не был самым первым человеком, который попытался создать симуляцию поведения групп существ. Но именно его алгоритм Boids сейчас считается основой, на которой многие разработчики игр создают симуляции стайного поведения в своих проектах.

В тот момент Крейг Рейнольдс работал в Symbolics Graphics Division, которая делала графический софт, использовавшийся при создании фильмов.

Софт, созданный компанией, использовался в таких фильмах, как «Звёздный Путь 3: В поисках Спока» и «Освободите Вилли». В 1987 году Symbolics Graphics Division выпустила трёхминутный мультфильм Stanley and Stella in: Breaking the Ice, в котором впервые был продемонстрирован алгоритм Boids в действии.Сюжет у мультфильма простенький. По космосу летает сфера, разделённая льдом на две половинки. Внизу — вода, и там плавают косяки рыб. Вверху — воздух, и там летают стаи птиц. Однажды птица Стэнли влюбляется в рыбку Стеллу и в пикирующем полёте пробивает клювом лёд, разделяющий их миры. Благодаря этому птицы и рыбы теперь парят в сфере вместе.

И стаи птиц, и косяки рыб в мультфильме вели себя так, как вели бы большие скопления рыб и птиц в реальном мире. Его показали на SIGGRAPH’87 — ежегодной конференции, посвящённой компьютерной графике. Там же Крейг Рейнольдс представил доклад, в котором подробно описал, как ему удалось с помощью нулей и единиц достоверно воспроизвести то, на что у эволюции ушли миллионы лет.

Если вкратце, то каждый боид в группе следует трём простым правилам:

1. Separation (Разделение): боид должен избегать столкновений с соседями по стае.

2. Alignment (Выравнивание): боид должен корректировать своё направление, чтобы оно совпадало с направлением ближайших соседей.

3. Cohesion (Сплочённость): боид должен двигаться в позиции, которую можно назвать средней позицией между позициями ближайших соседей, то есть он должен держаться товарищей.

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

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

Для взаимодействия с соседями у каждого боида есть два параметра. Во-первых, это радиус, на котором он ищет ближайшие боиды. Во-вторых, это угол обзора: боиду необязательно следить за всеми товарищами. Достаточно смотреть за теми, которые находятся перед ним. Если группа рассекается какой-то преградой на половинки, то большой радиус поиска товарищей позволит ей вновь соединиться. А маленький радиус в этом случае приведёт к распаду большой стаи на две маленьких. Также большой радиус защитит от ситуации, когда боиды отсоединяются от группы, потеряв из вида товарища, через которого они к ней и присоединились.

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

Радиус поиска и угол обзора боида можно делать разными для каждого из трёх правил, таким образом получив необходимый вид построения. Чтобы продемонстрировать это, мы взяли готовый проект для Unity от блогера SuboptimalEng, который как раз и построен на алгоритме Boids. В процессе работы программы мы постоянно изменяли радиус для Separation, Alignment и Cohesion, и боиды сразу меняли своё построение в зависимости от новых условий. То летали хаотично, игнорируя друг друга, то вдруг собирались в небольшие группки, то выстраивались в длинную цепочку или разлетались в стороны, снова забыв друг о друге.

Модификаций для алгоритма Boids можно создать бессчётное множество, тут всё зависит от потребностей разработчика и его фантазии. Делает он декорацию с симуляцией поведения животных вдалеке или систему для передвижения войск в стратегии в реальном времени? Использует алгоритм в двухмерном или в трёхмерном пространстве? Стаи просто передвигаются по определённой области или выполняют какую-то ещё функцию, например нападают на игрока?

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

Half-Life

Увидеть реализацию алгоритма, разработанного Крейгом Рейнольдсом, можно, например, в самой первой Half-Life 1998 года — в финальной сцене, в которой G-Man рассказывает Гордону Фримену о карьерных перспективах на новом рабочем месте. Действие происходило в мире Зен, и, если помните, позади G-Man’а в этот момент летала стайка существ, похожих на птиц. Стайка как раз использовала алгоритм Boids. Что забавно, в файлах игры модели этих птичек так и назывались — Boid.

Автор ютуб-канала MarphitimusBlackimus подробно разобрал, как работали эти птички. Их правдоподобное поведение было одной из технологических фишек, продемонстрированных ещё в ранней версии игры, Half-Life Alpha. При активации птицы выбирали себе лидера и следовали за ним.

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

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

К сожалению, в игре эти существа встречаются лишь раз, когда у игрока нет возможности взаимодействовать с ними. Они играют только роль декорации. Но благодаря тому, что двигаются они как захотят, а не по заранее прописанному маршруту, каждый игрок, прошедший Half-Life, видел свою уникальную и неповторимую версию полёта птичек позади G-Man’а.

Assassin’s Creed Unity

Впечатляющая работа с поведением уличной толпы была проделана разработчиками Assassin’s Creed Unity. В один момент времени игра может показать на экране лишь 120 NPC с детализированными моделями и анимацией. При этом проработанный искусственный интеллект будет лишь у 40 из них. Несмотря на эти ограничения, в некоторых сценах можно увидеть до 10 тысяч NPC, которые издалека выглядят и ведут себя так, будто у них проработанный ИИ и подробная модель.

В самой первой игре серии было ограничение в 100 NPC. Сюда входят вообще все люди, которых вы видите на улице, включая стражников и персонажей, необходимых для геймплея. Простых горожан-статистов, которые идут по улице, выполняя декоративную функцию, можно было сделать максимум 20. Их пришлось размазывать по уровню, чтобы улицы не казались пустыми. Поэтому рядом с главным героем всегда находится максимум четыре NPC. Улицы с настоящей толпой в игре тоже встречаются, но лишь в определённых миссиях, где разработчики могли сосредоточить все ресурсы на её реализации.

В Assassin’s Creed 3 разработчики внедрили технологию, позволявшую показывать на экране тысячи дешёвых мешей (низкополигональных 3D-моделей) с простой анимацией. Её использовали для крыс, птиц, крабов и для изображения многотысячной армии в битве при Банкер-Хилле. Но солдаты, из которых эта армия состоит, разве что проигрывают простые анимации — пригнуться, перезарядить оружие… Игрок не может с ними взаимодействовать.

Эту технологию использования упрощённых моделей доработали в Assassin’s Creed Unity, рассказывающей о Великой французской революции. Разработчики создали систему Bulk (английское слово, имеющее несколько значений, включая «объём», «масса»). Как в алгоритме Крейга Рейнольдса Boids каждое отдельное существо стаи называлось Boid, так и в системе Bulk каждого отдельного NPC разработчики называют… Bulk.

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

Если расстояние до NPC больше 40 метров, то игрок видит персонажа из 2000 полигонов, у которого всего 11 костей для анимации и простейшая система реакции на события. На расстоянии от 40 до 12 метров вместо упрощённой версии горожанина появляется NPC с полноценной моделью, но урезанной системой поведения, простыми системами анимации и проверки столкновений с окружающими объектами. А если до NPC меньше 12 метров, то он заменяется на объект с детализированной моделью из 20 000 полигонов с 300 костей для анимации и искусственным интеллектом, реалистично реагирующим на действия игрока.

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

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

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

A Plague Tale: Innocence

Главной фишкой A Plague Tale: Innocence стали полчища крыс. С их помощью разработчики из Asobo Studio хотели показать последствия чумы во Франции времён Столетней войны.

В качестве референса разработчики использовали документальные кадры о вторжении полчищ мышей и крыс на австралийские фермы, которых полно на YouTube. Правда, если вы сравните, как крысы двигаются в игре и на документальных записях, то заметите, что игровые грызуны не так проворны. Разработчики специально замедлили их, иначе от крыс было бы невозможно убежать.

Ещё на раннем этапе разработки в студии решили, что на экране одновременно будет бегать до 5000 особей (в сиквеле A Plague Tale: Requiem их уже около 300 000). При этом все крысы должны вести себя по-разному. Одна преследует игрока, другая бросается на стражников. Какая-то спасается от яркого света. Ещё одна просто бродит вдалеке в поисках еды.

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

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

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

Команда решила сделать наоборот. Не крысы вычисляют, как им дойти до цели, а, условно говоря, цель определяет, по каким маршрутам крысы могут к ней попасть. Игра строит что-то вроде конвейерных лент, которые из любой точки уровня ведут прямо к персонажу, и крысы просто бегут по созданным для них маршрутам, подключаясь к ближайшему. Когда цель перемещается в пространстве, маршруты для крыс просчитываются заново. Подобная механика называется flow field pathfinding.

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

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

Команда предусмотрела и ситуацию, при которой игрок с помощью факела загоняет толпу крыс в угол. Грызуны, которым больше некуда отступать, просто магическим образом исчезают, оставляя вместо себя искры. Это своеобразный костыль, чтобы перехитрить игроков, которые станут гонять крыс факелом по уровню, пытаясь «сломать» их.

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

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

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

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

Hitman: Absolution

В Hitman: Blood Money полноценную толпу пешеходов можно увидеть на уровне The Murder of Crows, где на улицах Нового Орлеана происходит парад. По большей части это — декорация. Например, в толпе нельзя спрятаться от преследователей. Людей из толпы нельзя ни скрытно убивать, ни использовать в качестве живого щита. А если 47-й начинает стрельбу, пешеходы сначала синхронно расходятся в стороны, прикрывая голову руками, а через несколько секунд забывают обо всём и снова ходят по улице как ни в чём не бывало.

В следующей игре серии, Hitman: Absolution, поведение толпы значительно доработали. Теперь вы можете использовать пешеходов как живой щит, а если будете спокойно стоять в толпе, то противник вас не заметит. Ну а перестрелка или взрыв приведут к более реалистичному поведению NPC: они запаникуют и убегут к ближайшему выходу.

Толпа в Hitman: Absolution может состоять из 1200 NPC с возможностью показать на экране 500 из них. Все NPC перемещаются по локации по навигационному мешу по такому же принципу, как в A Plague Tale: Innocence: пол, по которому ходят NPC, покрыт сеткой из клеток, и каждая из них хранит информацию, которую NPC использует при движении. Например, можно ли на эту клетку встать и кто на ней уже стоит.

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

Поведение каждого NPC в толпе работает по принципу машины состояний (state machine). В зависимости от ситуации и окружения ИИ выбирает одно из состояний — например, стоять, ждать, идти, насторожиться, испугаться или умереть.

В состоянии «ждать» пешеход проверяет пространство вокруг себя на преграды вроде стен и других пешеходов и ждёт, пока в одном из направлений не освободится дорога, после чего меняет состояние на «идти». Уже в этом состоянии NPC просто ходит по окрестностям, используя алгоритм блуждания (wander steering behavior), разработанный упомянутым в начале материала Крейгом Рейнольдсом.

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

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

В случае паники NPC находит кратчайший путь до выхода из локации. Путь генерируется автоматически при помощи сетки и клеток, обозначающих выход, о которых говорилось выше. Если в какой-то момент другие NPC перегородили дорогу, то убегающий пешеход переключается на соседний маршрут, ведущий к другой ближайшей клетке выхода. Отметим, что клеток выхода на уровне несколько и готовые маршруты к ним, которые используют NPC, вычисляются при помощи модифицированного алгоритма Дейкстры. Он как раз и помогает находить кратчайшие пути между несколькими соединёнными между собой точками.

Left 4 Dead

Толпы живых мертвецов, гоняющиеся за игроками в Left 4 Dead, произошли от ботов Counter-Strike: Source. Программист Майк Бут рассказывал, что, тестируя последних, команда однажды заметила, что отбиваться автоматами от 30 ботов, вооружённых только ножами, крайне весело. Поэтому, как только Counter-Strike: Source вышла, Valve сразу принялась экспериментировать с этой идеей. Разумеется, для новой игры о зомби-апокалипсисе поведение ботов пришлось переработать.

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

Все уровни в Left 4 Dead линейные. Но на каждом из них есть множество помещений и закутков, необходимых для спауна живых мертвецов, чтобы им было откуда внезапно выбежать толпой, застав игроков врасплох. В этих ответвлениях разработчики разместили случайно появляющиеся аптечки, бомбы, оружие и бутылки с зажигательной смесью, чтобы поощрять игроков за стремление изучить локацию.

При разработке команда столкнулась с ограничением на объём данных, которые сервер должен отправлять каждому из игроков. В многопользовательских играх вроде Counter-Strike достаточно передать информацию только о других игроках, их оружии и о том, куда летят их пули. Но в Left 4 Dead также надо обновлять данные о поведении каждого из десятков мертвецов.

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

В Left 4 Dead ограниченный набор локаций. Реиграбельность обеспечивает ИИ-режиссёр, который всякий раз наполняет уровень мертвецами по-разному, в зависимости от навыков игроков (хотя позже один из разработчиков уверял, что никакого ИИ-режиссёра не существует, а вместо него просто генератор случайных чисел).

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

Days Gone

Days Gone, ещё одна игра о мире, пережившем зомби-апокалипсис, разрабатывалась с оглядкой на фильм «Война миров Z». Авторы хотели повторить толпы заражённых, которые гонялись за персонажем Брэда Питта. Эффекта зомби-цунами они не сделали, но вполне правдоподобно изобразили большие скопления фрикеров, или, как их ещё называют, фриков, — людей, под действием вируса мутировавших в монстров (фрикерами также могут быть и животные, но далее речь пойдёт только про людей).

Численность одной стаи может составлять до 500 особей, причём разработчики не просто расставили их по определённым локациям. Каждая стая проживает день согласно своим потребностям.

Но была проблема: как создать иллюзию, будто толпа в 500 особей не состоит из близнецов? У команды было всего восемь уникальных моделей, поэтому игроки очень быстро заметили бы противников, как две капли воды похожих друг на друга. Чтобы внести разнообразие, разработчики немного изменили размер некоторых фрикеров в толпе — это повлияло и на их движения.

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

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

Subnautica

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

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

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

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

* * *

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

В некоторых случаях, как в Subnautica, можно обойтись и простым генератором частиц. Но в примерах вроде Assassin’s Creed Unity, Left 4 Dead или Hitman: Absolution, где толпа — это отдельная игровая механика, подобным хитростям места не найдётся. Придётся придумывать свои или использовать те наработки, уже имеющиеся в игровой индустрии, — например, алгоритм Boids Крейга Рейнольдса, созданный ещё в 1980-х, который в том или ином виде до сих пор встречается в играх и кино.