[Перевод] Реалистичный боевой ИИ для 2D-игры
Хотя Close Quarters преимущественно является многопользовательской игрой, в ней всё равно должны присутствовать сложные ИИ-боты, чтобы игроки продолжали играть при плохом Интернет-соединении или отсутствии других онлайн-игроков. Кроме того, боты играют важную вспомогательную роль в некоторых режимах игры. Поэтому они должны вести себя правдоподобно и демонстрировать набор сложных поведений, в том числе использование укрытий, применение предметов в подходящее время, обход с флангов, бросание гранат и убегание от них.
Окружение и ограничения
Игровое окружение состоит из полигонов. Большинство полигонов блокирует движение, область видимости и стрельбу, однако есть и «низкие» полигоны, только блокирующие движение. Окружение плотно заставлено препятствиями и укрытиями.
ИИ тоже ограничен несколькими техническими факторами. Самый важный из них: сервер, на котором выполняются боты, когда онлайн находится мало игроков, должен быстро работать на недорогом VPS как минимум при десяти ботах. Кроме того, нагрузка на ЦП должна оставаться достаточно низкой, чтобы можно было выполнять несколько инстансов сервера на одном VPS без превышения лимита ЦП, и не при этом вызвать санкций со стороны поставщика услуг VPS.
Рисунок 1: окружения
Рисунок 2: вид от лица игрока на препятствия, блокирующие обзор (серые области для него невидимы)
Меш навигации и видимости, тактический поиск пути
Боты используют плотный меш навигации, состоящий из дискретных точек. Меш генерируется следующим образом: сначала полигоны, из которых составлено окружение, расширяются и комбинируются. Рядом с углами добавляются дополнительные узлы, потому что эти места с наибольшей вероятностью окажутся подходящими позициями для укрытий. Получившееся пространство для перемещения затем триангулируется для генерации меша.
Рисунок 3: меш навигации
Так как боты должны выполнять тактический поиск пути, меш навигации должен содержать данные видимости, позволяющие нам быстро проверять, содержит ли узел укрытие от выбранного врага. Поэтому каждый узел содержит массив из 24 байтов, каждый из которых представляет собой заранее вычисленное приблизительное расстояние между узлом и ближайшим блокирующим область обзора препятствием в определённом направлении.
Рисунок 4: сохранённые в узле данные видимости (синие линии). Каждая линия представляет однобайтовое значение, определяющее видимость в заданном направлении.
Благодаря этим данным можно выполнять поиск по графам алгоритмом A* на меше навигации, при котором узлы, которые могут быть открыты для известных врагов, получают меньший приоритет без выполнения затратных проверок линии прямой видимости. Чтобы проверить, открыт ли для врага определённый узел, мы определяем направление и расстояние от узла до врага, а затем проверяем, меньше ли это расстояние чем, расстояние, сохранённое в элементе массива, наиболее близко соответствующему этому направлению. Кроме того, мы можем проверить, смотрит ли враг на узел. Затем мы можем применить штрафной коэффициент к затратам на перемещение по открытым для врагов узлам, и получившийся путь будет стремиться избегать таких узлов.
Те же данные видимости, кроме поиска пути между двумя заданными точками, можно использовать для других «тактических» действий. Например, бот ищет укрытие, выполняя поиск в ширину и останавливается, как только найдёт защищённый узел. Для проверки того, действительно ли узел обеспечивает укрытие, используются тесты линии видимости. Аналогично, мы можем генерировать пути атак с флангов, выполняя поиск A* к цели; при этом накладываются высокие штрафы на открытые узлы в пределах конуса стрельбы цели. Поиск останавливается, как только мы достигнем открытого узла за пределами этого конуса стрельбы. (Одна из проблем такого подхода заключается в том, что боты, вышедшие из области видимости, постоянно стремятся приблизиться к цели, а поэтому кажутся чересчур агрессивными; вероятно, это можно исправить настройкой эвристики A* так, чтобы бот двигался не напрямую к цели, а к любым узлам, находящимся на выбранном расстоянии до цели).
Чувства и память ботов
Чтобы боты вели себя убедительно, они не должны казаться «читерами». Другими словами, информация, с которой работает бот, должна быть похожа на информацию, которой обладает игрок. Например, враг за препятствием должен быть невидим для бота так же, как он не виден для игрока.
Существуют два способа, которыми игрок может обнаруживать позицию врага: он может увидеть врага или услышать, как тот движется, стреляет или выполняет какое-то другое действие.
Каждый бот хранит список известных ему «фактов» о позициях и направлении взгляда врагов. Без обновлений эти факты удаляются спустя десять секунд. Факт, относящийся к определённому врагу, обновляется, когда бот может услышать или увидеть этого врага. Когда бот слышит врага, для имитации неопределённости позиция соответствующего факта смещена от истинной позиции врага в случайное направление и расстояние, зависящие от того, как близко к боту был звук (см. видео, 1:28).
Рисунок 5: факты (розовые круги) в памяти бота
Дерево поведений
В более ранней версии Close Quarters ИИ использовал STRIPS — решение, популяризированное игрой F.E. A.R. в 2005 году. В STRIPS отношения между различными поведениями ИИ не задаются программистом заранее. Вместо этого каждое поведение содержит список двоичных предусловий и исходов. Каждый бот имеет состояние задачи в мире и использует поиск по графу A* для нахождения последовательности поведений её достижения. Такое решение хорошо работало, но я чувствовал, что для моего приложения оно было слишком сложным и лучше подходящим для ИИ, которому нужно разрабатывать сложные планы с участием множества разных поведений. В большинстве случаев я уже знал обстоятельства, при которых бот должен был выполнять то или иное поведение, поэтому использование для этого алгоритма A* было ненужной тратой ресурсов ЦП.
Поэтому теперь боты используют простое дерево решений и поведений. В каждом такте бот обходит дерево, начиная с корня, пока не достигнет поведения. Если это поведение такое же, как и уже выполняемое, то бот продолжает это поведение. Если нет, то бот инициирует поведение и начинает его выполнять.
Некоторые поведения могут «блокировать», то есть не позволять боту повторно обходить дерево, пока не будет выполнено определённое условие. Это полезно, например, чтобы гарантировать, что боты добрались до укрытия, прежде чем решат атаковать. Также поведения могут «обнулять» друг друга, вынуждая бота повторно обойти дерево и заново инициировать поведение. Это полезно, например, когда бот убегает от гранаты, и появляется другая граната, ставящая под угрозу выбранные позиции побега.
Рисунок 6: используемое сейчас дерево решений и поведений
Некоторые вторичные поведения закодированы внутри других, более общих поведений. Например, если бот пытается атаковать врага и обнаруживает, что враг не в предпологаемой позиции, то он предполагает, где враг может быть теперь, и вычисляет новый путь атаки, не выходя из поведения атаки.
Распределение нагрузки
Каждого бота необязательно обновлять в каждом кадре физики, то есть, 40 раз в секунду. Для снижения затрат ЦП каждый бот «думает» только 20 раз в секунду (это число при необходимости можно уменьшить). Поэтому в каждом такте физики обновляется ИИ только половины ботов.
Работа с гранатами
Серьёзной проблемой стало осмысленное использование ботами гранат. Работа с гранатами намного сложнее, чем стрельба, потому что гранаты могут отлетать от стен, иметь радиус поражения и время на бросание. К счастью, боты не обязаны использовать гранаты идеально, достаточно убедительности.
Традиционным решением этой задачи является предварительное вычисление траекторий гранат в узлах навигации, но при его реализации к времени загрузки каждой карты добавляется несколько секунд, что противоречит мой цели: Close Quarters должна бросать игроков в битву за считанные секунды после запуска игры.
Поэтому боты ищут возможности использования гранат, вычисляя траектории гранат на лету. В каждом такте атакующий бот проверяет несколько возможных траекторий в заданном направлении в пределах 60 градусов от направления выбранной цели. Если брошенная по проверенной траектории граната может убить цель и цель находится вне области видимости, бот бросает гранату. Проверяемое направление зациклено в каждом такте ИИ.
Рисунок 7: направления, проверяемые ботом в течение одной секунды (бледно-розовые линии) и протестированные траектории (синие круги) вдоль направления, выбранного в текущем такте (ярко-розовая линия).
То есть боты используют гранаты по возможности и не перемещаются в позицию специально для того, чтобы бросить гранату. Однако путь, выбираемый ботом для атаки на врага, часто бывает разумным путём, с которого можно бросить гранату.
Значительным недостатком такой системы является то, что из-за ограниченного количества проверяемых направлений боты упускают возможности бросать гранаты так, чтобы они отскакивали от небольших препятствий. Наиболее заметно это рядом с дверными проёмами, где боты обычно не распознают возможность использования гранаты. Эту проблему можно решить, тестируя в одном кадре несколько направлений и уменьшая таким образом угол между проверяемым направлением и следующим.
Движение к более человеческому поведению
Быстро становится очевидной такая проблема: боты слишком проворно жмут на спусковой крючок, потому их очень сложно победить в схватке один на один. Среднее время реакции человека на визуальные стимулы составляет 250 миллисекунд, но при 20 тактах в секунду, максимальное время реакции бота составит всего 50 миллисекунд!
Чтобы решить эту проблему, я намеренно добавил задержку между моментом, когда бот получает возможность выстрелить, и самим выстрелом, чтобы его время реакции было сравнимо с временем реакции человека.
Дальнейшие усовершенствования
Представленные выше системы обеспечивают сильный фундаментальный ИИ, но не дают возможностей для серьёзных улучшений. Например, сейчас пространственное мышление бота ограничено его непосредственными окрестностями, поэтому хотя бот обычно пытается обойти врага с фланга, он часто упускает пути обхода по флангу вокруг крупных препятствий. Кроме того, боты только примерно знают о присутствии товарищей по команде, поэтому иногда они скапливаются в одном месте, вместо того, чтобы разделиться и обходить с флангов.
