Monday, 19 November 2007

Unangband Dungeon Generation - Part One (History & Manifesto)

(This article series has nine parts: parts one, two, three, four, five, six, seven, eight and nine).

Back in 1992 (or perhaps 1993), a young university student first encountered the Angband source code. He had played Angband frog-knows previously on his father's Amiga 500, and achieved reasonable progress with a paladin at one stage: down to about 3,000 feet. But the source code afforded him new opportunities, and he fired up the Metrowerks compiler in the university lab, and added four terrain features to the Angband dungeon: ice, acid, water and lava. The design was simple; just a modification of the drunken walk algorithm already used to place streamers through the dungeon, and he spent endless hours generating dungeon levels and wandering through them, followed by countless nights of dungeon-infested sleep, dreaming of endless caverns and unlit seas. Never again would his adventures be as successful, as the world of Angband variant development lured him instead.

I'd like to say that that the roots of UnAngband's dungeon generation system can be traced back to that code, but it has been lost in time. Instead, very little survives. I recovered the design of several of the monstrous trees that I had in that proto-variant from a newsgroup post - I can no longer find that post, but there is definitely mention of it in a follow up discussion started by Ben Harrison (I also remember distinctly fighting 'killer bees' I had created, which was an orange 'I'). I also discussed the fact that I thought summoned monsters should surround the summoner, as opposed to the player, which was vigorously argued against, although history has proved me right. In fact, looking at that last link, it describes in detail, my early 'dungeon design manifesto', which I'll repeat here.

Basically, I would like to see a bigger variety of rooms and corridors espec-
ially at deeper levels, including:
* big pits, rooms which are filled with a big pit, bridges over pits etc.
* huge rooms, natural caverns, corridors which are 2 or 3 wide, long hallways,
pillars scattered about big rooms, big doors (if possible)
* statues, fountains, thrones, pedestals, gates, and other dungeon furnishings
* trapped doors, trapped furnishings, traps which activate for a wider variety
of effects (create traps anyone), hidden compartments which are handled as
traps but when disarmed create a GOOD or EXCELLENT drop
* more varieties of rooms within rooms, pits within rooms, rooms within pits,
to the point where some rooms will start to resemble the town level with LOTS
of monsters swarming around
* floor coverings, water, fog, mud, lava, creatures which are invisible in water
(ie SWIM)
* when monsters are generated on pits, they come from deeper levels ("It crawls
out of the pit.") and are not restricted to 25+ distance away. This restriction
shoud also be lifted for teleporting monsters.

Basically, I want the thrill of exploring to be heightened.
Fig 1: A typical Unangand dungeon. The chambers in the right hand side are surrounded by a grass-filled cavern with the occasional tree. Vines and mossy walls decorate the nearby tunnels. However, between the vines, some walls seep blood. Click for a more detailed view.

And lastly, I spent a lot of reprogramming that other Angband time sink: the Angband Borg. Again, this code has been lost. I can only suggest that Dr Andrew White has done a better job and more in the spirit of Ben Harrison's original intentions than I was ever capable of.

UnAngband proper appeared on or around December 2001. I can find a report of version 0.1.1 existing in a Angband variants FAQ and certainly I had progressed enough (in my mind) to advance the version number to 0.4.0 by mid-2001. My announcement post included a feature list that will seem familiar to the 'modern' Unangband player and long enough to impress Eric Bock, while accompanied by mild consternation by many that they couldn't access the website I was hosting it on nor download the executable from the ftp server. My, how things haven't changed. If anyone can locate a link to the original usenet posts where Robert Ruehlmann suggested that I call the variant UnAngband, that would be much appreciated (It may have actually been an IRC conversation, so don't search too hard).

Of particular relevance from that later announcement, is the description of UnAngband dungeon generation at the time:

Features added to the dungeon include new traps, water, ice, lava,
mud and chasms. These are detailled in f_info.txt and
defined using additional fields and flags documented in the same
file. Monsters should be able to traverse various terrain types
depending on additional flags in r_info.txt. Lakes and rivers
will be generated through some dungeon levels.

Room descriptions have been added. These are displayed when a
player lites up or enters a room. Room descriptions can also add
extra monsters, objects and features. See d_info.txt for details.
I can tell you that the dungeon lakes were still being generated at that point by a drunken walk algorithm, and rivers by a modified version of the streamer code.

If it's not clear to you why I'm discussing the history of the Unangband dungeon generation code, it's because I want to emphasize how long exactly I have been thinking about dungeon generation for, and how I have ended up with a monolithic 11,852 line generate.c file, 953 distinct feature types, 23 high-level room types, another 805 'room description' lines which may be combined in a number of ways, 64 separate dungeons in a linked wilderness, all of which together drives the Unangband dungeon generation routines. The Unangband dungeon generation code also has not existed in isolation: there has been considerable cross-pollination between it and other Angband variants - firstly with EyAngband adopting the Unangband room generation code, and then both Hengband (now Entroband) and NPPAngband adapted the Unangband feature types with considerable modification in both instances. I have also borrowed extensively from the NPPAngband and Sangband dungeon generation routines as well as spending more time than perhaps is healthy getting to understand the Zangband wilderness generation code.

And I'm finally in a position where I can confidently say that dungeon generation in Unangband is a 'solved' problem, and I am happy with the final result. I still want to completely rewrite wilderness generation, but that is a version 2 item, and one I'm happy to put aside for a while. I'll also steal FAAngband's 'full wilderness levels' at some point in the near future, but I don't feel a compelling argument for them, and without the FAAngband wilderness to go with it, those levels can seem empty and hard to explore.

So what does UnAngband dungeon generation deliver and how (and why)? Well, to understand that, you need to understand a little about Angband dungeon generation, and what the benefits and drawbacks of that are. And that is a discussion I'll be saving for part two.


Mikolaj said...

Now I understand better why I don't want to ever touch generate.c. :D

A technical issue: with my browser font setup I cannot see last 1/5 of the lines of the text written in monospace font. Stupid

Aron said...

Finally an artical that will actually aid me in my own roguelike endevours.

Not that your other havnt been terrific but im so lost with dungeon generation atm.

Christopher Brandt said...

Room descriptions add surprisingly much to roguelikes (along with npc and non-auto-generated item descriptions). I'll have to add them to my game, too, but first I should start adding some more generic content :D

Nice article, I'm looking forward to part 2.

You seem to be writing a lot, it was a good choice then to develop an Angband variant, which is less programming and more content adding (in my simple understandings).