Использование UDK NavMesh в алгоритме поиска пути

Алгоритм поиска пути в UDK NavMesh

И опять передо мной стоит задача реализации алгоритма поиска пути для игрового AI (ИИ) моих NPC (Non-player characters или попросту ботов). Напомню, сперва мной был выбран движок Unity для создания игры. Мне пришлось самостоятельно разрабатывать алгоритм поиска пути в Unity на базе A*. В UDK же все уже разработано до нас и доступно в Unreal Engine 3 через UnrealScript. Остается только во всем разобраться и научиться это правильно использовать.

Что такое NavMesh?

NavMesh — это одна из современных технологий поиска пути, а точнее, способ представления данных о пути на игровой карте. NavMesh представляет собой полигональную поверхность, покрывающую те части игрового ландшафта, где могут пройти наши NPC (или боты). Полигоны NavMesh строятся таким образом, чтобы получились выпуклые примитивы (в UDK ими являются простые треугольники). Выпуклость примитива дает нам гарантию того, что все объекты, находящиеся внутри этого многоугольника доступны нам безо всяких препятствий. Это одно из основных свойств NavMesh'а, и все алгоритмы поиска пути через NavMesh активно используют этот постулат.

В чем преимущество NavMesh?

Благодаря своей природе, алгоритмы, построенные на базе NavMesh, являются очень быстрыми. Это обусловлено отсутствием необходимости применять трассировку луча (RayCast) для поиска препятствий, а также минимальным количеством узлов в графе путей по сравнению с другими методами представления карты (например, PathNodes), особенно на больших картах.

Коротко о преимуществах:
  1. Снижение расхода памяти на хранение графа путей
  2. Отсутствие необходимости поиска начальной точки, как это было бы нужно при использовании PathNodes, т.к. мы по умолчанию уже находимся на одном из полигонов NavMesh.
  3. Более естественное перемещение по карте, в отличие от угловатых переходов других алгоритмов.
  4. Встроенный учет габаритов персонажа. Т.к. два соседних полигона NavMesh соединены между собой не отрезком прямой, как в PathNodes, а целой гранью, то для перехода из одного полигона в другой мы можем выбрать любую точку этой грани! Это позволит и солдату, и танку повернуть за угол, не зацепив при этом половиной корпуса само здание.
  5. Простой и удобный способ создания динамических препятствий.
Подробнее о преимуществах NavMesh рассказано в документации UDK:
Там же о том, как строится и работает NavMesh:

Использование UDK NavMesh в UnrealScript

От теории переходим к практике. Я надеюсь, вам не составит труда создать NavMesh в UDK в редакторе UnrealEd, правильно расположить его на карте и перестроить карту путей. Вот ссылка на документацию UDK по созданию NavMesh:
Помните: если вы произвели какие-либо манипуляции с настройками Pylon, отвечающего за построение NavMesh, или же изменили игровой ландшафт, то нужно обязательно перестроить пути! Это можно сделать в меню Build -> AI Paths или нажав на кнопочку в самом нижнем левом углу UnrealEd.

Теперь нам надо использовать полученный NavMesh в AI наших ботов (NPC), чтобы они могли свободно перемещаться по карте. В UnrealScript процесс работы с NavMesh делится на 2 этапа:
  1. Поиск желаемого пути (path finding)
  2. Следование NPC персонажем полученным путём (path following)
Я специально не стал писать «поиск пути до нужной точки», т.к. мы можем и не знать нужной нам точки, как в примере ниже.

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

Для реализации задуманного в UnrealScript нам потребуется внедрить следующий код в наш класс, унаследованный от UDKBot:

/**
 * Поиск пути к случайной точке.
 * Возвращает TRUE, если точка найдена.
 */
function bool FindRandomPath(){
    NavigationHandle.ClearConstraints();
    class'NavMeshGoal_Random'.static.FindRandom( NavigationHandle );
    class'NavMeshPath_EnforceTwoWayEdges'.static.EnforceTwoWayEdges( NavigationHandle );
    return NavigationHandle.FindPath();
}

/**
 * Для патрулирования территории определим специальное состояние.
 * По умолчанию контроллер сразу перейдет в него, т.к. состояние объявлено
 * с ключом auto. В конечном варианте этот ключ надо убрать, а переход в
 * состояния осуществлять через ExecuteWhatToDoNext().
 */
auto state Patrol
{
    // Здесь будем хранить нашу точку назначения
    local vector vFinalDestination;
    
    // Очередная промежуточная точка на пути к цели
    local vector vTempDest;

    Begin:
        // Ищем случайную точку
        if( FindRandomPath() ) {

            // Для отладки рисуем полученные пути прямо во время игры
            FlushPersistentDebugLines();
            NavigationHandle.DrawPathCache(,true);

	    // Устанавливаем точку назначения
	    NavigationHandle.SetFinalDestination( NavigationHandle.PathCache_GetGoalPoint() );
            vFinalDestination = NavigationHandle.FinalDestination.Position;
	    _log("final destination: "@vFinalDestination);

            // Движемся, пока не достигнем точки назначения
            while( NavigationHandle.GetNextMoveLocation( vTempDest, Pawn.GetCollisionRadius())
		&& !Pawn.ReachedPoint(vFinalDestination, none) ) {

                if (!NavigationHandle.SuggestMovePreparation( vTempDest, self)) {
                    MoveTo( vTempDest, none );
                    _log("Moving to"@vTempDest);
                }else{
                    break;
                }
            }
        }

        // Постоим 2 секунды
        Sleep(2.0);
        // и пойдем искать другую случайную точку
        goto('Begin');

        // В конечном варианте нужно заменить goto('Begin') на
        // LatentWhatToDoNext();
        // и реализовать в своем AI контроллере события WhatToDoNext() и 
        // ExecuteWhatToDoNext(). Смотрите в качестве примера класс UTBot.
}


Думаю, пояснений к коду не требуется, т.к. я пострался снабдить его комментариями. Единственное непонятное место — это классы NavMeshGoal_Random и NavMeshPath_EnforceTwoWayEdges, хотя с NavMeshGoal_Random вроде бы понятно из названия, но что это вообще такое? Об этом расскажу позднее, когда сам полностью разберусь с этим вопросом :)

Хочу обратить внимание на функцию _log(). На самом деле в UnrealScript нет такой функции, а есть `log(). Просто подсветка в блоге сбивается, когда я указывал оригинальную функция. Да и на самом деле полезно переопределить свою функцию _log, чтобы она выдавала имя объекта. Так удобнее для отладки:

function _log(string msg){
`log(Pawn.Name @ ": " @ msg);
}

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

В класс контроллера UDKBot приходит событие от пешки UTPawn под названием SeePlayer. Событие это вызывается, когда пешка UTPawn «видит» игрока своим периферическим зрением, т.е. пешка UTPawn обладает определенным углом зрения в обеих плоскостях.

Реализуем в нашем коде обработчик события SeePlayer:


event SeePlayer(Pawn SeenPlayer)
{
    // Переменная Enemy наследуется из класса UDKBot и хранит
    // текущего врага данного бота. Как только мы увидим игрока,
    // сразу же запишем его к себе в злейшие враги :)
    Enemy = SeenPlayer;
}


Этот обработчик можно реализовать как внутри состояния Patrol, так и как глобальную функцию класса, которая сама будет переключать нашего бота в нужное состояние. Для этого можно добавить в нее либо GotoState('FollowEnemy'), что переключит бота в новое состояние, либо вызвать WhatToDoNext() и в нем переключить бота в нужное состояние. Все зависит от архитектуры вашего бота. Я пока сам еще не разобрался, как это сделать удобнее, поэтому не буду советовать что-то конкретное.

Теперь, раз уж мы видим врага, то нам нужно найти путь до него. Для этого мы определим еще одну функцию:


function bool FindPathToActor(Actor TargetActor)
{
    // Очищаем предыдущие списки ограничений
    NavigationHandle.ClearConstraints();

    // Задаем ограничения поиска
    class'NavMeshPath_Toward'.static.TowardPoint( NavigationHandle, TargetActor.Location);
    class'NavMeshGoal_At'.static.AtLocation( NavigationHandle, TargetActor.Location);
    
    // Когда у нас в качестве цели есть объект класса Actor, то можно задать сразу вот так:
    // class'NavMeshPath_Toward'.static.TowardGoal( NavigationHandle, TargetActor);
    // class'NavMeshGoal_At'.static.AtActor( NavigationHandle, TargetActor);

    // Find path
    return NavigationHandle.FindPath();
}


Код преследования врага абсолютно аналогичен коду перемещения нашего NPC в заданную точку. Нужно только подправить пару строк:


    Begin:
        // Ищем путь до врага
        if( FindPathToActor( Enemy ) {

            ...

            // Устанавливаем точку назначения
            vFinalDestination = Enemy.Location;
            NavigationHandle.SetFinalDestination( vFinalDestination );
            _log("final destination: "@vFinalDestination);

            ...
        }
        // Не можем найти путь до врага
        else {
            _log("Fail: Can't find path to target!");

            // Здесь располагается код, который выведет бота из постоянной попытки
            // найти путь до врага. Например, бот может пойти попить чайку или постоять
            // несколько секунд в состоянии Idle.

            ...
        }


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

На этом пока все. В следующих постах я планирую описать более сложные модели поведения для игрового AI на базе UDK NavMesh с примерами кода на UnrealScript, чтобы наш NPC не заставил игрока скучать.
  • 0
  • 13 июня 2012, 20:30
  • dimanjy

Комментарии (4)

RSS свернуть / развернуть
+
0
Очень понравился твой блог и мысли высказанные по поводу Инди проектов.
Оставь пожалуйста свои контактные данные(желательно скайп,icq или id в контакте)
avatar

Giperbore1

  • 20 июня 2012, 11:26
+
0
Ответил в личку :)
avatar

dimanjy

  • 21 июня 2012, 15:10
+
0
Спасибо за блог, действительно интересно, хотя я во многом уже самостоятельно разобрался, но созвучные мысли приятно прочесть вновь.
Есть такой вопрос, может быть есть идеи как при помощи NavMesh можно выбрать альтернативный (не кратчайший) путь к цели? Проблема в том что при наличии узкого прохода толпа ботов, двигающаяся по навмешу, застревает в нем, хотя в шаге от них свободное пространство.
avatar

lorendroll

  • 06 декабря 2012, 15:35
+
0
Вообще говоря, поиск кратчайшего пути — это только одна из задач, которую решает NavMesh. Насколько я понял из документации, к NavMesh'у можно делать различные запросы, задавая ограничения поиска (Path constraints) и конечные навигационные цели (Path goal evaluators). Вот тут про это немного говорится:
udn.epicgames.com/Three/NavMeshConstraintsAndGoalEvaluators.html
Там упоминается о возможности фильтрации путей по какому-то значению, задаваемому пользователем.

А вообще, настоящий программист для таких целей обычно пишет свой поиск путей (это в качестве полу-шутки:)
avatar

dimanjy

  • 06 декабря 2012, 23:07

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.