src/mkmap.c

   1 /* NetHack 3.6  mkmap.c $NHDT-Date: 1432512767 2015/05/25 00:12:47 $  $NHDT-Branch: master $:$NHDT-Revision: 1.16 $ */
   2 /* Copyright (c) J. C. Collet, M. Stephenson and D. Cohrs, 1992   */
   3 /* NetHack may be freely redistributed.  See license for details. */
   4
   5 #include "hack.h"
   6 #include "sp_lev.h"
   7
   8 #define HEIGHT (ROWNO - 1)
   9 #define WIDTH (COLNO - 2)
  10
  11 STATIC_DCL void FDECL(init_map, (SCHAR_P));
  12 STATIC_DCL void FDECL(init_fill, (SCHAR_P, SCHAR_P));
  13 STATIC_DCL schar FDECL(get_map, (int, int, SCHAR_P));
  14 STATIC_DCL void FDECL(pass_one, (SCHAR_P, SCHAR_P));
  15 STATIC_DCL void FDECL(pass_two, (SCHAR_P, SCHAR_P));
  16 STATIC_DCL void FDECL(pass_three, (SCHAR_P, SCHAR_P));
  17 STATIC_DCL void NDECL(wallify_map);
  18 STATIC_DCL void FDECL(join_map, (SCHAR_P, SCHAR_P));
  19 STATIC_DCL void FDECL(finish_map,
  20                       (SCHAR_P, SCHAR_P, BOOLEAN_P, BOOLEAN_P, BOOLEAN_P));
  21 STATIC_DCL void FDECL(remove_room, (unsigned));
  22 void FDECL(mkmap, (lev_init *));
  23
  24 static char *new_locations;
  25 int min_rx, max_rx, min_ry, max_ry; /* rectangle bounds for regions */
  26 static int n_loc_filled;
  27
  28 STATIC_OVL void
  29 init_map(bg_typ)
  30 schar bg_typ;
  31 {
  32     register int i, j;
  33
  34     for (i = 1; i < COLNO; i++)
  35         for (j = 0; j < ROWNO; j++)
  36             levl[i][j].typ = bg_typ;
  37 }
  38
  39 STATIC_OVL void
  40 init_fill(bg_typ, fg_typ)
  41 schar bg_typ, fg_typ;
  42 {
  43     register int i, j;
  44     long limit, count;
  45
  46     limit = (WIDTH * HEIGHT * 2) / 5;
  47     count = 0;
  48     while (count < limit) {
  49         i = rn1(WIDTH - 1, 2);
  50         j = rnd(HEIGHT - 1);
  51         if (levl[i][j].typ == bg_typ) {
  52             levl[i][j].typ = fg_typ;
  53             count++;
  54         }
  55     }
  56 }
  57
  58 STATIC_OVL schar
  59 get_map(col, row, bg_typ)
  60 int col, row;
  61 schar bg_typ;
  62 {
  63     if (col <= 0 || row < 0 || col > WIDTH || row >= HEIGHT)
  64         return bg_typ;
  65     return levl[col][row].typ;
  66 }
  67
  68 static int dirs[16] = { -1, -1 /**/, -1, 0 /**/,  -1, 1 /**/, 0, -1 /**/,
  69                         0,  1 /**/,  1,  -1 /**/, 1,  0 /**/, 1, 1 };
  70
  71 STATIC_OVL void
  72 pass_one(bg_typ, fg_typ)
  73 schar bg_typ, fg_typ;
  74 {
  75     register int i, j;
  76     short count, dr;
  77
  78     for (i = 2; i <= WIDTH; i++)
  79         for (j = 1; j < HEIGHT; j++) {
  80             for (count = 0, dr = 0; dr < 8; dr++)
  81                 if (get_map(i + dirs[dr * 2], j + dirs[(dr * 2) + 1], bg_typ)
  82                     == fg_typ)
  83                     count++;
  84
  85             switch (count) {
  86             case 0: /* death */
  87             case 1:
  88             case 2:
  89                 levl[i][j].typ = bg_typ;
  90                 break;
  91             case 5:
  92             case 6:
  93             case 7:
  94             case 8:
  95                 levl[i][j].typ = fg_typ;
  96                 break;
  97             default:
  98                 break;
  99             }
 100         }
 101 }
 102
 103 #define new_loc(i, j) *(new_locations + ((j) * (WIDTH + 1)) + (i))
 104
 105 STATIC_OVL void
 106 pass_two(bg_typ, fg_typ)
 107 schar bg_typ, fg_typ;
 108 {
 109     register int i, j;
 110     short count, dr;
 111
 112     for (i = 2; i <= WIDTH; i++)
 113         for (j = 1; j < HEIGHT; j++) {
 114             for (count = 0, dr = 0; dr < 8; dr++)
 115                 if (get_map(i + dirs[dr * 2], j + dirs[(dr * 2) + 1], bg_typ)
 116                     == fg_typ)
 117                     count++;
 118             if (count == 5)
 119                 new_loc(i, j) = bg_typ;
 120             else
 121                 new_loc(i, j) = get_map(i, j, bg_typ);
 122         }
 123
 124     for (i = 2; i <= WIDTH; i++)
 125         for (j = 1; j < HEIGHT; j++)
 126             levl[i][j].typ = new_loc(i, j);
 127 }
 128
 129 STATIC_OVL void
 130 pass_three(bg_typ, fg_typ)
 131 schar bg_typ, fg_typ;
 132 {
 133     register int i, j;
 134     short count, dr;
 135
 136     for (i = 2; i <= WIDTH; i++)
 137         for (j = 1; j < HEIGHT; j++) {
 138             for (count = 0, dr = 0; dr < 8; dr++)
 139                 if (get_map(i + dirs[dr * 2], j + dirs[(dr * 2) + 1], bg_typ)
 140                     == fg_typ)
 141                     count++;
 142             if (count < 3)
 143                 new_loc(i, j) = bg_typ;
 144             else
 145                 new_loc(i, j) = get_map(i, j, bg_typ);
 146         }
 147
 148     for (i = 2; i <= WIDTH; i++)
 149         for (j = 1; j < HEIGHT; j++)
 150             levl[i][j].typ = new_loc(i, j);
 151 }
 152
 153 /*
 154  * use a flooding algorithm to find all locations that should
 155  * have the same rm number as the current location.
 156  * if anyroom is TRUE, use IS_ROOM to check room membership instead of
 157  * exactly matching levl[sx][sy].typ and walls are included as well.
 158  */
 159 void
 160 flood_fill_rm(sx, sy, rmno, lit, anyroom)
 161 int sx;
 162 register int sy;
 163 register int rmno;
 164 boolean lit;
 165 boolean anyroom;
 166 {
 167     register int i;
 168     int nx;
 169     schar fg_typ = levl[sx][sy].typ;
 170
 171     /* back up to find leftmost uninitialized location */
 172     while (sx > 0 && (anyroom ? IS_ROOM(levl[sx][sy].typ)
 173                               : levl[sx][sy].typ == fg_typ)
 174            && (int) levl[sx][sy].roomno != rmno)
 175         sx--;
 176     sx++; /* compensate for extra decrement */
 177
 178     /* assume sx,sy is valid */
 179     if (sx < min_rx)
 180         min_rx = sx;
 181     if (sy < min_ry)
 182         min_ry = sy;
 183
 184     for (i = sx; i <= WIDTH && levl[i][sy].typ == fg_typ; i++) {
 185         levl[i][sy].roomno = rmno;
 186         levl[i][sy].lit = lit;
 187         if (anyroom) {
 188             /* add walls to room as well */
 189             register int ii, jj;
 190             for (ii = (i == sx ? i - 1 : i); ii <= i + 1; ii++)
 191                 for (jj = sy - 1; jj <= sy + 1; jj++)
 192                     if (isok(ii, jj) && (IS_WALL(levl[ii][jj].typ)
 193                                          || IS_DOOR(levl[ii][jj].typ)
 194                                          || levl[ii][jj].typ == SDOOR)) {
 195                         levl[ii][jj].edge = 1;
 196                         if (lit)
 197                             levl[ii][jj].lit = lit;
 198                         if ((int) levl[ii][jj].roomno != rmno)
 199                             levl[ii][jj].roomno = SHARED;
 200                     }
 201         }
 202         n_loc_filled++;
 203     }
 204     nx = i;
 205
 206     if (isok(sx, sy - 1)) {
 207         for (i = sx; i < nx; i++)
 208             if (levl[i][sy - 1].typ == fg_typ) {
 209                 if ((int) levl[i][sy - 1].roomno != rmno)
 210                     flood_fill_rm(i, sy - 1, rmno, lit, anyroom);
 211             } else {
 212                 if ((i > sx || isok(i - 1, sy - 1))
 213                     && levl[i - 1][sy - 1].typ == fg_typ) {
 214                     if ((int) levl[i - 1][sy - 1].roomno != rmno)
 215                         flood_fill_rm(i - 1, sy - 1, rmno, lit, anyroom);
 216                 }
 217                 if ((i < nx - 1 || isok(i + 1, sy - 1))
 218                     && levl[i + 1][sy - 1].typ == fg_typ) {
 219                     if ((int) levl[i + 1][sy - 1].roomno != rmno)
 220                         flood_fill_rm(i + 1, sy - 1, rmno, lit, anyroom);
 221                 }
 222             }
 223     }
 224     if (isok(sx, sy + 1)) {
 225         for (i = sx; i < nx; i++)
 226             if (levl[i][sy + 1].typ == fg_typ) {
 227                 if ((int) levl[i][sy + 1].roomno != rmno)
 228                     flood_fill_rm(i, sy + 1, rmno, lit, anyroom);
 229             } else {
 230                 if ((i > sx || isok(i - 1, sy + 1))
 231                     && levl[i - 1][sy + 1].typ == fg_typ) {
 232                     if ((int) levl[i - 1][sy + 1].roomno != rmno)
 233                         flood_fill_rm(i - 1, sy + 1, rmno, lit, anyroom);
 234                 }
 235                 if ((i < nx - 1 || isok(i + 1, sy + 1))
 236                     && levl[i + 1][sy + 1].typ == fg_typ) {
 237                     if ((int) levl[i + 1][sy + 1].roomno != rmno)
 238                         flood_fill_rm(i + 1, sy + 1, rmno, lit, anyroom);
 239                 }
 240             }
 241     }
 242
 243     if (nx > max_rx)
 244         max_rx = nx - 1; /* nx is just past valid region */
 245     if (sy > max_ry)
 246         max_ry = sy;
 247 }
 248
 249 /*
 250  * If we have drawn a map without walls, this allows us to
 251  * auto-magically wallify it.  Taken from lev_main.c.
 252  */
 253 STATIC_OVL void
 254 wallify_map()
 255 {
 256     int x, y, xx, yy;
 257
 258     for (x = 1; x < COLNO; x++)
 259         for (y = 0; y < ROWNO; y++)
 260             if (levl[x][y].typ == STONE) {
 261                 for (yy = y - 1; yy <= y + 1; yy++)
 262                     for (xx = x - 1; xx <= x + 1; xx++)
 263                         if (isok(xx, yy) && levl[xx][yy].typ == ROOM) {
 264                             if (yy != y)
 265                                 levl[x][y].typ = HWALL;
 266                             else
 267                                 levl[x][y].typ = VWALL;
 268                         }
 269             }
 270 }
 271
 272 STATIC_OVL void
 273 join_map(bg_typ, fg_typ)
 274 schar bg_typ, fg_typ;
 275 {
 276     register struct mkroom *croom, *croom2;
 277
 278     register int i, j;
 279     int sx, sy;
 280     coord sm, em;
 281
 282     /* first, use flood filling to find all of the regions that need joining
 283      */
 284     for (i = 2; i <= WIDTH; i++)
 285         for (j = 1; j < HEIGHT; j++) {
 286             if (levl[i][j].typ == fg_typ && levl[i][j].roomno == NO_ROOM) {
 287                 min_rx = max_rx = i;
 288                 min_ry = max_ry = j;
 289                 n_loc_filled = 0;
 290                 flood_fill_rm(i, j, nroom + ROOMOFFSET, FALSE, FALSE);
 291                 if (n_loc_filled > 3) {
 292                     add_room(min_rx, min_ry, max_rx, max_ry, FALSE, OROOM,
 293                              TRUE);
 294                     rooms[nroom - 1].irregular = TRUE;
 295                     if (nroom >= (MAXNROFROOMS * 2))
 296                         goto joinm;
 297                 } else {
 298                     /*
 299                      * it's a tiny hole; erase it from the map to avoid
 300                      * having the player end up here with no way out.
 301                      */
 302                     for (sx = min_rx; sx <= max_rx; sx++)
 303                         for (sy = min_ry; sy <= max_ry; sy++)
 304                             if ((int) levl[sx][sy].roomno
 305                                 == nroom + ROOMOFFSET) {
 306                                 levl[sx][sy].typ = bg_typ;
 307                                 levl[sx][sy].roomno = NO_ROOM;
 308                             }
 309                 }
 310             }
 311         }
 312
 313 joinm:
 314     /*
 315      * Ok, now we can actually join the regions with fg_typ's.
 316      * The rooms are already sorted due to the previous loop,
 317      * so don't call sort_rooms(), which can screw up the roomno's
 318      * validity in the levl structure.
 319      */
 320     for (croom = &rooms[0], croom2 = croom + 1; croom2 < &rooms[nroom];) {
 321         /* pick random starting and end locations for "corridor" */
 322         if (!somexy(croom, &sm) || !somexy(croom2, &em)) {
 323             /* ack! -- the level is going to be busted */
 324             /* arbitrarily pick centers of both rooms and hope for the best */
 325             impossible("No start/end room loc in join_map.");
 326             sm.x = croom->lx + ((croom->hx - croom->lx) / 2);
 327             sm.y = croom->ly + ((croom->hy - croom->ly) / 2);
 328             em.x = croom2->lx + ((croom2->hx - croom2->lx) / 2);
 329             em.y = croom2->ly + ((croom2->hy - croom2->ly) / 2);
 330         }
 331
 332         (void) dig_corridor(&sm, &em, FALSE, fg_typ, bg_typ);
 333
 334         /* choose next region to join */
 335         /* only increment croom if croom and croom2 are non-overlapping */
 336         if (croom2->lx > croom->hx
 337             || ((croom2->ly > croom->hy || croom2->hy < croom->ly)
 338                 && rn2(3))) {
 339             croom = croom2;
 340         }
 341         croom2++; /* always increment the next room */
 342     }
 343 }
 344
 345 STATIC_OVL void
 346 finish_map(fg_typ, bg_typ, lit, walled, icedpools)
 347 schar fg_typ, bg_typ;
 348 boolean lit, walled, icedpools;
 349 {
 350     int i, j;
 351
 352     if (walled)
 353         wallify_map();
 354
 355     if (lit) {
 356         for (i = 1; i < COLNO; i++)
 357             for (j = 0; j < ROWNO; j++)
 358                 if ((!IS_ROCK(fg_typ) && levl[i][j].typ == fg_typ)
 359                     || (!IS_ROCK(bg_typ) && levl[i][j].typ == bg_typ)
 360                     || (bg_typ == TREE && levl[i][j].typ == bg_typ)
 361                     || (walled && IS_WALL(levl[i][j].typ)))
 362                     levl[i][j].lit = TRUE;
 363         for (i = 0; i < nroom; i++)
 364             rooms[i].rlit = 1;
 365     }
 366     /* light lava even if everything's otherwise unlit;
 367        ice might be frozen pool rather than frozen moat */
 368     for (i = 1; i < COLNO; i++)
 369         for (j = 0; j < ROWNO; j++) {
 370             if (levl[i][j].typ == LAVAPOOL)
 371                 levl[i][j].lit = TRUE;
 372             else if (levl[i][j].typ == ICE)
 373                 levl[i][j].icedpool = icedpools ? ICED_POOL : ICED_MOAT;
 374         }
 375 }
 376
 377 /*
 378  * When level processed by join_map is overlaid by a MAP, some rooms may no
 379  * longer be valid.  All rooms in the region lx <= x < hx, ly <= y < hy are
 380  * removed.  Rooms partially in the region are truncated.  This function
 381  * must be called before the REGIONs or ROOMs of the map are processed, or
 382  * those rooms will be removed as well.  Assumes roomno fields in the
 383  * region are already cleared, and roomno and irregular fields outside the
 384  * region are all set.
 385  */
 386 void
 387 remove_rooms(lx, ly, hx, hy)
 388 int lx, ly, hx, hy;
 389 {
 390     int i;
 391     struct mkroom *croom;
 392
 393     for (i = nroom - 1; i >= 0; --i) {
 394         croom = &rooms[i];
 395         if (croom->hx < lx || croom->lx >= hx || croom->hy < ly
 396             || croom->ly >= hy)
 397             continue; /* no overlap */
 398
 399         if (croom->lx < lx || croom->hx >= hx || croom->ly < ly
 400             || croom->hy >= hy) { /* partial overlap */
 401             /* TODO: ensure remaining parts of room are still joined */
 402
 403             if (!croom->irregular)
 404                 impossible("regular room in joined map");
 405         } else {
 406             /* total overlap, remove the room */
 407             remove_room((unsigned) i);
 408         }
 409     }
 410 }
 411
 412 /*
 413  * Remove roomno from the rooms array, decrementing nroom.  Also updates
 414  * all level roomno values of affected higher numbered rooms.  Assumes
 415  * level structure contents corresponding to roomno have already been reset.
 416  * Currently handles only the removal of rooms that have no subrooms.
 417  */
 418 STATIC_OVL void
 419 remove_room(roomno)
 420 unsigned roomno;
 421 {
 422     struct mkroom *croom = &rooms[roomno];
 423     struct mkroom *maxroom = &rooms[--nroom];
 424     int i, j;
 425     unsigned oroomno;
 426
 427     if (croom != maxroom) {
 428         /* since the order in the array only matters for making corridors,
 429          * copy the last room over the one being removed on the assumption
 430          * that corridors have already been dug. */
 431         (void) memcpy((genericptr_t) croom, (genericptr_t) maxroom,
 432                       sizeof(struct mkroom));
 433
 434         /* since maxroom moved, update affected level roomno values */
 435         oroomno = nroom + ROOMOFFSET;
 436         roomno += ROOMOFFSET;
 437         for (i = croom->lx; i <= croom->hx; ++i)
 438             for (j = croom->ly; j <= croom->hy; ++j) {
 439                 if (levl[i][j].roomno == oroomno)
 440                     levl[i][j].roomno = roomno;
 441             }
 442     }
 443
 444     maxroom->hx = -1; /* just like add_room */
 445 }
 446
 447 #define N_P1_ITER 1 /* tune map generation via this value */
 448 #define N_P2_ITER 1 /* tune map generation via this value */
 449 #define N_P3_ITER 2 /* tune map smoothing via this value */
 450
 451 void
 452 mkmap(init_lev)
 453 lev_init *init_lev;
 454 {
 455     schar bg_typ = init_lev->bg, fg_typ = init_lev->fg;
 456     boolean smooth = init_lev->smoothed, join = init_lev->joined;
 457     xchar lit = init_lev->lit, walled = init_lev->walled;
 458     int i;
 459
 460     if (lit < 0)
 461         lit = (rnd(1 + abs(depth(&u.uz))) < 11 && rn2(77)) ? 1 : 0;
 462
 463     new_locations = (char *) alloc((WIDTH + 1) * HEIGHT);
 464
 465     init_map(bg_typ);
 466     init_fill(bg_typ, fg_typ);
 467
 468     for (i = 0; i < N_P1_ITER; i++)
 469         pass_one(bg_typ, fg_typ);
 470
 471     for (i = 0; i < N_P2_ITER; i++)
 472         pass_two(bg_typ, fg_typ);
 473
 474     if (smooth)
 475         for (i = 0; i < N_P3_ITER; i++)
 476             pass_three(bg_typ, fg_typ);
 477
 478     if (join)
 479         join_map(bg_typ, fg_typ);
 480
 481     finish_map(fg_typ, bg_typ, (boolean) lit, (boolean) walled,
 482                init_lev->icedpools);
 483     /* a walled, joined level is cavernous, not mazelike -dlc */
 484     if (walled && join) {
 485         level.flags.is_maze_lev = FALSE;
 486         level.flags.is_cavernous_lev = TRUE;
 487     }
 488     free(new_locations);
 489 }
 490
 491 /*mkmap.c*/