The Angband dungeon generation discussion thread

[fizzix]

Keys in vaults might be interesting, but I'm having trouble seeing how they'd amount to more than "you have to go over here before you can go over there".

They'd only be interesting if they appeared in the drop of a certain monster in the vault. It would take a bit of coding and is pretty off topic from dungeon generation. However, if you had a special chest that had guaranteed great objects in them and one or more of the monsters held keys to the chest, it could be interesting.

[will_asher]

That would prevent teleport other as an easy way of getting loot.

[andrewdoull]

We've got I think four things: permanence, permiability to creatures, permiability to projections, and visibility.

[snip]

I'd say making an interesting terrain type is a simple matter of finding an empty slot in the 2x2x2x2 table, finding something that can plausably fill it, and if it blocks movement optionally making a flag for exceptions and figuring out which monsters should have it. If a terrain type doesn't sit in a different slot from an existing type it's probably not interesting enough to add.

Unangband allows you to define these four flags in terrain.txt, as well as the other 92 flags that I felt I needed, and the damage types each terrain causes, and transitions between terrain etc. I don't think limiting yourself to a 2^4 table is sufficient, but its a good basis to start thinking about. You will need to modify the LOS and LOF code - luckily its easy enough to borrow from elsewhere (I got the basis for the Unangband code from Sangband).

With regards to the illusory walls, I used the same set of flags (no projection, no LOS, allows movement) to represent vents (e.g. small crawlable corridors), as the process of moving through this particular terrain reminded me of the crawling around vent scenes in Aliens. The terrain acts in interesting ways without having to make it look identical to walls. (Limiting you to 1 square LOS no matter what your light source and no ranged attacks).

Andrew

[andrewdoull]

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.

The easy answer is either to switch the birth_campaign option off, or use debug commands and jump to Angband (dungeon 72). You'll probably want to see how the layout varies between shallow and deep dungeons as well, so ^a, j is probably your best bet.

Be sure to get the SVN version, because I think - finally - I've started to get this right.

^a, E (capital e) will show you the dungeon ecology. The numbers indicate which ecology number each monster belongs to, where 0 is wandering around the dungeon corridors, the c indicates that the monster is confined to a single 'core' room in that ecology. All monster generation (except at extremely low levels) including spawning of new monsters while the player is exploring the dungeon is chosen only from the appropriate ecology.

Switching the cheat_room option on will give you heaps of diagnostic information that is piped directly into the message history - ^P to recall. cheat_xtra will allow you to interrupt the generation process if a dungeon generation run fails and inspect the dungeon. You'll have to save and load the game if you interrupt and need the player to be placed in the dungeon for whatever reason.

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?

I just can't see how function callbacks would be useful for dungeon generation.

My limited experience with function call backs is they are absolute essential for user interface design (Thanks Pete Mack for showing me the way), and may be useful in some other circumstances, but not necessarily. Even sorting, which has had a function call back implementation in Angband for the longest time, about half the time, it'll be easier to write an in-line sort rather than set up the comparison and swap functions.

Having said that, there's several implementations unique to Unangband: handling the addition, removal of lights in the dungeon, and the region code I've recently written does use call backs, so I am using them more and more in places.

With regards to dungeon generation, there's basically 4 phases to dungeon generation:

1. Wiping all the structures you use.
2. Placing rooms in the dungeon.
3. Connecting these rooms using tunnels.
4. Placing monsters / treasure / objects throughout the dungeon.

You need to have a main loop that iterates through these steps, in the event when you end up with an illegal dungeon at any point, because it is true that you may not be able to e.g. place sufficient rooms, connect the rooms, or find space to place stuff in a finite amount of time, because of random choices made earlier in the process.

I believe moving away from the above model will stop the dungeons feeling like Angband dungeons. In particular:
1. Dungeon generation techniques which use recursive subdivision of space to allocate rooms won't readily allow you to place the largest vaults.
2. Techniques that build the corridors first, such as by creating a perfect maze and then absorbing parts of the maze into rooms won't allow placement of highly irregularly shaped rooms.
3. Techniques that expand the dungeon by tunnelling into new space, and then seeding a room won't allow the infrequent long wandering corridors that characterise current Angband dungeons.

The most interesting part of the above techniques is placing rooms, the most frustrating to get right is connecting corridors.

With regards to room types, Unangband has a mix of rooms which are generated in a privately allocated chunk of memory, and then painted into the dungeon, and some which are directly generated in the dungeon - mostly because we'll be placing too much stuff to bother with a private memory structure that duplicates exactly all the things the dungeon memory structures hold. This mix has occurred because I've been a real magpie when it comes to borrowing room generation code from other people. Some rooms - vaults, pits - will generate and place monsters directly, which requires we mess with the ecologies a bit.

My favourite of all room generation types is the basic 'overlapping room' type - which uses far too clever/hackish code to ensure that the placement of stuff in the room matches the room description that we generate at the same time.

The corridor generation code is your basic give each room its own partition and then merge partitions. The first run through we connect rooms randomly, then we try to connect the closest rooms together (if we did the reverse, the connections end up very boring), and then we relax various conditions in corridor placement such as not allowing corridors to follow each other too much, including allowing a corridor to merge with the connecting corridors as opposed to requiring we actually get to a room at the other end. The actual corridor type selected is to match the dungeon theme: crypts have ragged edge corridors that match their pillared rooms, strongholds have wide corridors to match their large rooms, sewers have terrain filled corridors to match their flooded rooms and so on. There's 12 themes in total although destroyed is underdeveloped and will be replaced by ruins, and battlefields. Remember 12 themes equals 12 unique corridor styles which is a much harder thing to come up with than room styles.

Andrew

[Nick]

Just for general information, here is the table of room types and chances of generating one at a given level in Oangband (unchanged in FAangband). The generation algorithm then tries to fit in an "average" number of each type, in reverse order (which roughly corresponds to size order). I don't know how widely this approach has been adopted.

/*
 * Table of values that control how many times each type of room will, 
 * on average, appear on 100 levels at various depths.  Each type of room 
 * has its own row, and each column corresponds to dungeon levels 0, 10, 
 * 20, and so on.  The final value is the minimum depth the room can appear 
 * at.  -LM-
 *
 * Level 101 and below use the values for level 100.
 *
 * Rooms with lots of monsters or loot may not be generated if the object or 
 * monster lists are already nearly full.  Rooms will not appear above their 
 * minimum depth.  No type of room (other than type 1) can appear more than 
 * DUN_ROOMS/2 times in any level.
 *
 * The entries for room type 1 are blank because these rooms are built once 
 * all other rooms are finished -- until the level fills up, or the room 
 * count reaches the limit (DUN_ROOMS).
 */
static room_data room[ROOM_MAX] = 
{
  /* Depth:        0   10   20   30   40   50   60   70   80   90  100   min */

  /* Nothing */{{  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0 },  0 },
  /* Simple */ {{  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0 },  0 },
  /*Overlap */ {{ 60,  80, 100, 120, 140, 165, 180, 200, 220, 240, 260 },  1 },
  /* Cross  */ {{  0,  25,  50,  70,  85, 100, 110, 120, 130, 140, 150 },  3 },
  /* Large  */ {{  0,  25,  50,  70,  85, 100, 110, 120, 130, 140, 150 },  3 },
  /* Pit    */ {{  0,   5,  12,  25,  30,  35,  38,  40,  40,  40,  40 },  5 },
  /*Chambers*/ {{  0,   2,   6,  12,  15,  18,  19,  20,  20,  20,  20 },  5 },
  /* I.Room */ {{ 50,  60,  70,  80,  80,  80,  80,  80,  80,  80,  80 },  0 },
  /* L.Vault*/ {{  0,   1,   4,   9,  16,  27,  40,  55,  70,  80,  90 },  5 },
  /* G.Vault*/ {{  0,   0,   1,   2,   3,   4,   6,   7,   8,  10,  12 }, 20 },
  /* Huge   */ {{  0,   0,   0,   0,   4,   4,   4,   4,   4,   4,   4 }, 41 }
};

[d_m]

The easy answer is either to switch the birth_campaign option off, or use debug commands and jump to Angband (dungeon 72). You'll probably want to see how the layout varies between shallow and deep dungeons as well, so ^a, j is probably your best bet.

Be sure to get the SVN version, because I think - finally - I've started to get this right.

I have done so... I'm still puttering around.

Incidentally, I ported the improved GCU mode to Unangband. If you had interesting features you didn't get from V I may have clobbered them, but this version will get you terminal resizing, xterm colors, and some other stuff. Here is the file:

http://www.bearhome.net/erik/un-main-gcu.c

Hopefully you'll find it useful.

I just can't see how function callbacks would be useful for dungeon generation.

My limited experience with function call backs is they are absolute essential for user interface design (Thanks Pete Mack for showing me the way), and may be useful in some other circumstances, but not necessarily. Even sorting, which has had a function call back implementation in Angband for the longest time, about half the time, it'll be easier to write an in-line sort rather than set up the comparison and swap functions.

This might be true, I don't know. I am imagining a situation where one can write different "room builder" functions, and then put them in an array of possible rooms with weights. This makes it easy to "plug-in" these things, comment them out, etc. I dunno, maybe I just like reflection and functional programming too much.

[Derakon]

Function pointers for room building are a very nice design, IMO. I've used them with great success in the past (admittedly in Python and in an OO context). The big thing they promote is a clean design: you set up (for example) a data structure that says "these room types are this likely", where a "room type" is a pointer to a function that creates the room, and then you just use the weightings to pick appropriate rooms. No need for lengthy if/else statements. It's great data-driven design.

[andrewdoull]

Function pointers for room building are a very nice design, IMO. I've used them with great success in the past (admittedly in Python and in an OO context). The big thing they promote is a clean design: you set up (for example) a data structure that says "these room types are this likely", where a "room type" is a pointer to a function that creates the room, and then you just use the weightings to pick appropriate rooms. No need for lengthy if/else statements. It's great data-driven design.

Sangband and Unangband do exactly the same thing, but with a weighting table and a case statement. I don't see how a function callback would especially help here. Especially since the case statement is more efficient and clear as opposed to a table, which gets hard to read once the table width exceeds screen size.

Andrew

[andrewdoull]

I have done so... I'm still puttering around.

Incidentally, I ported the improved GCU mode to Unangband. If you had interesting features you didn't get from V I may have clobbered them, but this version will get you terminal resizing, xterm colors, and some other stuff. Here is the file:

http://www.bearhome.net/erik/un-main-gcu.c

Hopefully you'll find it useful.

Thanks. Committed. Let me know if you want SVN access (apply for an account at berlios.de and email / PM me the user account).

Andrew

[Tobias]

When we are talking about special levels, how about REALLY huge vaults. As in filling the whole level.
Sort of like nethack's big rooms or castle.
Or a long room from one end of the level to the other upstairs on one end downstairs on the other. Doors leading of the the sides. After each door a Monster pit. Behind each pit is a Treasure room.

[Derakon]

ToME has some special levels that are basically vaults that take up the entire level. They're...okay, I guess. Part of the problem is probably that they always occur at certain depths (in certain of ToME's many dungeons) and always have the same monsters in them. That's good thematically but does make them rather predictable. As a matter of practice, I tend to skip as much of them as possible, heading straight to the fixed reward items and/or uniques that need killing.

Presumably Vanilla wouldn't have them be anywhere near as fixed. Still, as a vault that takes up the entire level, teleportation would become effectively useless (aside from teleport-level effects), which is a big limiter on the player's options. And of course, you'd need people to make the vaults. I don't think that ToME's special levels would transfer well style-wise to Vanilla, not least because of the inclusion of Void Jumpgates (a.k.a. fixed portals between two locations) in most of them.

[Magnate]

Presumably Vanilla wouldn't have them be anywhere near as fixed. Still, as a vault that takes up the entire level, teleportation would become effectively useless (aside from teleport-level effects), which is a big limiter on the player's options.

I think this is another diver/level-clearer thing. Since I started diving I've come to see tSelf almost as a liability - taking me to a part of the dungeon I don't know, with no guarantee of a move before the monsters. Better to stay where I am if at all possible and creep around or fight my way out.

When I used to clear levels, tSelf was quite likely to take me to an empty bit of level, and was therefore a fairly reliable escape.

[andrewdoull]

Still, as a vault that takes up the entire level, teleportation would become effectively useless (aside from teleport-level effects), which is a big limiter on the player's options.

You'd have to not mark level-sized vaults with the teleport prevention flag, simply because that flag is also checked when placing the player...

Andrew

[Hariolor]

Ok, my $.02 for anyone who needs pennies:

1) Terrain - yes yes yes. There are better and worse ways to do it. I am fond of the approach in Oanband, where terrain types have generally logical relationships with magic, LOS, movement, etc. Additionally, some races could be made more useful if they gained benefits in terrain types, ie: regular ol' elves benefit in trees, gnomes have no penalty to pass over rubble, etc.

2) Themed monsters/monster ecologies - yes on this too. Not only do I personally like the idea of meaningfully populated dungeons, rather than mariliths living with snagas living with dragons living with wolves etc etc, but I also think this would give fodder to creating more intelligent/interesting monster behaviors. Coupled with some of the other suggestions like patrols/preferred areas, this could be a great addition that does not fundamentally change the game into something other than V.

3) Wide corridors - as much as I appreciate the run key, I would make the argument that any dungeon in which you spend much of your time running through empty, narrow corridors is not a very interesting place. I'd rather slowly explore a dungeon in which every level is interesting, than quickly crush through a dungeon with only one or two worthwhile rooms. I further propose that the tactical changes necessary would be fantastic. While effective, it's a bit dull when almost every encounter involves retreating down a corridor, then watching enemies quietly march single-file into my whirling blades of death (or beams of acid, if I'm a mage). Some people might find this fun because it's a predictable and effective strategy. I just personally find that it's dull and disengages me from the game by making monsters behave in thoroughly irrational ways.

4) Detection/ESP > exploration - I've suggested elsewhere that ESP be made more granular (there's a ticket for it now I think). I absolutely agree with the suggestion that this granularity be applied to detection magic as well.

5) Mazes/special traps/locks/levers/etc - I think this is getting into variant territory. The idea of making loot in vaults harder to access is a good one, I think. In fact, it has always bothered me a little bit that there's any loot on the ground at all in a vault. If the monsters are there to guard it, and TO is a known magical ability, then they would probably not leave the loot on the floor. The idea of keys/chests in vaults is not bad - or better still, if it's reasonable to code, make the more powerful enemies hold guaranteed bonus items in their inventory when found within vaults. As for special traps/regions that drain HP or mana, prevent spellcasting, etc - this is awesome in theory, but would have to be pretty rare and implemented judiciously. It's on the edge of variant territory IMO, but especially at lower levels and combined with interesting terrain, it'd potentially make DL 50-99 way more interesting. Mazes sound like great fun in theory, but probably would suck in any implementation.