Tuesday, 8 May 2007

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.


tyrecius said...

I'm no expert on either Angband code or on level generation, but here's an idea. Since you care a lot more about which rooms are connected to which rooms, why not create an abstract graph of your rooms? Then, starting with the hardest room, place a room randomly, then all of the rooms it links to randomly, and so on. And you could weight random placement by the distance from the room linking to it. The hardest room could be weighted by distance from the edges so it wasn't as likely to be at the center.

Obviously, this isn't perfect, but it may be better for your purposes. And there are quite a few programs out there for printing graphs which use sophisticated techniques for putting abstract graphs onto two-dimensional surfaces. You could use similar techniques. And once you connected corridors between the rooms of the graph, even if the corridors overlap you'd have a connected dungeon.

As for hints, I know that in Angband unique creatures have 'taunts' where they will say an interesting or amusing message now and again. If you could use that same mechanism to make monsters give hints as you fight them, it might be better. You could likewise weight the probability of taunts based on how close the room is to the hardest room in abstract graph hops or just the distance to the hardest room. The taunts could be something like "[unique] will avenge me!" or "You will never survive the [vault type] vault" or could me more subtle.

Hope you find a way to do themed levels. In my own vaporware roguelike, I want to be able to do themed levels as well, so I hope it is a solved problem by the time I get there. :)

Andrew Doull said...

Firstly, thanks for the thoughtful response.

With regards to room placement, that's basically what I do, minus the weighting of distance (e.g. the room connected to the hardest room could be anywhere in the dungeon). I don't think weighting will necessarily make the remaining rooms randomly placed, but I'll try it and see if that helps.

The hack I was thinking of was placing the hardest to place room randomly in one corner, the easiest in the diagonally opposite corner and every thing else in between. That'd get the rooms placed in some kind of order and might be enough for my purposes.

The monster death cries is a good one: I'll have to borrow it.

As for themed levels, the difficulty seems to be finding a balance between 'this is a fountain level' (good) to 'every room on this level only has fountains' (bad).