NetHack corridor implementation

Question

I was just playing around with NetHack as I am in the process of coding up a simplified version for myself. My question is, how are corridors implemented? I have been trying to think of an approach for a few days now and cannot come up with anything reasonable.

Answer 1

Map generation in Nethack occurs in mkmap.c. The method join_map determines which rooms should be connected. The method dig_corridor in sp_lev.c does the actual digging.

lines of interest:

if (tx > xx)        dx = 1;
else if (ty > yy)   dy = 1;
else if (tx < xx)   dx = -1;
else            dy = -1;

this compares "current X and Y" with "target X and Y" to determine the direction that we will initially be digging in.

while(xx != tx || yy != ty) {
    /* loop: dig corridor at [xx,yy] and find new [xx,yy] */
    if(cct++ > 500 || (nxcor && !rn2(35)))
    return FALSE;

We'll keep going until we reach the target, with a few exceptions: if "corridor count" cct is 500, then we've dug a long way and want to give up. If nxcor is true, then the corridor is allowed to dead end. rn2 is a random number generator, so if a dead end is possible, then there is a small chance during each loop that we'll give up.

    crm = &levl[xx][yy];
    if(crm->typ == btyp) {
    if(ftyp != CORR || rn2(100)) {
        crm->typ = ftyp;
        if(nxcor && !rn2(50))
            (void) mksobj_at(BOULDER, xx, yy, TRUE, FALSE);
    } else {
        crm->typ = SCORR;
    }

crm is the tile that we are currently on. Most of the time, we make the tile into an ordinary corridor. Sometimes instead, we make the tile into a SCORR, or Secret Corridor, which can only be traversed after you find it by searching. We also place boulders if the path may be a dead end.

    /* do we have to change direction ? */
    if(dy && dix > diy) {
    register int ddx = (xx > tx) ? -1 : 1;

    crm = &levl[xx+ddx][yy];
    if(crm->typ == btyp || crm->typ == ftyp || crm->typ == SCORR) {
        dx = ddx;
        dy = 0;
        continue;
    }
    } else if(dx && diy > dix) {
    register int ddy = (yy > ty) ? -1 : 1;

    crm = &levl[xx][yy+ddy];
    if(crm->typ == btyp || crm->typ == ftyp || crm->typ == SCORR) {
        dy = ddy;
        dx = 0;
        continue;
    }
    }

If the "slope" of the line drawn between the current position and the target position is appreciably far from 45 degrees, we attempt to change direction; if we're moving along the X axis, instead we start moving along the Y axis; and vice versa. This causes the typical squiggly stair-shaped corridors that connect two diagonal rooms. If changing direction would cause us to hit an obstacle(other rooms, lava, etc), then we'll just keep going the direction we were going in.

Answer 2

You could check out the source for yourself! Link

I remember going through the source code at one time long ago. Memory is a bit rusty but I think it was a pretty simple sequential process. Boxes would be drawn for rooms to a certain ratio of available tiles, then they'd generate the corridors and mask the rooms against them. I think they had a pass where they looked for areas that were inaccessible (using a flood fill?).

Then stairs/doors/etc were populated.

What you're looking for is a Maze generation algorithm. There are tons.