В статье дан обзор нескольких самых актуальных методов процедурной генерации контента, которые могут быть использованы для генерации комнат и уровней в видеоиграх, обозначены их особенности и рекомендуемые области применения. Рассмотрены их недостатки и определены пути доработки.
Ключевые слова: разработка игр, процедурная генерация контента, уровни, BSP-деревья, клеточные автоматы
Введение
Процедурная генерация контента – одно из актуальных и быстроразвивающихся направлений в сфере разработки компьютерных игр. Разработки в этой области могут позволить значительно сократить расходы на производство игр, а также повысить качество продукта путем создания более привлекательного игрового наполнения и механик. Однако этот подход требует тщательной обдуманного и проработанного применения, так как, будучи выполнен некачественно, способен значительно испортить ценность игры. Успешное применение процедурной генерации контента требует широкую осведомленность в наборе доступных инструментов и их тонкостей. Эта статья посвящена обзору методов процедурной генерации, которые позволяют решить одну из самых популярных задач в этой области – создание игровых комнат и уровней. В ней рассматриваются одни из самых оптимальных алгоритмов, которые подходят для выполнения этой задачи, а также их тонкости и области применения.
Процедурная генерация комнат
Процедурная генерация подразумевает автоматическое создание наполнения игрового мира, к которому могут относиться всевозможные игровые объекты, такие как уровни, комнаты, предметы, противники, инструменты игрока. С помощью алгоритмов генерации могут задаваться как внешний вид и свойства этих объектов, так и их расположение и даже поведение. Кроме того, процедурно-сгенерированными могут быть текстуры, музыкальное сопровождение и сюжетные линии.
Процедурная генерация контента позволяет значительно снизить затраты на разработку компьютерных игр, позволяя с помощью одной процедуры создавать неограниченное количество различных объектов. Кроме того, генерация может происходить динамически во время игрового процесса, создавая для каждого игрока уникальные ситуации и неповторимый опыт при каждой новой попытке, значительно повышая интерес к игре.
Однако такой подход к разработке требует точности и детально проработки алгоритмов процедурной генерации. Контент, созданный таким образом, должен быть мало отличим от созданного вручную, чтобы не вызвать негативные впечатления.
Одной из первых задач, с решением которых отлично справляются алгоритмы процедурной генерации контента, стало построение игрового уровня и расположение комнат[1]. Понятие игрового уровня и комнат широко используется в компьютерных играх самых различных жанров. Особенно актуальна задача процедурной генерации уровней стоит в играх тех жанров, в которых особенностью является то, что игроку предстоит множество раз повторно начинать игру сначала, начиная с первого уровня. Для того, чтобы этот процесс не стал монотонным, было предложено каждый раз создавать новый тип уровня, меняя в нем расположение комнат, предметов и противников. Таким образом, игрок никогда не мог быть уверенным в том, что ждет его впереди, даже после нескольких попыток.
Перед алгоритмом процедурной генерации уровня ставятся следующие задачи:
- создание уникальных наборов комнат;
- полученный уровень должен быть сбалансированным и проходимым;
- комнаты должны располагаться естественным, интуитивно-понятным способом.
Комнаты в каждой отдельной игре будут обладать своим набором свойств, которые определят ее уникальность. Среди них могут быть ее структура, внешний вид, наполнение. Однако среди всех игр у комнат можно выделить такие обобщенные черты: форма, размер, расположение на карте, связь с другими комнатами.
Каждый алгоритм процедурной генерации будет включать в себя создание набора свойств из этого списка, и далее варьироваться в зависимости от особенностей игры[2]. Разные алгоритмы позволяют создавать комнаты, которые больше или меньше подходят под заданные условия игры. Так, например, структура уровня, действие которого происходит в пещерах под землей, должна значительно отличаться от уровня, расположенного в городской среде. Таким образом, для разных целей будут уместны разные алгоритмы, которые лучше справляются с построением уровней, структура которых ближе к определенным игровым реалиям.
Метод двоичного разбиения пространства
Метод двоичного разбиения пространства основывается на структуре, называемой BSP деревом.
Двоичное разбиение пространства (binary space partitioning) – метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом[3].
Входными данным для алгоритма являются общий размер уровня и минимальный размер ожидаемых комнат. Вся площадь уровня принимается за один лист BSP-дерева, который случайным образом делится на две части. Эти части становятся листьями в следующем уровне дерева (см. рис. 1). Алгоритм выполняется рекурсивно для каждого нового листа до тех пор, пока его размер не окажется ниже заданного минимального порога.
Рисунок 1 – Схема выполнения алгоритма двоичного разбиения пространства
Метод двоичного разбиения комнат является простым и удобным в реализации. Он позволяет быстро разбить заданную изначально фигуру на необходимое количество равномерно распределенных меньших фигур, не оставляя между ними пустых пространств и создавая геометрически строгие комнаты.
Уровень, полученный с помощью такого алгоритма, хорошо подойдет там, где есть необходимость изобразить искусственно-созданный ландшафт. Это может быть городская среда или этаж отдельного помещения (см. рис. 2).
Базовый алгоритм не предполагает создания коридоров – переходов между комнатами. Эту задачу можно выполнить вручную, либо дополнить алгоритм генерации.
Рисунок 2 – Пример двоичного разбиения пространства
Метод «Походки пьяницы»
Метод «Походки пьяницы» (Drunkard walk) – одна из вариаций метода «Случайной походки» (Random walk). Он получил свое название за соответствующий хаотичный узор, который образуется в результате его работы.
Метод основывается на перемещении курсора, который закрашивает область комнаты, двигаясь в случайном направлении[4]. Он описывается следующими этапами:
1. Каждая точка уровня объявляется «стеной» - непроходимой областью
2. На площади уровня выбирается случайная точка – точка начала. Она отмечается как «пол» - проходимая область
3. Выбирается случайное направление движения.
4. Курсор делает шаг в выбранном направлении, его новая точка расположения отмечается как «пол»
5. Шаги 3-4 повторяются до тех пор, пока не будет закрашено заданное количество точек.
Метод «Походки пьяницы» гарантирует отсутствие изолированных пустых областей – из каждой точки комнаты можно будет добраться в любую другую точку на карте.
Для создания более естественных структур комнат, алгоритм предполагает несколько улучшений. Так, на каждое возможное направление движения выставляются весовые коэффициент, таким образом, чтобы курсор смещался к центру уровня, а не упирался в границы. Кроме того, на следующей итерации можно задать больший коэффициент для предыдущего направления – таким образом между комнатами появятся более выраженные коридоры.
Данный алгоритм хорошо передает образование естественных, природных структур. Он хорошо подходит для создания уровней в пещерах либо джунглях (см. рис. 3).
Рисунок 3 – Итог работы алгоритма Походки пьяницы
Клеточные автоматы
Клеточный автомат – набор клеток, образующих некоторую периодическую решетку с заданными правилами перехода, определяющими состояние клетки в следующий момент времени через состояние клеток, находящимися от нее на расстоянии не больше некоторого, в текущий момент времени. Как правило, рассматриваются автоматы, где состояние определяется самой клеткой и ближайшими соседями[5].
Алгоритм, который основывается на клеточном автомате, начинает свою работу с того, что случайным образом объявляет каждую точку уровня «стеной» либо «полом». Таким образом получается стартовое состояние клеточного автомата. Соседями каждой точки считаются 8 смежных с ней точек. После этого начинается его итерационный процесс, который определяется следующими правилами:
- точка остается стеной, если она была стеной и четыре ее соседние точки – стены;
- точка становится стеной, если она была полом, а пять ее соседей – стены.
Таким образом, после нескольких итераций, образуются комнаты.
В результате работы алгоритма могут образовываться изолированные области, их обработку необходимо проводить вручную либо отдельным алгоритмом.
Конечный результат содержит пустые области с пологими, естественно выглядящими стенами, без строгого деления на «комнаты» и «коридоры». Такого рода уровень хорошо отражает ландшафт естественной среды (см. рис. 4).
Рисунок 4 – Итог работы клеточного автомата
Выводы
Алгоритмы процедурной генерации контента позволяют создавать неограниченное количество разнообразных и качественных структур уровней и комнат. Гибкие настройки генерации, после корректировок, позволяют добиться желаемого разработчиком внешнего вида уровня. Для разных типов окружения, которое передает игровой мир, будут уместны различные алгоритмы и параметры генерации. Осведомленность и разумное применение различных методов генерации позволяют создавать высококачественное наполнение видеоигр с минимальными затратами ресурсов. Однако, обобщенных алгоритмов недостаточно для создания конкурентно-способных продуктов, и каждый алгоритм нуждается в доработках для достижения лучших результатов. Информация данной статьи может быть использована для создания более узкоспециализированных алгоритмов процедурной генерации контента.
Литература
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. How to use BSP trees to generate game maps [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps—gamedev-12268. ¬– Загл. с экрана.
4. Drunken Master cave generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://forums.roguetemple.com//index.php?topic=4128.0. ¬– Загл. с экрана.
5. 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. ¬– Загл. с экрана.
V.S. Vivdenko, O.M. Kopytova Review of current methods for procedural generation of rooms in video games. The article provides an overview of several of the most relevant procedural content generation methods that can be used to generate rooms and levels in video games, identifying their features and recommended uses. Considered their shortcomings and identified ways to refine.
Keywords: game development, procedural content generation, levels, BSP-trees, cellular automata