Технические аспекты поиска пути ИИ в сложных средах полураспада
Двигатель за поведением: GoldSrc и архитектура ИИ
Система искусственного интеллекта Half-Life’ построена на движке GoldSrc, сильно модифицированном движке Quake, который Valve Software разработала в конце 1990-х годов. Архитектура ИИ в GoldSrc была революционной для своего времени, потому что она перешла за рамки простых шаблонов погони и атаки в систему, которая могла оценивать свою среду, выбирать между несколькими видами поведения и перемещаться по сложным трехмерным пространствам с удивительной надежностью. Ядром этой системы является класс объектов на C++, который представляет собой объект с конечным состоянием (FSM) в сочетании с подсистемой поиска пути. Каждый неигровой персонаж (NPC) в игре— от зомби-головы до военнослужащих—наследники из этого базового класса, который обеспечивает фундаментальную навигацию и возможности принятия решений. Понимание того, как эти части сочетаются друг с другом, показывает, почему враги Half-Life’ все еще чувствуют себя умными десятилетия спустя.
Путей не достаточно: основы навигационной сетки
Современный игровой ИИ в значительной степени опирается на навигационные сетки (nav meshes) в качестве основного представления пространства для ходьбы. Однако Half-Life предшествует широкому внедрению навигационных сеток в игровых движках в реальном времени. Вместо этого движок GoldSrc использует навигационную систему на основе узлов, которая концептуально похожа на граф. Дизайнеры уровней вручную размещают точки поворота (называемые & #8220;path corners & #8221; в редакторе Hammer) по всей среде. Эти точки пути связаны направленными краями, которые определяют возможные пути, которые может пройти персонаж ИИ. Система элегантна и ограничивает: она дает дизайнерам прямой контроль над движением ИИ, но требует тщательного ручного труда, чтобы обеспечить каждую область, которую ИИ может нуждаться в правильном подключении.
Навигация на основе узлов в Half-Life
Каждая точка пути сохраняет положение, соединения пути являются действительными, и флаги, которые указывают на особые условия, такие как сегменты, требующие скрещивания, скачки или подъем по лестнице. Когда персонаж ИИ должен перемещаться из одной точки в другую, он не вычисляет путь через произвольную геометрию. Вместо этого он ищет граф точки пути с помощью алгоритма поиска пути, чтобы найти самую короткую последовательность подключенных узлов. Сами поперечные поверхности определяются геометрией щетки карты, но ИИ никогда не находит прямой путь через эти поверхности; он всегда маршрутизирует через сеть узла. Этот подход резко сокращает пространство поиска по сравнению с методами сетки или навигационной сетки, что имеет решающее значение, учитывая ограниченные ресурсы процессора, доступные в аппаратном обеспечении 1998 года.
Почему узлы работают на GoldSrc
Система на основе узлов хорошо работает для Half-Life, потому что игровые уровни являются относительно линейными средами в стиле коридоров с предсказуемой геометрией. Исследовательский центр Black Mesa, основная настройка игры & #8217, состоит из прихожих, комнат и промышленных пространств, которые естественным образом перемещаются через точки удушья. Хорошо расположенная сеть из тридцати до пятидесяти точек пути может покрывать большую комнату и ее выходы, позволяя ИИ эффективно перемещаться без необходимости плотной сетки. Система также поддерживает иерархическое нахождение пути на базовом уровне: дизайнеры могут группировать точки пути в & #8220; области & #8221; и использовать соединения между областями для ускорения поиска пути на расстоянии через несколько разделов карты. Этот двухуровневый подход снижает сложность поиска пути от O (n log n) более сотен узлов до гораздо более управляемых вычислений.
Алгоритм A* в системе искусственного интеллекта Half-Life’
Half-Life использует алгоритм поиска A* (A-star) в качестве своей рабочей лошадки поиска пути. A* — это алгоритм поиска наилучшего пути от начального узла до целевого узла, который находит кратчайший путь от начального узла до целевого узла, оценивая сумму двух функций: g(n), стоимость пути от начала до узла n, и h(n), эвристическая оценка стоимости от узла n до цели. Алгоритм поддерживает приоритетную очередь узлов для исследования, всегда расширяя узел с наименьшим значением f(n) = g(n) + h(n). В реализации Half-Life’ расстояние между точками пути используется в качестве краевой стоимости, а евклидово расстояние от текущего узла до цели служит эвристической. Эта комбинация гарантирует оптимальный путь с точки зрения пройденного расстояния, предполагая, что сеть узла точно представляет среду.
Эвристика и функции затрат
Выбор эвристики имеет решающее значение для производительности A*. Half-Life использует стандартную эвристику расстояния Euclidean, которая допустима (никогда не переоценивает истинную стоимость) и последовательна, гарантируя, что алгоритм возвращает кратчайший путь. Однако движок добавляет некоторые оптимизации для учета структуры сети узла. Например, при расчете эвристики система рассматривает вертикальный компонент движения более тяжело, чем горизонтальный компонент, потому что подъем по лестнице или навигация по пандусу накладывает более высокую стоимость движения на символы ИИ. Этот вертикальный штраф препятствует алгоритму A* выбирать пути, которые требуют чрезмерного подъема, даже если горизонтальное расстояние короче. Кроме того, двигатель кэширует результаты поиска A* в пределах одного кадра, поэтому, если несколько символов ИИ ищут путь к одной цели, выполняется только один поиск и результаты делятся.
Путь гладкий и точка пути следующая
После того, как A* создает список точек пути, персонаж ИИ должен следовать по этому пути естественным образом. Half-Life реализует шаг сглаживания пути , который удаляет ненужные точки пути с вычисленного пути. Если персонаж может видеть следующую точку пути непосредственно без каких-либо промежуточных препятствий, промежуточные точки пути отбрасываются. Это уменьшает зигзагообразное поведение, которое может происходить при следовании за сетью узла наивно. После сглаживания персонаж ИИ использует поведение рулевого управления для перемещения к следующей точке пути, применяя ускорение и замедление на основе расстояния до цели и возможностей скорости персонажа & #8217. Система также включает в себя механизм & #8220; смотри вперед & #8221; механизм: персонаж ИИ не просто движется к непосредственной следующей точке пути, но к точке, немного впереди по пути. Это упреждающее движение создает более плавные траектории и предотвращает резкое остановку персонажа в каждой точке пути.
Обработка динамических сред
Одним из наиболее впечатляющих аспектов ИИ Half-Life’ является его способность обрабатывать динамические изменения в окружающей среде. Скриптовые последовательности, открывающиеся двери, уничтожаемые враги и даже физические события, вызванные игроком, могут изменять пространство для ходьбы в реальном времени. Система поиска пути должна реагировать на эти изменения, не пересчитывая весь навигационный график каждого кадра, что было бы вычислительно непозволительно.
Динамическое предотвращение препятствий
Когда персонаж ИИ сталкивается с неожиданным препятствием, которое не представлено в сети узлов & #8212; например, свалкой мусора, закрывающей дверью или даже другим персонажем & #8212; он использует локальный механизм предотвращения препятствий, который работает независимо от глобального следопыта. Эта система использует простой подход лучеуказания : персонаж отбрасывает лучи в своем направлении вперед и в каждую сторону. Если луч обнаруживает препятствие на определенном расстоянии, персонаж уводит от него. Это локальное избегание является чисто реактивным и не обновляет сеть узлов. Если локальное избегание не находит четкого пути через несколько секунд, персонаж ИИ возвращается к пути поведение: он запускает новый поиск A * из своего текущего положения к первоначальной цели, но с модифицированной функцией затрат, которая наказывает узлы рядом с обнаруженным препятствием. Этот гибридный подход & #8212; глобальное планирование пути с локальным реактивным избеганием & #8212; был инновационным для своего времени и остается стандартной техникой в современной игре AI.
Изменения окружающей среды и реактивность
Двери и платформы представляют собой особую проблему. Когда дверь закрывается, она создает непроходимый барьер, который сеть узлов может не учитывать. Half-Life обрабатывает это, прикрепляя флаг к краям точек пути, которые проходят через дверные проемы. Когда дверь закрывается, он устанавливает этот флаг на пораженные края, эффективно удаляя их с графика для целей поиска пути. Персонаж AI получает уведомление о событии, когда дверь закрывается, что вызывает немедленный репат. Аналогично, движущиеся платформы меняют положение точек пути, которые прикреплены к ним. Двигатель обновляет положения этих точек пути каждый кадр, и следопыт рассматривает их как динамические узлы. Это позволяет персонажам ИИ ездить на платформах и перемещаться по переходам между различными возвышениями без специального кода.
Государственные машины и принятие решений
Один только Pathfinding не создает интеллектуальное поведение. Персонаж ИИ должен решить , когда двигаться, , где двигаться, и , как расставлять приоритеты для нескольких целей. Half-Life реализует конечную машину состояний (FSM) в качестве уровня принятия решений на высшем уровне для каждого объекта ИИ. FSM определяет набор состояний, таких как Idle, Alert, Combat, Flee, и Patrol. Каждое состояние имеет свою собственную логику поведения, включая то, как направляется поиск пути и какие цели выбираются.
AI State Machine в GoldSrc
В состоянии Idle персонаж ИИ стоит на месте, периодически сканируя среду на наличие врагов или раздражителей. При обнаружении игрока (через зрение, звук или повреждение) персонаж переходит в состояние Alert. В Alert персонаж начинает поиск пути к последнему известному положению противника. Если врага не найти через короткое время, персонаж входит в состояние Поиска и использует рандомизированное поведение поиска пути: алгоритм A* используется для поиска пути к противнику’с последним известным местоположением, но персонаж не перемещается непосредственно туда. Вместо этого он перемещается в близлежащую точку пути, которая обеспечивает хорошую точку обзора, имитируя поведение охранника, который ищет злоумышленника. Если персонаж получает визуальный контакт с врагом, он переходит в состояние боя, которое использует другое поведение поиска пути, которое отдает приоритет фланкирующим движениям и укрывается.
Переходы и приоритеты
FSM включает в себя систему приоритетов, которая разрешает конфликты между конкурирующими целями. Например, персонаж может находиться в боевом состоянии и получать событие повреждения от нового врага за ним. Машина состояния оценивает угрозу на основе расстояния, типа оружия и нанесенного ущерба. Если новая угроза более опасна, персонаж переходит в состояние Evade, которое запускает запрос поиска пути к положению прикрытия, а не к первоначальному противнику. Этот механизм приоритета реализован как простая система численного подсчета баллов: каждый стимул генерирует оценку угрозы, а машина состояния сравнивает оценки каждого цикла принятия решения (обычно каждые 0,1-0,5 секунды для сохранения процессора). Система поиска пути работает рука об руку с этой системой приоритета, потому что назначение алгоритма A* определяется текущим состоянием и самой приоритетной целью.
Соображения в отношении эффективности
Запуск A* Pathfinding на нескольких ИИ-персонажах в режиме реального времени был значительной проблемой для аппаратного обеспечения 1998 года. Half-Life работает на процессорах, таких как Pentium II, на частоте 233-300 МГц с ограниченной пропускной способностью памяти. Разработчики реализовали несколько стратегий оптимизации, чтобы поиск пути не потреблял более 10-15% бюджета процессора на кадр.
Бюджетирование ЦП и частота поиска пути
Не каждый персонаж ИИ выполняет поиск пути каждый кадр. Half-Life использует подход , сокращающий время: каждый персонаж имеет личный таймер, который определяет, когда он может запросить новый путь. Таймер рандомизирован в диапазоне (обычно от 0,5 до 2,0 секунд) для ошеломляющих запросов поиска пути через кадры. Кроме того, персонажам, которые находятся далеко от игрока (за пределами настраиваемого порога расстояния), назначается гораздо больший интервал таймера (до 5 секунд) и может использовать упрощенный эвристический, который не требует полного поиска A *. Этот уровень детализации на основе расстояния гарантирует, что удаленные враги все еще, кажется, движутся разумно, не тратя циклы процессора на точное обнаружение пути, которое игрок не может видеть.
Уровень детализации для AI
Подобно графическим системам LOD, Half-Life реализует систему AI LOD. Персонажи за определённое расстояние от игрока продвинуты в упрощённое состояние AI, которое использует только локальное избегание препятствий без глобального поиска пути. Эти далёкие персонажи всё ещё патрулируют и реагируют на звуки, но их движение основано на простом блуждающем поведении, которое выбирает случайные ближние точки пути, а не вычисляет полный путь A*. Когда игрок приближается в пределах более близкого порога, персонаж смещается обратно в полную систему AI с машиной состояния и поиска пути. Этот переход бесшовен, потому что поведение блуждания спроектировано так, чтобы быть визуально совместимым с состоянием патрулирования. Система AI LOD значительно снижает общую нагрузку поиска пути, особенно на уровнях со многими врагами, таких как “Напряжение на поверхности ” глава, где десятки солдат одновременно вовлекают игрока.
Влияние и наследие реального мира
Система ИИ в Half-Life установила эталон поведения врагов шутера от первого лица, который повлиял на всю индустрию. Такие игры, как Halo: Combat Evolved и F.E.A.R., прямо ссылаются на Half-Life как на вдохновение для своих проектов ИИ. Сочетание навигации на основе узлов с поиском пути A*, динамическим избеганием препятствий и иерархической машиной состояния стало стандартным шаблоном для ИИ в линейных шутерах по крайней мере на десятилетие. Даже сегодня игры, использующие движок Source (прямой преемник GoldSrc), сохраняют большую часть той же архитектуры ИИ, хотя со значительными улучшениями в генерации навигационных сеток и многопоточной настройке пути.
Технические уроки из системы искусственного интеллекта Half-Life’ по-прежнему актуальны для независимых разработчиков, работающих с ограниченными бюджетами и современных разработчиков, оптимизирующих большие открытые миры. Основное понимание заключается в том, что интеллектуальное поведение происходит от взаимодействия между алгоритмом поиска пути и системой принятия решений, а не только от одного компонента. Сеть узлов обеспечивает осведомленность о местности, A* обеспечивает эффективный расчет маршрута, государственная машина обеспечивает цели и приоритеты, а локальное избегание обеспечивает реактивную гибкость. Эта многоуровневая архитектура дает врагам Half-Life’ их репутацию удивительного интеллекта.
Для разработчиков, заинтересованных в реализации подобных систем, такие ресурсы, как GameDev.net’s введение в A*, обеспечивают практическое руководство по алгоритмам поиска путей, в то время как документация системы искусственного интеллекта Исходный движок предлагает понимание того, как развивался оригинальный подход GoldSrc. Кроме того, книга AI для игр Иэна Миллингтона охватывает отраслевые стандарты, которые помогла установить Half-Life. Понимание технических основ поиска путей ИИ Half-Life’ является не просто уроком истории; это практическое образование в том, как построить убедительное, отзывчивое поведение противника в рамках вычислительных ограничений.
Система не лишена своих слабостей. Навигация на основе узлов может создавать неестественные шаблоны движения, когда плотность узла слишком низкая, а размещение ручных узлов трудоемко и подвержено ошибкам. Современные двигатели в значительной степени перешли к автоматической генерации навигаторов с использованием методов вокселизации или полигона. Однако принципы иерархического поиска пути, запросы на временные нарезки, LOD на основе расстояния и гибридная глобальная локальная навигация остаются краеугольными камнями игрового дизайна ИИ. Half-Life продемонстрировала, что с умной инженерией и продуманным дизайном даже ограниченные ресурсы процессора могут обеспечить ИИ, который чувствует себя живым и сложным.