Procedural Maze generation using Prim's algorithm

The one constraint of the Rising star challenge was that the game should be held inside a maze. I wanted to add procedural generation to my project to make it more replayable and to learn more about procedural generation, since I had never created procedural generation before. I researched multiple algorithms and found that Prim's algorithm created mazes in the way I wanted for my game. focusing on small paths with a lot of branches.

My goal for this was to create a maze with an adjustable width, height and adjustable amount of monsters in the maze. I wanted these adjustable values, because I wanted to be able to create multiple floors in a maze, having each floor be larger than the previous to make each floor be harder to complete.

These are a few iterations of the end result, showing generated mazes with different heights and widths. Supporting both big and small amounts of tiles.

I will first show how an example of how the algorithm works and then show how I implemented it in my code.

1. We start with a simple 3x3 grid.

2. Now we choose a cell and add it to the maze. (Our starting point)

3. Then we get all cells adjacent to the cell that we just added to the maze in the previous step. From all these cells, we add the ones that are not yet in the maze to a list (We'll call this list the frontier).

4. From the frontier(List mentioned in previous step) we get a random cell. We add this cell to the maze and connect it to a random neighbouring cell that is already added to the maze. Connections between cells are shown through the black line.

5. We repeat step 3, getting all cells adjacent to the cell added in the previous step and add the ones not yet in the maze to the frontier.

6. We repeat step 4, getting a random cell from the frontier. Then adding it to the maze and connecting it to a random neighbouring cell that is already added to the maze.

7. We repeat step 5

8. We repeat step 4, getting a random cell from the frontier. Then adding it to the maze and connecting it to a random neighbouring cell that is already added to the maze. (The cell in the middle is connected to the cell on it's right, but not to the cell above it. This will become important when creating paths between cells later on)

We continue step 4 and 5 until every cell is added to the maze.

Now I'll show how I did it in C++ code.

First I create all required rows, fill them with cells and add them to the MazeCells array. Which will contain all cells of which the maze consists. (The rows are their own objects, since Unreal engine 4 doens't support 2D arrays for UStructs and UObjects).

I choose a starting cell from which the maze will be built and mark the cell as visited (added to the maze).

I choose a starting cell from which the maze will be built and add it's neighbours to the frontier. I also mark the cell as visited (added to the maze).

This is the function I use for adding adjacent cells to the frontier. I get every cell around the cell at the coordinates passed into the function. If these cells are unvisited, I add them to the frontier.

Inside a while loop (while the frontier array size not empty), we get a random cell from the frontier. and get all of it's visited neighbours using the following function.

This function is very similar to the function used to get all unvisited neighbours. It adds all adjacent cells that have been marked as visited to an array and returns that array.

Then I get a random cell from the array returned in the previous step and link the cell selected from the frontier to this cell. This will create a link between both cells. (Which will get replaced by paths)

Finally I mark the cell selected from the frontier as visited, remove it from the frontier array and add it's neighbouring cells that haven't been marked as visited to the frontier array. (This is the end of the while loop. The code gets ran until the frontier is empty. After which every cell in the maze is visited and linked to at least 1 neighbouring cell.)

After generating the maze by connecting cells to each other, I spawn cube actors at the position of each cell and spawn paths between cells that are linked to each other.

While working on this, I ran into some unreal engine limitations. For example, I couldn't create 2 dimensional arrays of UStructs/UObjects. This prevented me from easily creating a grid of nodes and I needed to create a workaround for it. This workaround was using an array of rows, which each had an array of Cells.