Введение 3
Цель 5
Постановка задачи 6
Обзор литературы 7
Обзор алгоритмов генерации навигационных сеток 8
Поиск пути в навигационных сетках 10
Глава 1. Алгоритм генерации навигационной сетки 11
1.1. Начало алгоритма 11
1.2. Создание переходов 13
1.3. Переход Вершина-Вершина 13
1.4. Переход Вершина-Грань 14
1.5. Переход Вершина-Переход 15
1.6. Удаление ранее созданных переходов 16
1.7. Слабое определение выпуклости 17
1.8. Результат алгоритма 19
Глава 2. Поиск пути в навигационных сетках 20
2.1. Алгоритм поиска в ширину (breadth-first search, BFS) 20
2.2. Алгоритм Дейкстры 24
2.3. Алгоритм А* 29
2.4. А* в навигационных сетках 35
2.5. Сравнение и выявление лучшего из рассмотренных алгоритмов поиска 37
Глава 3. Управление передвижением 45
3.1. Интеллектуальные агенты 45
3.2. Выбор и проектирование агента 49
Глава 4. Реализация Unity проекта 52
4.1. Примеры работы 56
Результаты 57
Выводы 58
Заключение 59
Список литературы 60
Приложение
Для большинства современных компьютерных игр, особенно для стратегий в реальном времени, игровой опыт сильно зависит от правильной работы искусственного интеллекта. Такая часть искусственного интеллекта, как поиск пути, сильно влияет на успех игры. Поэтому игровые дизайнеры тратят огромное количество усилий, чтобы увеличить производительность алгоритмов ответственных за поиск пути. Такие алгоритмы работают с большим количеством компьютерных ресурсов, но не должны нагружать процессор.
Навигация в виртуальном мире осуществляется с помощью алгоритма А* вместе с локальным алгоритмом движения для нахождения оптимального пути. Навигационные сетки наиболее популярный подход для объединения алгоритмов поиска пути с локальными алгоритмами движения.
Навигационная сетка (NаvMеsh) - это абстрактное представление виртуального мира игры в виде ячеек, образующих доступное для перемещения компьютерных персонажей пространство (рисунок 1). Ячейки в этом пространстве являются многоугольниками. В зависимости от количества сторон у этих многоугольников, навигационные сетки делятся на триангуляционные и полигональные. Пример триангуляционной сети показан на рисунке 1 (серые многоугольники представляют пространство доступное для передвижения, белые многоугольники - препятствия). Многоугольники в навигационной сетке должны быть выпуклыми. Это необходимо для свободного перемещения персонажа игры внутри одного многоугольника. В этом случае алгоритм поиска оптимального пути может исполняться на графе, в котором ячейки являются узлами графа, а соединения между ними образуют переходы и являются ребрами графа.
Во многих случаях разработчикам требуется создавать навигационные сетки вручную, что занимает много времени и может привести к ошибкам, при которых образуются области недоступные для передвижения игровых персонажей, либо персонажи начинают застревать в углах и препятствиях. Поэтому существуют специальные алгоритмы генерации навигационных сеток для предотвращения таких ошибок.
Цель
Используя математический и программный аппарат разработать функционал, позволяющий проецировать карты реального мира в виртуальный. А также создать систему интеллектуального поведения, с помощью которой возможно эффективное управление объектами реального мира на построенных виртуальных картах
Проделанная работа пока зала, что даже такое усложнение поведения игровых объектов, путём добавления им интеллектуальной составляющей, как изменение способа построения путей и простейшей реакции в виде : перестроения путей в случае попадания их в область поражения, для внутриигровых персонажей, может существенно изменить геймплей, преобразив получаемый игровой опыт. Когда компьютер может подстраиваться под игровые действия, игроку приходится придумывать каждый раз новую стратегию или изменять имеющуюся, что, несомненно, делает игровой процесс более интересным.
