In the Obsidian Tower, the room layouts are completely random. Well, almost. Creating these random rooms was one of those challenges where the answer just came to me after mulling it over in the shower, at lunch, and laying in bed for a couple days.

I knew that my requirements were:

1. Each door in the room must be reachable.
2. It looks interesting.
3. There has to be enemies and chests.

To make every room reachable, I began a Depth-First Search algorithm at each door. Think of having a completely solid dirt room and releasing a mole at each of the doors to begin digging. I prohibit the moles to dig through the boundaries of the room, so as they continue to dig, eventually one will reach the tunnel of another mole. This means that the doors which those moles began from are now connected. We continue until each tunnel is connected to each other, and now we have a room that has random paths which connect all the doors and looks interesting.

Getting more technical: Each DFS algorithm replaces a wall tile with the ID of its path unique to the door that it started with. It cannot choose a wall where more than 1 adjacent tile has a path of its own ID. This way there will never be a large open area. Once the DFS chooses a tile that is adjacent to another path of a different ID, all of the other DFS's list of next nodes are combine with the current DFS's and all the IDs of the other DFS are replaced with the current one's. This effectively combines the 2 DFS into one. Continue until there is only 1 DFS left.

Enemies are generated based on how long the tunnels are. The longer the tunnels, the more enemies could spawn, and they are placed randomly in the room on a path tile.

Chests cannot be walked on, so I replaced a random wall tile in the room to choose to be a chest. It also has to be reachable by the player, so I make sure that the random wall block that was chosen is adjacent to a path tile.

And that’s how rooms in the Obsidian Tower are randomly generated!