The Angband dungeon generation discussion thread

[Nick]

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).

Another one is breaking LOS without blocking movement. There's also the feature that different monster types can interact in different ways with different terrain - so a vault full of lava and populated with demons that can walk across it is an interesting challenge.

[fizzix]

Just a quick (or not so quick) suggestion about terrain. This also ties in with AndrewDoull's point 7 about detection being the main source of finding stuff out of LoS.

There has been a bit of chatter about tweaking detection and ESP, namely reducing its efficacy. I think that this is a place that terrain (and junk) can come into use.

A simple application is to add terrain features to the dungeon randomly around a particular elemental creature. These would be something like scorched, melted, scarred (from elec) frozen, fetid walls/floor. I think this would be a pretty easy terrain application to code in and could be a first step at improving boring dungeons. The presentation to the user is difficult though.

Now, a much harder approach but possibly with more payoffs would be a knowledge system where @ learns the markings of monsters. Searching on a floor where a monster stood has a chance for @ to learn the prints, scratches, slime trails of that monster. Then in the future searching has a chance to tell @ what monsters have been there. These features get placed somewhat nearby in the same way that the obvious scorched walls get placed when a monster is generated. However, these would only be obvious if @ is searching for them. The idea would be that using S search would be a weak but functional replacement for ESP/detection, and can fill in the gap if these are weakened.

On the topic of dungeon generation. I think a lot can be gained by tweaking the room and special room generation to include vastly more varieties. Also the suggestion ( i think it was a suggestion) of dispersing pits around a section of the level is a good one.

[tigen]

I think judicious terrain is cool and adds tactical spice, and also flavor.
- translucent walls, block attacks but not LOS
- terrain with shifting smoke and mist, block LOS but not attacks
- water or lava blocks (some) movement but not ranged
- could also block ranged but not movement etc. (imagination)
- terrain interactions; e.g. flying, swimming, hide-in-terrain
- stuff can "catch on fire", leave smoke trails, etc.
- movement speed modifiers = tactics

When multiplied into the level generation it also significantly expands the variety/scenery which is important in and of itself. The rarities can always be tweaked.

*****

With more varied dungeons, the old lighting model could be re-examined. In old Angband, you can light rooms or straight lines with the wand. This works well when levels are nothing but rectangle rooms and single-grid corridors. It's annoying when you get other shapes and can't light up areas because the game doesn't consider them a room. Probably, the light spell(s) should be made more generous and be allowed to flood fill more irregular areas.

[Derakon]

I'm just going to outline a map-generation algorithm I've written that has the following characteristics:

1) It guarantees connectivity
2) It allows for easy modularity at both local and global levels
3) It is relatively straightforward and easy to modify

Here are some examples:
Tiny map
Midsize map
Really huge map

The mapgen algorithm is the one used in the 2D platforming game I work on from time to time, Jetblade. Of course, side-on 2D transfers to top-down 2D easily. In fact, top-down would actually be easier because connectivity == accessibility in top-down views, which is not true for side-on views due to gravity. You can take a look at the Python sourcecode (in map.py and treenode.py) if you want to see it in action; it's about 2k lines of Python, not counting modular components. Anyway, here's the algorithm in brief:

1) Generate a planar tree in the map space. This is done breadth-first to ensure that near-root branches of the tree do not get cut off too early.
2) Randomly connect some nodes of the tree to other nodes that are close spatially but not close by tree traversal (i.e. they are multiple steps away from each other on the tree).
3) Plant "seeds" for a spacefilling cellular automaton along the edges of the graph.
4) Expand the seeds out, using the following two basic rules:
* An empty space adjacent to seeds from two different nodes of the graph is replaced by a wall.
* Otherwise, an empty space adjacent to N seeds from the same branch is replaced by a seed from that branch, with lifespan equal to the longest-lived of the adjacent seeds, minus 1.
5) Detect small islands in the map and remove them
6) Remove walls that come to close to nodes in the tree

Step 3 is modular in my current system, and there's a step that runs after step 6 to allow for addition of new walls (e.g. to generate small local mazes). Additionally, the rules for generating the planar tree at the start are somewhat configurable.

The biggest problem I have with this algorithm is that it's pretty slow; I just made a 271x241 map in 20 seconds. However, the code is as-yet largely unoptimized, most of it's written in Python, and there's numerous steps that wouldn't be needed in a top-down game. I estimate that removing the unneeded steps would put this map at about 11-12 seconds in Python, with a speedup of around about 70% if you used something precompiled like Cython instead. So, still not great.

I know this isn't entirely relevant to the topic at hand; I just wanted to point out that you can make reasonably nice-looking maps without sacrificing code readability/flexibility.

[d_m]

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.

I just drove 5 hours to my parents house and ended up with a migraine, so I can't really write a real response to you. The one thing I want to say is that I'm not so much trying to avoid *any* unintended consequences as that I want to have a few dials that correspond to things I care about, rather than having very few dials which don't correspond to anything very interesting at all.

Derakon: I will definitely read your Python code (it being my favorite language) and see what it does!

[Djabanete]

Having played a few different roguelikes/*bands, I know what I like in terrain:

• A certain amount of variety in terms of rooms; circles, starbursts, interlocked rooms, overlapping rooms, etc. are all welcome.
• Easy-to-navigate corridors. Unlike Crawl, Angband does not have an auto-explore feature (for good reason), so I prefer corridors that are navigable by a small number of keystrokes. Wide corridors are fine, as they add some difficulty and interest, but are manageable from a UI perspective as long as you have radius 2 light.
• No special terrain. You know what I love love love about Vanilla? Every bit of terrain is either a wall or a floor (fine, traps and doors too. And rubble.). It's great. Whenever I play a variant, I do my best to hack the edit files so as to get rid of annoying terrain types. Really, I don't want ice, water, lava, trees, or glass walls, let alone more complicated structures. I'm not sure how to explain this preference, but I feel strongly about it. If weird terrains were introduced in Vanilla, I would not be happy unless there were an option that prevented that stuff from being generated. (Permarock vs diggable rock is an important part of tactics though.)
• Not too many huge open spaces. I'd actually be quite happy to have towns* and/or castles (unlike Magnate, who seems to feel the same way as I do on most dungeon feature ideas) --- as long as there are walls to duck behind and corners to hide in, I'm happy. Occasional terrain challenges make the game interesting, but too many huge open spaces just get old really fast. (And they make for extremely unsafe teleports, and consequently some extremely unfair deaths.) *I don't mean towns with stores in them, I mean town-shaped regions with lots of critters, over which you must prevail by judicious application of John McClane tactics. Doors/walls/rooms are a must, with the rooms preferably containing stockpiles of loot.
• I don't like themed levels. I like themed rooms, but not themed levels. I'm not sure how to explain this preference, but I'll try to. I think it has to do with the fact that I like my levels to be open-ended puzzles whose nature is determined by the individual pieces (i.e. rooms). My favorite levels are the ones with a vault here, a dragon pit there, a themed room there, a nasty unique over there. Those are the fun and exciting levels. I don't want a single blanket condition, applied to an entire level, to uniformize things. This is just personal preference. I'm not sure that I explained it well but I do feel strongly about it. Here's an analogy: Think of the dungeon level as your dinner plate. Would you want an entire plate heaped with mashed potatoes? Even if you like mashed potatoes, you'd be sad if that was your whole dinner. No, surely it would be better to have some roast beef, some mashes potatoes, some asparagus, some fresh bread, a salad on the side, maybe some wine. And how about ice cream and pumpkin pie for dessert. (I'm hungry.) Say no to huge plates of mashed potatoes.

OK, I also want to add my two cents on themed rooms. First of all, I agree with UnAndrew that it could be beneficial to have a couple more ways of linking monsters thematically. We can already meaningfully categorize monsters by letter and by "family" (for want of a better word: I mean evil, dragon, animal, etc.) I think that monsters could profitably also be categorized by "class" ("mage" type monsters, "holy" monsters etc.), and by element (fire monsters, ice monsters, etc.) This allows pits/nests and themed rooms to have a lot of variety in what they contain.

I really like Hengband's "letter rooms" (what I call them): rooms containing several (OOD?) monsters of the same letter, generated awake. These rooms can be quite spicy (D, h, A, p), and often it's best to just run away, but they're almost never unfair. (You won't die to them unless you're being brazen --- usually.) This concept can easily be extended, of course --- instead of monsters all of the same letter, there can be monsters all of the same family, class, or element. (Although sometimes you can't tell the difference: o/T vs orc/troll family, for example. Doesn't matter.)

That was a lot of text, and all of it, of course, is just this man's personal opinion. I don't think anything I've recommended would be unsuitable for Vanilla. (Cool room shapes --- town-shaped or castle-shaped dungeons that aren't *too* open --- wide corridors (all this in moderation of course) --- themed levels --- a couple more ways of grouping monsters for the sake of variety.)

[Magnate]

• Not too many huge open spaces. I'd actually be quite happy to have towns* and/or castles (unlike Magnate, who seems to feel the same way as I do on most dungeon feature ideas) --- as long as there are walls to duck behind and corners to hide in, I'm happy. Occasional terrain challenges make the game interesting, but too many huge open spaces just get old really fast. (And they make for extremely unsafe teleports, and consequently some extremely unfair deaths.) *I don't mean towns with stores in them, I mean town-shaped regions with lots of critters, over which you must prevail by judicious application of John McClane tactics. Doors/walls/rooms are a must, with the rooms preferably containing stockpiles of loot.

I've been thinking about this. I'd be ok with subterranean towns, I think. We're basically just talking about a bunch of aligned rooms in a regular pattern with linked monsters - a bit like the Elven Halls in Crawl (or the Vaults, I guess). Angband's dungeon is so vast that it's quite understandable that you'd stumble upon such a thing every now and then - an area where more work has been put in to taming the rock than on most levels.

Conversely I really hated destroyed levels and am not sad to see them gone, despite the fact that exactly the same logic applies. I guess they were just too irritating.

[RogerN]

I just wanted to chime in regarding corridors. I have a very strong preference for corridors that are easily navigable. In other words, I want corridors in which I can start running and travel the entire distance without a second key press (assuming a monster or item doesn't interrupt).

Corridors wider than 1 tile make and the above requirement tricky at best, and probably would necessitate further UI options to control how the running code behaves. I don't think we want that.

No offense to Andrew, but Unangband's odd corridors are probably my least favorite feature.

[d_m]

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.

At one point I played a bunch of Unangband but was feeling overwhelmed by the amount of stuff I could (and/or needed to) do. I felt the same way when I was learning to play TOME awhile back, although I eventually (kind of) figured it out. I'll see if I can't get this druid character doing well... worst case I will just use debug mode to create an uber character and then wander around.

Which dungeons do you recommend looking at? I tend to be foolhardy and try Farmer Maggot's dungeon, and all the plants are pretty disorienting. Ideally I'd try out some dungeons which are more similar to the "kind" that V expects to generate.

Thanks for your help! One approach I've been thinking of is to write (and/or port) dungeon generation code to use function pointers as callbacks so that it's possible to write small stand-alone dungeon-generation programs. This would enable one to write unit tests and/or brute force tests on dungeon generation. Ideally this would make the code easier to port between variants, since it would remove some of the dependence on specific data structures that might change. Maybe this seems misguided?

[d_m]

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 do think that if V moved to Mercurial (or git) it woudl be possible (albeit with some work) to maintain a variant-branched off of V and to periodically pull down changes and merge (or ignore) them. There would probably be some cases where it would be annoying (and there might be some weird patches going back upstream to put in hooks that are only used in variants) but I think it would be doable. Also, it might help keep push features from variants back into V.

As far as your rules, here are my feelings:

1. Agreed.

2. This is currently true and it's certainly essential that you be able to easily identify which squares are trapped, but if there was a way (e.g. via bg color) to indicate a trapped square holding an item, it would be OK.

3. Agree in general.

4. This seems more like a description of what's currently true. I guess I can imagine the argument that reducing or removing this would make detection and ESP less powerful, but I don't know if that's an essential property of V.

5. I think your formulation is a little bit unfair--given the way people play Angband, pretty much *all* monsters who aren't extremely dangerous are easily beatable. I'm not sure that monsters being "boring" or "not worth fighting" is at all intrinsic to V.

EDIT: Upon rereading I think I may have overstated this. People are pretty invested in keeping enemies that aren't worth fighting. I guess I really object to the idea that monsters should be either boring or not worth fighting, and/or that there should be lots of monsters not worth fighting. I personally would not mind a reduction in "not worth fighting" monsters, either by making them worth fighting or removing them.

6. Agreed. This is definitely something a lot of players feel strongly about, even though I personally think it's OK to have some levels which are less safe.

7. Again, I think you are describing the current state of V. I think improved feelings which were actually useful would be OK; I also think feelings applying only to a part of a level would be OK. Maybe other V developers feel differently?

8. I think I agree, although on Timo's recent thread he has argued that in fact V used to have a strong tradition of not giving the user complete information even when using detection, so I'm not sure this is set in stone. I do think the argument that the dungeon should be less "cluttered" is probably true.

Since Takkaria has the last word on a lot of this stuff I can't be certain, but I think at least some of the principles you outline are not first principles (or at least, they may have been but aren't currently).

[will_asher]

I thought I'd add to the discussion by saying how I've changed this kind of thing in DJA. There are some things I would've liked to do differently, but I'm restricted by my limited coding ability.
- room shapes: I like to have veriety in room shapes, but I don't really know how to code room/corridor shapes or dungeon generation in general so the way I did this is kindof hacky. I just made a bunch of new room designs in vault.txt. Then I made a new room type to be generated pretty much the same way that vaults are generated except that they aren't designed as vaults. Additionally, sometimes empty vaults are created which use vault designs but without most of the monsters and treasure (and walls often turn to empty space or rubble so that you can usually get into them without tunneling).
- themed levels: Probably not as complex as themed levels in other variants. In DJA, it only means that certain types of monsters are much more common than other types (and it's more likely to have out of depth monsters), and that there's a little bit of terrain flavor (trees and water, or in a dwarf mine you might find rubble in the middle of rooms instead of only in the corridors).
- terrain types: The only new terrain types I've added are trees, open pits, and water. Trees are in the game as monsters that don't do anything (and aren't detected by detect monster, but do appear with mapping spells). Open pits are rare except when caused by earthquake or destruction effects (It seemed to me an earthquake should mostly make pits and rubble instead of walls where ther used to be floor and floor where there used to be walls). The terrain is really there for flavor only and doesn't have much real effect in the game.
I'm conflicted about whether to add other terrain types. Certain themed levels would work better with fitting terrain, but I'm concerned that the gameplay effects might not be all good or (like Djabanete said) that they'd just be annoying. If I do add other terrain types, they'll probably be for themed levels (or vault designs) only and never appear on other levels. (currently trees and water do occationally appear on normal levels).
- themed rooms: I don't see how this could work well unless they were made by design (like in vault.txt). And even then, monsters appropriate for themed rooms would often leave the room before you meet them. Mentioning things like broken pots or shelves on the wall is kindof nice for flavor, but it isn't interesting enough to me to want to take the trouble to add that kind of thing to DJA.
- different sized pits and nests: I would definetly do this in DJA if I knew how (and maybe I will figure it out). Currently pits are too big. If the monsters are easy they're boring, and if they're hard you stay far away from the pit. Either way it doesn't add to gameplay. Making pits about half the size they are now would prevent them from being boring (because it's a lot quicker to clear them out) and make it less likely that you'd want to stay away at all costs (and animal pit with one greater basilisk and one gravity/time/chaos hound is not nearly as scary as a pit with several nasty hounds mixed with winged horrors and an elder aranea).
- other stuff to give my 2c on: I agree with the others who have said the maze levels would only be annoying in Angband. I like the idea of town/castle designs for levels (as Magnate described them), but I don't think they should be too common. I think keys & locked doors could work IF: 1) they were all generic and any key would work in any locked door. So that you didn't have to look for a particular key, but once you used a key it would be used up so that you'd have to find another key to open another locked door. 2) they didn't take up inventory space. Inventory management is part of the game, but if it were any harder it would be a royal pain.
Currently in DJA, traps and items can be in the same space (but are never generated originally in the same space). In DJA1.1.1, there's no way to see the trap in the space, but I fixed that for the next version. Still, even in the next version, you have to (l)ook at the space to see that there's a trap there.

On another note, I think detection is both essential and overpowered and I don't know how to reconcile this. I think some monsters / traps / hidden objects should have ways of avoiding detection, but I'm not sure how this would work without making things seem unfair to the player.

[Magnate]

I do think that if V moved to Mercurial (or git) it woudl be possible (albeit with some work) to maintain a variant-branched off of V and to periodically pull down changes and merge (or ignore) them. There would probably be some cases where it would be annoying (and there might be some weird patches going back upstream to put in hooks that are only used in variants) but I think it would be doable. Also, it might help keep push features from variants back into V.

Personally I think the heyday of "variant explosion" has passed, and we will see fewer variants in future. That said, a nice modular design to V would allow the rewriting or updating of dead variants with interesting stuff in (Kam, Kang, GSN etc.) - one of my many retirement projects.

7. Again, I think you are describing the current state of V. I think improved feelings which were actually useful would be OK; I also think feelings applying only to a part of a level would be OK. Maybe other V developers feel differently?

I think the whole concept of "level feelings" is idiotic. They are tactical hints which completely ruin the suspension of disbelief and have no place in the immersion aspect of the game. IIUC they were only introduced in the first place to stop people whining about missing artifacts before the advent of preserve mode. IMO they could be dispensed with altogether, if detection magic were more granular. Instead of a single fixed radius of detection, which you either have or don't, there should be Minor, Lesser and Greater Detection, each having a further reach than the last. (This increasing radius being orthogonal to the detection of visible monsters, invisible monsters, normal objects and magic objects, giving you lots of permutations.)

EDIT: That said, I could readily accept sensible observation-based hints on themed levels, like "you see an unusual amount of dragon excrement lying around" ...

[d_m]

EDIT: That said, I could readily accept sensible observation-based hints on themed levels, like "you see an unusual amount of dragon excrement lying around" ...

I think this is really what I was getting at: either smelling or hearing something, or having certain levels have an obviously more ornate design, or even carved warnings or something.

While the idea of an in-game spoiler about whether there's anything worthwhile on the level is clearly dumb, people do enjoy getting little messages from the game about things like that and I think it could be useful to expand/rationalize that system (since trying to remove it has met with such fuss already). I think Hellband does this very well.

[Marble Dice]

I think this is really what I was getting at: either smelling or hearing something, or having certain levels have an obviously more ornate design, or even carved warnings or something.

Sounds kinda like the level feelings in Spelunky? They show up periodically and determine some special features on that level. In Angband, it might be stuff like:

You feel uneasy about this place. (Monsters generated at deeper levels)
You feel like something good might be here. (Items generated at deeper levels)
You have entered a chilling ruins. (Undead more likely)
You have entered a lair of sleeping beasts. (Dragons more likely)
You have entered a den of hell. (Demons more likely)
You see many maze-like passages. (Rooms smaller and less likely)
You see many great halls. (Rooms larger and more likely)

[Nick]

EDIT: That said, I could readily accept sensible observation-based hints on themed levels, like "you see an unusual amount of dragon excrement lying around" ...

Which begs the question - what is the usual amount?