Статья:

Дискретизация трехмерного пространства для навигации

Конференция: XLVIII Студенческая международная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Технические науки

Выходные данные
Домрачева Т.С., Шиганова М.В., Романова Н.А. [и др.] Дискретизация трехмерного пространства для навигации // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XLVIII междунар. студ. науч.-практ. конф. № 8(48). URL: https://nauchforum.ru/archive/MNF_tech/8(48).pdf (дата обращения: 22.10.2021)
Лауреаты определены. Конференция завершена
Эта статья набрала 0 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Дискретизация трехмерного пространства для навигации

Домрачева Татьяна Сергеевна
студент, НГПУ им.Козьмы Минина, РФ, г.Нижний Новгород
Шиганова Марина Викторовна
студент, НГПУ им.Козьмы Минина, РФ, г.Нижний Новгород
Романова Наталья Анатольевна
студент, НГПУ им.Козьмы Минина, РФ, г.Нижний Новгород
Орловская Людмила Александровна
студент, НГПУ им.Козьмы Минина, РФ, г.Нижний Новгород

 

Зачастую начинающие программисты сталкиваются с проблемой навигации в трёхмерном пространстве.

Существует 3 наиболее популярных метода дискретизации трехмерного пространства:

· Navigation regular grid (навигационная регулярная сетка)

· Waypoints (путевые точки)

· NavMesh (навигационная сетка)

Каждый из перечисленных находит свое применение в трехмерных играх различных жанров.

В целом, суть методов - это деление пространства на определенные детали для осуществления передвижения неигровых персонажей сюжета (НПС) по ним, то есть реализации искусственного интеллекта (ИИ).

Navigation regular grid – регулярная сетка из ячеек, где каждая из них имеет общую для всех форму, соседей и  параметры проходимости. В некоторых случаях регулярная сетка может заменить имитацию физических законов в игре для НПС.

 

Рисунок 1. Navigation regular grid с промежуточными graph-point (движок SkyXEngine)

 

Форма ячеек может быть разная, наиболее популярны: квадратные (4 прямых и 4 диагональных соседа) и гексагональные/шестигранные (6 соседей).

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

Самый главный минус данной сетки заключается в высокой потребляемой памяти. Однако на примере движка X-Ray и любительским модификациям к игре “S.T.A.L.K.E.R Shadow of Shernobyl” уровни достигали размеров более 2000х2000 метров.

Достоинства:

· Относительная простота реализации  (автогенерация и ручная расстановка);

· Простой поиск пути;

· Легко модифицировать.

 

Недостатки:

· Для большого пространства требуется большое количество памяти

· Медленный поиск пути больших дистанций, исправляется внедрением промежуточных точек (к примеру графпоинты в SkyXEngine).

Navmesh (навигационная сетка) - это абстрактная структура данных, используемая в приложениях искусственного интеллекта для помощи агентам в поиске пути через сложные пространства. Этот подход известен с середины 1980-х годов в робототехнике, где его называют луговой картой, и начиная с 2000 года приобретал все большую популярность в видеоиграх.

 

Рисунок 2. navmesh (голубой цвет) (open source проект Recast/Detour)

 

Навигационная сетка представляет собой набор двумерных выпуклых многоугольников (полигональной сетки), которые определяют, какие области среды пересекаются агентами. Другими словами, персонаж в игре может свободно передвигаться по этим районам обходя препятствия, которые являются частью окружающей среды. Смежные многоугольники соединены друг с другом на едином графе.

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

Достоинства:

· занимает мало памяти;

· простое выпрямление путей;

· быстрые поиск пути.

Недостатки:

· cложность в реализации;

· cложности при real-time перестроении.

Waypoints (путевые точки) - это термин, используемый для обозначения промежуточной точки или места на маршруте.

Следовательно, этот термин обозначает опорную точку в трехмерном пространстве, чаще всего связанную с навигацией

Путевые точки - это наборы координат, которые идентифицируют точку в физическом пространстве.

 

Рисунок 3. waypoints (Google maps)

 

Рисунок 4. waypoints (скриншот пользователя Demiurg-HG с форума gamedev.ru)

 

Достоинства:

· Относительно простая реализация – расстановка вручную;

· Простота поиска пути;

· Занимает мало памяти;

· Поиск работает быстрее.

Недостатки:

· Долго расставлять вручную;

· Сложности в выпрямлении путей;

· Сложно модифицировать;

· Сложности при автогенерации.

Таким образом, различные методы дискретизации трехмерного пространства имеют свои достоинства и недостатки. Пользователю следует обращать на параметры и технические характеристики, анализировать, что больше подойдет, что будет более эффективным и быстрым, на его взгляд.

 

Список литературы:
1. С. Жуков, А. Ионес, “Моделирование поведения интеллектуальных персонажей в трехмерных пространствах в реальном времени”, Труды каф. «Прикладная математика», СПбГТУ
2. [Электронный ресурс ] http://www.gamedev.net/