Для большинства современных компьютерных игр, особенно для стратегий в реальном времени, игровой опыт сильно зависит от правильной работы искусственного интеллекта. Такая часть искусственного интеллекта, как поиск пути, сильно влияет на успех игры. Поэтому игровые дизайнеры тратят огромное количество усилий, чтобы увеличить производительность алгоритмов ответственных за поиск пути. Такие алгоритмы работают с большим количеством компьютерных ресурсов, но не должны нагружать процессор.
Навигация в виртуальном мире осуществляется с помощью алгоритма А* вместе с локальным алгоритмом движения для нахождения оптимального пути. Навигационные сетки наиболее популярный подход для объединения алгоритмов поиска пути с локальными алгоритмами движения.
Рисунок 1. Пример навигационной сетки (NavMesh).
Навигационная сетка (NavMesh) - это абстрактное представление виртуального мира игры в виде ячеек, образующих доступное для перемещения компьютерных персонажей пространство (рисунок 1). Ячейки в этом пространстве являются многоугольниками. В зависимости от количества сторон у этих многоугольников, навигационные сетки делятся на триангуляционные и полигональные. Пример триангуляционной сети показан на рисунке 1 (серые многоугольники представляют пространство доступное для передвижения, белые многоугольники - препядствия). Многоугольники в навигационной сетке должны быть выпуклыми. Это необходимо для свободного перемещения персонажа игры внутри одного многоугольника. В этом случае алгоритм поиска оптимального пути может исполняться на графе, в котором ячейки являются узлами графа, а соединения между ними образуют переходы и являются ребрами графа.
Во многих случаях разработчикам требуется создавать навигационные сетки вручную, что занимает много времени и может привести к ошибкам, при которых образуются области недоступные для передвижения игровых персонажей, либо персонажи начинают застревать в углах и препятствиях. Поэтому существуют специальные алгоритмы генерации навигационных сеток для предотвращения таких ошибок.
Проделанная работа показала, что даже такое с первого взгляда простое изменение искусственного интеллекта в игре, как изменение способа построения путей для внутриигровых персонажей, может существенно изменить геймплей, преобразив получаемый игровой опыт. Когда компьютер может подстраиваться под игровые действия, игроку приходится придумывать каждый раз новую стратегию или изменять имеющуюся, что несомненно делает игровой процесс более интересным.
