WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«Кафедра ПМиК Допустить к защите зав. кафедрой: проф., д.т.н. Фионов А.Н. ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА Разработка и исследование алгоритма процедурной ...»

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Сибирский государственный университет телекоммуникаций и информатики»

(СибГУТИ)

Кафедра ПМиК

Допустить к защите

зав. кафедрой: проф., д.т.н.

______________________ Фионов А.Н.

ВЫПУСКНАЯ

КВАЛИФИКАЦИОННАЯ РАБОТА

БАКАЛАВРА

Разработка и исследование алгоритма процедурной генерации виртуальных пространств Пояснительная записка Студент Провоторов Р.С. /…………………/ Факультет ИВТ Группа ИП-211 Руководитель Ракитский А.А. / …………..……/ Новосибирск 2016 г.

Содержание ВВЕДЕНИЕ

1 ПРЕДМЕТНАЯ ОБЛАСТЬ

Проблемы при создании игровых уровней

1.1 Процедурная генерация виртуальных пространств............. 6 1.2 Плиточное (тайловое) представление уровней

1.3 Анализ существующих алгоритмов

1.4 Игровой движок

1.5 Постановка задания

1.6 2 ВЫБОР СРЕДСТВ РАЗРАБОТКИ

Программные средства

2.1 Языки программирования

2.2 3 ОПИСАНИЕ АЛГОРИТМА

4 РЕАЛИЗАЦИЯ АЛГОРИТМА

Программное представление уровня

4.1 Реализация алгоритма

4.2 Интеграция со средой редактора Unreal Engine 4................ 38 4.3 Демонстрационный проект

4.4 5 РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

В 2011 году в США видеоигры официально признали видом искусства[2]. Так, практически любая игра содержит в себе целое множество аспектов. Двумя фундаментальными из них является программный код и игровой контент. Действительно, даже в самом термине видеоигра закладываются понятия игры – как интерактивного и программируемого процесса – и видео – как визуальной обратной связи. В ряде случаев границы двух этих аспектов несколько стираются; так, с нынешними технологиями и программным обеспечением существует возможность делать игры без написания программного кода как такового. Помимо двух названных аспектов можно выделить и другие – к примеру, дизайн игры, игровой баланс, маркетинг и прочие.

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

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

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

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

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

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

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

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

Третья часть работы содержит в себе подробное описание построенного алгоритма на псевдокоде.

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

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

1 ПРЕДМЕТНАЯ ОБЛАСТЬ Проблемы при создании игровых уровней 1.1

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

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

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

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

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

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

–  –  –

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

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

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

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

Однако, при этом наблюдается и целый ряд преимуществ. Основное из них – это возможность получить практически бесконечное число различных игровых уровней, а вследствие этого и теоретически бесконечную реиграбельность. Начиная новую игру или переходя на новый уровень, игрок попадает в новое виртуальное пространство, точную копию которого он не видел ранее. Более того, реализовав алгоритм процедурной генерации, программист может считать, что все уровни для его игры готовы, если алгоритм обладает достаточной гибкостью. Редактируя некоторый набор параметров (задающих структуру уровня и/или его внешний вид), программист с помощью одного и того же алгоритма может сделать так, что, например, в начале игры игрок ходит по узким подземным помещениям, а в конце игры – по огромным абстрактным космическим кораблям.

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

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

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

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

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

Зачастую могут быть краевые случаи, шанс появления которых крайне мал, и предугадать появление которых во время разработки алгоритма генерации программисту не удалось. Так, в игре Heroes of Might and Magic III возможна относительно редкая ситуация, когда игрок оказывается полностью окруженным непреодолимыми ландшафтными препятствиями, что препятствует возможности прохождения игры.

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

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

Нередко в играх применяется комбинированный подход к созданию уровней. Например, в таких играх, как The Binding of Isaac, Ziggurat, Our Darker Purpose и многих других сначала вручную создается большой набор отдельных комнат, а затем уже процедурно выбираются некоторые из этих комнат и случайно располагаются на уровне, будучи соединенными коридорами. Пример комбинированного подхода приведен на рисунке 1.1.

Рисунок 1.1 – комбинированный подход в The Binding of Isaac: Rebirth

–  –  –

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

В рамках данной бакалаврской работы рассматривается плиточное представление уровней, также зачастую называемое тайловым[3] (от англ.

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

В самом простом случае двумерный тайловый уровень может задаваться массивом, в котором каждая ячейка занимает 1 бит и указывает, какой тайл находится в данных координатах: тайл стены (считается непроходимым) или же тайл пола. Обычно используется несколько более сложный подход, при котором в каждой ячейке хранится индекс типа тайла (например, при размере элемента массива в один байт большой уровень размера 1024х1024 тайлов занимает всего 1 МБ, и каждый элемент может принимать одно из 256 значений). При этом отдельно задается список всех возможных тайлов, для каждого из которых задается текстура или 3Dмодель.

На рисунке 1.2 приводится пример игры с использованием тайлового подхода к представлению уровней.

Рисунок 1.2 – Пример тайлового виртуального пространства Преимущество тайлового подхода – это простота структуры, задающей виртуальное пространство.

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

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

Анализ существующих алгоритмов 1.4

Алгоритм на основе BSP-дерева 1.4.1 Данный алгоритм имеет рекурсивную природу, хотя может быть реализован и в итеративном виде.

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

Далее процедура деления происходит для каждой из таких областей, в том числе и для их собственных подобластей. Процесс продолжается, пока размер каждой рассматриваемой области не станет слишком маленьким хотя бы по одной из осей[4]. К примеру, задается, что область может делиться только тогда, когда и ее ширина, и ее высота не менее 10 клеток, и при этом координата деления не может стоять ближе, чем на 5 клеток к области границы. Это гарантирует, что все конечные области будут иметь размер не менее, чем 3х3 клеток.

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

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

Далее внутри каждой конечной области создается комната случайного размера. Минимальный размер комнаты – 1х1, что коррелирует с минимальным размером области – 3х3 (т.е. комната занимает одну клетку, и она окружена восемью клетками стен). Максимальный размер комнаты – (Wx(H-2), где W – ширина данной области, а H – ее высота. Это гарантирует окруженность комнаты стенами.

Расположение комнаты внутри области также задается случайно, если сгенерированные ее размеры меньше, чем максимально допустимые для данной области размеры. Пусть верхний левый угол области начинается в координатах X0, Y0, а ее размеры – WxH клеток. Пусть полученные размеры комнаты – AxB, при этом 1 A (W-2), 1 B (H-2). Тогда координаты X1, Y1 верхнего левого угла комнаты будут случайно заданы следующим образом: X1 – в диапазоне от X0 + 1 до X0 + W – A – 1, а Y1 – в диапазоне от Y0 + 1 до Y0 + H – B – 1. На рисунке 1.3 приведен пример расставленных таким способом комнат.

–  –  –

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

–  –  –

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

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

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

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

Если M1 M2, то строится горизонтальный коридор, расположенный по вертикали в случайной координате в диапазоне от M1 до M2. Иначе же, если M1 M2, то здесь необходимо построить угловой (или Z-образный) коридор.

Минимум же самой области-родителя вычисляется как минимум минимумов областей-дочерей, а максимум, соответственно, как максимум максимумов.

–  –  –

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

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

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

Алгоритм в игре Wasteland Kings 1.4.2 В 2013 компания Vlambeer выпустила игру Wasteland Kings, в которой была реализована процедурная генерация двумерных тайловых уровней. На рисунке 1.6 приведен кадр из игры. Данная игра получила широкое дальнейшее развитие, и в 2015 году вышла ее обновленная версия под названием Nuclear Throne.

Рисунок 1.6 – Игра Wasteland Kings

Вскоре после выхода оригинальной игры на своем официальном сайте компания Vlambeer разместила статью о методе процедурной генерации уровней, реализованной в ней[5]. Рассмотрим его.

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

Сделав очередной шаг в выбранном направлении, червь создает в новых координатах тайл пола (если до этого пола там еще не было). При этом есть шанс создать не один тайл пола, а небольшой участок пола. Например, на некоторых уровнях игры на каждом шаге червя имеется шанс 50% создать участок размера 2х2 тайлов, или же шанс 11% создать участок 3х3. Варьируя шансы и размеры таких участков, можно задавать, насколько открытая в целом будет получаться местность (или наоборот закрытая и состоящая в основном из коридоров).

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

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

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

Площадь выражает общий размер доступного для игрока игрового пространства.

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

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

Алгоритм на основе клеточного автомата Жизнь 1.4.3 Рассмотрим сначала клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.

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

Распределение живых клеток в начале игры называется первым поколением. Далее на основе каждого предыдущего поколения рассчитывается новое.

Существует четыре правила, которым подчиняется каждая из клеток:

- Если у живой клетки менее двух соседей, она погибает;

- Если у живой клетки ровно 2 или 3 соседки, она остается живой;

- Если у живой клетки более трех соседей, она погибает;

- Если у мертвой клетки ровно 3 соседки, она оживает.

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

На основе игры Жизнь можно построить генератор случайных игровых уровней, если немного изменить правила. Каждая клетка игрового пространства изначально заполняется случайным образом. Оптимальным является задать шанс появления живой клетки (будущей клетки стены) не равным шансу появления мертвой (будущей клетки пола), а чуть меньше, например, 40%[6].

Изменим правила следующим образом: клетка становится живой, если она была живой, и не менее 4 ее соседок живы, или же если она была мертвой, и не менее 5 ее соседок живы. С помощью этих правил на каждой итерации жизни клеток постепенно устраняется шум, контуры стен сглаживаются, и уровень постепенно приобретает пещерную форму. Пример данного процесса изображен на рисунке 1.7. Рекомендуется проводить не менее трех итераций; в большинстве случаев к пятому поколению уровень входит в состояние статической конфигурации или близко подходит к нему.

Рисунок 1.7 – Первые три поколения сгенерированного пространства

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

Структура уровня получается сглаженной и приятной на вид.

Главным недостатком алгоритма является отсутствие гарантии связности графа клеток. На рисунке 1.7 можно заметить, что верхняя правая часть уровня не связана со всей остальной областью. Существует как минимум два способа решения данной проблемы. Первое из них гласит, что можно взять любую точку пола на уровне, запустить алгоритм заливки области и пометить все вершины, принадлежащие данной области. Затем все остальные точки пола, которые не были помечены, объявляются изолированными от основного уровня и превращаются в стены. Если число помеченных вершин, разделенное на произведение ширины и высоты всего пространства, больше некоторой константы (например, 0.4), то уровень считается успешно сгенерированным, а в противном случае генерация уровня происходит полностью заново, пока данное условие не выполнится. Это может показаться неоптимальным, но при большом размере пространства практически всегда изначально выбирается точка, принадлежащая наибольшей области; при малом же размере пространства вероятность получить неудовлетворительный уровень выше, но и генерировать малые уровни менее затратно по времени. Второе возможное решение включает в себя многократное использование алгоритма заливки, чтобы пос троить множество всех связных областей на уровне. Затем с помощью системы непересекающихся множеств (и, возможно, с помощью алгоритмов поиска кратчайшего пути) отдельные области соединяются между собой коридорами. Данный процесс уже более сложен, а кроме того, прямые и ровные коридоры могут выглядеть искусственными среди пещер необычных и случайных форм.

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

Данный алгоритм порождает уровни исключительно пещерного вида.

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

–  –  –

Игровой движок – совокупность программных продуктов и/или библиотек, являющихся центральной частью архитектуры одной или более видеоигр. Игровой движок представляет собой технологический фундамент, обеспечивающий базовые возможности, необходимый для работы игры. К функционалу игровых движков относят систему рендеринга (визуализации), физический движок, воспроизведение звука и музыки, управление искусственным интеллектом и анимациями персонажей, сетевой код, управление памятью и многие другие системы[7].

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

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

Термин игровой движок появился в 1990-ых годах с ростом популярности таких игр, как Doom и Quake. Фундаментальный программный функционал (рендеринг, физический движок и т.д.) стал отделяться от логики конкретной игры, что позволило разработчикам движков использовать их для создания нескольких игр на одном и том же фундаменте, а также лицензировать их сторонним компаниям.

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

используя язык(и) и/или библиотеки, предоставленные движком, программист пишет код, который может быть скомпилирован и запущен на многих платформах (таких, как Windows, Linux, Mac OS X и т.д.) без учета особенностей архитектуры каждой из них. Точный список поддерживаемых платформ определяется самим игровым движком. Кроме того, некоторые из них идут в комплекте с набором программных средств (например, редактором игровых уровней и т.д.), которые также уменьшают требуемый объем работы и оптимизируют производственный процесс.

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

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

Постановка задания 1.6

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

2 ВЫБОР СРЕДСТВ РАЗРАБОТКИ Программные средства 2.1

2.1.1 Unreal Engine 4 Unreal Engine – игровой движок, разрабатываемый компанией Epic Games. Первая версия движка была выпущена в 1998 году вместе с игрой Unreal, созданной на нем. С тех пор движок прошел через множество изменений и улучшений, с его помощью рядом компаний было выпущено множество игр разнообразных жанров и на разных платформах, а его наиболее поздняя на сегодняшний день версия – Unreal Engine 4 – активно поддерживается компаний Epic Games.

Unreal Engine 4 представляет собой совокупность программ, редакторов, огромного набора библиотек, подробной документации, множества уроков по разработке и использованию движка, а также широкого спектра как платного, так и бесплатного контента, готового к интегр ации в пользовательских проектах. Работа с движком возможна на платформах Microsoft Windows, Mac OS X и Linux.

В свою очередь проекты, созданные на нем, поддерживают практически все популярные платформы:

- Microsoft Windows;

- Mac OS X;

- Linux;

- SteamOS;

- Xbox One;

- PlayStation 4;

- Xbox One;

- iOS;

- Android;

- Oculus Rift;

- HTML5;

- и другие[8].

Данный движок обладает рядом возможностей для разработки самых разнообразных игр. Как и некоторые другие движки, Unreal Engine 4 включает в себя систему рендеринга, физический движок, воспроизведение звука, работу с моделями, текстурами, анимациями, менеджмент игровых ресурсов и управление памятью, сетевой код и иные базовые аспекты. Среди его особенностей можно перечислить поддержку разрушаемых объектов, оптимизированную и реалистичную обработку столкновений между высоким числом объектов сложной формы, динамическое освещение и множество эффектов постобработки, редактирование игры непосредственно во время ее выполнения, систему искусственного интеллекта, поддержку сложных ландшафтов, систему материалов как совокупностей текстур и шейдеров, иерархию объектов в игровом пространстве и многое другое[9].

Основная часть работы с Unreal Engine 4 происходит в его главном редакторе. Внешне он выглядит как редактор уровней, которым он полноценно и является. Непосредственно внутри редактора можно мгновенно запустить и протестировать текущий уровень игры. В него же входит менеджер существующих на уровне объектов, область редактирования этих объектов, браузер доступного для игры контента, меню настройки проекта и другие элементы интерфейса. Из главного окна запускаются дополнительные редакторы – материалов, скриптов, анимаций и т.д.

Логика игры программируется на движке UE4 с помощью одного из двух способов – с помощью Blueprints Visual Scripting, или же на языке С++.

С помощью Unreal Engine 4 можно как легко и быстро создавать рабочие прототипы игр, так и разрабатывать большие игры, не уступающие по качеству самым современным стандартам.

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

Изначально доступ к движку Unreal Engine 4 требовал подписку в размере $19 в месяц, но с марта 2015 года движок стал бесплатен для скачивания и использования в полном объеме для всех пользователей. На данный момент схема оплаты следующая: когда доход с игры или в целом программного продукта, построенного на движке Unreal Engine 4, превышает $3000 за квартал (т.е. три месяца), то разработчик обязуется платить 5% с последующей прибыли за данный квартал. Здесь имеется в виду общая прибыль; так, например, если разработчик получает $10 с продажи игры в App Store, то плата в пользу Epic Games составит $0.50 (5% от $10), хотя чистая прибыль составила бы $7 после того, как Apple взымет свой собственный налог в размере $3 (30% от $10) взымает компания Apple. Налог взымается отдельно по каждому программному продукту, а также отдельно по каждому кварталу. Иными словами, если игра не приносит за три месяца такого дохода или более не продается, то не требуется платить за пользование движком.

2.1.2 Microsoft Visual Studio 2015 (14.0) Microsoft Visual Studio – серия продуктов от компании Microsoft, главным образом включающий среду разработки программного обеспечения, а также ряд других инструментов. Среди этих инструментов можно отметить IntelliSense – технологию автодополнения, которая дописывает название функции при вводе начальных букв, а также обеспечивает доступ к документации, устраняет неоднозначности в именах функций, методов, полей, переменных[10].

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

Движок Unreal Engine 4 интегрирован с Visual Studio. До версии 4.9 (включительно) движок работал с версией Visual Studio 2013. Начиная с 4.10 и далее, он перешел на версию Visual Studio 2015. Использование Visual Studio как редактора кода для разработки на движке Unreal Engine 4 в целом не является обязательным требованием, однако имеет ряд преимуществ в силу интеграции и официальной поддержки движком.

Visual Studio 2015 предоставляется в трх редакциях:

- Community Edition – бесплатная версия. Дается 30-дневный пробный период, после которого пользователю необходимо будет зарегис трироваться на сайте Microsoft, чтобы продолжить пользоваться продуктом, но регистрация также открыта для всех и бесплатна.

- Professional Edition – платная версия для небольших проектов;

- Enterprise Edition – более дорогая версия для крупных проектов.

Редакции Community Edition достаточно для полноценной работы с движком Unreal Engine 4. Ее лицензия гласит, что разрешается бесплатно использовать ее и даже продавать программные продукты, написанные с ее помощью, если работа ведется не полноценным предприятием (а, например, индивидуальным разработчиком или небольшой командой до пяти программистов). Подробней с лицензией и функционалом Visual Studio 2015 Community Edition можно ознакомиться на официальном сайте компании Microsoft[11].

В рамках бакалаврской работы Visual Studio 2015 Community Edition была выбрана как среда разработки согласно указанным причинам.

Языки программирования 2.2

2.2.1 Blueprints Visual Scripting Blueprints Visual Scripting – это визуальная система скриптов в Unreal Engine 4, позволяющая создавать внутреннюю архитектуру и логику игры без написания программного кода.

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

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

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

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

Описание языка C++ 2.2.2 С++ – компилируемый строго типизированный язык программирования общего назначения. Язык поддерживает разные парадигмы программирования: процедурную, обобщнную, функциональную.

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

Нововведениями C++ в сравнении с C являются:

• поддержка объектно-ориентированного программирования через классы. C++ предоставляет все четыре возможности ООП — абстракцию, инкапсуляцию, наследование (в том числе и множественное) и полиморфизм.

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

• стандартная библиотека C++ состоит из стандартной библиотеки C (с некоторыми модификациями) и библиотеки шаблонов (Standard Template Library, STL), которая предоставляет обширный набор обобщенных контейнеров и алгоритмов;

• дополнительные типы данных;

• обработка исключений;

• виртуальные функции;

• пространства имн;

• встраиваемые (inline) функции;

• перегрузка (overloading) операторов;

• перегрузка имн функций;

• ссылки и операторы управления свободно распределяемой памятью[12].

Разработка языка началась в 1979 году, а впервые для коммерческого использования выпуск состоялся в 1985 году. В 1990-х годах язык стал одним из наиболее широко используемых языков программирования общего назначения. На сегодняшний день последним стандартом языка является C++14, опубликованный и одобренный в 2014 году. С++14 является сравнительно небольшим расширением стандарта С++11, внесшего существенное число изменений и нововведений относительно предыдущего стандарта С++03. В 2017 году ожидается выход стандарта С++17[13].

C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков.

Библиотеки в Unreal Engine 4 2.2.3 Unreal Engine 4 содержит в себе огромную библиотеку на языке С++.

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

Рассмотрим некоторые из его возможностей.

Многие контейнеры из STL переделаны в Unreal Engine 4, а также добавлен ряд новых. Несколько примеров приведены в таблице 1.

–  –  –

Такие алгоритмы, как сортировка массива TArray, нахождение максимального или минимального элемента в контейнере и т.д. реализованы как методы соответствующих классов.

Математическая библиотека содержит набор классов и функций для упрощения работы как с 3D, так и с 2D пространством[14]. Так, например, класс FVector инкапсулирует три float-значения и набор методов для работы с ними, а также существует широкий функционал статических функций, позволяющих находить дистанции между векторами, проецировать их на плоскости, находить их скалярное произведение и т.д. FMatrix реализует матрицы, FPlane – плоскости, FBox – параллелепипеды, FSphere – сферы, FColor – цвета, FInterval – интервалы между двумя значениями, TBigInt – длинную арифметику и т.д. Такие классы, как вектор, матрица, параллелепипед имеют отдельные версии для 2D-пространства.

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

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

Одним из наиболее интересных и часто используемых макросов является UPROPERTY(). Для него существует несколько применений, среди которых важнейшим является возможность изменять значение какого-либо поля класса из главного редактора движка Unreal Engine 4 без перекомпиляции кода, в т.ч. даже непосредственно во время игры. Для этого достаточно написать, к примеру, UPROPERTY(EditAnywhere, Category = Test) float property; внутри тела класса. Скомпилировав код и добавив на уровень объект типа данного класса, в его настройках появится добавленное float-значение в категории Test. Помимо двух названных спецификаторов (EditAnywhere и Category) существует и ряд других[15].

Новые С++-классы создаются в проекте автоматически через меню главного редактора, где вводится имя класса, а также выбирается родитель из стандартного списка (пустой объект, игровой компонент, игрок и т.д.).

Генерируются соответствующие.h- и.cpp-файлы, автоматически объявляется класс с наследованием от родителя и с использованием нескольких специальных макросов движка Unreal Engine 4, а также добавляется несколько стандартных методов (в зависимости от родительского класса).

3 ОПИСАНИЕ АЛГОРИТМА

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

Входными данными алгоритма является набор целочисленных параметров:

- УровеньШирина: ширина уровня, выраженная числом тайлов;

- УровеньВысота: высота уровня;

- ЧислоКомнат: кол-во прямоугольных комнат, которое будет создано;

- МинРазмерКомнат: минимальная ширина и высота любой из комнат, выраженная числом тайлов;

- МаксРазмерКомнат: максимальная ширина и высота комнат;

- МинСмещение: минимальное кол-во шагов, которые будут проделаны от найденных краевых точек уровня для расстановки старта и выхода;

- МаксСмещение: аналогично максимальное кол-во шагов;

- МинПлощадь: минимальная площадь уровня (под площадью здесь понимается общее кол-во клеток пола);

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

Выходными данными являются:

- Уровень[][]: двумерный прямоугольный массив, каждый элемент которого принимает одно из трех значений: Пустота, Стена или Пол;

- Старт: координаты старта уровня;

- Выход: координаты выхода из уровня.

Кроме того, для работы алгоритма необходимы следующие промежуточные данные:

- ПоследнийПол: координаты последнего добавленного на уровень тайла пола;

- Площадь: текущая площадь уровня;

- Комнаты[]: массив, элементами которого является структура комната. Данная структура состоит из четырех значений: координат левого верхнего угла комнаты (обозначается X0, Y0) и ширины и высоты комнаты.

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

Итак, запишем общую структуру алгоритма.

функция СоздатьУровень Площадь = 0;

цел Попытка = 0;

Уровень.ВыставитьРазмер(УровеньШирина, УровеньВысота);

// Генерация уровня цикл пока (Площадь МинПлощадь и Попытка МаксПопыток) Попытка = Попытка + 1;

Уровень.Инициализировать(Пустота);

Площадь = СгенерироватьУровень();

конец цикла если (Попытка = МаксПопыток) АварийноеЗавершение();

конец если // Расстановка старта и выхода Старт = НайтиКрай(ПоследнийПол);

Выход = НайтиКрай(Старт);

возврат Уровень;

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

Символ & указывает, что параметр передается по ссылке и является выходным.

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

После получения удовлетворяющего уровня в нем выбирается старт и выход (подробнее об этом ниже).

В функции СгенерироватьУровень используется вспомогательный массив Соединения, элементами которого являются вложенные массивы целых чисел (индексов комнат). Будем считать, что запись Соединения означает обращение к массиву массивов в целом, Соединения[0] – обращение к первому по счету вложенному массиву, а Соединения[0][0] – к первой ячейке первого вложенного массива.

–  –  –

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

Сгенерированная информация о каждой комнате дописывается в массив Комнаты. При этом создаются временные массивы А, состоящие из одного элемента (индекса новой комнаты), и дописываются в массив Соединения.

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

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

–  –  –

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

процедура ДобавитьСтену(X, Y) если (Уровень[X][Y] = Пустота) Уровень[X][Y] = Стена;

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

–  –  –

функция ВыбратьКлеткуКомнаты(комната К) цел X = СлучайноеЧисло(К.X0 + 1, К.X0 + К.Ширина – 2);

цел Y = СлучайноеЧисло(К.Y0 + 1, К.Y0 + К.Высота – 2);

возврат точка(X, Y);

конец функции Наконец, рассмотрим процедуру создания коридорами между двумя различными произвольными точками p1 и p2. В общем случае есть три варианта:

- точки лежат на одной горизонтали;

- точки лежат на одной вертикали;

- точки лежат на разных горизонталях и вертикалях.

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

В процедуре задаются точки Шаг и Направление, которые используются как векторы. Например, если точка p2 находится правее и ниже точки p1, то Направление.X = 1, Направление.Y = –1. Коридор может проходить только горизонтальными и/или вертикальными отрезками, но не диагональными; вектор Шаг помогает это обеспечивать тем, что у него всегда одно поле равно нулю, а другое – единице.

Общая идея процедуры заключается в том, что от точки p1 коридор начинает движение случайным образом либо по горизонтали, либо по вертикали на случайное число клеток в диапазоне от единицы до половины расстояния, которое необходимо соединить коридором. После этого значения в векторе Шаг обмениваются, т.е. движение сменяется с горизонтального на вертикальное или наоборот, и подобное движение повторяется. Так происходит до того, пока текущая точка и конечная точка p2 не выравняются либо по горизонтали, либо по вертикали. Это обеспечивает создание коридоров, по внешнему виду напоминающих ступеньки лестницы. После того, как такие коридоры пересекутся друг с другом и/или с какими-либо комнатами, на уровне образуются пространства самых разнообразных форм.

–  –  –

Теперь, когда сам уровень уже сгенерирован, на нем необходимо расположить старт и выход. Для этого используется модифицированный алгоритм нахождения диаметра графа. Функция НайтиКрай принимает на вход некоторую точку и находит наиболее удаленную от нее с помощью обхода графа уровня в ширину. При этом в массиве Родители для каждой точки сохраняются координаты той точки, из которой алгоритм пришел в данную. Идея в том, что после нахождения наиболее удаленной точки алгоритм проделывает несколько (от МинСмещение до МаксСмещение) шагов в обратную сторону. Без этого было бы очевидно, что и старт, и выход всегда расположены в самых дальних углах уровня, но за счет небольшого смещения от настоящих точек диаметра графа это менее заметно.

Функция используется дважды: для нахождения старта (относительно произвольной точки) и для нахождения выхода (относительно старта).

–  –  –

На этом подробное описание алгоритма завершается. Примеры уровней, генерируемых им, а также выводы об их особенностях и трудоемкости алгоритма приводятся в разделе 5 данной бакалаврской работы.

–  –  –

Как алгоритм процедурной генерации, так и программное представление уровня инкапсулированы в специальном классе AProceduralLevel, отнаследованном от AActor. AActor – это один из стандартных классов в Unreal Engine 4; от него наследуются все классы, которые могут быть созданы внутри мира. Под миром здесь понимается вс бесконечное игровое пространство. В частности, объект игрока – это потомок AActor-а, как и направленный солнечный свет (для освещения уровня, отрисовки теней) и многое другое. Таким образом, наш уровень по своей природе является еще одним AActor-ом и в конечном счете играет роль большого цельного набора геометрических объектов – стен, пола и т.д. – который создается в определенной точке внутри мира. В системе иерархии объектов в Unreal Engine 4 и процедурно сгенерированный уровень, и сущность игрока являются объектами одной природы.

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

Тайлы бывают четырех видов:

- ETileType::Init: начальное значение (не инициализированный тайл);

- ETileType::Void: пустая клетка;

- ETileType::Wall: клетка стены;

- ETileType::Floor: клетка пола.

Массив является одномерным и имеет тип TArrayETileType. TArray

– это фактически аналог контейнера std::vector в Unreal Engine 4. Так как данный одномерный массив на самом деле задает двумерную сетку из тайлов, зачастую возникает необходимость переходить от координат некоторого конкретного тайла (x, y) к индексу данного массива, в котором хранится тип этого тайла. Делается это обращением LevelData[x + y * LevelSizeX], где LevelSizeX – это ширина всего уровня. Таким образом, в массиве LevelData данные хранятся по строкам подряд.

Процедурно генерируется именно логическое представление уровня.

После того, как этап генерации закончен и получена полная информация о том, как должен выглядеть уровень, начинается его построение в игровом мире. Тайлы стен и тайлы пола (согласно информации, записанной в массиве LevelData) получают свои физические воплощения.

Простейшим способом воссоздать виртуальный уровень из его логического представления было бы использование так называемых Static Mesh-ей. Static Mesh – это статическая полигональная сетка. Иными словами, это 3д-модель, созданная в стороннем редакторе моделей и затем импортированная в редактор Unreal Engine 4. Static Mesh-и представляют собой набор полигонов, которые отрисовываются видеокартой во время игры. Они также кешируются в видеопамяти, за счет чего существенно понижаются затраты производительности на их отрисовку, даже если они имеют сложные формы. Кроме того, по той же причине можно применять аффинные преобразования к каждому отдельному Static Mesh-у – передвигать их, поворачивать, менять масштаб по одной или более осям координат. Однако, изменять их непосредственную форму (т.е. анимировать их отдельные вершины) не представляется возможным; для этого необходимо использовать иные технологии, предоставляемые движком Unreal Engine 4.

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

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

Возвращаясь к теме алгоритма процедурной генерации уровня, можно сделать вывод, что для того, чтобы физически воссоздать уровень, для каждого тайла стены можно создать соответствующий Static Mesh в форме прямоугольного параллелепипеда (или же просто куба). Для каждого тайла пола можно поступить таким же образом, сдвинув пол ниже относительно уровня стен. В таком случае движок Unreal Engine 4 возьмет существенную часть работы на себя, обеспечив корректную обработку столкновений игрока со стенами и полом (чтобы тот мог корректно перемещаться в рамках уровня), автоматическую отрисовку уровня во время игры, а также теней, отбрасываемых стенами и игроком на пол.

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

Большинство из перечисленных вещей движок Unreal Engine 4 сделает автоматически без написания дополнительного кода, но тем не менее, это вс затраты процессорного времени. При небольших размерах уровня (в т.ч. при низком числе комнат и т.д.) эти затраты незначительны, но с ростом же размеров уровня – если речь пойдет о тысячах или десятках тысяч объектовстен и объектов-полов – можно ожидать достаточно ощутимые потери производительности, выражающиеся в зависании приложения на несколько секунд при старте уровня или даже в низком кол-ве отображаемых в секунду кадров во время игры. Даже если производительность системы, на которой запускается данный алгоритм, позволяет без ощутимых проблем генерировать и отрисовывать относительно большие порождаемые им уровни, то вс равно нужно не забывать, что сам по себе уровень является только одним из элементов видеоигры; при появлении в игре оружия, аптечек, врагов и т.д., населяющих данный уровень, на систему будет возлагаться дополнительная нагрузка. Всю эту нагрузку необходимо учитывать и по возможности минимизировать.

Среди возможностей движка Unreal Engine 4 существует технология под названием Instanced Static Mesh, инкапсулированная классом UInstancedStaticMeshComponent. Ее идея заключается в следующем. Вместо того, чтобы создавать большие число отдельных, например, стен, которые на самом деле друг от друга отличимы только положением в пространстве, однократно описывается объект участок стены (задается его текстура, форма модели и т.д.), а затем создаются экземпляры этого объекта. За счет этого достигается существенная оптимизация сразу в двух аспектах. Во первых, инициализация происходит значительно быстрее, т.к. каждому новому экземпляру нужно лишь задать положение в пространстве (в общем случае – произвести над ним аффинные преобразования). Во-вторых, отрисовка всех стен на уровне произойдет за одно обращение к видеокарте. В этом и есть основное преимущество использования Instanced Static Mesh там, где это возможно. А возможно это действительно не всегда, ибо существуют ограничения при использовании этой технологии. Очевидным из них является тот факт, что все экземпляры должны иметь одну и ту же текстуру и одну и ту же 3д-модель. Данная технология не подходит в случае, когда требуется создать и отрисовывать большое количество схожих по природе, но визуально различных объектов. Кроме того, существует и несколько технических ограничений, таких, к примеру, как невозможность задавать экземплярам таких объектов отрицательный масштаб при аффинных преобразованиях сжатия-растяжения; в случае обычных Static Mesh это возможно (и приводит к зеркальному отображению модели по одной или более оси). Для рассматриваемого алгоритма стены вполне укладываются во все существующие ограничения.

Таким образом, физически в мире уровень представлен в виде двух компонент типа UInstancedStaticMeshComponent – одна для тайлов стен, другая для тайлов полов. Такой подход оптимален, в отличие от работы с огромными массивами различных компонент типа UStaticMeshComponent.

Реализация алгоритма 4.2

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

FIntPoint является стандартной структурой в Unreal Engine 4, инкапсулирующий пару целочисленных координат X и Y, задающих точку в двумерном пространстве. С ее помощью можно удобно задавать некоторый конкретный тайл на уровне (а точнее, его координаты), поэтому она достаточно широко используется в реализации описанного алгоритма.

Опишем созданную структуру FRoom. Данная несложная структура задает прямоугольную комнату на уровне. У нее есть четыре поля: Left, Top, Width и Height, задающие координат левого верхнего угла комнаты, а также ширина и высота комнаты, включая внешние стены. Т.е. если Width и Height равны 3, и комната имеет размер 3х3, то получается, что она состоит из 8 тайлов стен и одного тайла пола посередине между ними. Комната не может иметь размер меньший, чем 3х3.

У структуры FRoom имеется конструктор и несколько вспомогательных методов, позволяющих удобно указывать положение и размер комнаты, задаваемой данной структурой. Кроме того, у нее есть метод GetRandomFloorTile, возвращающий пару координат типа FIntPoint. Данный метод возвращает случайный тайл пола, лежащий внутри этой комнаты (за счет наличия требования минимального размера комнаты 3х3 гарантируется, что такой тайл всегда есть). Иными словами, метод возвращает такую структуру FIntPoint, у которой поле X имеет значение от Left + 1 до Left + Width – 2 включительно, а поле Y – аналогично от Top + 1 до Top + Height –

2. Данный метод понадобится в реализации немного позже.

Опишем класс AProceduralLevel. Как уже отмечалось, он наследуется от стандартного класса AActor.

При этом заголовок класса имеет следующий вид:

UCLASS() class PROCEDURALGEN_API AProceduralLevel : public AActor { GENERATED_BODY() … };

Здесь используются три макроса: UCLASS, PROCEDURALGEN_API и GENERATED_BODY(). Данные макросы подставляются автоматически при создании класса через меню редактора Unreal Engine 4 и в своей совокупности имеют ряд назначений, включающих корректную интеграцию как с остальным кодом движка, так и с самим редактором.

В классе содержится набор полей, среди которых трое являются компонентами. Из них две имеют тп UInstancedStaticMeshComponent, с помощью которых создаются физические воплощения всех тайлов стен и всех тайлов пола в виртуальном мире (см. 4.1), а третья – UStaticMeshComponent, задающая 3д-модель, обозначающую выход из уровня (внешне выглядит как люк в подвал). В этом же классе хранятся указатели на загруженные материалы для данных трех компонент. Кроме того, в классе содержится ряд полей, настраивающих как визуальное представление уровня (высота и смещение стен относительно пола; размер модели, обозначающей выход с уровня и т.д.), так и его структурный состав (минимальный и максимальный размер комнат, а также самого уровня;

минимальное и максимальное число комнат и другие параметры). Все эти поля можно настраивать из редактора Unreal Engine 4 без перекомпиляции кода. Подробнее об интеграции данного класса со средой редактора описано в разделе 4.3.

Рассмотрим понятия загрузка мира и начало игры в контексте движка Unreal Engine 4. Если запускается уже готовая, собранная, отдельная игра, то сначала загружается игровой мир (со всеми объектами внутри), а затем сразу же происходит событие начала игры. Однако, на этапе разработки игры эти два понятия имеют существенную разницу. Работая в редакторе Unreal Engine 4, пользователь всегда взаимодействует с уже загруженным игровым миром. Получается, что все объекты в данном мире уже инициализированы, но не активны. Если добавить в мир новый объект, он будет инициализирован так же, как при обычной загрузке мира, но не активен, пока не произойдет начало игры (либо внутри редактора, либо в рамках самостоятельного приложения).

На языке С++ под инициализацией объекта понимается выполнение конструктора класса, а под обработкой события начала игры и вступлением в фазу активной работы – выполнение специального виртуального метода BeginPlay. При реализации данного класса создание дерева компонент, загрузка материалов и текстур для моделей стен и пола и т.д. находится в конструкторе класса, а непосредственная генерация уровня вызывается уже в методе BeginPlay. Такое разделение процесса создания уровня является удачным, т.к. оно максимально утилизирует возможности движка Unreal Engine 4. Действительно, если бы инициализация моделей была бы в методе BeginPlay вместе с генерацией уровня, то в редакторе движка невозможно было бы настроить, к примеру, текстуры и размеры стен, т.к. они не будут созданы до начала игры вообще. В то же время, если бы процедурная генерация уровня происходила сразу в конструкторе, то при добавлении в редакторе объекта уровень в мир он бы появился уже готовый и сгенерированный. А так как при каждом запуске игры необходимо получать новый уровень, то все равно в методе BeginPlay пришлось бы удалять существующий и генерировать новый.

Каждый объект в виртуальном мире Unreal Engine 4 содержит в себе дерево компонент. Компонента – это объект, реализация которого наследуется от стандартного класса UActorComponent, и который играет роль подобъектов для других объектов, в том числе и других компонент.

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

В конструкторе AProceduralLevel также происходит инициализация материалов для всех трех компонент и задание значений по умолчанию для интегрируемых настраиваемых параметров. Далее из метода BeginPlay вызывается генерация уровня. Непосредственная реализация алгоритма идентична его описанию в разделе 3 и при этом практически полностью отделана от специфики движка Unreal Engine 4 (за исключением использования некоторых структур данных, описанных в разделе 2.2.3), поэтому не описывается здесь повторно. Исходный код класса AProceduralLevel можно изучить в приложении А.

После того, как внутреннее логическое представление процедурно сгенерированного уровня получено (а именно, заполнен массив LevelData), остается только пройти по всему массиву и для каждого тайла типа ETileType::Wall (ETileType::Floor) добавить экземпляр стены (пола) в соответствующие компоненты типа UInstancedStaticMeshComponent. Для этого они сдвигаются в координаты, равные индексам тайла по горизонтали и по вертикали, умноженным на размер тайла TileSize. Кроме того, необходимо передвинуть объект выхода в соответствующие найденные координаты выхода.

На этом создание уровня заканчивается, и сгенерированный уровень отображается в игровом мире.

Интеграция со средой редактора Unreal Engine 4 4.3

Реализованный в рамках данной бакалаврской работы класс AProceduralLevel интегрирован со средой редактора Unreal Engine 4. Добавив в редакторе объект данного класса в виртуальный мир и затем выбрав его в списке объектов, пользователь может гибко настроить многие параметры, меняющие как визуальное оформление будущего сгенерированного уровня, так и его структурный состав. Рассмотрим более подробно, как пользователь может повлиять на процедурно генерируемые данным классом уровни.

Все публичные поля реализованного класса объявлены с пометкой следующего вида: UPROPERTY(EditAnywhere, Category = "Example").

UPROPERTY – это макрос движка, который после разовой компиляции кода добавляет данное поле в список доступных для изменения параметров класса в редакторе. Впоследствии все объявленные таким способом поля класса отображаются в специальном меню в редакторе Unreal Engine 4. При этом у данного макроса в скобках перечисляются настройки поведения интеграции.

Если не перечислить никаких настроек, то по умолчанию переменная будет закрыта от изменений и доступна только для чтения, отображаясь с интуитивно понятным серым фоном в меню редактора. Ключевое же слово EditAnywhere, перечисленное в настройках макроса, позволяет изменять описанное поле из меню редактора. Кроме того, Category указывает категорию, к которой относится данное поле. Движок Unreal Engine 4 позволяет удобно объединять переменные, связанные по смыслу, в такие группы; для этого достаточно просто указать одинаковое имя категории для двух или более полей класса.

Класс AProceduralLevel использует несколько таких категорий.

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

Перечислим их.

Поля LevelSizeX и LevelSizeY – это горизонтальный и вертикальный размеры уровня. Фактически, это ограничение на то, насколько далеко друг от друга могут появляться комнаты. К примеру, если оба поля имеют значение 32, то, учитывая отступ в одну клетку от границ уровня, комнаты могут появляться внутри квадрата 30х30. Минимальный допустимый размер уровня – 5х5 (отступ в одну клетку оставляет квадрат 3х3 – минимальный размер одной комнаты). Чем больше максимальный указанный размер уровня, тем более разряженно будут располагаться комнаты, и между ними будут проходить более длинные коридоры. Пользователю предлагается самостоятельно подобрать размер уровня так, чтобы он в совокупности с остальными параметрами образовывал подходящие к требованиям игры случайные уровни.

MinRoomCount и MaxRoomCount задают минимальное и максимальное число комнат, в то время как MinRoomSize и MaxRoomSize соответственно задают минимальный и максимальный размер каждой из них (одновременно по горизонтали и по вертикали). Внешние стены вокруг пола комнаты включаются в нее саму, поэтому минимально допустимый размер комнаты – 3х3 (с единственной клеткой пола посередине между 8 стенами).

MinBfsOffset и MaxBfsOffset задают минимальное и максимальное смещение старта и выхода из уровня относительно краевых точек (т.е. диаметра уровня). MinFloorCount задает минимальную требуемую площадь уровня, при этом разрешается не более чем MaxAttemptCount попыток сгенерировать уровень, соблюдая данное ограничение. После успешной генерации уровня в меню редактора можно увидеть итоговую площадь сгенерированного уровня, посмотрев значение переменной FloorCount, открытой только для чтения и заполняемой программным кодом алгоритма.

Особый интерес представляет категория Seed, состоящая из единственного поля с таким же названием. Данным значением инициализируется датчик случайных чисел, содержащийся внутри класса AProceduralLevel. По умолчанию это поле задается нулем, но оно может быть изменено пользователем. Непосредственно перед генерацией уровня происходит проверка: если данное поле равно нулю, то оно перезаписывается некоторым псевдослучайным числом (в этом случае используется кол-во секунд, прошедших с полуночи 1 января 1970 до текущего момента времени), а затем уже этим числом инициализируется датчик случайных чисел. Смысл интеграции данного поля с редактором Unreal Engine 4 заключается в том, что во время игры внутри редактора после генерации очередного случайного уровня можно поставить игру на паузу и посмотреть текущий Seed данного уровня. Сохранив это значение, пользователь может остановить игру и далее в режиме редактирования мира задать это значение в поле Seed (вместо нуля по умолчанию). Тогда при всех последующих запусках игры будет генерироваться тот же самый уровень, а не новый случайный. Это удобно использовать для тестирования игры; в законченном проекте, использующем данный генератор уровней и добавляющем врагов и т.д., может появиться логическая ошибка или возникнуть проблема с игровым балансом. Тестировщик может записать Seed такого уровня и передать его программистам вместе с описанием возникшей проблемы, и они смогут разобраться в причинах возникновения проблемы, получая тот же самый уровень, что и был у тестировщика.

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

Демонстрационный проект 4.4

В рамках бакалаврской работы был разработан интерактивный проект, демонстрирующий работу алгоритма. К реализованному классу AProceduralLevel, подробно описанному в разделах 4.1 – 4.3, добавляются классы AProceduralGenCharacter и AGameplay. Первый из них инкапсулирует реализацию объекта-игрока, а второй контролирует ход игрового процесса (в частности, создает и располагает на уровне подбираемые звездочки). Схема взаимодействия классов представлена на рисунке 4.1.

Рисунок 4.1 – Иерархия объектов

Класс игрока AProceduralGenCharacter содержит в себе физическую модель типа UCapsuleComponent, компоненту обработки нажатий кнопок клавиатуры типа UInputComponent, а также объект камеры типа UCameraComponent. Камера зафиксирована статично над игроком, направлена на него и таким образом всегда следует за ним.

Игрок может перемещаться по уровню с помощью стандартных для многих игр клавиш WSAD.

Для этого в настройках проекте создаются так называемые Axis Mapping (оси ввода), на которые затем регистрируются обработчики нажатий:

InputComponent-BindAxis("MoveForward", this, &AProceduralGenCharacter::MoveForward);

InputComponent-BindAxis("MoveRight", this, &AProceduralGenCharacter::MoveRight);

За счет использования стандартных возможностей движка и их корректной настройки в редакторе Unreal Engine 4 обеспечивается обработка столкновений между игроком и стенами уровня. Иными словами, игрок всегда находится внутри доступной игровой области. Также на уровне работает динамическое освещение (отображаются тени от стен, игрока и т.д.), которое является стандартным свойством для любого шаблонного проекта на движке Unreal Engine 4.

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

Класс AGameplay содержит массив UStaticMesh-ей, задающих звездочки. Кол-во звездочек настраивается в интегрированном поле StarCount и по умолчанию равно 5. Регистрируются события столкновения между игроком и звездочками, в момент которых звездочки убираются с уровня. Снимок экрана демонстрационного проекта приведен на рисунке 4.2.

Рисунок 4.2 – Демонстрационный проект

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

Для этого используется метод Монте-Карло. Интегрированная переменная MaxAttemptCount задает кол-во попыток расставить звездочки на уровне (минимальное значение – 1 попытка). Затем выбираются StarCount случайных точек уровня, таких, что соответствующие им тайлы – это клетки пола, и при этом они все гарантированно не совпадают друг с другом, а также с координатами старта и выхода уровня.

Затем считаются два значения: StartExitScore и DistanceScore.

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

DistanceScore – это наименьшее из всех попарных расстояний между всеми звездочками. Для его нахождения запускаются (StarCount – 1) схожих обходов в ширину.

Если звездочки имеют индексы от 0 до (StarCount – 1), то на псевдокоде этот процесс выглядит следующим образом:

–  –  –

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

Наконец, считается значение Score как произведение StartExitScore на DistanceScore. Score можно рассматривать как общий рейтинг данного расположения точек. Чем он больше, тем более удачным считается случайно полученное расположение. Соответственно, на каждом шаге метода МонтеКарло сравнивается полученный Score с текущим максимальным рейтингом, и если он больше текущего максимума, то последнее сгенерировааное расположение точек записывается в массив результатов.

По итогу работы алгоритма выбирается наиболее удачное из всех полученных расположений звездочек, такое, что они все достаточно далеки как от старта, так и от выхода из уровня (чтобы игроку приходилось их искать, ровно как искать и сам выход), а кроме того, они находятся не слишком близко друг к другу. Пример результата приведен на рисунке 4.3.

Старт находится вверху слева (видно игрока), а выход – внизу справа.

Очевидно, что расположение звездочек удовлетворяет данным условиям.

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

Рисунок 4.3 – Возможное расположение звездочек на уровне

5 РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ

Пример виртуального пространства, сгенерированного алгоритмом данной бакалаврской работы, приведен на рисунке 5.1, а параметры, при котором он был сгенерирован – в таблице 5.1.

–  –  –

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

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

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

Рассмотрим сложность данного алгоритма. Расстановка комнат на уровне имеет сложность O(n*w*h), где n – число комнат, w – средняя ширина комнат, h – средняя высота комнат, т.к. для каждой комнаты необходимо выполнить цикл по прямоугольнику пола внутри нее. Соединение комнат коридорами имеет сложность O(n*l), где l – средняя длина коридора, т.к.

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

Приведем статистическое исследование уровней, генерируемых данным алгоритмом, при том же наборе параметров, что были описаны в таблице 5.1. Будем считать площадь уровня (в кол-ве тайлов), а также длину кратчайшего пути от старта до выхода (в кол-ве горизонтальных и/или вертикальных шагов по тайлам). Результат процедурной генерации 1000 случайных уровней и подсчета статистики отражен в таблице 5.2.

–  –  –

ЗАКЛЮЧЕНИЕ

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

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

Алгоритм был реализован на языке C++ и интегрирован с движком Unreal Engine 4. Кроме того, была создана интерактивная демонстрация данного алгоритма, в которой игрок может управлять персонажем, перемещающимся по уровню, находить выход из текущего уровня и попадать в новый и т.д. В разделе 5 приводится пример уровня, генерируемого данным алгоритмом, а также статистика о минимальных, средних и максимальных площади и диаметра получаемых уровней.

С помощью разработанного алгоритма процедурной генерации виртуальных пространств, а также знания теории графов и наличия творческих идей, программист может создать игру, в фундаменте которой лежат такие случайно генерируемые уровни. Благодаря тому, что алгоритм реализован на игровом движке Unreal Engine 4, программист может использовать возможности данного движка для существенной оптимизации процесса разработки игры, а также экспортировать сборку игры практически на любые платформы: Windows, Linux, Mac OS, мобильные и консольные платформы и т.д. Демонстрационный проект, разработанный в рамках бакалаврской работы, является примером такой игры.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. More than 1.2 billion people are playing games [Электронный ресурс] /

Dean Takahashi // GamesBeat. – Режим доступа:

http://venturebeat.com/2013/11/25/more-than-1-2-billion-people-areplaying-games/ (дата обращения 20.05.2016) – яз. англ.

2. Supreme Court sees video games as art [Электронный ресурс] / John D.

Sutter // CNN.com. – Режим доступа:

http://edition.cnn.com/2011/TECH/gaming.gadgets/06/27/supreme.court.vid eo.game.art/ (дата обращения 20.05.2016) – яз. англ.

3. Map representations [Электронный ресурс] // Amit’s Thoughts on

Pathfinding. – Режим доступа:

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.h tml (дата обращения 20.05.2016) – яз. англ.

4. Basic BSP Dungeon generation [Электронный ресурс] // RogueBasin. –

Режим доступа:

http://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generatio n (дата обращения 20.05.2016) – яз. англ.

5. Random level generation in Wasteland Kings [Электронный ресурс] / Jan

Willem Nijman // Vlambeer. – Режим доступа:

http://www.vlambeer.com/2013/04/02/random-level-generation-inwasteland-kings/ (дата обращения 20.05.2016) – яз. англ.

6. Generate Random Cave Levels Using Cellular Automata [Электронный ресурс] / Michael Cook // EnvatoTuts+. – Режим доступа:

http://gamedevelopment.tutsplus.com/tutorials/generate-random-cave-levelsusing-cellular-automata--gamedev-9664 (дата обращения 20.05.2016) – яз.

англ.

7. Пишем игровой движок [Электронный ресурс] // Хабрахабр. – Режим доступа: https://habrahabr.ru/post/102930/ (дата обращения 20.05.2016) – яз. рус.

8. Unreal Engine FAQ [Электронный ресурс] // Epic Games : Часто задаваемые вопросы и ответы по движку Unreal Engine 4. – Режим доступа: https://www.unrealengine.com/faq (дата обращения 20.05.2016)

– яз. англ.

9. Unreal Engine Features [Электронный ресурс] // Epic Games :

Возможности движка Unreal Engine 4. – Режим доступа:

https://www.unrealengine.com/unreal-engine-4 (дата обращения 20.05.2016) – яз. англ.

10. IntelliSense [Электронный ресурс] // Википедия, свободная энциклопедия – Режим доступа: https://ru.wikipedia.org/wiki/IntelliSense (дата обращения 20.05.2016) – яз. рус.

11. Microsoft software license terms | Visual Studio Community 2013 [Электронный ресурс] // Microsoft : Лицензионное соглашение Microsoft – Режим доступа: https://www.visualstudio.com/enus/dn877550.aspx (дата обращения 20.05.2016) – яз. англ.

12. C++ [Электронный ресурс] // Энциклопедия языков программирования

– Режим доступа: http://progopedia.ru/language/c-plus-plus/ (дата обращения 20.05.2016) – яз. рус.

13. Current Status : Standard C++ [Электронный ресурс] // Standard C++

Foundation : Статус стандарта языка С++ – Режим доступа:

https://isocpp.org/std/status (дата обращения 20.05.2016) – яз. англ.

14. Unreal Engine API Reference [Электронный ресурс] // Epic Games :

Документация Unreal Engine 4 – Режим доступа:

https://docs.unrealengine.com/latest/INT/API/index.html (дата обращения 20.05.2016) – яз. англ.

15. Unreal Property System [Электронный ресурс] // Unreal Engine Blog – Режим доступа: https://www.unrealengine.com/blog/unreal-propertysystem-reflection (дата обращения 20.05.2016) – яз. англ.

16. Static Meshes | Unreal Engine [Электронный ресурс] // Epic Games. –

Режим доступа:

https://docs.unrealengine.com/latest/INT/Engine/Content/Types/StaticMeshe s/ (дата обращения 20.05.2016) – яз. англ.



Похожие работы:

«Э. М. БРАНДМАН ГЛОБАЛИЗАЦИЯ И ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ ОБЩЕСТВА Глобальная информатизация и новые информационные технологии открывают небывалые возможности во всех сферах человеческой деятел...»

«TNC 320 Руководствопользователя Программированиециклов ПрограммноеобеспечениеNC 340551-06 340554-06 Русский (ru) 3/2014 Основные положения Основные положения О данном руководстве О данном руководстве Ниже приведен список символов-указаний, используемых в данном руководстве Этот симв...»

«Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» «УТВЕРЖДАЮ» Декан факультета ИСТ наименование факультета Салмин А.А. подпись Фамилия И.О. 2014 г. « » _ РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ...»

«Учебно – методический комплекс “Охрана труда” 1. Учебная программа, для Белорусского государственного университета по всем специальностям факультета прикладной математики и информатики.2. Примерный тематический план.3. Программа курса “Охрана труда” для студентов 5-ого курса ФПМИ.4. Содержание лекционного курса “Охрана труда”....»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» «Институт информационных технологий» Кафедра микропроцессорных...»

«Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра Автоматизации Систем Вычислительных Комплексов Анциферова Анастасия Всеволодовна Автоматический метод оценки степени у...»

«ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2008 Математические основы компьютерной безопасности № 1(1) УДК 681.322 РЕАЛИЗАЦИЯ ПОЛИТИК БЕЗОПАСНОСТИ В КОМПЬЮТЕРНЫХ СИСТЕМАХ С ПОМОЩЬЮ АСПЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ Д.А. Стефанцов Томский государственный университет E-mail: d.a.stephantsov@gmail.com Рассматрив...»

«Программа внеурочной деятельности по информатике и ИКТ «Путешествие в Компьютерную Долину» А.Г. Паутова Целью программы внеурочной деятельности по информатике и ИКТ «Путешествие в Компьютерную Долину» является информационная поддержк...»

«АННОТАЦИЯ ПРОГРАММЫ УЧЕБНОЙ ПРАКТИКИ ( по получению первичных профессиональных умений и навыков, в том числе первичных умений и навыков научно-исследовательской деятельности) Место учебной практики в структуре ОПОП ВО Данный разд...»

«Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра математических методов прогнозирования Панкратов Антон Михайлович Распознавание входящих ключевых слов в оцифрованных изображениях рукописных текстов ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА Научный руководитель:...»

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ» Сборник материалов 48-ой НАУЧНОЙ КОНФЕРЕНЦИИ АСПИРАНТОВ, МАГИСТРАНТОВ И СТУДЕНТОВ МОДЕЛИРОВАНИЕ, КОМПЬЮТЕРНОЕ ПРОЕКТИРОВАНИЕ И Т...»

«Зайцев Владислав Вячеславович РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДИКИ ПРОЕКТИРОВАНИЯ БАЗЫ МЕТАДАННЫХ ХРАНИЛИЩА ГЕОДАННЫХ Специальность 25.00.35 – «Геоинформатика» ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук Научный руководитель д-р техн. наук, проф. А.А. Майоров Москва 2015   ОГЛАВЛЕНИЕ...»

«Глава 2. Новая кибернетика как объект исследования 2.1. Кризис кибернетики В настоящее время термин «кибернетика» практически вышел из употребления и считается многими учеными и инженерами чуть ли ни архаизмом. Вместо термина «кибернетика» сейчас чаще всего...»

«Министерство образования Республики Беларусь Учреждение образования «БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ» УТВЕРЖДАЮ Проректор по учебной и воспитательной работе _ С.К. Дик 04.05.2016 ПРОГРАММА...»

«Анализ мотивов поведения российских участников добровольных распределенных вычислений ТИЩЕНКО В. И. Институт системного анализа ФИЦ «Информатика и управление» РАН, Россия, 117312 Москва проспект 60-летия Октября, 9; тел. (499)135-24-38, факс (499)783-91-32, tischenko@isa.ru Ключевы...»

«230 УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА УДК 37.018.46:339.138 И.И. Веберова Исследование рынка потребителей как основа позиционирования и продвижения программы дополнительного профессионального образования Рассмотрена одна из ключевых проблем маркетинга в сфере дополнительного профессионального обра...»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра электронной техники и технологии В. Л. Ланин МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ СБОРКИ И МОНТАЖА ЭЛЕКТРОННЫХ МОДУЛЕЙ Методическое пособие для пр...»

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА ТЕХНОЛОГИЙ ПРОГРАММИРОВАНИЯ Андриенко Артем Сергеевич Выпускная квалификационная работа бакалавра Выделение именованных сущностей в тек...»

«Министерство образования Республики Беларусь Учреждение образования Белорусский государственный университет информатики и радиоэлектроники «Утверждаю» Проректор по учебной работе и социальным вопросам _ А.А. Хмыль «_»...»

«Информатика, вычислительная техника и обработка информации УДК 621.391 АНАЛИЗ МЕТОДОВ АВТОМАТИЗАЦИИ ПРОЦЕССОВ РАСПОЗНАВАНИЯ ОБЪЕКТОВ Н.С. Акиншин, А.В. Андреев, Е.А. Старожук Рассматриваются методы принятия решения при распознавании объектов, даются их...»

«№ 2 (38), 2016 Физико-математические науки. Математика МАТЕМАТИКА УДК 519.854 DOI 10.21685/2072-3040-2016-2-1 С. И. Веселов, А. Ю. Чирков, Д. В. Грибанов АГРЕГАЦИЯ УРАВНЕНИЙ В ЦЕЛОЧИСЛЕННОМ ПРОГРАММИРОВАНИИ1 Аннотация. Актуальность и цели. Исследуется следующее обобщение агрегац...»





















 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.