Better Constraints For Better Dungeons
Let’s say you want to build a system that can generate dungeons for some some kind of procedural metroidvania game, like a roguelike or a randomizer. The most common approach would be to pluck rooms out of a pool and arrange them in some kind of 2D map.
To get a sense for how that task works, imagine that I took every room in Super Metroid, printed them all out on pieces of paper, and asked you to to build me a dungeon by selecting any ten of them and arranging them on a table. To make sure dungeon is valid, it must satisfy these two rules:
Rooms cannot overlap other rooms
All room exits must align with a matching exit on an adjacent room
You’d probably make a lot of progress really fast, choosing an exit from the previous room to place the next one off of. Eventually, though, you’d run into problems:
What happens when you run out of rooms, but you still have open exits left?
What happens if you have an open exit to an empty space in the map where no other rooms will fit?
How do you recover from bad states? Do you reverse your last step? Give up and start over?
Maybe you’re already coming up with strategies that might make finishing the dungeon easier. For example, maybe you want to avoid creating unnecessary exits that you’ll have to fill in later. You could do that by only using rooms that:
Have two or fewer exits
Only have exits going right or left
Only take up one “screen”
That would almost certainly lead you to creating a valid dungeon on your first try… but what would it look like?
By removing all the rooms that can cause branching, these strategies guarantee that you’ll end up with a linear string of rooms.
By removing all the larger rooms and any that go up or down, you guarantee that it’s flat.
This dungeon would satisfy our stated rules, but it probably wouldn’t be very fun to explore. We could add more rules about the shape or branching of the dungeon, but then these strategies would stop working altogether, because they’d now be at-odds with our stated goals.
Tight Room Constraints Make Boring Dungeons
These kinds of constraints on room size, shape, and connectivity are the same ones used in actual dungeon generators. In fact, it’s nearly impossible to generate great dungeons without them — doing so is probably equivalent to the knapsack problem, one of the hardest computational tasks known to Computer Science.
The more you constrain your rooms, though, the less interesting your dungeons will be, but the easier they’ll be to generate. This is why randomizers and roguelikes usually produce dungeons with the same kinds of problems: boxy, boring rooms, long empty hallways, and spaces that are either either completely linear or impossibly convoluted.
That doesn’t mean those games are bad — it just means they don’t really feel like Metroidvanias. For example, Scourgebringer is a great game with pretty boring dungeons — it doesn’t need a complex world to be fun because it focuses is on combat, not exploration.
If our goal is to create procedural games that center the experience exploration and discovery, we’re going to need new strategies that better support those mechanics. As an example, let’s look at the most common room constraint used in procedural Metroidvania games, identify it’s flaws, and come up with some ways to improve it.
The Perfect Grid
You probably recognize this strategy from Rogue Legacy: the dungeon is built on top of a rectilinear grid, with spaces the size of a single screen, and each room is a rectangle containing an whole number of subunits. Room exits can be placed only in fixed positions along the perimiter of the room (usually the center of each subunit) to ensure that all room exits are compatible with one another.
This makes generation really easy — it’s much harder to “fail” partway through because you’re guaranteed to have rooms you can place in any location. Since all rooms are perfect rectangles, they can never create gaps in your map that are too small for other rooms to fit. It’s also really well suited to Metroid-style minimaps, since all your rooms fit nicely into a rectilinear grid.
A (partial) dungeon generated with these rooms might look like this. (Note that exits pointing out of this image are connected to other rooms, it’s just been cropped!)
First, let’s look at the rooms themselves. Notice how little verticality there is to any of them — rooms that have exits on the left and right sides feel very flat, becuse you must enter and exit the room at the same y-position. This leaves very little room for platforming challenges. I also think having vertical exits in the middle of the ceiling or floor feels really strange, as it forces level designers to place platforms in awkward spots to ensure the player can move up or down freely.
Because of this, many games (including Rogue Legacy) treat most of these single-screen rooms as combat arenas or hallways, restricting platforming to rooms that take up more than one screen… but of course, when your dungeon generator relies on single-screen rooms to function, you’re going to end up with lots of them.
Next, consider the effect of these room designs on the overall vibe of the dungeon. To me, it feels very rigid and boxy, almost like a skyscraper made up of stratified floors broken up into cubicles. It’s also full of dead-end rooms that only exist to cap dangling exits from other rooms, creating a new design problem — what do we put in there to keep the player from feeling frustrated? Treasure? Secrets? More combat?
How do we fix it?
I think the biggest problem with this approach isn’t the rectilinear grid, but the tight constraints on the placement of room exits. After all, Super Metroid rooms fit nicely onto a grid, and that’s still one of the gold standards we compare new Metroidvania games against.
Freeing up the level designer to move the exits anywhere they want along the room perimeter would radically improve these rooms, making them much more expressive. The problem is that it breaks one of our two rules: the exits no longer line up:
Individual rooms do feel much better, though — there’s more room for verticality, fewer awkward platforms in the middle of open spaces, and fewer hallways. These rooms were also way more fun to build than their perfectly-gridded counterparts, because there are so many more options to play with.
What would we have to sacrifice to make this strategy work, and how have other games tried to solve this problem?
Abandoning the Grid
If we didn’t need rooms to align with a grid, we could nudge them up or down relative to their neighbors such that their exits align. A great example of this is the Celeste Randomizer, which can take the game’s original levels and re-arrange them into a snaking path:
The result is completely linear, which suits the randomizer’s gameplay just fine. Looking closely, though, we can also see that it violates one of our core dungeon rules — there are lots of exits connected to nothing! This feels pretty weird, since it’s tricky to know which is the “real” exit and which ones are dead ends.
Teleportation
Another option would be to abandon the concept of actually moving the character between rooms. I mentioned Scourgebringer before — their strategy was to completely abandon the placement of rooms in a shared physical space.
Notice how the left and right exits aren’t vertically aligned, but the minimap is a perfectly square, rectilinear grid — that’s a dead giveaway that some sneaky teleporation is going on. Again, this works well for Scourgebringer, because it’s not vital for the dungeon to feel like one big, connected world.
It poses an interesting question, though— does this violate our rules of what makes a valid dungeon? It certainly feels like it should, since it doesn’t feel much like a Metroidvania dungeon, but all room exits are paired, and the rooms don’t overlap, because we’re never inside two rooms at the same time.
Maybe part of our problem isn’t that we don’t have the right room constraints, but that our rules are wrong.
There Is No Dungeon
The rules I proposed at the start of this post were intended to help us build a dungeon by shuffling rooms around on a table — they result in arrangements where the rooms fit nicely on a 2D plane and we can clearly visualize the connections between them. But… does the player actually care whether our dungeon is planar?
Super Metroid only shows you one room at a time, blacking out the world to scroll the camera into a new space. The in-game maps are representational, abstracting rooms into tidy little squares that fit nicely into a rectilinear grid so that you can figure out where you’re been and where you need to go. Sure, nowadays we can visualize the entirety of its world at once, but nobody playing the game in the late 90’s had that power.
How is that different from Scourgebringer, which limits your view in the exact same way, and makes the same abstractions? They feel different because Super Metroid tricks you into thinking you’re physically moving from one space to another, but in reality it’s loading and unloading rooms from memory. Scourgebringer lets you in on the dirty secret — there is no dungeon, there are only rooms.
What matters isn’t whether the dungeon fits on a table, but whether it fits in the player’s head.
A Better Set of Rules
Let’s re-write our original rules from the perspective of the player:
The player can never be in two rooms at the same time
Rooms can be represented clearly on a 2D map
The player must be able to move through any room exit and into an adjacent room
This lets us re-evaluate our previous attempt from a new perspective:
Does this dungeon pass our new rules?
These rooms still fit into a grid, which means the player can only be in one of them at a time.
Clearly, we can represent this dungeon on a 2D map — we’re looking at it!
Can the player move between the rooms? Well, that depends…
What if the player teleported between rooms instead of walking, like in Scourgebringer? That would mean this dungeon passes our rules just fine. We only ruled that option out because it degraded the player’s sense of the dungeon existing as a big, physical space… but what if it didn’t?
Here’s a prototype I built in Unity, which shows the player moving through four rooms in a loop. Notice anything weird about it?
As a hint, here’s the same four rooms rendered like the dungeon above:
The secret to this approach is combining performance optimization techniques with a little bit of Non-Euclidean Trickery.
Dynamic content loading (or “chunking”) is a common strategy where content that’s hidden from the player is disabled or degraded, cutting out extraneous processing and rendering work that would otherwise be wasted. In a 3D game, you might do this by avoiding loading in terrain that’s behind the player, or rendering far-off or partially-occluded content at a lower detail level. When done correctly, the player will never notice this is happening, and it’s critical to making huge open-world games run efficiently while maintaining the illusion of a big, continuous world.
We can use the same tactic here: we activate the next room when the player approaches an exit and deactivate any others, but we also move it such that its entrance matches perfectly with the exit of the previous room. The result is that the physical location of each room is decoupled from its theoretical position in the minimap, creating a playable space that’s just slightly Non-Euclidean.
Instead of teleporting the player between rooms, I’m essentially teleporting the rooms to keep up with the player.
Here’s how it looks in-game, using the same dungeon as before:
And here’s what it looks like from a zoomed-out camera:
Why does this trick work?
I don’t know for sure — to be honest, when I came up with it at 3AM, I didn’t expect it to work at all.
If I had to guess, I think it leans heavily on our collective assumptions about how the standard Super Metroid-style camera should work when transitioning between rooms of different sizes. Having a minimap also helps, since it will automatically “correct” any drift in the player’s estimation of their overall location within the dungeon.
The player’s state is unaffected by these transitions — their position in game-space isn’t modified at all — which means that mobility and momentum can be preserved when traversing between rooms, making exploration feel more dynamic and fluid. It feels totally normal to wall-jump your way up to the next room, because by the time you can perceive a room, it’s already in the right spot.
This isn’t a perfect fix — I’m still working out the kinks, and it won’t make complex shortcuts and secrets any easier to generate, but I’ve found it very effective in my own game, and I think it might be a useful step towards improving the way roguelikes and randomizers feel to play through… even if it makes them look weird on paper.