Процедурная генерация укрытий в играх
Дизайнер может и сделает лучше, но сколько времени он потратит?
В игровых мирах сражения, взаимодействия НПС и стратегические маневры приводят к необходимости поиска точек защиты или точек укрытия (cover). В этой статье я рассмотрю один из аспектов игровой механики — создание такой системы на основе анализа окружения, которые позволяют игрокам и AI эффективно и эффектно сражаться в разных игровых сценариях и делают игровой опыт более динамичным. Посмотрим на особенности, которые влияют на алгоритм генерации и реализацию в движке 4A Engine.
Система укрытий позволяет построить интересное поведение NPC в играх, давая им возможность укрываться за различными объектами на игровой карте. Это существенно повышает уровень реализма, а также вводит возможность использования тактических элементов, вроде наступления, обороны, окружения и других.
Обычно реализация системы укрытий (covers) состоит из двух модулей: создания укрытий и их поиска. В большинстве современных игр создание укрытий выполняется на этапе проектировки уровня (либо человеком UE4/Unity, либо автоматически как CryEngine, либо отдельными модулями как в ArenaEngine (GW2) — сильно модифицированный UE3), в то время как поиск укрытий происходит в режиме реального времени во время игры. Дизайнер при расстановке точек укрытий (каверов, covers) руководствуется собственным видением возможного применения статических объектов на уровне и окружающий геометрии, что вносит опредленную долю творчества в этот процесс.
Плюсы ручного подхода
Подходит для небольших областей вроде комнаты, этажа или здания, но необходимость применения подобной ручной расстановки на больших пространствах, приводит и к ошибкам позиционирования и банальной усталости от однотипных действий. Ситуация осложняется, если происходит изменение геометрии или расстановки объектов на уровне. Но не думайте, что статическая система укрытий плоха или устарела, наоборот — она позволяет дизайнерам зафиксировать определенные интересные решения, или подвести игрока к срежиссированным сюжетным сценам, ведь игра это театр для одного зрителя — для игрока.
Процедурная генерация
Создание алгоритма для генерации системы укрытий на первый взгляд может показаться сложной задачей, если вы видите только работу опытного левел или AI дизайнера, потому что они оценивают десятки и сотни параметров уровня и окружения на нем. Но если разбить их действия на последовательность более простых, то задача станет гораздо менее сложной. Я использую для примеров скриншоты из редактора 4A Engine, но сам алгоритм может быть реализован для любого движка, будь то Unity или Unreal Engine 4/5, потому что сами принципы алгоритма едины и отличаются только технической реализацией.
Дизайн системы укрытий
Систему укрытий можно разбить на несколько частей:
1. Генерация укрытий
2. Хранение результатов
3. Использование укрытий
Задачи генерации и использования данных сильно связаны, поэтому использование укрытий точно определяет в каких условиях они могут быть сгененерированы. Поскольку данная статья не ставит перед собой целью создавать и обновлять укрытия в рантайме, то вопросы производительсности условно можно опустить, но важно помнить про необходимость оптимизации подхода к каждой из этих задач.
В качестве отправной точки стоит рассмотреть работу левел дизайнера, который расставляет каверы на уровне. Обычно он анализирует края объектов их положение относительно других, видимость из точек стрельбы, затем прикидывает возможность определенных действий NPC в данной точке (выстрел изза угла, стельба вслепую) и в конце анализирует защищенность точки элементами окружения и статическими объектами. Простой пример, дизайнеру надо расставить каверы вокруг некоторого объекта.
Дизайнер обычно расставляет их обходя объект по (против) часовой стрелке, обращая внимание на углы и выступающие части и прикидывая возможность выстрела из этой точки. Заметно, что каверы стоят вдоль края навигационной карты, чтобы НПС мог в него добежать, они примерно перпедикулярны плоскостям, которые ограничивают объект и расставлены на некотором удалении друг от друга, чтобы не мешались. Дизайнер не поставил укрытия на открытых участках карты, потому что это не имеет смысла и анимации будут выглядеть нелепо. В общем случае неважно как мы будет делать обход, по часовой стрелке или против, важен сам принцип установки и оценки.
Так и нам для реализации следует опираться на края навигационной карты, как показательные места возможного размещения каверов. Почему именно край карты, а не равномерный опрос по всему объему? Край карты образуется там, где происходит пересечение объемов объектов (aabb или obb), внутри объема алгоритм будем выполнять заведомо провальные тесты проверки геометрии, иначе бы там не было навигационной карты.
Использование полученных результатов проверки геометрии также позволяет хранить пользовательские данные об укрытии, такие как материал (камень, сено, кирпич), высота, здоровье и так далее, с быстрым и эффективным доступом к ним, если понадобится. Так NPC могут оперативно получить информацию о каждой точке укрытия во время игры, что также ведет к снижению числа проверок геометрии вокруг (raypick, eqs) и повышает информационную насыщенность уровня для разных видов пространственного поиска.
Например как на картинке выше, можно хранить примерную открытость каждой позиции. Анализируя большое число боев QA с нпс, я заметил что только порядка 20% окружения поддается полному разрушению, т.е. 80% запросов окружения в игре всегда будет возращать одно и тоже. Это утверждение спорно для игры, где разрушаемость является кор механикой, но в остальных случаях можно сэкономить на этом, проведя расчеты в офлайне и записав полученные значения в свойства укрытия. Таким образом мы получаем еще одну часть системы укрытий, которая позволяет NPC примерно оценивать с какой стороны укрытия лучше стрелять: слева, справ, стоя или сидя.
Дополнительно ко всему сказанному можно реализовать систему активного обновления свойств укрытия в игре, которые использует эти данные, например чтобы она соответствовала степени разрушения объектам вокруг. Все это важно для эффективного и своевременного принятия решений NPC в условиях динамичного боя, и поднимает игровой ИИ еще на одну ступеньку реализма и взаимодействия с окружением.
Генерация укрытий на основе окружения
Выше я упомянул я рассказал про обход краев, он позволяет относительно дешево найти возможные места где нпс может спрятаться. Теперь, основываясь на сканирование окружающей геометрии в этих точкая, надо определить точно ли они подходят для этого. Пусть это будет некий процент перекрытия, по которому оно считается достаточным надежным, если перекрывает более 50% брошеных рейпиков).
Для этого нам потребуется создать сетку точек по двум осям, расположенным на одинаковом расстоянии друг от друга, и в каждой точке выполнить рейпик в направлении перпендикулярном краю навмеша. Это решение основано на том свойстве навмеша, что в большинстве случаем своем если точка на карте НЕ покрыта навигационными полигонами, то она занята чем-то достаточно большим, чтобы является препятствием для построения навмеша.
Чтобы не вызывать лишние проверки геометрии в каждой точке сегмента, надо сначала вообще определить подходит ли эта точка для каверов. Обычно для этого хватает выполнить два рейпика по обе стороны перпендикулярно направлению сегмента для выявления что она (красные точки) находится на открытом пространстве и такие точки мы отбрасываем сразу. И еще два рейпика на уровне середины тела человека/монстра для выявления того, что точка подходит как минимум для укрытия в присяде (зеленые точки)
Если обе эти проверки прошли, дополнительно делаем проверку точек на расстоянии вытянутых рук в т-позе, имитирую выход из укрытия для стрельбы. Можно еще проверить там же пересечение рейпика с «землей», чтобы отсечь края уступов, куда NPC придется заступить в этом случае. Также эти проверки на уровне рук в т-позе хорошо справляюся, чтобы убрать «ложные» укрытия на сломах геометрии и в углах.
После всех этих проверок, остается очень небольшое число возможных мест, которые надо подвергнуть детальному сканированию геометрии, порядок отбраковки на этом этапе составляет примерно 85–90% от всего числа точек на всех сегментах. Как видно на изображениях ниже, результаты работы такого алгоритма не зависят от поворота объекта, а лишь от наличия достаточной области защиты.
Алгоритмы подходит для любого типа геометрии, и вам больше не нужно вручную размещать каверы на уровне, освободив больше времени для творчества дизайнерам. Это конечно не освободит их от исправления ошибок алгоритма, но сделает это существенно дешевле в плане времени. Также вы наверное заметили, эти задачи очень хорошо параллелятся, позволяя на полную задействовать доступные ресурсы пк. Можно разбить на отдельные задачи как проход по сегменту навигационной карты, так и детальное сканирование геометрии в точках укрытия.
Стратегия обхода по краям, для большинства игр будет достаточной или покроет большую часть потребностей системы укрытий, просто за счет особенностей генерации навигационной карты. Остальное творческие добавит человек.
Обход краев карты
Создание каверов на обходе краев очень простое и эффективное решение, которое можно применять в большинстве случаев. В самом простом варианте можно взять три точки на сегменте, и проверить лучом перпендикулярным получившемуся направлению в обоих направлениях наличие геометрии в центре тела НПС и в голове, этого будет достаточно чтобы быстро расставить их на уровне.
Более сложным и затратным является обход всех граней навмеша, или разбиение области на равноудаленные точки и сканирование в них. По опыту реализации таких систем в Unity он немного точнее, чем обход по краям, но намного более затратный по времени, а точка на краю имеет значительный шанс получить пересечение с геометрией без ненужных просчетов.
Вторым преимуществом алгоритма обхода краев является то, что количество полигонов навигационной сетки даже на сложном объекте не превышает обычно нескольких сотен, поэтому объект может быть таким большим, как вам угодно. Его объем никак не влияет на количество полигонов навигационной сетки, за исключением случаев когда на карте множество мелких деталей, но тогда встает вопрос о целесообразности построение навкарты в этом месте. Это остается на совести и опытности дизайнера уровней.
И даже если у вас получится создать огромный объект, то количество полигонов навигационной сетки все равно будет значительном меньше чем число равнораспределенных точек, которые потребовались бы для ее сканирования.
Ошибки
Алгоритм обхода краев не лишен недостатков, и в большинстве случаев это проявляется в странных артефактах по краям сегмента, когда объекты имеют сложную форму. Сложно чтото сделать с ними, кроме как убрать их во время генерации отступив некоторое расстояние от края сегмента и запретив генерацию на коротких сегментах.
Поиск укрытий во время игры (cover evaluation)
Итак, имея в распоряжении массив точек укрытия на нашей карте, мы можем можем использовать его для работы не обращая (условно) внимания на геометрию уровню. Более того, если на протяжении некоторого интервала времени этот массив остается неизменным (для случая с предгенерацией укрытий это время существования самого уровня), то мы можем использовать его в распределенном поиске для каждого NPC отдельно в соотвествии с заданной логикой, не перегружая движок игры лишними рейкайстами, в идеальном случае вообще не вызывая их и опираться только на данные точек укрытий.
Так например, мы можем создать алгоритм (задачу), которая оценит расстояние от плеера до каждой точки укрытия в некотором радиусе от него, и выберет ближайшую из них, потом НПС перейдет (перебежит, перелетит) в найденную точку, и сможет выполнить действия, которые доступны там (пострелять, высунуться, кинуть что-то в игрока, покричать).
Или что-то посложнее, создать задачу (cover evaluator), которая среди доступных элементов подберет тот, что больше всего подойдет под условия. Так может выглядеть поиск точки стрельбы за высоким ящиком или колонной.
1. нет возможности стрелять сверху укрытия
2. можно стрелять по бокам
3. линия обзора не блокируется другими НПС или объектами
4. НПС может добраться в эту точку
Для проверки того, может ли НПС попасть по врагу, выглядывая из-за укрытия или наклоняясь, можно использовать рейпик из точки, которая смещена относительно центра укрытия, основываясь на информации, которая была сохранена. На скриншоте желтыми линиями обозначены места, из которых может безопасно атаковать, и доступные возможные пути (синие).
Заключение
Система укрытий использует два отдельных метода для генерации: сканирование окружения и обход по краям навигационной сетки. Первый метод лучше позволяет находить укрытия подходящие под конкретное место на уровне, второй ускоряет поиск укрытий и позволяет строить систему на сложной геометрии за управляемое время. Сканирование объектов включает в себя обсчет геометрии в некоторой точке через подсистемы движка\игры, эта система может быть дополнена обнаружением выступов, балконов и углов. С небольшими доработками она может выполняться в рантайме и поддерживать динамический пересчет этих точек, если это необходимо.
З.Ы. Я надеюсь что эта статья была полезна для понимания принципов работы и организации подобнаых систем в вашем проекте. Если что-то не ясно или у вас возникнут вопросы, не стесняйтесь задать их в комментариях.
