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


Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Notice: Функция get_currentuserinfo с версии 4.5.0 считается устаревшей! Используйте wp_get_current_user(). in /hlds/web/u138079p19/code4life.ru/htdocs/wp-includes/functions.php on line 3840

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

Для начала рекомендую ознакомится со статьей AI в играх. Основы.

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

Говоря о самом процессе дискретизации, надо заметить, что он должен иметь стартовую точку (вершину), при этом вовсе не важно, каким способом будет производиться дискретизация (ai сетка или navmesh либо waypoints). Но данная статья по большей части опирается на метод Navigation regular grid (ai сетка), сделанной в нашем движке SkyXEngine.

Стартовая вершина

Стартовая вершина дискретизации – первая вершина в графе дискретизированного уровня, которая устанавливается непосредственно дизайнером уровней. Программа по ней узнает, откуда надо начинать расчеты деления  уровня.

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

Стартовая вершина должна ставится в том месте игрового мира, которое доступно для «живых» игровых объектов для перемещения.

Стартовая вершина в движке SkyXEngine, не имеет соседей и помечена красным цветом
Стартовая вершина в движке SkyXEngine, не имеет соседей и помечена красным цветом

После постановки стартовой вершины следует процесс создания соседних вершин для всех вершин, «соседи» которых еще не просчитаны. Однако можно расставить несколько стартовых вершин, либо добавить соседей к стартовой вершине. В этом случае поиск можно начать с самой первой созданной вершины и анализировать наличие соседних вершин.

Генерация графа – процесс, выполняющий создание всех соседних вершин для текущей анализируемой, и повторяющийся до момента, пока все вершины графа не приобретут соседние вершины либо их генерация будет невозможной.

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

По центру расположена текущая вершина, все лежащие рядом с ней вершины являются соседними. AI сетка движка SkyXEngine
По центру расположена текущая вершина, все лежащие рядом с ней вершины являются соседними. AI сетка движка SkyXEngine

После процесса генерации следует валидация всего того что было сгенерированного.

Валидация графа

Валидация/проверка сгенерированного графа – процесс проверки соответствия графа минимальным требованиям для осуществления навигации по нему.

В проверку могут входить:

  • проверка отсутствия не инициализированных соседей (пометка о невозможности инициализации не учитывается)
  • удаление вершин, не имеющих соседей, так как по таким вершинам невозможна навигация (здесь также стоит упомянуть о количестве связей, к примеру если одна вершина (размер 70 см на 70 см) может вмещать в себя малые «живые» объекты размером 70 см на 70 см, то  возможно несколько вершин (радиус 2 вершины, то есть 9 вершин совокупной площадью 210 см на 210 см) будут вмещать себя большие «живые» игровые объекты и так далее)
  • определение непрерывных пространств/слоев и присвоение им уникального идентификатора (может просто порядкового номера), в случае наличия условно «не цельного» графа
  • другие проверки
Отдельные непрерывные пространства, движок SkyXEngine
Отдельные непрерывные пространства, движок SkyXEngine

После валидации графа, возможно создание стартовых вершин для генерации новых пространств.

Ручная правка графа

Ручная правка сгенерированного графа – процесс, при котором дизайнер уровней вносит правки в сгенерированный граф для более точной навигации по нему. Рассматривая в качестве графа AI сетку, можно выделить следующие правки:

  • изменение высоты вершин, как в единичном варианте так и в массовом (выборочном)
  • изменение параметров вершин (к примеру проходимость, опасность и так далее)
  • создание новых вершин, а также связка пространств
  • удаление лишних вершин

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

  • соединение пространств
  • удаление соединений пространств

Заключение

В целом, абстрактно процесс преобразования игрового уровня в пространство для навигации, можно описать так:

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

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

Поделиться:

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

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

*