Вивденко Владислав Сергеевич

Реферат по теме выпускной работы

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования, планируемые результаты
• 3. Обзор исследований и разработок
• 3.1 Обзор международных источников
• 3.2 Обзор национальных источников
• 3.3 Обзор локальных источников
• 4. Обзор актуальных методов процедурной генерации комнат в видеоиграх
• Выводы
• Список источников

Введение

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

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

1. Актуальность темы

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

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

2. Цель и задачи исследования, планируемые результаты

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

Основные задачи работы:

1. Исследование доступных методов и алгоритмов процедурной генерации контента, их базовых принципов и областей применения.
2. Отбор наиболее универсальных и гибких методов, которые находят широкое применение и удобны в использовании
3. Совершенствование выбранных методов, включение в их работу большего числа параметров для получения более точных результатов
4. Реализация методов с учетом универсальных входных/выходных данных
5. Разработка интерфейса для взаимодействия с полученной библиотекой методов

3. Обзор исследований и разработок

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

3.1 Обзор международных источников

В международном сообществе тема процедурной генерации весьма популярна. Регулярно появляются новые материалы, а большинство работ, которые можно первыми найти в сети Интернет – опубликованы совсем недавно, в последние несколько лет.

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

Большая часть материалов является англоязычными, однако статьи также активно переводятся на русский язык. Крупнейшим ресурсом, целиком посвященным процедурной генерации, является Procedural Content Generation Wiki[1] - Вики-сайт, на котором можно найти большое количество статей, алгоритмов и их описаний, различных пример использования. Однако ресурс последние годы почти перестал обновляться и некоторая его информация может быть неактуальна.

Детальный разбор текущего положения процедурной генерации в игровой индустрии, выполняемые ею задачи и ее потенциал представлены в цикле статей The Death of the Level Designer: Procedural Content Generation in Games[2], автор - Andrew Doull

«Procedural Content Generation in Games»[3] – книга, полностью посвященная применению процедурной генерации в играх.

Подробное руководство по созданию полных игровых миров с помощью процедурной генерации можно найти в статье «Procedural Generation of Villages on Arbitrary Terrain»[4], где рассматривается разработка алгоритма для создания небольшого виртуального поселения.

3.2 Обзор национальных источников

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

Единственная найденная научная работа, в которой подробно рассматривалась процедурная генерация контента в играх принадлежит М.Г. Меженину - «Обзор систем процедурной генерации игр».[5]

В статье «Процедурная генерация уровней»[6] пошагово рассматриваются несколько алгоритмов генерации помещений, выявляются их области применения.

«Процедурная генерация в Distrust»[7] является авторской статьей от разработчика игры Distruct, в которой описан ход разработки процедурной генерации для проекта.

Несколько значимых случаев применения процедурной генерации в известных игровых проектах рассмотрено в статье «7 примеров использования процедурной генерации в играх»[8].

3.3 Обзор локальных источников

В рамках ДонНТУ тема процедурной генерации окружения раскрыта очень поверхностно.

Единственная работа, в которой рассматривалось процедурное создание графических эффектов, была представлена Лунтовской А.А. «Средства разработки динамического игрового окружения для mmorpg игр»[9]. В ней процедурная генерация применялась для строго поставленной задачи разработки системы генерации динамических изображений с использованием шейдерной графики.

4. Обзор актуальных методов процедурной генерации комнат в видеоиграх

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

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

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

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

Перед алгоритмом процедурной генерации уровня ставятся следующие задачи:

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

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

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

Метод двоичного разбиения пространства

Метод двоичного разбиения пространства основывается на структуре, называемой BSP деревом.

Двоичное разбиение пространства (binary space partitioning) – метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом[11].

Входными данным для алгоритма являются общий размер уровня и минимальный размер ожидаемых комнат. Вся площадь уровня принимается за один лист BSP-дерева, который случайным образом делится на две части. Эти части становятся листьями в следующем уровне дерева (см. рис. 1). Алгоритм выполняется рекурсивно для каждого нового листа до тех пор, пока его размер не окажется ниже заданного минимального порога.

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

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

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

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

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

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

1. Каждая точка уровня объявляется «стеной» - непроходимой областью

2. На площади уровня выбирается случайная точка – точка начала. Она отмечается как «пол» - проходимая область

3. Выбирается случайное направление движения.

4. Курсор делает шаг в выбранном направлении, его новая точка расположения отмечается как «пол»

5. Шаги 3-4 повторяются до тех пор, пока не будет закрашено заданное количество точек.

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

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

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

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

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

Алгоритм, который основывается на клеточном автомате, начинает свою работу с того, что случайным образом объявляет каждую точку уровня «стеной» либо «полом». Таким образом получается стартовое состояние клеточного автомата. Соседями каждой точки считаются 8 смежных с ней точек. После этого начинается его итерационный процесс, который определяется следующими правилами:

- точка остается стеной, если она была стеной и четыре ее соседние точки – стены;

- точка становится стеной, если она была полом, а пять ее соседей – стены.

Таким образом, после нескольких итераций, образуются комнаты.

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

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

Выводы

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

Список источников

1. Procedural Content Generation Wiki [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://www.pcg.wikidot.com. – Загл. с экрана
2. The Death of the Level Designer: Procedural Content Generation in Games [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://roguelikedeveloper.blogspot.com/2008/01/death-of-level-designer-procedural.html - Загл. с экрана
3. Procedural Content Generation in Games [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://pcgbook.com/ - Загл. с экрана
4. Procedural Generation of Villages on Arbitrary Terrain [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://link.springer.com/article/10.1007%2Fs00371-012-0699-7- Загл. с экрана
5. Меженин М.Г. Обзор систем процедурной генерации игр / М.Г. Меженин / Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2015, том 4, выпуск 1, с. 5–20
6. Процедурная генерация уровней [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/post/418685/- Загл. с экрана
7. Процедурная генерация в Distrust [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/post/333692/- Загл. с экрана
8. 7 примеров использования процедурной генерации в играх [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/company/ua-hosting/blog/275195/- Загл. с экрана
9. Средства разработки динамического игрового окружения для mmorpg игр [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://masters.donntu.ru/2015/fknt/luntovskaya/diss/index.htm- Загл. с экрана
10. Procedural Map Generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://www.gridsagegames.com/blog/2014/06/procedural-map-generation. - Загл. с экрана.
11. 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. - Загл. с экрана.
12. Drunken Master cave generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://forums.roguetemple.com//index.php?topic=4128.0. - Загл. с экрана.
13. 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. - Загл. с экрана.