УДК 004

Способы процедурной генерации карт в видеоиграх

Копылова Яна Антоновна – студент направления Прикладной информатики Российского технологического университета Института информационных технологий.

Матвеев Владимир Евгеньевич – студент направления Прикладной информатики Российского технологического университета Института информационных технологий.

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

Ключевые слова: процедурная генерация, видеоигры, bsp-дерево, алгоритм туннелирования, клеточные автоматы, муравей Лэнгтона, шум перлина, симплекс шум.

Во многих играх используется случайная генерация для создания игровых уровней и карт. Такой подход называется процедурной генерацией и для ее реализации существует множество различных способов. Методы, которые будут описаны далее, описаны со стороны создания двумерных карт, но могут быть применены и для генерации 3D миров.

  1. BSP-деревья

Первый и один из самых простых алгоритмов - BSP-деревья (Binary Space Partitioning). Данный алгоритм заключается в рекурсивном разделении областей на две части. Изначально предполагается, что есть единое, в играх зачастую прямоугольное, пространство, которое разделяется по следующему общему алгоритму:

  • Выбирается случайная точка внутри области;
  • Через точку проводится либо вертикальная, либо горизонтальная прямая, образуя две новые области;
  • Аналогичные действия повторяются в каждой из областей.

Очевидно, как и в любом рекурсивном алгоритме, при построении BSP-дерева есть несколько условий остановки, которые могут отличаться в зависимости от реализации. Наиболее частыми условиями являются количество шагов рекурсии, общее количество сгенерированных областей, минимальный размер области, причём условия могут использоваться как самостоятельно, так и в комбинации друг с другом.

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

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

Пример карты, сгенерированной при помощи BSP-дерева приведен на Рисунке 1.

Рисунок3

Рисунок 1. Карта, сгенерированная при помощи BSP-дерева

  1. Туннелирование

Следующий несложный алгоритм - алгоритм туннелирования. Основная идея такого подхода заключается в “пробивании” туннелей и комнат в полностью заполненном пространстве. В своей простейшей реализации алгоритм редко приводит к хорошим результатам, так как большинство карт получаются сильно однообразными и линейными: каждая из комнат обладает одним входом и максимум одним выходом, что приводит к одинаковости при игре.

Решение вышеописанной проблемы предложил разработчик Билли Брандстеттер в [1]. Основная идея улучшения заключается в том, что при создании туннелей у прохода по уже “открытым” клеткам и по “закрытым” клеткам разная, что чаще всего приводит к тем же результатам, что и стандартный алгоритм (так как цена прохода по “открытой” клетке ниже, чем по “закрытой”), но иногда генерируются дополнительные туннели, создающие дополнительные ответвления или циклы в итоговой карте. Результат генерации методом туннелирования приведен на рисунке 2.

Рисунок4

Рисунок 2. Пример генерации карты методом туннелирования

  1. Клеточные автоматы

Следующий раздел алгоритмов генерации можно объединить в группу клеточных автоматов. Основной идеей таких алгоритмов является симуляция “живого” организма - клетки, определяющей к какому типу относится та или иная ячейка карты.

Одним из примеров клеточного автомата является муравей Лэнгтона, который проходит по общей области и назначает одну из категорий для каждой ячейки данной клетки. Алгоритм может быть описан следующим образом:

  • Муравей начинает в случайной точке карты;
  • Муравей проверяет текущее состояние клетки и состояния соседних клеток;
  • На основе проверенной информации муравей назначает новое состояние для текущей клетки;
  • В зависимости от назначенного состояния муравей выбирает новое направление движения;
  • Алгоритм продолжает пока муравей не пройдет по всей карте или пока не выполнит определенное количество шагов.

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

Рисунок5

Рисунок 3. Карта, сгенерированная муравьем Лэнгтона

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

  1. Шумы

Для генерации карт используются также алгоритмы из категории “шумов”. Шум - понятие из компьютерной графики, описывающее псевдослучайные алгоритмы для генерации текстур. Такие алгоритмы позволяют получить бесконечные области, состоящие из значений от -1 до 1, после чего данные числа могут использоваться для получения карты уровня (например, все значения ниже -0.6 - заполненные пространства, а остальные - пустые). Существует множество различных шумов и далее в статье будут рассмотрены наиболее популярные варианты реализации.

4.1 Случайный шум

Самый простой шум - случайный, основывающийся на том, что случайным точкам плоскости присваиваются случайные значения от -1 до 1, после чего значения во всех остальных точках вычисляются при помощи линейной интерполяции относительно сгенерированных “ключевых” точек. Недостатком такого алгоритма является генерация слишком непредсказуемых результатов, которые редко позволяют получить подходящие карты. Пример случайного шума приведен на рисунке 4.

Рисунок6

Рисунок 4. Пример случайного шума

4.2 Шум Перлина

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

Рисунок7

Рисунок 5. Пример генерации шума Перлина

4.3 Симплекс шум

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

Рисунок8

Рисунок 6. Пример генерации симплекс шума

  1. Вывод

В данной статье были рассмотрены различные алгоритмы для процедурной генерации карт в видеоиграх. Рассмотренные алгоритмы нацелены на генерацию различных шаблонов и могут использоваться как для генерации как 2D, так и 3D пространств. Каждый из рассмотренных методов может дополняться и комбинироваться с другими для получения более разнообразных и интересных для игрока результатов.

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

  1. Procedural Dungeon Generation – Текст : электронный // Wax Project: [сайт]/ – 2020. – URL: https://goo.su/GGwuZft (дата обращения: 01.01.2024).
  2. Procedural Generation of Computer Game Maps – Текст : электронный // Baeldung: [сайт]/ – 2023. – URL: https://www.baeldung.com/cs/gameplay-maps-procedural-generation (дата обращения: 03.01.2024).
  3. Процедурная генерация и с чем ее едят – Текст : электронный // DTF: [сайт]/ – 2023. – URL: https://dtf.ru/gamedev/1895392-procedurnaya-generaciya-i-s-chem-ee-edyat (дата обращения: 03.01.2024).
  4. Langton’s Ant – Текст : электронный // Langtonsant: [сайт]/ – 2015. – URL: http://www.langtonant.com (дата обращения: 04.01.2024).
  5. Шум Перлина (Perlin Noise) – Текст : электронный // Habr: [сайт]/ – 2012. – URL: https://habr.com/ru/articles/142592/ (дата обращения: 05.01.2024).