ИССЛЕДОВАНИЕ ТЕХНОЛОГИЙ И АЛГОРИТМОВ ПРОЦЕДУРНОЙ ГЕНЕРАЦИИ В ТРЕХМЕРНОЙ ГРАФИКЕ

RESEARCH OF TECHNOLOGIES AND ALGORITHMS OF PROCEDURAL GENERATION IN THREE-DIMENSIONAL GRAPHICS

Daniyar Mukhametkaliev

master student, faculty of "computer systems and professional education ", Kazakh Agrotechnical University named after S. Seifullin,

Republic of Kazakhstan, Nur-Sultan

Zhanat Kenzhebaeva

Scientific Supervisor, Candidate of Technical Sciences, Acting Associate Professor of the Computer Engineering and Software Department, Kazakh Agrotechnical University named after S. Seifullin,

Republic of Kazakhstan, Nur-Sultan

АННОТАЦИЯ

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

ABSTRACT

The article provides an overview of several of the most relevant methods of procedural content generation that can be used to generate rooms and levels in video games, their features and recommended applications are outlined.

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

Keywords: procedural content generation, levels, Dungeon Generation, cellular automata.

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

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

Основные задачи алгоритма процедурной генерации:

• Генерация уникальных игровых комнат.
• Полученные уровни должны быть сбалансированы и проходимы.
• Игровая комната должна быть интуитивно понятной.

Каждая игровая комната имеет свой набор функций. К ним относятся структура, внешний вид и содержание. Однако форма комнаты, ее размер, местонахождение и взаимосвязь с другими комнатами одинаковы для всех игр.

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

Генерация подземелий

Генерация подземелий — первый пример процедурной генерации уровней в играх: в Rogue и Beneath Apple Manor используется создание нового уровня, состоящего из ряда комнат, соединенных коридорами, окруженными каменными стенами. Есть два основных подхода к созданию подземелий: сначала разместить комнаты, а затем попытаться соединить их коридорами; или разместите коридоры, используя алгоритм генерации лабиринта, затем объедините секции лабиринта, чтобы сформировать комнаты.

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

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

Метод «Походки пьяницы»

Метод «Походки пьяницы» (Drunkard walk) – одна из вариаций метода «Случайной походки» (Random walk). Он получил свое название благодаря ошеломляющим узорам, которые он создает.

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

Алгоритм заключается в следующем:

• Выбирает случайную точку на заполненной сетке и помечает ее пустой.
• Затем выбирается случайное кардинальное направление (N, E, S, W).
• Происходит движение в этом направлении и помечает точку пустой, если она уже не была пустой.

    Повторяет шаги 2-3, пока не очистится столько решеток, сколько нужно. Метод «Походки пьяницы» гарантирует отсутствие изолированных пустых областей – из каждой точки комнаты можно будет добраться в любую другую точку на карте.

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

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

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

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

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

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

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

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

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

1. Procedural Content Generation Wiki [Electronic resource]/ Интернет-ресурс. – Режим доступа: www/ URL: pcg.wikidot.com.
2. Procedural Map Generation [Electronic resource]/ Интернет-ресурс. – Режим доступа: www/ URL: https://www.gridsagegames.com/blog/2014/06/procedural-map-generation.
3. Drunken Master cave generation [Electronic resource]/ Интернет-ресурс. – Режим доступа: www/ URL: https://forums.roguetemple.com//index.php?topic=4128.0.
4. Generate random cave levels using cellular automata [Electronic resource]/ Интернет-ресурс. – Режим доступа: www/ URL: https://gamedevelopment.tutsplus.com/tutorials/generate-random-cave-levels-using-cellular-automata—gamedev-9664.