Unangband Dungeon Generation - Part Two (Vanilla Angband)

(I recommend you start with part one of this article).

The most charitable thing that can be said about the Angband dungeon generation system is that it works. It has survived a considerable length of time in its current state, and looks only now on the verge of being replaced. The algorithm is straight forward:

1. The dungeon is filled with granite (terrain is recorded in a byte size cave_feat array of up to 256x256 in size - the actual dimensions for each dungeon are constant).
2. The dungeon is divided into logical blocks of 11x11 grids.
3. A room type is picked - which fills up a rectangle of blocks (usually 33x11). A random top-left hand corner is picked in the dungeon and the blocks that the room would occupy are checked to see if a room has already been placed there.
4. If it has not, the room is drawn using the room generation algorithm for that particular room type, and the blocks marked as being occupied. In particular, each grid of the room has a flag set called CAVE_ROOM in a separate cave_info array and the 'outer walls' and 'corners' of the room are set to particular feature types to aid in later corridor placement.
5. The dungeon generator attempts to place 50 rooms this way. The edge of the dungeon is then surrounded by permanent rock (to prevent the corridors and player from tunnelling outside it).
6. Then the corridor generator attempts to connect each successfully placed room to each other in a great cycle: room 1 connects to 2, 3, 4... then room 2 connects to 3, 4, ... etc. The corridor generator maps out a single grid width corridor from the centre of the origin room which tries to move to the centre of the destination room (usually in the right direction but sometimes in a random direction). The corridor generator skips over walls 'inside' a room, puts doorways in walls 'outside' a room and moves around corners and the edges of already placed doorways. If the corridor overlaps another corridor outside a room (identified by the lack of CAVE_ROOM flag) it tries to put doors in the right place.
7. If the corridor generator is successful in navigating to the destination room centre, it tunnels out the path it has mapped out. Otherwise it aborts and does not place anything (including doorways and corridor intersections it identified).
8. Once all corridors have attempted to be placed, a random number of objects, monsters, traps and rubble are placed in the dungeon, allowed in either rooms, or corridors, or both. The allocation of objects and corridors is based on depth: usually objects and monsters up to a set depth are allowed, but some room types placed monsters or objects in set locations within the room in depths greater than the current level (Known as out of depth, or OOD).

Fig 1: A false colour image of the Angband dungeon. 'Basic' granite is white, the 'outer' walls of rooms are green and 'solid' walls on the edge of corridor entrances are purple. This is actually from the Sangband based version of the Angband code, which can be seen from lack of solid corners of the rooms and the additional solid walls next to corridor entrances. Note that the 'cupboard' at the top of the southern room is a bug in the tunelling code, caused by the tunnel penetrating exactly the outer wall of the room and no further, then turning around and exiting the room again out the east.
Fig 2: A false colour image of the Angband dungeon. The 'inner' walls of the room are yellow, and are not overwritten by the tunnelling code. The 'inner' walls of the room are placed by the room drawing code, in this instance, as pillars lining the edge of the room.

This algorithm is surprisingly effective. For instance, there is absolutely no guarantee of connectivity in the elements in the Angband dungeon. But the number of instances of Angband dungeons that I've seen with connectivity problems is less than 0.1%. The room types include simple rectangular rooms, rooms built by overlapping two simple rooms, rooms with an inner room, that may sometimes be filled with a set type of monsters (known as pits) and rooms built from a simple design template system called vaults, where various combinations of dungeon features, monsters and objects can be specified in a text file.
Fig 3: An example from the vault text file.

Unfortunately, the algorithm is not terribly robust. It has a number of places which can readily degenerate into infinite loops if the underlying assumptions break, due to the presence of loops with no guard variables. It relies on a number of assumptions that can be broken by vaults designed by someone without an intimate knowledge of the design system: for instance, the corridor algorithm can tunnel through width 1 walls correctly, but not width 2 walls, which are required if a designer wants to create diagonal or circular vaults. To avoid this, many vault designs require that the player manually tunnel through the last few grids because the corridor algorithm is incapable of this task. Pits are horrendously unbalancing in terms of the number of monsters produced in them, and can result in the maximum permitted monsters being reached, so are restricted with a 'crowded' boolean. And finally, the largest and most complicated vaults can only be placed if they are the first or second room type selected, which makes it very hard for a vault designer to specify the correct distribution for these monstrosities.
Fig 4: A false colour image of the Angband dungeon, featuring a troll pit. The trolls are surrounded by 'inner' walls as a hack to ensure they stay together, and the door to the right is placed by the room drawing algorithm. Also shown here are the streamers through the dungeon (% and *) which have be mentioned but not discussed in detail. These are placed after the corridors have been completed and replace existing granite.

But my biggest problem with the dungeon generator, is that it is boring. There is very little incentive to travel around the map. This encourages the tactic of repeatedly climbing up and down the stairs, in conjunction with detection spells or items, until excellent items can be found on the ground - called stair scumming. This is possible because Angband doesn't have 'persistent' dungeons. Each dungeon level is thrown away when the player leaves it, and a n
ew one is generated. To compensate for the dullness of the levels, and to try to discourage stair scumming, the player receives a 'feeling' when first entering a level, provide he has spent enough time on the previous level. But feelings are bandage on a broken system, and this is acknowledged by the presence of an auto-scum option, which automates the process of generating and throwing away levels until a sufficiently interesting one appears.

A number of Angband variants make improvements to the Angband system. The typical variant incorporates a number of additional, more 'interesting' room types, such as mazes, caves and fractal chasms, and usually incorporates a delayed level feeling mechanism, so that the level feeling is displayed only after searching the new level for a period of time. The variant usually incorporates some additional terrain types such as water and lava, which can appear as pools in various room types. Arguably the variant that addresses most of the Angband dungeon generator issues is Sangband, where Leon Marrick once again makes his presence felt. I mentioned previously that Angband was moving away from the existing generation method - it looks like a number of the Sangband dungeon generation routines will be adopted in its place.

But I want to move beyond just piece-meal improvements to the existing Angand dungeon generator, while keeping as many of its parts as possible - for compatibility, to allow me to adopt code from other variants, and to keep my player base familiar with a proven workhorse of a design. And to do that, I started asking some searching questions: What is a level and why do we have them? And why should we have them?

And to answer those, you'll have to wait for part three.