#nethack source code

[procedural-generation]

Nethack Level Generation, Part 2: Making Rooms

NetHack's maps are based around rooms and corridors. In gameplay, rooms are open areas that are usually lit, which makes them visible at a distance, while corridors are the connecting paths that are dark, which means that by default you can only see monsters that are one tile away. This creates a tradeoff between the bottlenecked corridors that are prone to ambushes and the more open spaces where you can see threats before they attack you. Doors are placed where corridors connect to the rooms, and have a chance to be secret doors. More than one player has gone down the stairs only to find themselves in a room that has no visible exits.

To create the rooms, makelevel() starts by calling two functions: makerooms() and sort_rooms().

The core of makerooms() is a while loop that runs until it reaches the maximum number of rooms (which is defined as 40) [] or runs out of places to put new rooms.

Each time it goes through the loop, it first check to see if it can try to place a vault. If it isn't placing a vault, instead it creates an ordinary room with -1 for all of the optional arguments. If it fails to place this room, it stops trying to place any more rooms, returning out of makerooms().

To place a vault requires the number of rooms to be at least one-sixth of the maximum (with the default max of 40 and C's truncation towards zero, this is usually 6). It also requires that no vault has previously been tried, plus a 50% random chance. It then calls create_vault(), which is a preprocessor macro for create_room() with a different set of arguments: (-1, -1, 2, 2, -1, -1, VAULT, TRUE). This creates a vault with a fixed size of 2 and guaranteed to be lit.

Either way, the bulk of the work is done in create_room(). Since this is also used by the special level system, it has some flexibility for specifying more kinds of rooms than the basic generator uses. It takes eight arguments: the x position, the y position, the width, the height, xal, yal, the room type, and whether it is lit.

The first step in creating a room is to check the requested light value; if it is -1, the lighting state is randomly set based on how deep the level is; once the player reaches level 10, there's an increasing chance that the room will be dark. (There's also a 1-in-77 chance that it will be lit, no matter the result of the first random check.)

Similarly, if any of the other arguments are -1, they will be generated randomly.

Way back in clear_level_structures(), the game built an array of rectangles in the level. This started as one large rectangle that covers the entire level. In create_room() it now grabs a random rectangle from this array. If this is our first room, there's only one rectangle to grab.

Rectangles are a struct with four variables: the low x and y coordinates, and the high x and y coordinates. (The terminology seems to date back at least to the early days of Hack, if not earlier.)

It picks some random coordinates based on the rectangle it grabbed:

The result of all of this is a set of coordinates (absolute upper left corner x position, room x width, absolute y position, room y height) that define where it wants the room placed. 

Using these values, it checks to see if a room will fit in that spot, shrinking it if necessary. If it fails, it starts over. If it fails more than 100 times, it gives up and returns with whatever rooms have already been created.

Assuming that a spot to place a room has been found, it splits the rectangle the new room is going to be in into smaller rectangles. It then adds the room to the array of rooms and writes the walls and floors onto the level map.

The next time through, create_room() will grab one of the smaller rectangles and attempt to put a room in it. If it fails completely, no more empty rectangles can be found, or MAXNROFROOMS is reached, then room creation is over and makerooms() returns.

Once makerooms() is done, sort_rooms() takes the array of rooms and runs a qsort on them, ordering them in the array according to their position on the map from left to right by their low x value.

(Unless you're compiling on Unix System V or DG/UX, in which case it uses a slightly different qsort call that passes the number of rooms as an unsigned variable. Same behavior, but demonstrates the lengths the code goes through for portability.)

The order of the rooms is going to be important for the corridors connecting the rooms, because it first tries to connect each room to the next one in the array. With a few more complications, which we'll get to next time in Part 3.

[procedural-generation]

NetHack Level Generation, Part 3

We're back in makelevel(), at line 666. The rooms are placed, but they're empty.

The one thing that every level needs are the stairs that will connect it to the levels above and below it. Unlike some other roguelikes with many stairs between levels, NetHack levels always have exactly one up stair, and every level except the bottom one also has one down stair. Plus, there is the possibility of a second down stair to one of the special branches of the dungeon.

To create the stairs, first pick a random room. If this isn't the bottom level, place the down stair at a random location in this room. Now, check to see if there is more than one room. NetHack prefers to place the stairs in different rooms, so if there are at least two rooms, it picks a new random room. This time, instead of picking from all of the rooms, it picks from any room except the last one. This is in case it randomly picks the same room that the down stair is already in, in which case it picks the room with the next highest number.

Whichever room it has selected, it places the up stairs in a random, unoccupied location within that room, by randomly generating coordinates in a while loop until it finds one that returns false for occupied(). At this point, "occupied" mostly means "the down stairs are in this tile". (This is terribly inefficient, but seldom matters.)

Then it checks to see if this level has a connection to a dungeon branch. This is where room_threshold finally gets set, with the ternary operator. If there is a branch, the threshold is 4; otherwise it is 3.

(If this is the special Rogue level, there’s a goto command here, to skip over this next bit. I told you this code was gnarly.)

The rooms are now connected with corridors via makecorridors().

First, it loops through the array of rooms, trying to join each room to the next one in the sequence. After each join, there's a 2% chance that it'll stop and go to the second step.

Second, it loops through the list again, this time trying to join each room to the room two steps down the array.

Third, it goes through the list of rooms, trying to join each room to every other room, but stopping once it runs out of rooms that aren't the current room (e.g. if there's only one room).

Finally, if there are more than two rooms, it picks a random number (based on the number of rooms), adds 4 to it, and then counts down, each loop attempting to link two random rooms. To keep the randomly selected rooms from being the same, it uses the same trick as with the stairs: a is random(number of rooms) and b is random(number of rooms minus two). If b is equal to or greater than a, add two to b.

As you can see, it attempts to add connections between nearly every room, so what is important here is the order the joins are attempted; join() tries to find places to put doors and then tries to dig corridors between them. It doesn't always succeed, which the algorithm takes advantage of. Enough corridors are placed to result in NetHack's characteristic look of rooms suspended in a sea of tunnels.

Once the corridors are placed, makelevel() calls make_niches()  to add closets  to the level, which are 1-square corridors-rooms that will either be connected to a room with a door (often a secret door) or which can only be reached by digging or teleportation.

For the number of niches, it picks a number between 0 and the number of rooms bitshifted to the right plus 1: rnd((nroom>>1) + 1). It also checks the depth: between level 5 and level 25 (noninclusive) there’s a chance for a trap door. And if the depth is greater than 15 and it’s a no-teleport level, there won’t be a teleport-trap niche.

Niche generation is handled by makeniche().

As long as the level hasn’t already exceeded DOORMAX, it runs a loop 8 times, picking a random room each time and attempting to place a connected niche. There’s some restrictions on where they’re allowed: only in ordinary rooms, only if there’s space to place it, etc.

If it can place a niche, it checks the requested trap type, and sets up the niche accordingly. Some traps get engravings (trap doors get “Vlad was here”).

Once there have been eight attempts at placing the niche, it finishes and returns, where we resume execution in makelevel().

Next time, we'll talk about adding special rooms and secret treasure vaults.