A Long Dark Tea-Time of the Soul

This is nothing to do with the book - I just like the turn of phrase.

I've taken a little time out from Unangband development, but am now back in the thick of it, which is where I am having my proverbial cuppa. And reflecting on where I am at, I can say assuredly: 'Don't mess with Angband level generation'.

I mean, I know the code inside and out, I've 'hardened' the code, in the style of NPPAngband, so that it gracefully aborts from many potential infinite loops. I've improved the tunnel generation code so that it actually checks connectivity between all rooms instead of just hoping for it. I've added lots of terrain, different room types, monster ecologies, room contents based on the description of the room, theming of levels, room decorations and more, which work really well together.

And yet I'm still not happy with it, and can't tell you definitively whether any change I intend will work or break the code.

This is the soul-destroying part.

Level generation isn't clean code. Its lots of 'tried and true' heuristics to try and connect funny shaped bits into an interesting topology. I refer you to a great paper on procedural terrain generation (pdf) in the game Tribal Trouble that attempts to emulate erosion using a number of 'real world' algorithms as a part of their level generation. The solution: thermal erosion doesn't work quite right using the physically correct model, but hey, if you reverse the sign on the key equation, it looks much better. So lets use it.

I've got quite strong ideas about what constitutes a level, as least as far as Angband goes. It should be a topology of 'interesting' and 'uninteresting' rooms with 'good' connections (and some 'bad' connections), and contain a 'theme' that a player can choose either play in or bypass.

All 'interesting' rooms should have 'good' connections, so that the player never has to cheat to get between them. 'Uninteresting' rooms can have 'bad' connections: these are primarily so that monsters can navigate between them. A 'bad' connection could be hard to navigate for the player (e.g. filled with lava). The 'interesting' rooms should be ranked in terms of increasing 'interesting-ness', with equivalent escalating threat levels. The 'most' interesting room on a level may be 'badly' connected though. It contains the best reward, and should be a challenge to get to.

The 'theme' is usually a set list of monsters, plus some 'themed' rewards. Because we have an infinite pool of levels to pick from, players should be able to pick and choose from this pool relatively easily (by moving to another level if required).

So this implies a starting area with a number of staircases leading from it: a partial ordering of rooms away from the starting area, a vault or some other reward location that potentially hard to get to, and a ranking of monsters from easy to hard within a level.

Of course, Angband's level generation gives none of this.

And how does Unangband's level generation shape up?

1. We place the hardest room first, because its usually the biggest and hardest to place. Of course, that means it'll get in the way of any attempt at partial ordering, because statistically, the big, hard room will be in the middle of the level.
2. Connecting rooms is hard. Real hard. Its the likeliest reason for infinite loops. And I get these even just ensuring all randomly placed rooms are connected. Forget trying to connect them in any order.
3. If we can't connect the rooms in any order, its sure hard to figure out where to place the starting room, or to generate monsters in increasing level of difficulty.
4. I've got this great system of room descriptions to hint what the toughest monster on the level is. But its based on monster attributes (drops potions = laboratories, fires arrows = rooms filled with broken arrows), that don't actually tell the player what the monster is: except for leaving dead bodies or statues of the monster around which (may) tell the player exactly what it is. So the player usually runs into the monster, before having enough information to be helpful. And if I don't add a little bit of noise, it makes the levels look really boring. But that just makes the even limited information about the monster too unreliable...

Ah well. Writing this has given me ideas. But none of them are elegant - they're all just variations of hacks. And I don't have any guarantees that they'll work.