Здравствуйте, меня зовут Дмитрий. Я занимаюсь созданием компьютерных игр на Unreal Engine в качестве хобби. Сегодня я расскажу как я создал процедурную генерацию уровней для моей игры «The Future City Project». Все исходники будут представлены в конце статьи. И ещё будет сюрприз.

Алгоритм

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

1. Поскольку уровень представляет из себя город то необходимо с генерировать сетку дорог. Сетка дорог у меня состоит из дорог двух типов: это главные дороги и обычные. Главные дороги отличаются от обычных тем, что они во первых шире а во вторых они пересекают город насквозь, в то время как обычные дороги имеют протяженность не более квартала. В результате мы получаем вот такую картину (извиняюсь что криво):
   
   
2. Теперь у нас появились дороги и островки между ними. Эти островки нужно чем-то наполнить. Для этого я генерирую граф который представляет из себя прямоугольную сетку. Каждый узел этого графа будет комнатой случайно расположенной внутри пространства конкретного острова (естественно в определенных пределах то есть последующий узел не может быть перед предыдущим). Комнаты я определяю заранее. При этом графов может быть несколько слоев чтобы получить многоуровневую структуру. И чтобы эти слои как-то пересекались близлежащие графы имеют общие узлы(комнаты), которые определяются случайным образом.
3. Теперь остается только соединить эти узлы(комнаты) коридорами в соответствии с их положением в графе. Для этого я использовал «жадный» алгоритм поиска пути. То есть я беру одну из секций коридора (секции коридора как и комнаты определяются заранее) и приставляю её к выходу комнаты затем делаю это и со всеми остальными секциями и выбираю ту секцию чей выход ближе всего к нужной точке(которая является входом в другую комнату), после этого проделываю тоже самое но прикладываю секции уже к секции коридор найденной во время предыдущей итерации и так до победного конца.
4. После создания структуры графов внутри островов. Нужно соединить острова между собой. Для этого в соседних островах находится по комнате которые находятся ближе всего друг к другу. После чего эти комнаты комнаты соединяются таким-же образом как и остальные.
5. Итак у нас уже есть сеть состоящая из комнат соединенных коридорами между собой. Но она висит в воздухе что-же делать. Ну во-первых можно сделать каждый из «островов» небоскребом а комнаты и коридоры соответственно будут комнатами и коридорами этого небоскреба. В принципе я так и сделал с 1/5 всех островов. Но делать так со всеми будет очень скучно.
6. С оставшимися 4/5 островов я поступил так. Верхнии комнаты и коридоры образуют как-бы крышу. Комнаты которые оказались под ними оказываются во внутреннем пространстве «острова» но пространство между ними я не заполняю как в случае небоскребов а оставляю пустым, поэтому у нас образуются «площадки» между которыми можно легко перепрыгивать. Приведу пару примеров:
   
   
   
   Здесь можно видеть как верхнии комнаты и коридоры сливаются в единую крышу.
   
   
   
   А здесь можно видеть внутреннее пространство такого острова.
7. Но получается что такой остров просто парит в воздухе. Чтобы избавится от этого, я добавил к островам башни. Которые будут их поддерживать.
8. Собственно уровень уже готов но не мешало-бы добавить несколько элементов чтобы сделать его красивее. Во первых внизу я добавил модели здания чтобы не казалось что город находится над пустыней вот они:
   
   
9. Кроме того я добавил ховеркары курсирующие над дорогами.

Все процедурно генерируемый город готов.

Как пользоваться

Ну а теперь я расскажу как использовать плагин который вы скачаете с GitHub. После того как вы откроете проект вы увидите лишь карту на которой будет находится лишь один объект LevelGenerator (Если вы хотите вытащить этот объект на карту но не видите его в контент браузере проверте галочку ShowPluginContent).

Итак вот его настройки:

1. Generate, Rebild level, Delete level — Кнопки используются для отладки при помощи них можно сгенерировать, перестроить или удалить уровень.
2. Set Generate Seed — Использовать случайное число для генерации или заданое
3. MainMenuLevel — Используется для задника главного меню от основного режима отличается тем что нет цикла отрисовки который дорисовывает город при движении персонажа
4. Generate Order — Позволяет задать дальность прорисовки для разных модулей (сами модули можно задать в файле LevelGenerator.cpp). Модули разделяются на «Data Fillers» и «Level Bilders» первые данные генерируют, а вторые по этим данным сроют уровень. Цифры дальности представляют собой радиус в центре которого находится персонаж.
5. Дальше идут настройки материала для конкретных элементов окружения.
6. RoadFrequency — Среднее количество ячеек между дорогами. Чем больше число тем реже дороги.
7. MainRoadFrequency — Среднее количество обычных дорог разделяющее главные дороги.
8. RoadSize — ширина обычной дороги в ячейках
9. MainRoadSize — ширина главной дороги в ячейках
10. TowerFrequency — сколько ячеек острова приходится на одну поддерживающую башню.
11. FullBildingTowersFrequency — Количество островов представляющих из себя небоскреб относительно остальных. Чем больше число тем их меньше.
12. FloorNum — Количество этажей уравня. Это число лучше брать кратным число слоев графа + 1
13. CellSize — Размер ячейки.
14. CellHeight — Высота ячейки
15. FirstCityFloor и SecondCityFloor — Эти величины определяют насколько высоко от земли находится уровень.
16. ActorTag — В папку с этим именем будут помещатся сгенерированые экторы
17. GraphNodsFrequency — Определяют среднее расстояние между узлами графа. Чем больше число тем реже граф.
18. GraphLayerNum — Количество слоев графа.
19. HoverCarTrackLayers — Содержит слои с ховеркарами. Каждый слой имеет такие параметры как: Высота ховеркаров, направление полета ховеркаров и среднее расстояние между ними.
20. WallThickness — Толщина стен у генерируемых мешей. Хочу добавить что толщина потолочных перекрытий тоже равна этому числу.
21. ComplicitySpawnForTick — Суммарная сложность генерируемых экторов за один тик. Чем выше число тем больше задержки на спавн и могут возникнуть подергивания при игре. Вы спросите, а почему не устоновить просто количество экторов которое можно генерировать за тик. А потому что разные экторы требуют разные затраты времени на свой спавн. Посмотреть сложность для каждого конкретного эктора можно в файле VirtualSpawner.h.
22. DeltaCellForGeneration — Количество ячеек на которое должен сместится персонаж чтобы началось перестраивание уровня.
23. MinBildingZoneSize — Минимальный размер острова в ячейках. Если вдруг появится остров
    шириной или длинной меньше этого значения то он будет соединен с соседним.

А дальше идут три хранилища (данные хранилища создаются по клику правой кнопки мыши подраздел LevelGen):

TowerStorage

В TowerStorage — Находятся объекты двух видов это:

1. Twers — это объекты которые являются производными от класса LevelTowerActorTower. Они определят как будут выглядит башни идущие сквозь острова.
2. Bildings — это объекты которые являются производными от класса LevelTowerActorBilding. Определяют внешний вид зданий спавнищихся внизу уровня

Итак создав один из блюпринтов мы увидим это:



В дереве построения присутствует объект BordersShower — он нужен для того чтобы можно было понять попадает ваша модель внутрь области которая выделена под неё или вылезает за пределы.

• Size — размер приметив в ячейках.
• BildingHeight — Определяет высоту здания если значение 1 то оно должно не превышать SecondCytiFlore (красный цвет) если 2 то не должно превышать FistCytiFlore + SecondCytiFlore.
  Это необходимо поскольку под дорогами буду спавнится только здания с BildingHeight = 1, чтобы дать простор ховеркарам.
• CellSize — размер ячейки нужен только для правильного отображения BorderComponent поскольку при генерации уровня будет браться CellSize из настроек LevelGenrator.
• FistCytiFlore, SecondCytiFlore — точно также нужны лишь для правильного отображения BorderComponent.

RoomStorage

В RoomStorage находятся объекты которые определяют параметры комнат размещаемых на уровне.

1. NodeRooms — Комнаты расположенные в узлах графа. Являются производными от LevelRoomActorNode
2. GroundLinkRooms — Это секции коридоров соединяющих NodeRoom. Являются производными от LevelRoomActorLink
3. RoadLinkRooms — Эта секция которая вставляется если коридор идет через дорогу. Являются производными от LevelRoomActorRoadLink
4. TerraceLinkRoom — Это секции коридоров расположенные над дорогой вдоль стен. Являются производными от LevelRoomActorTerraceLink

Создав одну из комнат мы увидим это:



Как и в предыдущем случае мы видим BordersShower — но у него уже другие параметры:

• JointSlots — Определяют куда будут присоединятся другие комнаты. Для их задания нужно определить относительную координату и направление из 4. Если определен не правильно то слот окрасится во WrongSlotsMaterial.
• RoomSize — Размер комнаты в ячейках. Все комнаты представляют из себя прямоугольные параллелепипеды.
• RoomWals — Можно добавить ограничивающую комнату стену, задается как и JointSlot. Зачем они нужны? В зависимости от расположения комнату у неё может не быть стен, а если стены здесь добавлены то они будут всегда.
• CanPlayerSpanw — Может-ли персонаж появится в этой комнате.
• CellSize, CellHeight, WallTicness — Точно также нужны только для отрисовки BordersShower на генерацию уровня не влияют.

HoverCarStorage

HoverCarStorage содержит объекты определяющие параметры ховеркаров. Эти объекты являются производными от HoverCarActor.

Вот что мы увидим создав такой объект:



У этого объекта уже нету BordersShower а параметр всего один это Speed определяющий скорость хрверкара, параметр ForwardCarDistance ни как не используется.

На этом все

Ссылка для скачивания плагина

Сюрприз

Тех кто все таки дочитал до конца ждет обещенный сюрприз, и им будет, моя игра «The Future City Project». Игра представляет собой экшен от первого лица с паркуром в процедурно сгенерированом мире.

Ссылка для скачивания «The Future City Project»