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

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

Термины

Игровой мир представлен 3d моделями, которые в свою очередь состоят из треугольников. Это может быть ландшафт, здания, деревья и все то что формирует целостную картину мира, это тоже самое что видит игрок.

Дискретизация (лат. discretio — «распознавать») трансформация непрерывного в дискретное.

Дискретность (лат. discretus — разделённый) — свойство материи, характеризуемое как прерывистое.

В итоге:

Дискретизация пространства — это деление и распознавание иными, словами интерпретация пространства. В нашем случае этопространство — игровой мир.

Примечание: слово «дискретизация» вместо слова «деление» используется намерено, ибо деление в данном случае это очень грубое описание процесса, и не передает всей сути процесса интерпретации игрового мира для осуществления навигации, то есть процесса дискретизации.

Навигация в простом смысле это перемещение.

С терминами разобрались, теперь перейдем к сути.

Примечание: я очень много провел времени за чтением и изучением форума gamedev.ru за что его создателям и обитателям большое спасибо. Изложенный мной материал основан как на личных обсуждения так и изучением других обсуждений. Также при написании я основывался на реализации сделанной нами в движке SkyXEngine.

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

  • Navigation regular grid (навигационная регулярная сетка)
  • Waypoints (путевые точки)
  • NavMesh (навигационная сетка)

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

Рассмотрим каждый из перечисленных.

Navigation regular grid (ai сетка)

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

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

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

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

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

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

  • Относительная простота реализации (автогенерация и ручная расстановка)
  • Простой поиск пути
  • Легкость в модификации

Недостатки:

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

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

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

navmesh (проект <a href="https://github.com/recastnavigation/recastnavigation">Recast/Detour</a>)
navmesh (проект Recast/Detour)

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

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

Поиск пути может выполняться просто по прямой, потому что многоугольники выпуклые и проходящие.

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

  • занимает мало памяти
  • простое выпрямление путей
  • быстрые поиск пути

Недостатки:

  • cложность в реализации
  • cложности при real-time перестроении

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

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

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

Примечание: с этим методом я возможно оказался в каких-то местах не компетентен))

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

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

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

  • Относительно простая реализация – расстановка вручную
  • Простота поиска пути
  • Поиск работает быстрее

Недостатки:

  • Долго расставлять вручную
  • Сложности в выпрямлении путей
  • Сложно модифицировать
  • Сложности при автогенерации

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

Хочу сказать спасибо автору данной темы на форуме, а также рекомендую ее почитать.

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

*

code