Overview of the algorithm

Let’s talk about how our level generation algorithm works.

We are going to separate the program into two parts:

1. Building an abstract representation of the level.
2. Using this representation to construct the level.

Doing so allows us to test and debug both parts separately. It can also make the generator work with any kind of assets, not just tile maps. For instance, you could use a complete scene for each room.

Our algorithm is going to start at the top of the level and walk horizontally and downwards. On each step, we update a state data container that constructs a valid path for the player. After that, we copy rooms from the Rooms scene on this path and move on to filling the remaining unused grid cells.

Let’s break this down a little more.

We start with a grid of a given size, say Vector2(8, 6). With this, our random walker is first going to pick a starting position on the top row, a Vector2(r, 0) where r is a number in the range [0, grid_size.x - 1] inclusive.

Then, the walker generates the main level path in a loop. While we haven’t reached a y position greater than grid_size.y, we:

1. Pick a random, non-blocking room type for the cell, and save our position on the grid.
2. Pick an adjacent position we haven’t visited within the grid’s boundaries.

Once we are at the bottom of the grid, we have a guaranteed path from the level’s start to its end. Then, in another loop, we build the actual level:

1. Place the walls of our level so the player can’t go past the boundaries.
2. Place rooms on the valid path we previously calculated.
3. Loop over empty cells in the grid and fill them with random rooms.