System procedural level generation in the Unreal Engine

Hello, my name is Dmitry. I create computer games on the Unreal Engine as a hobby. Today I will tell you how I created procedural level generation for my game “The Future City Project”. All source codes will be presented at the end of the article. And there will be a surprise.

Algorithm

First you need to clarify that my game is a first-person shooter with parkour. Therefore, the level should not be flat, that is, there should be some height differences to which you can climb or jump to the opposite. In addition, as the setting for the game, I chose the city of the future with giant skyscrapers and flying hovercars, this also imposed requirements on the level generation algorithm.

1. Since the level is a city, it is necessary to generate a grid of roads. The grid of roads in me consists of two types of roads: these are the main roads and the usual ones. The main roads differ from the usual ones in that they are firstly wider and secondly they cross the city through, while ordinary roads have a length of no more than a quarter. As a result, we get the following picture (I apologize what is crooked):
   ')
   
2. Now we have roads and islets between them. These islands need something to fill. For this, I generate a graph which is a rectangular grid. Each node of this graph will be a room randomly located within the space of a particular island (of course, within certain limits, that is, the next node cannot be before the previous one). I define the rooms in advance. In this case, there may be several layers of graphs to obtain a multi-level structure. And so that these layers somehow intersect nearby graphs have common nodes (rooms), which are determined randomly.
3. It now remains only to connect these nodes (rooms) corridors in accordance with their position in the graph. For this, I used the greedy pathfinding algorithm. That is, I take one of the corridor sections (the corridor sections, as well as the rooms, are determined in advance) and put it to the room exit, then I do it with all the other sections and select the section whose exit is closest to the desired point (which is the entrance to the other room) , after that I do the same thing, but I attach the section already to the section of the corridor found during the previous iteration and so on to the bitter end.
4. After creating the structure of graphs inside the islands. It is necessary to connect the islands with each other. To do this, in the neighboring islands is located around the room that are closest to each other. Then these rooms are connected in the same way as the rest.
5. So, we already have a network consisting of rooms connected by corridors among themselves. But she hangs in the air to do the same. Well, firstly, you can make each of the "islands" a skyscraper and the rooms and corridors will be the rooms and corridors of this skyscraper, respectively. In principle, I did just that with 1/5 of all the islands. But doing so with everyone will be very boring.
6. With the remaining 4/5 of the islands I did this. The upper rooms and corridors form a sort of roof. The rooms that were under them in the inner space of the “island” but I do not fill the space between them as in the case of skyscrapers but leave them empty, so we have “platforms” between which we can easily jump over. I will give a couple of examples:
   
   
   
   Here you can see how the upper rooms and corridors merge into a single roof.
   
   
   
   And here you can see the inner space of such an island.
7. But it turns out that such an island just floats in the air. To get rid of this, I added towers to the islands. Which will support them.
8. Actually the level is already ready but it would not hurt to add several elements to make it more beautiful. First, below, I added a model of the building so that it would not seem that the city is above the desert, here they are:
   
   
9. In addition, I added hovercars plying over the roads.

All procedurally generated city is ready.

How to use

Well, now I will tell you how to use the plugin that you download from GitHub. After you open the project, you will see only a map on which there will be only one LevelGenerator object (If you want to pull this object onto the map but do not see it in the content browser, check the ShowPluginContent checkbox).

So here are its settings:

1. Generate, Rebild level, Delete level - Buttons used for debugging with them you can generate, rebuild or delete the level.
2. Set Generate Seed - Use a random number to generate or set
3. MainMenuLevel - Used for the back of the main menu from the main mode, it is different in that there is no drawing cycle that draws the city as the character moves
4. Generate Order - Allows you to set the drawing distance for different modules (the modules themselves can be set in the LevelGenerator.cpp file). The modules are divided into “Data Fillers” and “Level Bilders”, the first data is generated, and the second is based on this data. Range figures represent the radius in the center of which the character is located.
5. Next come the material settings for specific elements of the environment.
6. RoadFrequency - The average number of cells between roads. The greater the number of the less expensive.
7. MainRoadFrequency - The average number of ordinary roads separating main roads.
8. RoadSize - the width of the usual road in the cells
9. MainRoadSize - the width of the main road in the cells
10. TowerFrequency - how many cells of the island fall on one supporting tower.
11. FullBildingTowers Frequency - The number of islands representing a skyscraper relative to the rest. The greater the number of their less.
12. FloorNum - Number of floors This number is better to take a multiple of the number of layers of the graph + 1
13. CellSize - Cell size.
14. CellHeight - Cell Height
15. FirstCityFloor and SecondCityFloor - These values ​​determine how high the level is from the ground.
16. ActorTag - Generated ectors will be placed in the folder with this name.
17. GraphNodsFrequency - Determine the average distance between nodes of the graph. The greater the number of the less the graph.
18. GraphLayerNum - The number of graph layers.
19. HoverCarTrackLayers - Contains layers with hovercars. Each layer has such parameters as: The height of hovercars, the direction of flight of hovercars and the average distance between them.
20. WallThickness - The thickness of the walls of the generated meshes. I want to add that the thickness of the ceiling is also equal to this number.
21. ComplicitySpawnForTick - The total complexity of the generated ectors for one tick. The higher the number, the greater the delay in spawning and jerking may occur when playing. You ask, why not just set the number of ectors that can be generated per tick. And because different ectors require different time costs for their spawn. You can see the complexity for each particular ector in the file VirtualSpawner.h.
22. DeltaCellForGeneration - The number of cells by which the character must move in order for the level to start rebuilding.
23. MinBildingZoneSize - The minimum size of the island in the cells. If an island suddenly appears
    width or long less than this value, it will be connected to the next.

And then there are three storages (the storages are created by clicking the right mouse button on the LevelGen subsection):

Towerstorage

In TowerStorage - There are two types of objects:

1. Twers are objects that are derived from the LevelTowerActorTower class. They will determine how the towers going through the islands will look like.
2. Bildings are objects that are derived from the LevelTowerActorBilding class. Determine the appearance of buildings spawning at the bottom of the level.

So by creating one of the blueprints we will see this:



In the construction tree there is an object BordersShower - it is needed in order to be able to understand if your model gets inside the area that is allocated for it or crawls out.

• Size - size marked in the cells.
• BildingHeight - Determines the height of the building if the value is 1 then it should not exceed SecondCytiFlore (red) if 2 then it should not exceed FistCytiFlore + SecondCytiFlore.
  This is necessary because under the roads I will only spawn buildings with BildingHeight = 1 to give hovercar space.
• CellSize - the cell size is needed only for the correct display of the BorderComponent, since CellSize will be taken from the LevelGenrator settings when generating the level.
• FistCytiFlore, SecondCytiFlore - just as needed only to properly display the BorderComponent.

Roomstorage

In RoomStorage there are objects that define the parameters of rooms located on the level.

1. NodeRooms - Rooms located in nodes of the graph. Derived from LevelRoomActorNode
2. GroundLinkRooms - These are sections of the corridors connecting NodeRoom. Derived from LevelRoomActorLink
3. RoadLinkRooms - This section which is inserted if the corridor goes across the road. Derived from LevelRoomActorRoadLink
4. TerraceLinkRoom - These are sections of corridors located above the road along the walls. Derive from LevelRoomActorTerraceLink

By creating one of the rooms we will see this:



As in the previous case, we see BordersShower - but it already has different parameters:

• JointSlots - Determine where other rooms will join. To set them, it is necessary to determine the relative coordinate and direction of 4. If not defined correctly, the slot will be colored in the WrongSlotsMaterial.
• RoomSize - The size of the room in the cells. All rooms are rectangular parallelepipeds.
• RoomWals - You can add a wall bounding the room, as well as a JointSlot. What are they needed for? Depending on the location of the room, it may not have walls, and if the walls are added here, they will always be there.
• CanPlayerSpanw - Can a character appear in this room.
• CellSize, CellHeight, WallTicness - Similarly, they are only needed for drawing BordersShower on the generation of the level is not affected.

HoverCarStorage

HoverCarStorage contains objects that define the parameters of hovercars. These objects are derived from HoverCarActor.

Here is what we will see by creating such an object:



This object already does not have BordersShower, and the parameter is only one, it is Speed, which determines the speed of the hrverkar, the ForwardCarDistance parameter is not used either.

That's all

Link to download the plugin

Surprise

Those who still read to the end waiting for the promised surprise, and they will, my game "The Future City Project". The game is a first-person action game with parkour in a procedurally generated world.

Download link "The Future City Project"