Nethack Level Generation, Part 1

Because so many roguelikes are open source, their map generators are available for examination. While many clearly borrow from each other, they also show a number of different approaches to procedural generation. Examining the source code can tell us a lot about what works.

NetHack is one of the major roguelikes, rivaling Angband at the most significant roguelike of the Usenet era. Unlike Angband, but like Rogue, it generates levels that are the same size as the screen and consist of rooms and connecting corridors. (It’s close enough to Rogue that there’s actually an optional Rogue-emulation bonus level!)

Nethack is mostly written in the 1989 version of ANSI C with some translation macro hacks to account for different compilers and versions of C. This makes for a fairly gnarly codebase, though it means that it is portable enough that the current version still runs natively on an Atari ST. The syntax isn’t too hard to follow if you’re familiar with the syntax of C++, C#, Java, or the like, but there’s some weirdness even for C programs. (Many function declarations are actually preprocessor macros so the code can work on compilers with different ways of defining functions with a variable number of arguments.)

Because of this, I don’t actually recommend copying NetHack’s level generation line by line. It is undercommented and nearly three decades of development have left tons of hidden assumptions buried in the code. Or more than three decades: some of this code seems to date to Hack. Still, I think there’s a few things we can learn by looking at its approach.

Helpfully, the NetHackWiki has the source code of NetHack  in a relatively easy to access format. A few of the files have been annotated in great detail, though unfortunately that doesn’t include much about the map generator (yet).

Note that when I’m basing this on the code in 3.4.3. This was because it had been the latest version for the past ten years, so I figured it was pretty stable. Right up until 3.6.0 came out and shocked everyone. There’s been a few changes to the code (and it’s formatted slightly differently) so I’ll continue to link to 3.4.3′s version. The essence of the code is pretty much the same.

When Nethack starts a new game, it does some setup of the player and the objects in the game, and then creates the first level by calling mklev(). The name has some historical reasons behind it, but the modern version is pretty straightforward.

If this isn’t a bones level, we start by calling the makelevel() function, where the bulk of the room creation happens.

In makelevel(), we start by declaring some variables that will be used later:

room_threshold is the minimum number of rooms before a special room can be added. There’s always two reserved rooms (for the up and down stairs) and possibly a third (if there’s a stair to a dungeon branch) so room_threshold will eventually be set to either 3 or 4, after the stairs are added.

The keyword “register” is a somewhat obsolete way to tell the C compiler to keep the variable in memory because we’re going to be using it a lot. Modern compilers do this automatically, but NetHack doesn’t rely on modern compilers.

The game then checks if wiz1_level.dlevel is equal to zero. There’s nothing particularly relevant about this variable itself, it just uses this as a flag to check if things are uninitialized. If this variable is set to 0 (such as by the code that loads a saved game), it assumes that a bunch of other stuff isn’t set either. A quick call to init_dungeons() takes care of that.

There’s a couple of other setup things to do: set level dependent object probabilities (which appears to be only used for for gems?) and clear out the saved information about the current level, such as the number of rooms it has, the list of monsters, and so on.

Once the setup is done, it does a check to see if this is a special level. There’s a entire system for creating these special levels from templates, using the makemaz() function. So-called because if you don’t specify a level, it will create a maze instead (again, this function dates back to Hack). There’s also a separate check here to see if this is the Rogue emulation level, in which case it does the Rogue room generation instead, complete with a ghost of the Rogue player character.

Once we pass all those checks and setup, it’s time to start making the actual rooms, which we’ll discuss in Part 2.