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 init_map(SCHAR_P);
  12 STATIC_DCL void init_fill(SCHAR_P,SCHAR_P);
  13 STATIC_DCL schar get_map(int,int,SCHAR_P);
  14 STATIC_DCL void pass_one(SCHAR_P,SCHAR_P);
  15 STATIC_DCL void pass_two(SCHAR_P,SCHAR_P);
  16 STATIC_DCL void pass_three(SCHAR_P,SCHAR_P);
  17 STATIC_DCL void wallify_map(void);
  18 STATIC_DCL void join_map(SCHAR_P,SCHAR_P);
  19 STATIC_DCL void finish_map(SCHAR_P,SCHAR_P,XCHAR_P,XCHAR_P);
  20 STATIC_DCL void remove_room(unsigned);
  21 void 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     }
 223     if(isok(sx,sy+1)) {
 224         for(i=sx; i<nx; i++) {
 225             if(levl[i][sy+1].typ == fg_typ) {
 226                 if ((int) levl[i][sy+1].roomno != rmno)
 227                     flood_fill_rm(i,sy+1,rmno,lit,anyroom);
 228             } else {
 229                 if((i>sx || isok(i-1,sy+1)) &&
 230                       levl[i-1][sy+1].typ == fg_typ) {
 231                     if ((int) levl[i-1][sy+1].roomno != rmno)
 232                         flood_fill_rm(i-1,sy+1,rmno,lit,anyroom);
 233                 }
 234                 if((i<nx-1 || isok(i+1,sy+1)) &&
 235                       levl[i+1][sy+1].typ == fg_typ) {
 236                     if ((int) levl[i+1][sy+1].roomno != rmno)
 237                         flood_fill_rm(i+1,sy+1,rmno,lit,anyroom);
 238                 }
 239             }
 240     }
 241     }
 242     if(nx > max_rx) max_rx = nx - 1; /* nx is just past valid region */
 243     if(sy > max_ry) max_ry = sy;
 244 }
 245
 246 /*
 247  *      If we have drawn a map without walls, this allows us to
 248  *      auto-magically wallify it.  Taken from lev_main.c.
 249  */
 250 STATIC_OVL void
 251 wallify_map()
 252 {
 253
 254     int x, y, xx, yy;
 255
 256     for(x = 1; x < COLNO; x++)
 257         for(y = 0; y < ROWNO; y++)
 258             if(levl[x][y].typ == STONE) {
 259                 for(yy = y - 1; yy <= y+1; yy++)
 260                     for(xx = x - 1; xx <= x+1; xx++)
 261                         if(isok(xx,yy) && levl[xx][yy].typ == ROOM) {
 262                             if(yy != y) levl[x][y].typ = HWALL;
 263                             else        levl[x][y].typ = VWALL;
 264                         }
 265             }
 266 }
 267
 268 STATIC_OVL void
 269 join_map(bg_typ, fg_typ)
 270         schar   bg_typ, fg_typ;
 271 {
 272     register struct mkroom *croom, *croom2;
 273
 274     register int i, j;
 275     int sx, sy;
 276     coord sm, em;
 277
 278     /* first, use flood filling to find all of the regions that need joining */
 279     for(i=2; i<=WIDTH; i++)
 280         for(j=1; j<HEIGHT; j++) {
 281             if(levl[i][j].typ == fg_typ && levl[i][j].roomno == NO_ROOM) {
 282                 min_rx = max_rx = i;
 283                 min_ry = max_ry = j;
 284                 n_loc_filled = 0;
 285                 flood_fill_rm(i,j,nroom+ROOMOFFSET,FALSE,FALSE);
 286                 if(n_loc_filled > 3) {
 287                     add_room(min_rx, min_ry, max_rx, max_ry,
 288                              FALSE, OROOM, TRUE, FALSE, FALSE);
 289                     rooms[nroom-1].irregular = TRUE;
 290                     if(nroom >= (MAXNROFROOMS*2))
 291                         goto joinm;
 292                 } else {
 293                     /*
 294                      * it's a tiny hole; erase it from the map to avoid
 295                      * having the player end up here with no way out.
 296                      */
 297                     for(sx = min_rx; sx<=max_rx; sx++)
 298                         for(sy = min_ry; sy<=max_ry; sy++)
 299                             if ((int) levl[sx][sy].roomno ==
 300                                     nroom + ROOMOFFSET) {
 301                                 levl[sx][sy].typ = bg_typ;
 302                                 levl[sx][sy].roomno = NO_ROOM;
 303                             }
 304                 }
 305             }
 306         }
 307
 308 joinm:
 309     /*
 310      * Ok, now we can actually join the regions with fg_typ's.
 311      * The rooms are already sorted due to the previous loop,
 312      * so don't call sort_rooms(), which can screw up the roomno's
 313      * validity in the levl structure.
 314      */
 315     for(croom = &rooms[0], croom2 = croom + 1; croom2 < &rooms[nroom]; ) {
 316         /* pick random starting and end locations for "corridor" */
 317         if(!somexy(croom, &sm) || !somexy(croom2, &em)) {
 318             /* ack! -- the level is going to be busted */
 319             /* arbitrarily pick centers of both rooms and hope for the best */
 320             impossible("No start/end room loc in join_map.");
 321             sm.x = croom->lx + ((croom->hx - croom->lx) / 2);
 322             sm.y = croom->ly + ((croom->hy - croom->ly) / 2);
 323             em.x = croom2->lx + ((croom2->hx - croom2->lx) / 2);
 324             em.y = croom2->ly + ((croom2->hy - croom2->ly) / 2);
 325         }
 326
 327         (void) dig_corridor(&sm, &em, FALSE, fg_typ, bg_typ);
 328
 329         /* choose next region to join */
 330         /* only increment croom if croom and croom2 are non-overlapping */
 331         if(croom2->lx > croom->hx ||
 332            ((croom2->ly > croom->hy || croom2->hy < croom->ly) && rn2(3))) {
 333             croom = croom2;
 334         }
 335         croom2++; /* always increment the next room */
 336     }
 337 }
 338
 339 STATIC_OVL void
 340 finish_map(fg_typ, bg_typ, lit, walled)
 341         schar   fg_typ, bg_typ;
 342         boolean lit, walled;
 343 {
 344         int     i, j;
 345
 346         if(walled) wallify_map();
 347
 348         if(lit) {
 349             for(i=1; i<COLNO; i++)
 350                 for(j=0; j<ROWNO; j++)
 351                     if((!IS_ROCK(fg_typ) && levl[i][j].typ == fg_typ) ||
 352                        (!IS_ROCK(bg_typ) && levl[i][j].typ == bg_typ) ||
 353                        (bg_typ == TREE && levl[i][j].typ == bg_typ) ||
 354                         (walled && IS_WALL(levl[i][j].typ)))
 355                         levl[i][j].lit = TRUE;
 356             for(i = 0; i < nroom; i++)
 357                 rooms[i].rlit = 1;
 358         }
 359         /* light lava even if everything's otherwise unlit */
 360         for(i=1; i<COLNO; i++)
 361             for(j=0; j<ROWNO; j++)
 362                 if (levl[i][j].typ == LAVAPOOL)
 363                     levl[i][j].lit = TRUE;
 364 }
 365
 366 /*
 367  * When level processed by join_map is overlaid by a MAP, some rooms may no
 368  * longer be valid.  All rooms in the region lx <= x < hx, ly <= y < hy are
 369  * removed.  Rooms partially in the region are truncated.  This function
 370  * must be called before the REGIONs or ROOMs of the map are processed, or
 371  * those rooms will be removed as well.  Assumes roomno fields in the
 372  * region are already cleared, and roomno and irregular fields outside the
 373  * region are all set.
 374  */
 375 void
 376 remove_rooms(lx, ly, hx, hy)
 377     int lx, ly, hx, hy;
 378 {
 379     int i;
 380     struct mkroom *croom;
 381
 382     for (i = nroom - 1; i >= 0; --i) {
 383         croom = &rooms[i];
 384         if (croom->hx < lx || croom->lx >= hx ||
 385             croom->hy < ly || croom->ly >= hy) continue; /* no overlap */
 386
 387         if (croom->lx < lx || croom->hx >= hx ||
 388             croom->ly < ly || croom->hy >= hy) { /* partial overlap */
 389             /* TODO: ensure remaining parts of room are still joined */
 390
 391             if (!croom->irregular) impossible("regular room in joined map");
 392         } else {
 393             /* total overlap, remove the room */
 394             remove_room((unsigned)i);
 395         }
 396     }
 397 }
 398
 399 /*
 400  * Remove roomno from the rooms array, decrementing nroom.  Also updates
 401  * all level roomno values of affected higher numbered rooms.  Assumes
 402  * level structure contents corresponding to roomno have already been reset.
 403  * Currently handles only the removal of rooms that have no subrooms.
 404  */
 405 STATIC_OVL void
 406 remove_room(roomno)
 407     unsigned roomno;
 408 {
 409     struct mkroom *croom = &rooms[roomno];
 410     struct mkroom *maxroom = &rooms[--nroom];
 411     int i, j;
 412     unsigned oroomno;
 413
 414     if (croom != maxroom) {
 415         /* since the order in the array only matters for making corridors,
 416          * copy the last room over the one being removed on the assumption
 417          * that corridors have already been dug. */
 418         (void) memcpy((void *)croom, (void *)maxroom,
 419                         sizeof(struct mkroom));
 420
 421         /* since maxroom moved, update affected level roomno values */
 422         oroomno = nroom + ROOMOFFSET;
 423         roomno += ROOMOFFSET;
 424         for (i = croom->lx; i <= croom->hx; ++i)
 425             for (j = croom->ly; j <= croom->hy; ++j) {
 426                 if (levl[i][j].roomno == oroomno)
 427                     levl[i][j].roomno = roomno;
 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*/