The Angband dungeon generation discussion thread

[andrewdoull]

Hi,

I don't want to pre-empt the work that d_m is doing on dungeon generation, but I figured it'd be worth starting a thread to discuss what people want from dungeon generation in Angband. Rather than voice an opinion here, I'm going to do more of a 'lay of the land' discussion to start things off - what can we achieve with dungeon generation vs what we should do for Angband.

Firstly, it's important to point out, that with a couple of exceptions, dungeon generation works surprisingly well in Angband. I say surprisingly, because there is no guarantee of connectivity at all, and yet almost all dungeons are generated connected. I also don't remember seeing too much in the way of complaints ever about directly about dungeon generation from people who play the game a lot - the exception being with the level feelings system, which does need some kind of revision or re-examination. Timo's complaints are more to do with the probabilities of interesting vs. non-interesting stuff occuring on a level. That's one important aspect of dungeon generation, but most people who spend time coding dungeon generation in variants spend as much time working on things like new room generation, as the distribution of monsters and objects.

The key areas for considering improvement I can see are - remember, not all of them are going to be 'good' for Angband:

new room shapes (there are algorithms for most of these in other variants) - overlapping rooms (2 rectangles of varying sizes), fractal caves, cellular automata caves, starburst caves, chambers (a number of rooms tightly linked together), delved caves/burrows, mazes, polygonal / irregular concave rooms, conic section rooms, towns, castles, huge rooms, open regions

vaults: support for more variety of vault contents, rotation / flipping of vaults, 'interesting rooms' which are weaker than lesser vaults, more predictable vault rarity, procedurally generated vaults instead of template generated vaults

monster pits: greater variety, smaller pits, spaced out placement in pits, monster ecologies so that only certain types of monsters are generated across one or more other room types

new room contents: themed treasure, objects, monsters, more ways of associating different monsters with each other (insects, warriors, fire elementals etc), monsters with predictable drops, text descriptions, special regions that prevent item use, spell casting, archery etc, traps with triggerable regions, more variety of trap types, wall and floor decorations

new corridors (assume a running algorithm which can handle all these corridor types): wider corridors, pillared and ragged edged corridors, corridors drawn via projection algorithm (straight or ragged), changing corridor generation to limit the maximum length of straights, cave-like corridors, guaranteed dungeon connectivity via corridors, hints inside a room as to secret door location, secret areas of the dungeon

new terrain types: water, lava, acid, fire, chasms, ice, lakes, rivers, waves, flooded rooms and corridors

dungeon themes: select only some of the above elements for a level in the dungeon in a way that relates them to each other, multiple dungeon branches, multiple dungeons, wilderness levels

guaranteed interesting stuff on a level: improved feelings, auto-scum always on, guaranteed out of depth monsters / objects / vaults, quests, guaranteed resources (food, light, healing, recall)

persistent levels: where taking a previously used stairwell take you to the old connecting level, but unused stairwells in the same direction take you to a new level (cf Entroband/Hengband)

monster ai: patrols, preferred regions, scent trails, foot prints, predator / prey relationships, different ways of moving around the dungeon (flying, swimming, crawling, oozing)

I'll add stuff as it comes to me. The question is what of the above is worthwhile including in Angband, and what should be kept in variants?

Andrew

[Magnate]

I don't want to pre-empt the work that d_m is doing on dungeon generation, but I figured it'd be worth starting a thread to discuss what people want from dungeon generation in Angband.

Before d_m blasts me for over-egging his efforts, my understanding is that he's working on improving room and corridor generation. Much of the stuff below (monsters, items, traps, terrain) is beyond the scope of that. Not sure where that leaves vaults.

The question is what of the [below] is worthwhile including in Angband, and what should be kept in variants?

My opinions on this are simple: anything to do with improving dungeons is possible for V, and anything to do with wilderness / towns / open spaces isn't. So:

new room shapes (there are algorithms for most of these in other variants) - overlapping rooms (2 rectangles of varying sizes), fractal caves, cellular automata caves, starburst caves, chambers (a number of rooms tightly linked together), delved caves/burrows, mazes, polygonal / irregular concave rooms, conic section rooms, towns, castles, huge rooms, open regions

All good for V except towns, castles and open regions.

vaults: support for more variety of vault contents, rotation / flipping of vaults, 'interesting rooms' which are weaker than lesser vaults, more predictable vault rarity, procedurally generated vaults instead of template generated vaults

No objection to this, though removing the vault templates seems quite a bit of work for potentially small gain. I think one of the main objectives of improving dungeon generation should be more frequent interesting vaults. I haven't seen a single GV in dozens of games.

monster pits: greater variety, smaller pits, spaced out placement in pits, monster ecologies so that only certain types of monsters are generated across one or more other room types

Yes, this is a hugely important area for improvement. At the moment in V, aside from vaults, past a certain depth you get only zoos, graveyards or giant/dragon pits. The first two are automatic level-leaving time, and the last two are extremely tedious if you can survive them, and no-go areas if you can't. A greater variety of habitats would make this whole nest/stronghold idea much more fun.

new room contents: themed treasure, objects, monsters, more ways of associating different monsters with each other (insects, warriors, fire elementals etc), monsters with predictable drops, text descriptions, special regions that prevent item use, spell casting, archery etc, traps with triggerable regions, more variety of trap types, wall and floor decorations

Yes, all this could be interesting. What I like about some of these is that you wouldn't need to have them in every game: so, say once in every 3-5 games you got a message saying "you feel a strong anti-magic force on this level" and couldn't use any spells (or devices??).

new corridors (assume a running algorithm which can handle all these corridor types): wider corridors, pillared and ragged edged corridors, corridors drawn via projection algorithm (straight or ragged), changing corridor generation to limit the maximum length of straights, cave-like corridors, guaranteed dungeon connectivity via corridors, hints inside a room as to secret door location, secret areas of the dungeon

All good.

new terrain types: water, lava, acid, fire, chasms, ice, lakes, rivers, waves, flooded rooms and corridors

I've never really been a huge fan of terrain - Crawl has water and lava and I find the additional richness to be more than outweighed by additional irritation and effort required. This is an area for variants IMO, though I know that Takkaria is keen to add more terrain types to V (at least according to the tracker).

dungeon themes: select only some of the above elements for a level in the dungeon in a way that relates them to each other, multiple dungeon branches, multiple dungeons, wilderness levels

I like the idea of themed levels (e.g. a dragon stronghold with nothing but dragons and their minions), but obviously multiple dungeons is variant territory.

guaranteed interesting stuff on a level: improved feelings, auto-scum always on, guaranteed out of depth monsters / objects / vaults, quests, guaranteed resources (food, light, healing, recall)

Here I think we risk entering the "sterile" territory Timo so abhors. I don't think anything should be guaranteed - if we design it well enough it will work 99.9% of the time, and the 0.1% of the time you get (for example) no down stair, that will seem like an interesting quirk. Like Timo, I don't mind the idea of meeting an instakill monster once every few dozen games - I don't need that sort of guarantee. (I *am* concerned to guarantee no death from ID-by-use, but that's a different debate.)

persistent levels: where taking a previously used stairwell take you to the old connecting level, but unused stairwells in the same direction take you to a new level (cf Entroband/Hengband)

Definitely variant territory.

monster ai: patrols, preferred regions, scent trails, foot prints, predator / prey relationships, different ways of moving around the dungeon (flying, swimming, crawling, oozing)

Yes, this is v interesting too. I am rather hoping that Takk decides to go for finite monster mana at some point, because I feel a lot of the AI improvements depend on this (though interestingly not the ones you list).

[buzzkill]

I doubt either of these are 'Vanilla' ideas but I think that a rarely occurring maze level would be cool. One way in and only one way out, no rooms, heavily trapped, and themed monsters. I'm also in favor of persistent levels as you described them.

In general though, I'd just like more variety. When I play FA, I notice the difference, and I like it. Even if you don't want to make radical changes, having several different 'standard' dungeon generation routines would be help. I'd like things to appear fairly normal at first glance, but then would turn out to be something unexpected. Too many room and corridor layouts are entirely predictable. I mean, even without MM, you know where the secret doors are 95% of the time (locked/trapped doors that require keys or picks might be more fun). Pits and many other standard room types aren't much harder to figure out. You can just sense them once you get close enough, even by torchlight, boring.

As an afterthought, how about levels where the various forms of detection don't function, or are limited (with appropriate added incentives, higher XP, better drops).

[cofresi]

Great topic, here's my 2 cents.

new corridors (assume a running algorithm which can handle all these corridor types): wider corridors, pillared and ragged edged corridors, corridors drawn via projection algorithm (straight or ragged), changing corridor generation to limit the maximum length of straights, cave-like corridors, guaranteed dungeon connectivity via corridors, hints inside a room as to secret door location, secret areas of the dungeon Andrew

Wider corridors would spice up the game, changing many defensive tactics. It would make melee more dangerous and would limit the use of hockey sticks. Ragged edge corridors are needed. Currently, the typical enviroment consists of square/rectangular rooms connected by mostly straight corridors. Flavor wise, ragged/snakelike corrodors leading to small interconnected chambers would do more to remind @ they are underground. Tactically, they may change the way we shoot/volley/beam/and bolt. hmm, what would happen to trick shots?

I doubt either of these are 'Vanilla' ideas but I think that a rarely occurring maze level would be cool.

Agreed. Rare maze levels would be particlary challenging if permawalled, Especially in ironman if there is only one exit and it has to be solved. But again, it might fit the variants better than V.

...(locked/trapped doors that require keys or picks might be more fun).

This is a tricky one. Such instances would have to be very rare, as use of lock and key dungeons are what has destroyed the concept of rpg's across many platforms. Roguelikes think outside the box, and are about tactics. I can see lock and key used within special vaults in which they keys, are specific to that vault and useless elsewhere. Levers and buttons that open gates/close traps etc. would make vaults more interesting and certainly more challenging than tpo and get the loot.

so, say once in every 3-5 games you got a message saying "you feel a strong anti-magic force on this level" and couldn't use any spells (or devices??). All good.

This I like. If I may borrow from an 80's game whose key character was *Cough* a minstrel *Cough*, there is a lot that can be done to dungeon floor areas. There could be areas/corridors of hidden runes that can be detected but not disarmed and walking through them would sap hp or mana. The opposite is true, there could be sanctuary areas that increase them. Also, there could be areas that knock out your defenses or dim your lights. Just ideas from the past.

[Marble Dice]

Some greater room variety would be good (shapes/size), but keep the rarity in check. I think large or open rooms get old pretty fast when you see them on every level.

Similarly, dungeon levels that get flooded with corridors are annoying and ugly. V does a good job of avoiding swiss cheese, some variants do not. That said, I wouldn't mind some levels that use primarily corridors (maze/labyrinth style).

I don't really like wider corridors because it feels like rooms connecting rooms, but again with sufficient rarity they could mesh well. I also tend to dislike rooms and corridors with excessively ragged edges because exploring them is time consuming. A little bit of judgement in their design would make them tolerable.

I never really got terrain. Do any variants do anything more interesting with it than drown in water / lava burns you / poisonous plants? Maybe you could have some types with non-damage effects like short-range aggravation (walking on dry leaves) or temporary minor slow-down (walking through thick underbrush). I will say I don't like the varying strength of terrain like in ZAngband, where you have shallow water and deep water scattered about randomly in a body of water. It is somewhat tedious to cross while taking minimal damage.

I actually like valuts from templates, but you could probably do a good job of procedurally generating them. My concern would be to keep them interesting with enough density, chambers, corridors, symmetry about various axises, etc.

[Derakon]

Caution needs to be taken while designing new corridor types to ensure that they aren't a royal pain to explore. The player should be able to run down corridors without either a) failing to reveal a tile that is part of the corridor, or b) being disturbed by something that is not the end of the corridor. FAAngband has new corridor generation, and I don't like it because of these issues. The running algorithm also got tweaked to try to be "smarter", with the net result being that I try to run down a corridor to get somewhere and get taken on this massive detour by the game instead.

I've yet to see something done with terrain that I think is actually worthwhile. Most uses that aren't just colored floors and walls turn special terrain into damage fields, which I don't find particularly interesting. ToME makes the additional mistake of having elemental attacks create damage fields (e.g. fireballs can create lava and frost breaths can create ice) -- barring the absurdity of a Giant Salamander's breath creating a pool of lava, this makes key attack spells very annoying for the player to use. Particularly, cold spells before the player gets levitation, since the ice fields can cause you to "slip" and move in a different direction from the one you intended.

[Psi]

FAAngband has new corridor generation, and I don't like it because of these issues.

Excuse my ignorance, but what is the difference in corridor generation in FAA?

[Derakon]

I can't pull it up right now to look at it, but from what I recall, what turned me off was:

* Corridors are wide and irregular, so to make certain I reveal the walls I have to walk slowly along them, bouncing from one wall to another.
* The run algorithm has been tweaked to make it possible to run down these corridors without getting stopped repeatedly, but these tweaks have the side-effect that it makes decisions "for" you that I don't anticipate. Thus, I try to run to a particular area, and end up taking a detour to an entirely separate location.

It's been a month or so since I last played FA, though, so don't take my words as any kind of gospel.

[Magnate]

Crawl has quite an intelligent auto-explore mode that seems to map corridors and nooks well without doing anything you wouldn't expect. It wouldn't surprise me if some Angband variants had something similar. That said, I feel about corridors a bit like I feel about terrain: I'm not sure the gain is worth the additional hassle.

[d_m]

So I failed to check the Development forum before posting a response on the balance thread. Here it is:

So, here is the 5 second overview of what I was hoping to do (I'm going to lay out the things I want with the understanding that some of them can be stolen from Leon's patch):

1. Circular or other interestingly shaped rooms
2. Better "high-level" control of room placement
3. Distinct "level feels" e.g. cave levels, maze-levels, more-or-less open-feeling levels, etc.
4. More explicit determination of how "good" a level is, in terms of explicitly deciding whether to place vaults, how many, etc, etc "up front"
5. Try to vary dungeon size in interesting ways

Basically, after creating a patch to vary dungeon-size I got (at least somewhat rightly) smacked by PowerDiver for drastically changing the likelihood of finding greater vaults, based on the reduced chance that the generation algorithm would have room to place them (as well as some other more minor issues).

So my idea was to try to determine "interesting" things, like vaults, weird rooms, level difficulty (mabe generation of unique or OOD monsters) first, and then do all the boring stuff like connecting them with corridors or placing boring rooms. I think this would make useful level feelings possible, and it would also make the quality of a level less based on its size.

Whew. That was more than 5 seconds.

I can start a thread if people want to sound off on this.

So yeah, while a lot of the more lofty ideas are ones I find interesting, my big annoyance is how haphazard and opaque the current algorithm is (which Andrew alludes to). I think it's bad that you can't (easily) tweak the sorts of things you might want to tweak without totally messing up other ideally unrelated things.

I also think it would be nice to be able to dial down (or up) the size and complexity of corridors versus rooms--the current dungeons are basically OK as an average (maybe a little corridor heavy) but get kind of boring and repetitive.

I think for Vanilla the best thing is to have lots of interesting stuff, and have it done in such a way that variants who want to steal from it can easily tweak things to get the behavior they want, rather than rewriting everything from scratch (which I believe is often what has happened). Thus it would be nice for V to have themes even if it didn't make as much use of them as variants might.

[konijn_]

Crawl has quite an intelligent auto-explore mode that seems to map corridors and nooks well without doing anything you wouldn't expect. It wouldn't surprise me if some Angband variants had something similar. That said, I feel about corridors a bit like I feel about terrain: I'm not sure the gain is worth the additional hassle.

I've started coding this for Angband and then asked for feedback here or on rgra. I got a fairly eloquent reply on why that would not work for *bands, basically the punishment of not detecting monsters/traps is so big that you need to detect them and take evasive actions if you want to win this game ( you dont want to run into an eye Druj and then say ooops ).

So I abandoned auto-xplore for Hellband at that point.

T.

[andrewdoull]

Agreed. Rare maze levels would be particlary challenging if permawalled, Especially in ironman if there is only one exit and it has to be solved. But again, it might fit the variants better than V.

The maze levels in Nethack are only one screen wide, and are universally hated. I don't think bigger mazes although technically possible will be any fun.

Andrew

[Nick]

I can't pull it up right now to look at it, but from what I recall, what turned me off was:

* Corridors are wide and irregular, so to make certain I reveal the walls I have to walk slowly along them, bouncing from one wall to another.
* The run algorithm has been tweaked to make it possible to run down these corridors without getting stopped repeatedly, but these tweaks have the side-effect that it makes decisions "for" you that I don't anticipate. Thus, I try to run to a particular area, and end up taking a detour to an entirely separate location.

It's been a month or so since I last played FA, though, so don't take my words as any kind of gospel.

I think what you are talking about it is mountain levels, one of the wilderness types. The run algorithm in wilderness is different (it has to be to deal with more open spaces); I am not very happy about the way it works in mountains either. As far as I'm aware, though, the actual dungeon running experience is pretty much the same as Vanilla.

In fact, not breaking running in corridors was in my mind as the first thing to be careful about with dungeon generation changes.

[andrewdoull]

Caution needs to be taken while designing new corridor types to ensure that they aren't a royal pain to explore. The player should be able to run down corridors without either a) failing to reveal a tile that is part of the corridor, or b) being disturbed by something that is not the end of the corridor. FAAngband has new corridor generation, and I don't like it because of these issues.

The running algorithm in Unangband does this correctly as far as I can tell. The only exception is for wilderness paths, which coincidentally are the corridors I stole from FAAngband. I didn't want to get too much into the running navigation issue, as I think I've solved it for the majority of corridor types, and it's the most common issue with unusual corridors, so everyone was going to bring it up.

Andrew

[andrewdoull]

So yeah, while a lot of the more lofty ideas are ones I find interesting, my big annoyance is how haphazard and opaque the current algorithm is (which Andrew alludes to). I think it's bad that you can't (easily) tweak the sorts of things you might want to tweak without totally messing up other ideally unrelated things.

I suspect, based on my development experience with Unangband, is that you'll never get away from opaque, haphazard, hard to tweak algorithms for creating dungeons. That's the nature of procedural generation: you get all sorts of unintended side effects as soon as you touch the dials.

There are some code improvements which can be made relatively easily - more cleanly breaking up the various parts of the dungeon generation into separate functions, which allows you to test and fail generation on various functions. Sangband and (especially) NPPAngband are good examples here.

From your feature list, you sound like you want to adopt some of the major bullet point features of Unangband dungeon generation. How familiar are you with what that code does? It's 15.5 K lines long, so it might be better to chat about it than slow you down by making you read it. The latest SVN has 99% of the bugs shaken out - with the following exceptions:

* Parts of lakes can be cut off from dungeon connectivity by having rooms placed over the top.
* Sometimes corridors end up being walled off - I suspect this is to do with the corridor pillar placement code.
* The dungeon array is getting stomped on by an out of bounds memory write occasionally.
* Room descriptions don't match some room types very well.
* You end up with some crazy terrain combinations (e.g. apple trees surrounded by walls of fire).
* Needs playtesting to find more bugs.

Even if you just compile from SVN and generate some levels, you'll get a feel for whether it fits.

I also think it would be nice to be able to dial down (or up) the size and complexity of corridors versus rooms--the current dungeons are basically OK as an average (maybe a little corridor heavy) but get kind of boring and repetitive.

I think for Vanilla the best thing is to have lots of interesting stuff, and have it done in such a way that variants who want to steal from it can easily tweak things to get the behavior they want, rather than rewriting everything from scratch (which I believe is often what has happened). Thus it would be nice for V to have themes even if it didn't make as much use of them as variants might.

Ah. The old 'Vanilla should be the base for variants argument'. I don't necessarily agree with this (although it would have helped immensely) - mostly because most source control systems don't handle permanent branches too well. T.o.M.E. 3 shows what happens when you attempt to make a module based game.

I started this thread on the Chinese menu approach, where we create a big list of everything we could possible do, and then just pick the bits we want. But in reality, I think we need some 'principles of Angband' that will guide this approach. Magnate saw that straight away, which is why he started with a wilderness != Angband response. But the decision space is still so vast, that having some more design principles will help par down what we can do to a much more manageable level. Here's some other design principles, and some complying variants and violaters by way of example. Please note that I don't necessarily think these principles are the right ones, but they are a good basis for discussion.

1. Every move in Angband should take a constant and predictable amount of time, and be interruptable based on the disturb options a player has set.
Compliant extension: Sangband. Climbing and other actions which take two turns are treated as repeatable actions, which can be interrupted. Violater: Terrain in NPPAngband which takes a hard to predict amount of energy to move through. Hengband/Entroband in general because of monster random energy.

2. Each square holds either an object or a trap, but not both. Only monsters can hide objects or traps underneath them. 50/50 extension: NPPAngband has ranged traps. Unangband has traps with zones of effect which may hold objects.

3. The dungeon is mostly black and white. Creatures and objects are coloured. Violater: Unangband.

4. There should be a non-zero chance of getting killed by an off-screen breath weapon for a monster you weren't aware of. Violaters: Sangband and co, which limit the length of corridors to avoid this.

5. Most of the monsters encountered will be boring and easily beatable - some will be extremely dangerous and not worth fighting. Monster pits are both of these types. Violaters: Oangband and descendants which makes most monsters interesting. Unangband, which only generates monsters of depth near the dungeon level.

6. There should be sufficient space in the dungeon for the player to safely teleport to, some of the time. Teleporting lots of dangerous monsters away (as from a vault) decrease this chance. Violaters: Unangband (currently released version) which felt unsafe because of the lack of space in the dungeon to escape to.

7. Detection magic should be the only way of determining what is on a level outside of the player's LOS, except for an ill-defined 'feeling'. 50/50: Sangband, which has interesting rooms which contain themed monsters, and should provide a hint, but the player almost always encounters the monsters before the room they spawned in. Violaters: Unangband, which attempts to provide hints as to other monsters on the level, by limiting the total number of different races that can appear on the level, and providing textual and terrain based hints as to what monsters can be found.

8. Rooms should be mostly empty. Searching should be limited in effectiveness and replaced by detection magic, which should allow the player to see completely what is on the level, as opposed to e.g. there may be useful objects here, but you have to get closer to find that out. Rubble is the only exception. Violaters: Sangband with it's interesting rooms. Unangband, which has terrain which contains an object, without specifying what that object is.

I'm sure there are more.

Andrew