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

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

Существует 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)

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

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

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

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

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

Недостатки:

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

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

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

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

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