Procedural Generation Of Mazes In Unreal Engine, Part II

Today, we'll use pattern matching based on a technique I learned in Master Procedural Maze & Dungeon Generation course by Penny de Byl. Although that course is Unity-oriented, the underlying principle is universal.

If you followed along in the last part, and you want to follow along today too, download these five FBX models. We're going to build the entire maze just from them.

Preparing UAssets

Importing FBX meshes to Unreal Engine is straightforward. In the Content Browser, let's create a new folder. We're going to name it Models. Then, we'll drag and drop the five FBX files inside.

Continue With AMazeGenerator Class

When we have our assets ready, it's time to open our AMazeGenerator Actor class to continue with the coding part.

Let's briefly look at what we've done last time. We implemented a recursive Step function with an algorithm that creates a memory representation of a maze as an array of numbers. These numbers are either 1 or 0, 1 means wall, and 0 means a path.

We also declared some properties. These are StartX, and StartY, a starting point for our Step function, Width, and Height to set dimensions of our maze.

That is the place from where we're going to continue. First, in the public section in AMazeGenerator.h, let's add more properties decorated with UPROPERTY(EditAnywhere) macro.

UPROPERTY(EditAnywhere)
    int32 Scale = 300;
UPROPERTY(EditAnywhere)
TSubclassOf<AActor> StraightPiece;
UPROPERTY(EditAnywhere)
TSubclassOf<AActor> TJunctionPiece;
UPROPERTY(EditAnywhere)
TSubclassOf<AActor> CrossroadPiece;
UPROPERTY(EditAnywhere)
TSubclassOf<AActor> TurnPiece;
UPROPERTY(EditAnywhere)
TSubclassOf<AActor> DeadEndPiece;

We'll be getting back to those properties of type TSublassOf<Actor>, but you probably already know why we have them since we just prepared our five Actors from modular pieces.

The one I'd like to stop for a while with is the first one, the Scale, which is by default set to 300. Look at the following top-view picture of our modular pieces.

void Draw() const; void PlacePiece(int32 X, int32 Y, float Yaw, TSubclassOf<AActor> Piece) const; bool IsPatternMatching(int32 X, int32 Y, TArray<int8> Pattern) const;

In a nutshell, the Draw function will loop through our maze array. We'll be testing in IsPatternMatching "blocks" of nine (3 times 3) 1s and 0s from that maze array against patterns of the same size. If we'll have a match, the PlacePiece function places and rotates the piece accordingly.

I'll explain how these functions work in more detail on the fly. Let's now, under those functions define our matching patterns.

// Straight
TArray<int8> HorizontalStraightPattern = { 5, 1, 5,
                                           0, 0, 0,
                                           5, 1, 5 };
TArray<int8> VerticalStraightPattern = { 5, 0, 5,
1, 0, 1,
5, 0, 5 };
// T Junctions
TArray<int8> TJunctionUpPattern = { 1, 0, 1,
0, 0, 0,
5, 1, 5 };
TArray<int8> TJunctionDownPattern = { 5, 1, 5,
0, 0, 0,
1, 0, 1 };
TArray<int8> TJunctionLeftPattern = { 1, 0, 5,
0, 0, 1,
1, 0, 5 };
TArray<int8> TJunctionRightPattern = { 5, 0, 1,
1, 0, 0,
5, 0, 1 };
// Crossroad
TArray<int8> CrossroadPattern = { 1, 0, 1,
0, 0, 0,
1, 0, 1 };
// Turns
TArray<int8> TurnLeftUpPattern = { 1, 0, 5,
0, 0, 1,
5, 1, 5 };
TArray<int8> TurnLeftDownPattern = { 5, 1, 5,
0, 0, 1,
1, 0, 5 };
TArray<int8> TurnRightUpPattern = { 5, 0, 1,
1, 0, 0,
5, 1, 5 };
TArray<int8> TurnRightDownPattern = { 5, 1, 5,
1, 0, 0,
5, 0, 1 };
// Dead ends
TArray<int8> DeadEndUpPattern = { 5, 0, 5,
1, 0, 1,
5, 1, 5 };
TArray<int8> DeadEndDownPattern = { 5, 1, 5,
1, 0, 1,
5, 0, 5 };
TArray<int8> DeadEndLeftPattern = { 5, 1, 5,
0, 0, 1,
5, 1, 5 };
TArray<int8> DeadEndRightPattern = { 5, 1, 5,
1, 0, 0,
5, 1, 5 };

The code is formatted so that the pattern would be more obvious. You might be confused why there are also 5s in there. I'll explain that soon. For now, look at those patterns like 5 and 1 is a wall and 0 is a path.

Look closely at this picture and compare the positions of 1s and 0s with those of the modular pieces.

void AMazeGenerator::Draw() const { for (int32 x = 1; x < Width - 1; x++) { for (int32 y = 1; y < Height - 1; y++) { // Straight if (IsPatternMatching(x, y, HorizontalStraightPattern)) { PlacePiece(x, y, 90.f, StraightPiece); } else if (IsPatternMatching(x, y, VerticalStraightPattern)) { PlacePiece(x, y, 0.f, StraightPiece); }

        // Turns
        else if (IsPatternMatching(x, y, TurnLeftUpPattern))    { PlacePiece(x, y, 0.f, TurnPiece);   }
        else if (IsPatternMatching(x, y, TurnLeftDownPattern))  { PlacePiece(x, y, 90.f, TurnPiece);  }
        else if (IsPatternMatching(x, y, TurnRightUpPattern))   { PlacePiece(x, y, -90.f, TurnPiece); }
        else if (IsPatternMatching(x, y, TurnRightDownPattern)) { PlacePiece(x, y, 180.f, TurnPiece); }

        // T Junctions	
        else if (IsPatternMatching(x, y, TJunctionUpPattern))    { PlacePiece(x, y, -90.f, TJunctionPiece); }
        else if (IsPatternMatching(x, y, TJunctionDownPattern))  { PlacePiece(x, y,  90.f, TJunctionPiece); }
        else if (IsPatternMatching(x, y, TJunctionLeftPattern))  { PlacePiece(x, y,   0.f, TJunctionPiece); }
        else if (IsPatternMatching(x, y, TJunctionRightPattern)) { PlacePiece(x, y, 180.f, TJunctionPiece); }

        // Dead ends
        else if (IsPatternMatching(x, y, DeadEndUpPattern))    { PlacePiece(x, y,  90.f, DeadEndPiece); }
        else if (IsPatternMatching(x, y, DeadEndDownPattern))  { PlacePiece(x, y, -90.f, DeadEndPiece); }
        else if (IsPatternMatching(x, y, DeadEndLeftPattern))  { PlacePiece(x, y, 180.f, DeadEndPiece); }
        else if (IsPatternMatching(x, y, DeadEndRightPattern)) { PlacePiece(x, y,   0.f, DeadEndPiece); }

        // Crossroad
        else if (IsPatternMatching(x, y, CrossroadPattern)) { PlacePiece(x, y, 0.f, CrossroadPiece); }
    }
}

}

Once we have a match, we don't need to perform more tests. That's why the order of the conditional statements is not random. Those where the probability for the match is higher come first.

We delegated logic for pattern matching and placing to other functions. Let's now implement below the Draw the first of them, IsPatternMatching.

bool AMazeGenerator::IsPatternMatching(int32 X, int32 Y, TArray<int8> Pattern) const
{
    int Count = 0;
    int i = 0;
    for (int y = 1; y > -2; y--)
    {
        for (int x = -1; x < 2; x++)
        {
            if (Pattern[i] == Maze.Get(X + x, Y + y) || Pattern[i] == 5)
            {
                Count++;
            }
        i++;
    }
}

return Count == 9;

}

From this function, we want an answer to this question. Does the 3 x 3 "block" of 1s and 0s around X and Y match the Pattern parameter?

The pattern matches when all elements are the same. We loop through all the eight around X and Y plus the one at the X, Y position from our maze array and compare them with the elements in the Pattern array.

When an element in this 3 x 3 "block" from our maze is the same as the element in the Pattern, we increment the counter (Count). In the end, we have a match only when the counter reaches 9, which means that all nine elements must have been the same.

Is that correct? Almost. But there's a catch. If we'd do this exact pattern matching, the final output would look like this.

1 1 0 0 0 0 1 1 0

We have no such pattern defined in AMazeGenerator.h, but we have this one.

5 1 5
0 0 0
5 1 5

And the number 5 here is something we call a wildcard. It could be any number, but the number 5 is visually very different from 1 and 0. You can read the pattern like this:

Whatever  Wall  Whatever
Path      Path      Path
Whatever  Wall  Whatever

Let's look back inside the nested for loop in IsPatternMatchihg. We increment Count when an element in the maze matches with the one at the same position in the Pattern or the element in Pattern is 5.

if (Pattern[i] == Maze.Get(X + x, Y + y) || Pattern[i] == 5)
{
    Count++;
}

Scroll up a bit and look again at all the patterns we defined in AMazeGenerator.h. Notice where we have the 5s.

We're almost at the end. All we need to do in AMazeGenerator.cpp is to implement the PlacePiece function. That's very simple. It just spawns given Piece at position X * Scale, and Y * Scale (Scale is 300 centimeters), rotated around the Z-axis (which in Unreal Engine's left-handed, z-up coordinate system corresponds with Yaw) of a given Yaw angle (in degrees).

void AMazeGenerator::PlacePiece(int32 X, int32 Y, float Yaw, TSubclassOf<AActor> Piece) const
{
    FVector Location(X * Scale, Y * Scale, 0);
    FRotator Rotation(0, Yaw, 0);
    FActorSpawnParameters SpawnInfo;
GetWorld()->SpawnActor&#x3C;AActor>(Piece, Location, Rotation, SpawnInfo);

}

And also don't forget to call the Draw function at the end of the BeginPlay.

void AMazeGenerator::BeginPlay()
{
    Super::BeginPlay();
Maze.Init();
Step(StartX, StartY);
Draw();

}

Putting It All Together

We have our MazeGenerator implemented. We have prepared assets. Now it's time to put it together and let the Unreal Engine generate a maze for us.

In the Content Browser, right-click and add another Blueprint Class. This time expand All classes and derive it from our MazeGenerator Actor class.

Conclusion

In the previous part, we've created a maze memory representation using a simple recursive algorithm. That representation is an array filled with 1s and 0s, where 1 means a wall, 0 is a path.

Today, we've seen how to build a maze from just five modular pieces based on that memory representation, using pattern matching.

If you've followed along and the result is not what you've expected, you can always refer to the example project.

I hope you like what you've learned. Most of it is universal and transferable to other environments. I, for example, used the same algorithm for maze generation in this project with Wolfenstein 3D style rendering, which is something that has nothing to do with Unreal Engine.

You can use a lot of what we've covered in a completely different environment.