ПРОЦЕСС ПРЕОБРАЗОВАНИЯ ИГРОВОГО УРОВНЯ В ДИСКРЕТИЗИРОВАННОЕ ПРОСТРАНСТВО ДЛЯ НАВИГАЦИИ

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

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

Стартовая вершина дискретизации – это первая вершина в будущем графе дискретизированного уровня, которая устанавливается дизайнером уровней. Она сообщает программе, откуда надо начинать просчеты деления  уровня.  Стартовая вершина на непрерывном дискретном пространстве может быть только одна [2]. Она ставится на той местности игрового мира, которая будет доступна для «живых» игровых объектов.

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

Как правило, после постановки стартовой вершины следует циклический процесс генерации соседних вершин для всех вершин, «соседи» которых еще не просчитаны. Генерация графа для навигации – это процесс, выполняющий генерацию всех соседних вершин для текущей анализируемой, и повторяющийся до тех пор, пока все вершины графа не приобретут соседние вершины либо их генерация будет невозможной. Именно таким образом программа может понять «куда сможет зайти живой игровой объект», исследуя каждый доступный уголок игрового мира. Данный процесс имеет настройки ограничения, как общего, так и частного (для каждой вершины) пространства, а также допустимые параметры наклонов и иных расхождений. На Рис.2 по центру расположена текущая вершина, все лежащие рядом с ней вершины являются соседними, то есть к ним можно перейти из текущей точки, а выделенные вершины (не считая текущей) являются прямыми соседями [3].

Рисунок 2. AI сетка движка SkyXEngine

После генерации следует валидация сгенерированного. Валидация/проверка сгенерированного графа для навигации – это процесс проверки соответствия графа, минимальным требованиям для осуществления навигации по нему. Сюда могут входить:

1. проверка отсутствия неинициализированных соседей (пометка о невозможности инициализации не в счет);
2. удаление вершин, не имеющих соседей, и как следствие по таким вершинам невозможна навигация;
3. идентификация непрерывных пространств/слоев, в случае наличия условно «не цельного» графа;
4. иные проверки.

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

1. изменение высоты вершин (по отдельности);
2. изменение дополнительных параметров вершин;
3. создание новых вершин, в том числе и связка пространств;
4. удаление не нужных/лишних вершин.

Рисунок 3. Отдельные непрерынвные пространства, движок SkyXEngine

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

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

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

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

Список литературы:

1. Code4Life [Электронный ресурс] // Блог о программировании, проектах и жизни программистов – URL: https://code4life.ru (дата обращения: 16.11.2017)
2. GameDev.ru [Электронный ресурс] // Разработка игр – URL: http://www.gamedev.ru (дата обращения: 23.11.2017)
3. SkyXEngine [Электронный ресурс] // Графический 3D движок с real-time рендером – URL: https://skyxengine.com (дата обращения: 11.11.2017)