Unangband Dungeon Generation - Part Eight (Persistence)

(You probably want to read parts one, two, three, four, five, six and seven before starting this).

It's been a while since I've updated this series of articles, particularly as I prematurely hinted I might be finishing the series in part eight. But I've been thinking a lot more about dungeon generation recently, and how this persistence is important, if you'll excuse the pun.

In most modern games, you take persistence for granted. You open a door, come back to the same location, and the door stays open - blow a hole in a wall, and the hole remains. But scratch the surface of many games and you'll see that persistence is a facade.

Persistence requires memory, a precious resource in computer science that for a long time was heavily restricted. It is only in the last few years that multi-gigabyte memory on a desktop PC is the norm. Streaming the environment to and from disk causes it's own issues, which is why fewer games than you'd expect take advantage of this. But keeping track of persistent object interactions also increases the overall complexity (think CPU utilisation) of the game space as well.

Grand Theft Auto's disappearing cars are a classic example of reclaiming a resource to reduce the scene complexity as well as work on an environment with limited memory. If you walk half a block from any car you've driven and come back it'll be gone. Even Doom 3 cheats death, with the bodies of fallen enemies dissolving away instead of cluttering the environment.

But there's another aspect of persistence that complicates play, and that is persistence can lead to a failed game state. If you can make a change to the environment, and it stays that way, you can end up in a situation where you can no longer finish the game, because some persistent mechanism prevents you from doing so. Imagine filling a room with the dead bodies of your enemies, so that you could no longer walk through it to get to your destination. Or the hundreds of in-game puzzles you've played, where if a puzzle piece is lost or destroyed, it no longer magically reappears at it's starting location.

Respawning enemies usually exist not to continue to make your game harder and unrealistic, but because the rewards that those enemies drop allow you to refresh and regenerate your in game supplies so that you can continue to play - or in the worst examples, so you can increase your power through grinding to make any encounter trivial.

Detecting a failed game state can often be easy - and usually is rewarded with a game over screen, forcing you to start from before the failure. But not every failed game state is so trivially detectable. In fact, I'd suggest through a possibly flawed conflation of two ideas, that detecting failed game states is as complex as the Halting Problem, and therefore impossible in the general case. And the most frustrating thing would be for the player to fail to recognise the problem either, and continue playing from a situation where it is impossible for them to win.

So how does this idea of persistence translate to Unangband?

Well, with many roguelikes, each new dungeon level is a tabula rasa, a blank slate which the errors of the past can safely be erased. Angband is a canonical example of these: the only things to persist between dungeon levels are what you can carry in your inventory, the state you are in, and what the shops and your home holds. This works well for two equally important reasons: with procedural content generation, the game has an infinite amount of content, and so it is easier to throw old content away rather than keep it. And secondly, with procedural content generation it is easy to end up in an unbalanced or impossible game situation, so that provided eascape from the level is possible, the situation can be harmlessly wiped away.

But this lack of persistence breaks the suspension of disbelief, and encourages various types of game breaking behaviour: the worst of which is called stair scumming. With stair scumming, a player stays on the set of entry stairs to the level, climbing and descending them. Since each level is generated anew, it becomes possible to explore a large possibility space, looking for exploitable edge cases such as powerful rewards on the ground nearby, or powerful but vulnerable monsters that can be easily defeated.

It is possible to ensure disconnected stairs between levels to prevent this, so that when you arrive on a new level, you have to explore to find a return set of stairs, instead of them being generated under you. The drawback is that the same exploits that allow easy situations to be take advantage of, allows very dangerous situations to be readily escaped, should an unfortunate cast of the die, or whispered invocation of the RNG, fall the wrong way.

The solution, ultimately, is semi-persistent levels. These were implemented originally in Hengband. Semi-persistent levels are a compromise between the resets and wipes that non-persistence provide, with the stair-scumming prevention of persistent levels. With semi-persistent levels, all levels you visit persist, but are only accessible through the stairs you travelled to them from. With any other stairwell, up or down, you get a new level generated instead.

This ensures the dungeon is still infinite, because there are multiple sets of stairs exiting every level, but that you can visit any previous level by going back up the set of stairs you came down (or vice versa). You can't stair scum, because you just go back to the previous level you visited. But you aren't restricted in explorable dungeon scope, and the resource poor or badly laid out dungeon levels that the procedural content generation throws your way.

You can visualize a semi-persistent dungeon with your current level as the root node, and a branching tree of levels spreading away from it, with infinite leaves.

In part nine, I approach the end game.