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.