Create randomized levels with prefabricated rooms is a great way to increase replayability and is often found in what is known as the Rogue-like/lite genre. Given a collection of rooms, we need to find a way to connect them in a logical manner while maintaining a target room count. In Rouge Star Rescue we’ve devised an algorithm that ensures the player must complete a minimum amount of rooms before clearing the level.

The Main Chain

The main room chain is the shortest path the player can follow, from the start room to the end room. At a high level the algorithm for this is as follows:

— Start by placing a random start room at 0,0.

— Find an unconnected door in that room.

— Create a hallway with limited length from that door, check that it doesn’t overlap with any previously placed rooms or hallways.

— Attach a new random room to the end of that hallway (check that it doesn’t overlap).

— Repeat this loop, treating the newly placed room as the start room, for X amount of times. X is the length of the chain.

(The main chain, of length 8, start room at the top, end room at the bottom)

Branching

Although the main chain is fully randomized, it still doesn’t create very interesting gameplay. We don’t want the player to just go from the start room to end room. We want the player to be able to explore around. In roguelite games it shouldn’t be immediately obvious which door the player should choose. There has to be some side and backtracking to maintain a sense of mystery.

To fix this we add branch rooms to the main chain. These are rooms that extend from the main chain rooms. The high-level algorithm is as follows:

— Choose a room in the existing chain.

— Check if it has any unconnected doors.

— If yes, create a hallway, check that it doesn’t overlap.

— If the hallway is valid, place a random room at the end of it, check that it doesn’t overlap.

— Repeat this for each room in the main chain.

Additionally, you can choose to branch even more by repeating the same algorithm on the branch rooms. You can continue to loop over them as many times as you want, creating a large branch out effect. In our game we specify MAX_ROOMS for each level, and the branches will continue to loop over itself until the MAX_ROOMS number is achieved.

(The main chain with 4 branches added)

Post-Linking Hallways

Branching has gone a long way to create more interesting levels. However after the player plays the game for a while, he might notice that there is a pattern that feels like he’s in a tree with branches. We want to eliminate any chance of the player being able to predict which room to go to for the shortest level completion. For this we add post linking hallways. The high-level algorithm is as follows:

— Loop through each generated room

— check if that room has an unconnected door

— if yes, check if there is another room with an unconnected door nearby

— if yes, make a hallway between them (check for overlaps).

It’s a fairly simple algorithm but the effects of this on gameplay are profound. With this the level generates loops that can lead a player in an exploration circle. Optionally you can check that you are only post linking two rooms that are at a similar degree in the chain generation. For example, you don’t want to post link the second room in the chain with the 7th room in the chain, since by doing so the player will be able to bypass a large part of the chain. In Rogue Star Rescue we ensure that only rooms with a chain degree of +/- 2 can post link.

(Post linking hallways has created a nice loop around chain link #2 and #3)

The details of this level generation implementation are complicated and we will cover more detailed aspects of it in the future. Use this high-level plan to create interesting levels of your own.