Objective:
This article aims to note down the milestone in the procedural map generator in Unreal Engine. Also this is my first Unreal C++ project so I am still exploring UE C++.
UE Version: 4.22.1
Author: Boson
Step to Generate the room
The algorithm I used came from here:
https://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php
This is a old school dungeon map generator. The idea inside this article was pretty easy to implement so it might be a good start for my Unreal C++ practice.
Since there was a fundamental article, I would not introduced a lot about the generation algorithm here. My focus was on the functions and basic knowledge in Unreal C++.
1. Setting up the project
To overview the whole map, I choose a C++ top-down template as my base project. Then I delete all default mesh, clear all transforms for actors in world to make them to center of the world. When user clicks play in this game, user can use mouse click to move the default character (which is the default top-down controller).
Now I have cleaned everything that is not needed. So we are ready to generate room now.
2. Generate Rooms in level
First of all, to generate rooms, we need a room base to stand at the bottom of all other buildings / environment. And the distribution of all room bases describes the layout of this map, which is important.
I created an ARoomBase class which derived from AActor class.
A room should have an unique id, world position and size delta.
2.1 Parameters of a RoomBase:
//An Unique id of this room
int32 id;
//Relative Location of the root component
FVector2D worldPosition;
//Self defined Bounding Box of my Room base
FAABB m_AABB;
The FAABB is a self-defined UStruct bounding box, which describes the center of this room base and the extend from X and Y axis.
2.2 Define the Visual of the room:
staticMesh = CreateDefaultSubobject<UStaticMeshComponent>("StaticMesh");
if (staticMesh) {
staticMesh->SetupAttachment(RootComponent);
static ConstructorHelpers::FObjectFinder<UStaticMesh> myMesh(TEXT("/Game/Geometry/Meshes/1M_Cube"));
if (myMesh.Succeeded()) {
staticMesh->SetStaticMesh(myMesh.Object);
staticMesh->SetRelativeLocation(FVector(0, 0, 70));
staticMesh->SetWorldScale3D(FVector(1, 1, 0.3f));
}
}
In this section, I create a static mesh for the room base and the geometry was the basic cube in UE and I changed its size.
So in Content Browser, the ARoomBase class looks like:
2.3 Create a Room Generator:
Room generator should generate certain amounts of room, the range of size delta of the room, the area where room can be spawned, the room actor to spawn, a list of generated room to store data.
After initializing all those parameters, we can generate rooms now.
// In Begin play function
for (size_t i = 0; i < StartRoomAmount; i++){
FVector Location(AMapGeneartor::GetRandomPointInCircle(CircleRadius), 70);
FRotator Rotaion(0);
UWorld* WRLD = GetWorld();
ARoomBase* tempRoom = Cast<ARoomBase>(WRLD->SpawnActor(RoomActorToSpawn,&Location,&Rotaion));
RoomList.Add(tempRoom);
tempRoom->SetPositionAndScale(i, Location.X, Location.Y, FMath::RandRange(RoomSizeMin, RoomSizeMax), FMath::RandRange(RoomSizeMin, RoomSizeMax));
}
There is two static functions in this class, they help to generate the locations in world where rooms will be spawned, and the location will be rounded according to the tile. In this project, the tile is 4.
int16 AMapGeneartor::RoundnBym(float input, int16 tile) {
return FMath::FloorToInt(((input + tile - 1) / tile))*tile;
}
FVector2D AMapGeneartor::GetRandomPointInCircle(float radius) {
float a = FMath::FRandRange(0.0f,1.0f);
float b = FMath::FRandRange(0.0f, 1.0f);
if (b < a) {
float t = b;
b = a;
a = t;
}
return FVector2D(
RoundnBym(b*radius*cos(2 * PI*a / b), TILE_SIZE),
RoundnBym(b*radius*sin(2 * PI*a / b), TILE_SIZE)
);
}
When we put the Map Generator actor into the level and press run.
It will generate different size of rooms spawned in the level.
3. Separate those rooms
The idea of separating rooms is to calculate the center location of all overlapped rooms for the room. And move the room through the opposite direction to the center of others overlapped rooms frame by frame.
To achieve that, we need to
3.1 add some more parameters and functions for our ARoomBase class.
//*********Parameters**************//
// Shifting Speed for a room when it is collided, it should be the multiple of TILE_SIZE
int32 ShiftingSpeed;
//The lis of stroing others room that overlaped in
TArray<ARoomBase*> otherRooms;
//*********Functions**************//
void SetWorldLocation(int32 i_worldX, int32 i_worldY);
UFUNCTION() // Delegate function for Begin overlap
void OnBeginOverlap(UPrimitiveComponent* OverlappedComponent, AActor* OtherActor, UPrimitiveComponent* OtherComp, int32 OtherBodyIndex, bool bFromSweep, const FHitResult & SweepResult);
UFUNCTION() // Delegate function for End overlap
void OnEndOverlap(UPrimitiveComponent* OverlappedComponent, AActor* OtherActor, UPrimitiveComponent* OtherComp, int32 OtherBodyIndex);
We add a moving speed when we separate the room, a list of other room that overlapped this actor. And the delegate functions for overlap event. Now when other actors overlap with this actor, the functions will be called.
3.2 Activate overlap event from static mesh
In ARoomBase constructor, add more lines to enable overlap events.
static FName MeshCollisionProfileName(TEXT("OverlapAllDynamic"));
staticMesh->SetCollisionProfileName(MeshCollisionProfileName);
staticMesh->SetGenerateOverlapEvents(true);
staticMesh->SetCanEverAffectNavigation(false);
staticMesh->OnComponentBeginOverlap.AddDynamic(this, &ARoomBase::OnBeginOverlap);
staticMesh->OnComponentEndOverlap.AddDynamic(this, &ARoomBase::OnEndOverlap);
3.3 Manipulating the Other Room list
void ARoomBase::OnBeginOverlap(UPrimitiveComponent* OverlappedComponent, AActor* OtherActor, UPrimitiveComponent* OtherComp, int32 OtherBodyIndex, bool bFromSweep, const FHitResult & SweepResult) {
// Other Actor is the actor that triggered the event. Check that is not ourself
if ((OtherActor != nullptr) && (OtherActor != this) && (OtherComp != nullptr)) {
ARoomBase* castedRoom = Cast<ARoomBase>(OtherActor);
// Push the Room into the list if it is a room
if (castedRoom && castedRoom->GetClass() == ARoomBase::StaticClass()) {
otherRooms.AddUnique(castedRoom);
inOverlapListNum ++;
}
}
}
Add the other actor to the list when it is a room, and the End overlap function does similar things but it is removing the room.
3.4 Moving all rooms together
There is a function will be called in Tick() function so it will be called once per frame. It will move the room according to the rule we discussed before.
void ARoomBase::MoveActorsToProperLocation() {
// Only do it when they are collided
if (otherRooms.Num() > 0) {
FVector CenterOfAllOverlappedRoom;
for (auto& room : otherRooms) {
CenterOfAllOverlappedRoom += room->GetRootComponent()->RelativeLocation;
}
CenterOfAllOverlappedRoom /= otherRooms.Num();
USceneComponent* MyRoot = GetRootComponent();
// Other center to Root
FVector Difference = (MyRoot->RelativeLocation - CenterOfAllOverlappedRoom).GetSafeNormal2D();
MyRoot->MoveComponent(Difference * ShiftingSpeed * TILE_SIZE, MyRoot->RelativeRotation, true);
// Round the location according to TILE_SIZE
FVector RoundedRelativeLocation(
AMapGeneartor::RoundnBym(MyRoot->RelativeLocation.X, TILE_SIZE),
AMapGeneartor::RoundnBym(MyRoot->RelativeLocation.Y, TILE_SIZE),
MyRoot->RelativeLocation.Z);
MyRoot->SetRelativeLocation(RoundedRelativeLocation);
worldPosition = FVector2D(RoundedRelativeLocation.X,
RoundedRelativeLocation.Y);
}
}
3.5 Result of separating rooms
4. Selecting main room
The idea of selecting main room is that after finishing separating, using some algorithms to choose some big rooms. The determinant can be the size delta of the room. After that, use Delaunay triangulation to draw the graph of all available rooms.
4.1 Detect when the separating ends
I added an Enum in RoomBase, to determine the type of the room:
UENUM(BlueprintType)
enum class ERoomEnum : uint8
{
RE_NULL UMETA(DisplayName = "Empty"),
RE_MAIN UMETA(DisplayName = "Main Room"),
RE_HALLWAY UMETA(DisplayName = "Hallway")
};
And I add an another Enum in MapGenerator to determine the Steps of generating rooms:
UENUM(BlueprintType)
enum class EGenStepEnum : uint8
{
GSE_GENERATING_ROOMS UMETA(DisplayName = "Generaing"),
GSE_SEPARATING_ROOMS UMETA(DisplayName = "Separating"),
GSE_SELECTING_ROOMS UMETA(DisplayName = "Selecting")
};
We need to enable ticking in map generator to dynamically check if all rooms are separated. There is an extra step in the constructor because in Beginplay(), I spawned a lot of actors so that there is a delay to call Tick().
PrimaryActorTick.bCanEverTick = true;
PrimaryActorTick.bStartWithTickEnabled = true;
PrimaryActorTick.TickGroup = TG_PrePhysics;
These three lines are necessarily needed to call Tick() in MapGenerator.
Then it will be easy:
// Called every frame
void AMapGeneartor::Tick(float DeltaTime)
{
Super::Tick(DeltaTime);
if (GenStepEnum == EGenStepEnum::GSE_GENERATING_ROOMS) {
bool bAllFinished = true;
for (auto& room : RoomList) {
bAllFinished = room->IsFinishSeperating();
if (!bAllFinished)
break;
}
if (bAllFinished)
GenStepEnum = EGenStepEnum::GSE_SELECTING_ROOMS;
}
}
4.2 Determining the main Room
As the article said, use a threshold to decide which room is main. And we need to make sure there some rooms at the center. So the determinant lines will be as below. The code is right after all rooms are finished separating.
if (bAllFinished) {
GenStepEnum = EGenStepEnum::GSE_SELECTING_ROOMS;
if (RoomList.Num() > 0) {
// Calculaing Rooms mean here
float AreaSum = 0;
for (auto& room : RoomList) {
AreaSum += room->GetAreaOfRoom();
}
float AreaMean = AreaSum / RoomList.Num();
// another loop to check if it is larger than mean and if it
is in the center
for (auto& room : RoomList) {
if (
room->GetAreaOfRoom() > AreaMean * SizeThreshold ||
room->IsIn2DArea(CenterArea)
) {
room->SetAsMainRoom(UM_MainRoomInst);
}
}
}
}
The result looks like the following image. To make it easier to see, make the material as red.
5. Determine the path among rooms
5.1 Bowyer–Watson algorithm
For implementing Delaunay-Trianglation, there are serveral ways.
Here is the algorithm I used:
https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm
The Pseudocode of this way is listing here.
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
badTriangles := empty set
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
add triangle to badTriangles
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
I divided it into three steps:
1. Making super triangle which is able to cover all vertices (The center of the room).
2. Looping all uncalculated vertices, calculating it according to Bowyer–Watson algorithm
3. Remove the three vertices from the super triangle.
5.2 Implemeting different classes
5.3 Super Triangle
5.3 Looping all rooms
Boson Area 