Every Level Is Winnable, and I Can Prove It

Photo by Joana Godinho on Unsplash

The next game I’m making builds its levels itself. Every floor is laid out fresh: rooms and corridors stitched together, doors hung, a few of them locked behind coloured keycards you have to find first, the odd hidden room for the curious, an exit you have to reach to descend. Play it twice and you’ll never see the same place twice.

This is a wonderful way to make a game. It is also a wonderful way to lie awake at night, because of one question that will not leave you alone once you’ve thought it:

What if it builds a level you can’t finish?

The cruelty of random

Random doesn’t care about you. Give it enough rolls and it will, eventually, hand you the red keycard locked inside the room that needs the red keycard. It will wall the exit off behind a door whose key sits on the wrong side of that same door. It will build a beautiful, atmospheric, utterly impossible maze and present it to you with a straight face. And the player — reasonably — will assume you are the idiot who shipped a broken game, because they have no way of knowing a dice roll did it.

You cannot test your way out of this by hand. There are effectively infinite levels. You will never see the broken one in testing; your players will see it on day one.

Don’t trust it — prove it

So the generator doesn’t get the final say. Every time it lays out a floor, a little solver walks the result before you ever see it.

It starts exactly where you’ll start. It floods outward through every space it can reach. When it reaches a key, it picks it up. When it reaches a door it now has the key for, it opens it and floods on through. It keeps going — reach, collect, unlock, reach further — until one of two things happens: it touches the exit, or it runs out of anywhere new to go.

If it can reach the exit, the floor is real, and you get to play it. If it can’t — if the keys and doors have tied themselves into a knot — the whole level is thrown in the bin and the generator tries again. It’s cheap, it’s quick, and it means every single floor you ever set foot in has been proven beatable before you arrive. You might die on it. You will never be trapped on it.

The bugs the solver couldn’t see

Here is where it gets humbling, because ‘solvable’ turned out to have layers I hadn’t accounted for.

The solver checks the layout — the rooms, the doors, the keys. It does not, it turns out, know anything about the furniture. And so I got a run of beautiful, certified-solvable levels that were nonetheless quietly impossible, because something solid had been parked in the way after the solver signed off:

• A fuel drum — a big, solid, explodable barrel — that generated dead in the middle of a doorway, sealing the room behind it like a cork in a bottle. The solver swore the level was fine. As far as it knew, the doorway was wide open. It had no idea a barrel had moved in.
• A length of wall pipework that routed straight across a doorway, like someone had installed a turnstile and forgotten the gate.
• A bed that stuck out just far enough into a corridor to wedge me in place. Solvable on paper. Not solvable with shoulders.

Each one taught me the same lesson from a different angle: the layout can be perfectly winnable while the furnishing quietly makes it not. So now the set-dressing gets the same suspicion the layout does. Nothing solid is allowed to block a way through, and the automated checks that run on every build don’t just confirm the maze is solvable — they confirm nothing has wandered into a doorway and ruined it.

The actual philosophy

I think people hear ‘procedural generation’ and picture letting the computer do the work. In my experience it’s almost the opposite. The generator is a slot machine — gloriously productive, completely untrustworthy. The real work isn’t the generating. It’s the refusing-to-trust: the bouncer standing at the door, turning away every level that can’t prove it’s fair before it’s allowed anywhere near you.

You’ll never play a floor of mine I didn’t prove you could finish. What you do with that floor is entirely your problem.