ROHAN PATEL
Procedural Map Generation with UE4 C++
wrote on 29th May 2020
Image 1.1
Hi everyone, I hope you are all safe and doing well in these tough times with COVID 19 pandemic.
This blog is about how I created procedural maps aka dungeons generator using the Unreal Engine with C++.
Above shown image 1.1 is a demo video of the working algorithm.
"This blog primarily covers the algorithm and steps to achieve it without going too much into tutorial-like steps as I expect that the readers main interest is in the algorithm and they are aware of using unreal engine with C++"
For the Unreal engine project and C++ files go to this Github Repo.
This blog is divided into the following steps/categories. Feel free to directly jump to any categories by clicking them.
-
Setting up Level and Development environment in Unreal Engine (C++)
-
Spawning Rooms Randomly Inside a circle and Separating them
-
Highlighting main Rooms and further Separation
-
Run Delaunay Triangle Algorithm to draw close triangles
-
Get optimal routes between rooms with Minimum Spanning Tree Algorithm
-
Finally, Generate Hallways base on MST
-
Setting up Level and Development environment in Unreal Engine (C++)
I started with Unreal Engine's basic third-person example map with C++ and created a basic size cube Blueprint as shown below and named it "BP_Room" based on Parent class Room(a C++ base class that we will cover next). We will customize the size while we spawn this Bluprint object from C++ at the time of generating rooms.
I also created a few basic colored materials. (Because I forgot to select starter content while creating the project oops!!) In the following images, you can see the materials and Room Blueprint.
Image 1.2 BP_Room and materials
After that, I created a C++ base class named Room shown in image 1.3 and as I mentioned choose this as a base class while creating the blueprint for BP_Room.
In the image, we can see I created the UStaticMeshComponent variable which I set a physics cube as the value in the BP_Room.
I also created some useful variables such as scale, functions to change materials and separate from other rooms, etc as I felt necessary.
Image 1.3 Room.h
Image 1.2A
Okay without further delay lets jump into the algorithm...
2. Spawning Rooms Randomly Inside a circle and Separating them
As you can read from the title, the ideas here are to generate some points randomly(evenly) distributed inside a circle. After that, I spawn randomly scaled room on those points(locations), and then once they are all spawned I start separating them by moving them away from each other until they are all apart ie none of them is overlapping each other.
Here is the demo video of that.
For spawning points randomly inside a circle with a radius, I created a function as follows.
Image 1.4
After that, I use the SpawnActor() method to spawn the Room and then generate a random scale values X, Y, and Z to set the scale of the room.
Image 1.5
At the end, I start moving overlapping rooms in the opposite direction of each other until they all are separated.
3. Highlighting main Rooms and further Separation
This step is probably the simplest steps of all in which I select some rooms as main rooms and discard the rest of them. To select main rooms there is more than one way to achieve it based on whatever makes it look natural and even distribution as you can see in the following video.
I used a fixed scale to select the rooms if the scale is above minimum threshold I select the room and add it to the container list for main Rooms. After that, I apply the material to those rooms and destroy the remaining rooms which I don't need anymore.
Now what I observed after doing that, is sometimes some rooms were still too close and it was making it uneven distribution so I decided to fix this. Adding furthermore separation fixed it. I started moving rooms further more away from each other if they sitting with less than a minimum threshold distance.
4. Run Delaunay Triangle Algorithm to draw close triangles
Once we have rooms now we need to generate hallways. For that, I will start by generating triangles with the closest distance rooms as following. For that, I used the Delaunay Triangulation Algorithm.
Image 1.6
This algorithm generates triangles bt selecting three closest points and returns a set of triangles. I found someone already implemented the algorithm here so I changed it a bit to add it to unreal engine and used it.
As shown in the above image, you can see there are triangles drawn connecting three closest rooms.
For drawing these triangles I simply used UE4's DrawDebugLine function.
5. Get optimal routes between rooms with Minimum Spanning Tree Algorithm
Now that I have triangles ie routes between those rooms, I need to select a few of them which are optimal when it comes to distance. Also, I need to select only a few of them and make sure that there are not too many routes connecting two rooms, in other words, there should only be a few ways to go to a certain room which is not the case currently as there are many ways in the above picture.
So in order to achieve this, I will generate a graph from the above triangle and feed it to the Minimum Spanning Tree algorithm to select optimum roots to travel between nodes in that graph.
After applying MST I get the optimum routes nodes pair and draw them which will look like following.
Image 1.6
There is one important thing to note here where I added a few extra nodes in the result(of MST) to make the routes look more natural.
Why I did that? Because MST gives us optimum routes which means there is only one way to go to a certain room which is very optimum but games do not do that. In the dungeon crawler game, we have optimum routes but we also have more than one route between some rooms which makes the game map looks more natural and interesting to explore.
I followed this implementation and created a function that returns the pairs of optimum routes.
6. Finally Generate Hallways based on MST
Once we have routes, it is time to generate hallways between them as those straight direct lines look unnatural and very robotic.
I followed a very basic approach in which I take the X and Y axis difference between those rooms and then draw a horizontal and a vertical line between them.
Also all of the above procedures you can see in the video shown in step 3.
Image 1.7
Again there are multiple ways to achieve this algorithm and the whole process. I do not claim that this is the best one out there and this was my effort to implement this as I was very curious about figuring out how it works and it was fun to implement this.
Thank you for Reading :)
Techincal Stats
Tools used:
Download the Project files here
-
Unreal Engine 4.23
-
Visual Studio 2019
-
Visual Studio Code