src/mkmap.c

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