Unangband Dungeon Generation - Part Five (Elements)

(If you haven't been following this series of articles, you'll probably want to start with parts one, two, three and four).

If the room is too small a design element to properly handle delivery of monsters to the player, then it turns out that the level is too large. Actually, I'm getting ahead of myself here. What I mean by design elements, are the different elements that make up the Unangband dungeon generation, beyond placement of the individual entities (monsters, objects, traps and grid features). It is worthwhile introducing the design elements that I've added and changed in Unangband, in order to provide a framework around which the mechanism of 'delivering enemies to the player in an meaningful and consistent fashion' is hung.

1. Room Types

Room types were mentioned briefly in part four, and consist of different sets of algorithms for placing the edges and contents of a room on the map. Effectively, the room layouts are 'drawn' in different ways, depending on the algorithm selected. This is subdivided into normal sized, large sized and huge sized rooms - with larger rooms appearing deeper in the dungeon, and using up more of the total room count allowed on a level.

Most of the room types listed here are not unique to Unangband, but have been implemented first in other variants and copied into the Unangband code-base. The code in the original location is usually easier to understand and I recommend you refer to the generate.c file for each of the mentioned variants in the first instance to see the algorithm in more detail.

• Lakes: large, huge

Lakes are placed ahead of any other room type, and can be overlapped by other rooms and each other. They are drawn using the starburst algorithm (see below), but are completely filled with a 'lake' terrain.

• Waypoints

These are rooms that consistent of a 1x1 square, effectively providing a point of intersection for tunnels.

• Overlapping rooms: normal, large and huge

These are the 'basic' room type in Unangband, and are created by selecting two random rectangles within the a larger rectangular space. Simple rectangular rooms occur when one of the rectangles is completely enclosed by the other. Rooms similar to Angband's cross-shaped rooms occur when the rectangles are identical when reflected by a mirror at 45º. A bias towards symmetry encourages more frequent cross-shaped rooms than otherwise expected.

Fig 1a: Examples of overlapping rooms (featuring a fountain in the north of the room)

Fig 1b: Examples of overlapping rooms (featuring a pile of feathers in the centre of the room)

Fig 1c: Examples of overlapping rooms (featuring webs surrounded by gas traps)

Fig 1d: Examples of overlapping rooms (featuring a well in the north surrounded by thorns)

• Starburst rooms: large and huge

Starburst rooms are from Leon Marrick's implementation in Sangband. They are generated by projecting a number of rays of random length from a common origin, and have natural looking curvilinear edges.

Fig 2a: Examples of starburst rooms (featuring burnt floors)

Fig 2b: Examples of starburst rooms (featuring iron cages around the walls)

Fig 2c: Examples of starburst rooms (featuring an object strewn midden in the centre of the room)

• Fractal rooms: normal, large and huge

Fractal rooms are generated using Diego Gonzalez's fractal cave algorithm from NPPAngband. They are generated by using recursively selecting from a list of fractal templates, including 'pools' of terrain. Connectivity between all 'floor' and 'pool' squares is guaranteed or the generated fractal is rejected and tried again.

Fig 3a: Examples of fractal rooms (open floor surrounded by scratched granite walls)

Fig 3b: Examples of fractal rooms (featuring a blood-stained altar in the centre of the room)

Fig 3c: Examples of fractal rooms (featuring a wet floor)

• Maze rooms: normal, large and huge

Maze rooms are generated using a heavily modified version of Eric Bock's maze algorithm from Sangband, which generates acyclic or 'perfect' mazes from a passage carving algorithm (See Think Labyrinth for an explanation of maze terminology and an excellent overview of mazes). The modifications in Unangband attempt to match the maze design to the tunnel types allowed for the level (see below).

Fig 4: Example of a maze, featuring dead ends filled with bushes (click to enlarge).

• Chambers

Multiple adjacent rooms either connected to each other by common doors or short tunnels. These are built from Leon Marrick's chambers algorithm in Sangband. Chamber complexes are filled with many monsters.

Fig 5: Example of chambers (click to enlarge).

• Lairs

A lair is a set of chambers, surrounding by a lake of a particular terrain feature (with a guaranteed moat around the edge of the chambers). The lair then contains a unique monster or other set of monsters.

• Vaults: lesser, greater and 'interesting rooms'
  

Rooms built from a text template, as discussed in part two. Currently vaults are generated using the Angband algorithm, but I will be moving to Sangband's implementation, after adjusting the Unangband tunnelling algorithm to handle width 2 walls.

• Towers

Towers are handled as a special case of the vault algorithm, although they are 'ascended' as opposed to 'descended'. Towers about the surface are surrounded by open air.

Note that Unangband does not have the monster pits or nests that many other variants do.

2. Room Descriptions

Complementing the room types is a room description mechanism. I wanted each room to be uniquely distinguished by a passage of text that the player could read when they first entered the room, if it was lit, or when they successfully lit the room with a light spell.

The text passages are built up by using Markov chains of sentence fragments (actually not strict Markov chains, as the system supports conditionals), which also add trap, objects, monsters or terrain features to the room, which are defined in room.txt.

A room.txt entry might look as follows:

N:152:107:0:0:25:1:1:128
A:trapped
B:
D:surrounded by trip wires.
R:SNEAKY
F:2:0:0:77:0
S:SEEN
P:PLACE | MAZE_WALL

The first line says 'in state 152, transition to state 107 if this entry is selected, with a 25% chance of picking this entry normally (minimum 1% chance), between dungeon depths 1 to 128'. Entries 3 and 4 on the N: line act as a conditional 'if you got to state 3 after choosing this entry, transition to state 4 instead'. The A: and B: lines help provide the room name, built from an adjective (A:) and noun (B:), where the first word in encountered in the chain is used. The D: line gives the sentence fragment. The F: line provides information about features - in this case feature 2 (invisible trap) is placed around the room, which when a trap is selected turns into traps like feature 77 (trip wire).

The R: and G: lines (not shown) control the monster race flags and monster graphic char for monsters in the room. The K: line (not shown) control the item kinds that are placed in the room. The L: line (not shown) controls what levels the terrain appears on - if the level has a matching level flag, the higher percentage on the N: line is used; if the level does not have the matching flag, the lower percentage is used.

The S:SEEN flag indicates that the sentence fragment is part of the description when the room is lit and the player can see it. Descriptions can be displayed if the room is entered without being seen, consisting of tactile and auditory information, temperature and so on. It is also possible to have textual information such as writing which depends on the player understanding the language of the room inhabitants, using S:LANGUAGE.

And most importantly, the P: line controls the placement of the entities around the room. What I refer to as 'room descriptions v1', the room description would say 'In the west of the room' and the objects, traps etc. would be placed anywhere in the room. Not until version 0.6.2, did I successfully get the code to place these in the west of the room, and only for the overlapping room types. As a result, the other room types have restrictions on which room.txt entries can be chosen, based on the P: flags.

In this instance, the P: flag says now place all the entities which we have accumulated up until now, using a maze pattern, where the features form the walls of the maze. This could be ignored, if the room size is too small to support drawing a maze in it, and the features will just be scattered around instead. The fact there is an explicit 'PLACE' flag allows the separation of where and how in the room, from the what in the room, which allows much more flexibility in how room.txt entries can be combined.

3. Tunnel Types

I wanted more variety in the tunnel types that could be selected. In particular, I explicitly allow width 2 and width 3 tunnels, with support for pillars running down the centre or edges of these tunnels. In addition, I provided some persistent tunnel parameters, such as frequency of changing direction, so that the tunnels could appear to be very cave-like, or have inconsistent or consistent width and pillars over the course of the tunnel.

Tunnels can also support various decorations, such as a central pool running along the middle of a width 3 corridor, or one edge of a width 2 corridor. Other tunnels have decorations, such as torches, wooden supports or windows that appear with varying frequency along the length of the tunnel, and usually at dead ends. The nature of these decorations is determined by the room descriptions of the rooms at either end of the tunnel. The 'solid' walls at each end of the tunnel (see part two) will be turned into other terrain as well, if certain room descriptions are picked.

The basic tunnel path logic is from Sangband, although I haven't adopted all of its features yet. However, due to the presence of width 2 and width 3 tunnels, the Unangband tunnel generation has to be a lot more careful in ensuring that only the minimum number of tunnels are generated, lest the dungeon start to resemble swiss cheese. The tunnel algorithm also has to take account of lakes of terrain through which a tunnel can pass, without necessarily terminating in the terrain.

This complicated the algorithm enormously. Tunnels in Unangband either bridge or tunnel terrain, with bridges being narrower and bridge-like. The rooms are divided into partitions, initially one per room, and combined as the tunnels connect separate partitions. Tunnels are aborted if they intersect a destination room of the same partition as the source room, and as a result the source and destination selection algorithm starts very strict, to maximise the chance of connecting nearby rooms together, and ends up very permissive, and then desperately random, to try to connect any room to any other room, in the event of being unable to merge all partitions through connectivity.

4. Level Theme or 'architecture'

A problem with older versions of Zangband, was that the large number of room types in that variant could be thrown together in any mix, resulting in weird architectural combinations. I wanted to avoid that, which resulted in the decision to tie room types together at a higher level, using a level theme. The level theme is based on the first room type placed on the level, which is selected using the Sangband process of trying the largest, and therefore hardest to place, room types first, and then progressively smaller. The theme then restricts subsequent room types to only those consistent with the level theme.

Luckily, the room types, room descriptions and tunnel types conspired to form some consistent 'architectural patterns'. The following level themes are generated in Unangband.

Dungeons - dungeons are the most permissive and allow most room and tunnel types
Stronghold - large and huge overlapping rooms, width 2 tunnels without pillars and width 3 tunnels with central pillars, tunnel shape consistent for length of the tunnel
Crypt - pillar filled overlapping rooms with features on the edges of the room, width 2 and 3 tunnels with pillars on the edge of the tunnel, tunnel shape consistent for length of the tunnel
Mine - mix of fractal and smaller overlapping rooms without features and waypoints, width 1 tunnels that do not change direction often
Cave - mix of fractal and starburst rooms, width 1 tunnels that change direction highly frequently
Wild - large or huge lakes, no fractal or starburst rooms, the rest allowed as they look like buildings in the wilderness, width 1 tunnels that change direction moderately frequently
Labyrinth - mix of various size mazes, some labyrinth levels mix in stronghold, crypt or cave level theme and make the mazes look like tunnels from that level theme
Sewers - large or huge starbursts, large or huge overlapping rooms with features in the centre of the room (which tends to be a pool), tunnels width 2 or 3 with a central 'pool' running down the tunnel, tunnel shape changes throughout the length of the tunnel

In addition, Vault and Chamber level themes are used to control the occurrence of other room types with these two room types, but may be deprecated at some point.

5. Terrain Features

There are enough terrain features in Unangband that they deserve a separate article in themselves (part five). But I'll at least discuss how they impact on the other design elements in this section.

Firstly, a percentage of dungeon levels are generated with a lake or river feature running through them. This could also be forced by the dungeon type that the character is exploring.

This may instead result in some 'flooded dungeons'. Flooded dungeons are special in that up to a third of rooms are generated as flooded with a particular terrain feature. In the instance of fractals, starbursts and overlapping rooms, the terrain feature fills the room. But in the case of chambers, vaults and mazes, the terrain feature surrounds the room, just as lairs are surrounded by a lake / moat of terrain (mazes also have some dead-ends filled with the lake of terrain). These rooms are not treated as flooded for tunnelling purposes.

Flooded rooms connect to other flooded rooms with tunnels that are full of the flooding terrain, while non-flooded rooms are connected normally. This proved to be the most effective way of ensuring monsters restricted to the flooded terrain could navigate between rooms, while ensuring that the character could navigate to any room that proves more interesting. The centre of sewer tunnels will preferentially use the flooding terrain where possible.

The type of terrain flooding the dungeon then restricts what terrain is generated as pools in starburst and fractal room types, through the use of water, lava, acid etc. flags. These flags also influence room descriptions - the L: flag matches in the room.txt entries include these flags. In particular, this is used to select auditory, temperature and wind room descriptions, which are generated for virtually all room types, and have an increased prevalence for room floor contents. So an acid level will not only have acid-filled rooms, but the remaining rooms may have clouds of acidic vapours, acid-damaged walls and pools of acid in the centre of the room.

At the room description stage, a terrain is selected as the level theme terrain, separate from the flooding terrain - usually from the first terrain generated. This is used to bias the room description selections and can be used in various ways to ensure different room types tend to match together. For instance, all rooms containing human-usable equipment tend to have shelves around there edges and a shelf themed level will have rooms filled with potions, books, and so on. And as mentioned in the tunnel types, room features influence what is placed along the tunnels, as well as at either end.

6. Monster Ecologies

I decided as a part of considering levels as an expendable resource, that I could readily limit the list of monsters on the level, as a way of letting the player select what type of challenge they wanted to face.

I reasoned that monsters would exist in various ecologies in the dungeon - I wouldn't have to model the ecology, just provide a reasoned enough a selection of ancillary minions for a major monster type (called the seed monster), and limit the generated monsters to that collection. Luckily, the way of relating a monster and his minions already existed, in the form of escorts and summoned monsters. In order for a summoning spell to be successful, I'd have to include at least one of the candidate monsters in the ecology, and so I built the ecology selection routines on this basis. Where a monster didn't summon anything, I created a hack_ecology technique where I randomly chose members of the ecology from a subset of summoning spells (in particular, kin, animals, classes, groups, and so on) as if the monster had that spell.

This required some tuning, in the sense that I still wanted to populate vaults with as random a selection as possible, so had to ensure a reasonable maximum size and range of monsters, and find a suitable minimum (which turned out to be 4), in order to ensure sufficient variety in monsters on a level. The monster ecology model, once debugged, turned out to be very useful.

7. Dungeon Types

Finally, for those playing the Middle-Earth campaign in Unangband (by far one of its most popular features), you'll have discovered that each dungeon has a particular set of restrictions on monsters used as seed monsters for the ecology (or even a specific monster guardian on certain levels), and fills or floods the dungeon with various terrain types.

So other than influencing each other, how do these design elements successfully deliver monsters to the player in a consistent and interesting way?

I deliberately missed an important detail in the discussion of room descriptions, that is particularly relevant to this. In version 1 of the room descriptions, the room.txt entry details relating to monsters (R: and G: lines) were used to select monsters to place in the room.

But in version 2 of the room descriptions, the those details were used to restrict which room entry to pick. I had decided at this point that room descriptions were going to be key to telling the player what the most powerful monster on the level was. So in addition to building the ecology, I recorded the most powerful monster in it. Then I restricted the room descriptions, so that the higher percentage chance was used if the deepest monster matched the R: or G: line, and the lower percentage chance if that line existed in the entry, and it did not match this most powerful monster.

Suddenly I was able match room descriptions and monster properties. This meant I could relate thrones, checkered floors and weapon racks to warriors. And magic circles, magic books and magical lights to wizards. And altars, prayer books and candles to priests. And so on.

And it still provided to be a failure. Levels became boring - the features were too tied to monsters, most powerful monsters were evil, and the feature theming meant that most levels ended up being filled with bloody walls and bloody altars (the two being related).

I tried to analyze what I was doing wrong, messed with the frequencies and got nowhere.

So I played around with monster ecologies, and stumbled on the solution by accident.

What I did was split up the ecologies into sub-ecologies. Remember, each ecology was based on a single seed monster, and his minions. Well, it made sense to associate each seed monster with a separate sub-ecology. Seed monster one had sub-ecology one, with his minions filling out the rest of the sub-ecology. Seed monster two had sub-ecology two, with his minions as the rest of the members. In fact, sub-ecologies came directly from the fact I had to have a minimum number of different monsters on the level, to stop the level being boring.

So in order to split the sub-ecologies up, I decided a simple relationship. First ecology with first room placed, second with second room placed and so on. It made sense that the largest, hardest to place rooms got separate ecologies. And then when I ran out of ecologies, I just assigned ecologies to rooms based on the nearest room which did have an ecology. But I didn't want the seed to be wandering outside his 'base' room, so only his minions get generated in these ancillary rooms.

But what about the most powerful monster for each room. Well, lets use the most powerful monster for each sub-ecology. And I'll allow this to spread to the ancillary rooms, so some consistency holds between nearby rooms.

And something magical happened.

Levels started to be interesting again. Because over here, you had the laboratories where the potion-dropping slimes hung out. And then on the other side of the level, the war loving orcs kept their weapon racks and wargs in kennels.

What I had built was a modified room-based monster delivery system. It still had the core room descriptions telling you what the most powerful monster for the main room. But each room also had this hinterland of ancillary rooms, which also told you the most powerful monster - but didn't have that monster in it (there was a high correlation between most powerful monster and seed monster).

And the significant difference between that and the level model, is that you could walk through the transition of two different hinterlands. So you associated monsters and their hinterlands in a dynamic, spatially associative way that travelling up and down a level didn't tell you.

In this particular layout, you had a much greater chance of encountering the hinterland before the most powerful monster. In fact, weaker monsters also served as the advanced warning, in a manner of speaking. You'd fight through a whole lot of orcs, before getting to the orc chieftain who led them.

I was lucky in a sense, that many of the design elements I had worked on previously had fortuitously come together, not just for the 'architectural' layout of the level, but also its 'ecological' layout.

And the features of these layouts, I'll discuss in part six.