src/rooms.c

   1 /*
   2  * File: rooms.c
   3  * Purpose: make rooms. Used by generate.c when creating dungeons.
   4  */
   5
   6 /*
   7  * Copyright (c) 1997 Ben Harrison, James E. Wilson, Robert A. Koeneke
   8  *
   9  * This software may be copied and distributed for educational, research,
  10  * and not for profit purposes provided that this copyright and statement
  11  * are included in all such copies.  Other copyrights may also apply.
  12  */
  13
  14 #include "angband.h"
  15 #include "generate.h"
  16 #include "grid.h"
  17 #include "rooms.h"
  18
  19
  20 /*
  21  * [from SAngband (originally from OAngband)]
  22  *
  23  * Table of values that control how many times each type of room will
  24  * appear.  Each type of room has its own row, and each column
  25  * corresponds to dungeon levels 0, 10, 20, and so on.  The final
  26  * value is the minimum depth the room can appear at.  -LM-
  27  *
  28  * Level 101 and below use the values for level 100.
  29  *
  30  * Rooms with lots of monsters or loot may not be generated if the
  31  * object or monster lists are already nearly full.  Rooms will not
  32  * appear above their minimum depth.  Tiny levels will not have space
  33  * for all the rooms you ask for.
  34  */
  35 static room_info_type room_info_normal[ROOM_T_MAX] =
  36 {
  37         /* Depth */
  38         /*  0  10  20  30  40  50  60  70  80  90 100  min limit */
  39
  40         {{999,900,800,700,600,500,400,300,200,100,  0},  0}, /*NORMAL   */
  41         {{  1, 10, 20, 30, 40, 50, 60, 70, 80, 90,100},  1}, /*OVERLAP  */
  42         {{  1, 10, 20, 30, 40, 50, 60, 70, 80, 90,100},  3}, /*CROSS    */
  43         {{  1, 10, 20, 30, 40, 50, 60, 70, 80, 90,100},  3}, /*INNER_F  */
  44         {{  0,  1,  1,  1,  2,  3,  5,  6,  8, 10, 13}, 10}, /*NEST     */
  45         {{  0,  1,  1,  2,  3,  4,  6,  8, 10, 13, 16}, 10}, /*PIT      */
  46         {{  0,  1,  1,  1,  2,  2,  3,  5,  6,  8, 10}, 10}, /*LESSER_V */
  47         {{  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  4}, 20}, /*GREATER_V*/
  48         {{  0,100,200,300,400,500,600,700,800,900,999}, 10}, /*FRACAVE  */
  49         {{  0,  1,  1,  1,  1,  1,  1,  1,  1,  2,  2}, 10}, /*RANDOM_V */
  50         {{  0,  4,  8, 12, 16, 20, 24, 28, 32, 36, 40},  3}, /*OVAL     */
  51         {{  1,  6, 12, 18, 24, 30, 36, 42, 48, 54, 60}, 10}, /*CRYPT    */
  52         {{  0,  0,  1,  1,  1,  2,  3,  4,  5,  6,  8}, 20}, /*TRAP_PIT */
  53         {{  0,  0,  1,  1,  1,  2,  3,  4,  5,  6,  8}, 20}, /*TRAP     */
  54 };
  55
  56
  57 /* Build rooms in descending order of difficulty. */
  58 static byte room_build_order[ROOM_T_MAX] = {
  59         ROOM_T_GREATER_VAULT,
  60         ROOM_T_RANDOM_VAULT,
  61         ROOM_T_LESSER_VAULT,
  62         ROOM_T_TRAP_PIT,
  63         ROOM_T_PIT,
  64         ROOM_T_NEST,
  65         ROOM_T_TRAP,
  66         ROOM_T_INNER_FEAT,
  67         ROOM_T_OVAL,
  68         ROOM_T_CRYPT,
  69         ROOM_T_OVERLAP,
  70         ROOM_T_CROSS,
  71         ROOM_T_FRACAVE,
  72         ROOM_T_NORMAL,
  73 };
  74
  75
  76 static void place_locked_door(int y, int x)
  77 {
  78         if (d_info[dungeon_type].flags1 & DF1_NO_DOORS)
  79         {
  80                 place_floor_bold(y, x);
  81         }
  82         else
  83         {
  84                 set_cave_feat(y, x, FEAT_DOOR_HEAD+randint1(7));
  85                 cave[y][x].info &= ~(CAVE_FLOOR);
  86         }
  87 }
  88
  89 static void place_secret_door(int y, int x)
  90 {
  91         if (d_info[dungeon_type].flags1 & DF1_NO_DOORS)
  92         {
  93                 place_floor_bold(y, x);
  94         }
  95         else
  96         {
  97                 cave_type *c_ptr = &cave[y][x];
  98
  99                 /* Create secret door */
 100                 place_closed_door(y, x);
 101
 102                 /* Hide by inner wall because this is used in rooms only */
 103                 c_ptr->mimic = feat_wall_inner;
 104
 105                 /* Floor type terrain cannot hide a door */
 106                 if (feat_floor(c_ptr->mimic))
 107                 {
 108                         c_ptr->feat = c_ptr->mimic;
 109                         c_ptr->mimic = 0;
 110                 }
 111
 112                 c_ptr->info &= ~(CAVE_FLOOR);
 113         }
 114 }
 115
 116 /*
 117  * This funtion makes a very small room centred at (x0, y0)
 118  * This is used in crypts, and random elemental vaults.
 119  *
 120  * Note - this should be used only on allocated regions
 121  * within another room.
 122  */
 123 static void build_small_room(int x0, int y0)
 124 {
 125         int x, y;
 126
 127         for (y = y0 - 1; y <= y0 + 1; y++)
 128         {
 129                 place_inner_bold(y, x0 - 1);
 130                 place_inner_bold(y, x0 + 1);
 131         }
 132
 133         for (x = x0 - 1; x <= x0 + 1; x++)
 134         {
 135                 place_inner_bold(y0 - 1, x);
 136                 place_inner_bold(y0 + 1, x);
 137         }
 138
 139         /* Place a secret door on one side */
 140         switch (randint0(4))
 141         {
 142                 case 0: place_secret_door(y0, x0 - 1); break;
 143                 case 1: place_secret_door(y0, x0 + 1); break;
 144                 case 2: place_secret_door(y0 - 1, x0); break;
 145                 case 3: place_secret_door(y0 + 1, x0); break;
 146         }
 147
 148         /* Clear mimic type */
 149         cave[y0][x0].mimic = 0;
 150
 151         /* Add inner open space */
 152         place_floor_bold(y0, x0);
 153 }
 154
 155
 156 /*
 157  * This function tunnels around a room if
 158  * it will cut off part of a cave system.
 159  */
 160 static void check_room_boundary(int x1, int y1, int x2, int y2)
 161 {
 162         int count, x, y;
 163         bool old_is_floor, new_is_floor;
 164
 165
 166         /* Initialize */
 167         count = 0;
 168
 169         old_is_floor = get_is_floor(x1 - 1, y1);
 170
 171         /*
 172          * Count the number of floor-wall boundaries around the room
 173          * Note: diagonal squares are ignored since the player can move diagonally
 174          * to bypass these if needed.
 175          */
 176
 177         /* Above the top boundary */
 178         for (x = x1; x <= x2; x++)
 179         {
 180                 new_is_floor = get_is_floor(x, y1 - 1);
 181
 182                 /* Increment counter if they are different */
 183                 if (new_is_floor != old_is_floor) count++;
 184
 185                 old_is_floor = new_is_floor;
 186         }
 187
 188         /* Right boundary */
 189         for (y = y1; y <= y2; y++)
 190         {
 191                 new_is_floor = get_is_floor(x2 + 1, y);
 192
 193                 /* increment counter if they are different */
 194                 if (new_is_floor != old_is_floor) count++;
 195
 196                 old_is_floor = new_is_floor;
 197         }
 198
 199         /* Bottom boundary */
 200         for (x = x2; x >= x1; x--)
 201         {
 202                 new_is_floor = get_is_floor(x, y2 + 1);
 203
 204                 /* increment counter if they are different */
 205                 if (new_is_floor != old_is_floor) count++;
 206
 207                 old_is_floor = new_is_floor;
 208         }
 209
 210         /* Left boundary */
 211         for (y = y2; y >= y1; y--)
 212         {
 213                 new_is_floor = get_is_floor(x1 - 1, y);
 214
 215                 /* increment counter if they are different */
 216                 if (new_is_floor != old_is_floor) count++;
 217
 218                 old_is_floor = new_is_floor;
 219         }
 220
 221         /* If all the same, or only one connection exit. */
 222         if (count <= 2) return;
 223
 224
 225         /* Tunnel around the room so to prevent problems with caves */
 226         for (y = y1; y <= y2; y++)
 227         {
 228                 for (x = x1; x <= x2; x++)
 229                 {
 230                         set_floor(x, y);
 231                 }
 232         }
 233 }
 234
 235
 236 /*
 237  *  Helper function for find_space().
 238  *
 239  *  Is this a good location?
 240  */
 241 static bool find_space_aux(int blocks_high, int blocks_wide, int block_y, int block_x)
 242 {
 243         int by1, bx1, by2, bx2, by, bx;
 244
 245         /* Itty-bitty rooms must shift about within their rectangle */
 246         if (blocks_wide < 3)
 247         {
 248                 if ((blocks_wide == 2) && (block_x % 3) == 2)
 249                         return FALSE;
 250         }
 251
 252         /* Rooms with width divisible by 3 must be fitted to a rectangle. */
 253         else if ((blocks_wide % 3) == 0)
 254         {
 255                 /* Must be aligned to the left edge of a 11x33 rectangle. */
 256                 if ((block_x % 3) != 0)
 257                         return FALSE;
 258         }
 259
 260         /*
 261          * Big rooms that do not have a width divisible by 3 must be
 262          * aligned towards the edge of the dungeon closest to them.
 263          */
 264         else
 265         {
 266                 /* Shift towards left edge of dungeon. */
 267                 if (block_x + (blocks_wide / 2) <= dun->col_rooms / 2)
 268                 {
 269                         if (((block_x % 3) == 2) && ((blocks_wide % 3) == 2))
 270                                 return FALSE;
 271                         if ((block_x % 3) == 1)
 272                                 return FALSE;
 273                 }
 274
 275                 /* Shift toward right edge of dungeon. */
 276                 else
 277                 {
 278                         if (((block_x % 3) == 2) && ((blocks_wide % 3) == 2))
 279                                 return FALSE;
 280                         if ((block_x % 3) == 1)
 281                                 return FALSE;
 282                 }
 283         }
 284
 285         /* Extract blocks */
 286         by1 = block_y + 0;
 287         bx1 = block_x + 0;
 288         by2 = block_y + blocks_high;
 289         bx2 = block_x + blocks_wide;
 290
 291         /* Never run off the screen */
 292         if ((by1 < 0) || (by2 > dun->row_rooms)) return FALSE;
 293         if ((bx1 < 0) || (bx2 > dun->col_rooms)) return FALSE;
 294
 295         /* Verify available space */
 296         for (by = by1; by < by2; by++)
 297         {
 298                 for (bx = bx1; bx < bx2; bx++)
 299                 {
 300                         if (dun->room_map[by][bx])
 301                         {
 302                                 return FALSE;
 303                         }
 304                 }
 305         }
 306
 307         /* This location is okay */
 308         return TRUE;
 309 }
 310
 311
 312 /*
 313  * Find a good spot for the next room.  -LM-
 314  *
 315  * Find and allocate a free space in the dungeon large enough to hold
 316  * the room calling this function.
 317  *
 318  * We allocate space in 11x11 blocks, but want to make sure that rooms
 319  * align neatly on the standard screen.  Therefore, we make them use
 320  * blocks in few 11x33 rectangles as possible.
 321  *
 322  * Be careful to include the edges of the room in height and width!
 323  *
 324  * Return TRUE and values for the center of the room if all went well.
 325  * Otherwise, return FALSE.
 326  */
 327 static bool find_space(int *y, int *x, int height, int width)
 328 {
 329         int candidates, pick;
 330         int by, bx, by1, bx1, by2, bx2;
 331         int block_y = 0, block_x = 0;
 332
 333
 334         /* Find out how many blocks we need. */
 335         int blocks_high = 1 + ((height - 1) / BLOCK_HGT);
 336         int blocks_wide = 1 + ((width - 1) / BLOCK_WID);
 337
 338         /* There are no way to allocate such huge space */
 339         if (dun->row_rooms < blocks_high) return FALSE;
 340         if (dun->col_rooms < blocks_wide) return FALSE;
 341
 342 #if 0
 343         /* Sometimes, little rooms like to have more space. */
 344         if (blocks_wide == 2)
 345         {
 346                 if (one_in_(3)) blocks_wide = 3;
 347         }
 348         else if (blocks_wide == 1)
 349         {
 350                 if (one_in_(2)) blocks_wide = rand_range(2, 3);
 351         }
 352 #endif
 353
 354         /* Initiallize */
 355         candidates = 0;
 356
 357         /* Count the number of varid places */
 358         for (block_y = dun->row_rooms - blocks_high; block_y >= 0; block_y--)
 359         {
 360                 for (block_x = dun->col_rooms - blocks_wide; block_x >= 0; block_x--)
 361                 {
 362                         if (find_space_aux(blocks_high, blocks_wide, block_y, block_x))
 363                         {
 364                                 /* Find a varid place */
 365                                 candidates++;
 366                         }
 367                 }
 368         }
 369
 370         /* No place! */
 371         if (!candidates)
 372         {
 373                 return FALSE;
 374         }
 375
 376         /* Normal dungeon */
 377         if (!(d_info[dungeon_type].flags1 & DF1_NO_CAVE))
 378         {
 379                 /* Choose a random one */
 380                 pick = randint1(candidates);
 381         }
 382
 383         /* NO_CAVE dungeon (Castle) */
 384         else
 385         {
 386                 /* Always choose the center one */
 387                 pick = candidates/2 + 1;
 388         }
 389
 390         /* Pick up the choosen location */
 391         for (block_y = dun->row_rooms - blocks_high; block_y >= 0; block_y--)
 392         {
 393                 for (block_x = dun->col_rooms - blocks_wide; block_x >= 0; block_x--)
 394                 {
 395                         if (find_space_aux(blocks_high, blocks_wide, block_y, block_x))
 396                         {
 397                                 pick--;
 398
 399                                 /* This one is picked? */
 400                                 if (!pick) break;
 401                         }
 402                 }
 403
 404                 if (!pick) break;
 405         }
 406
 407         /* Extract blocks */
 408         by1 = block_y + 0;
 409         bx1 = block_x + 0;
 410         by2 = block_y + blocks_high;
 411         bx2 = block_x + blocks_wide;
 412
 413         /*
 414          * It is *extremely* important that the following calculation
 415          * be *exactly* correct to prevent memory errors
 416          */
 417
 418         /* Acquire the location of the room */
 419         (*y) = ((by1 + by2) * BLOCK_HGT) / 2;
 420         (*x) = ((bx1 + bx2) * BLOCK_WID) / 2;
 421
 422         /* Save the room location */
 423         if (dun->cent_n < CENT_MAX)
 424         {
 425                 dun->cent[dun->cent_n].y = *y;
 426                 dun->cent[dun->cent_n].x = *x;
 427                 dun->cent_n++;
 428         }
 429
 430         /* Reserve some blocks. */
 431         for (by = by1; by < by2; by++)
 432         {
 433                 for (bx = bx1; bx < bx2; bx++)
 434                 {
 435                         dun->room_map[by][bx] = TRUE;
 436                 }
 437         }
 438
 439
 440         /*
 441          * Hack- See if room will cut off a cavern.
 442          *
 443          * If so, fix by tunneling outside the room in such a
 444          * way as to connect the caves.
 445          */
 446         check_room_boundary(*x - width / 2 - 1, *y - height / 2 - 1, *x + (width - 1) / 2 + 1, *y + (height - 1) / 2 + 1);
 447
 448
 449         /* Success. */
 450         return TRUE;
 451 }
 452
 453
 454
 455 /*
 456  * Room building routines.
 457  *
 458  * Room types:
 459  *   1 -- normal
 460  *   2 -- overlapping
 461  *   3 -- cross shaped
 462  *   4 -- large room with features
 463  *   5 -- monster nests
 464  *   6 -- monster pits
 465  *   7 -- simple vaults
 466  *   8 -- greater vaults
 467  *   9 -- fractal caves
 468  *  10 -- random vaults
 469  *  11 -- circular rooms
 470  *  12 -- crypts
 471  *  13 -- trapped monster pits
 472  *  14 -- trapped room
 473  */
 474
 475
 476 /*
 477  * Type 1 -- normal rectangular rooms
 478  */
 479 static bool build_type1(void)
 480 {
 481         int y, x, y2, x2, yval, xval;
 482         int y1, x1, xsize, ysize;
 483
 484         bool light;
 485
 486         cave_type *c_ptr;
 487
 488         /* Pick a room size */
 489         y1 = randint1(4);
 490         x1 = randint1(11);
 491         y2 = randint1(3);
 492         x2 = randint1(11);
 493
 494         xsize = x1 + x2 + 1;
 495         ysize = y1 + y2 + 1;
 496
 497         /* Find and reserve some space in the dungeon.  Get center of room. */
 498         if (!find_space(&yval, &xval, ysize + 2, xsize + 2)) return FALSE;
 499
 500         /* Choose lite or dark */
 501         light = ((dun_level <= randint1(25)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS));
 502
 503
 504         /* Get corner values */
 505         y1 = yval - ysize / 2;
 506         x1 = xval - xsize / 2;
 507         y2 = yval + (ysize - 1) / 2;
 508         x2 = xval + (xsize - 1) / 2;
 509
 510
 511         /* Place a full floor under the room */
 512         for (y = y1 - 1; y <= y2 + 1; y++)
 513         {
 514                 for (x = x1 - 1; x <= x2 + 1; x++)
 515                 {
 516                         c_ptr = &cave[y][x];
 517                         place_floor_grid(c_ptr);
 518                         c_ptr->info |= (CAVE_ROOM);
 519                         if (light) c_ptr->info |= (CAVE_GLOW);
 520                 }
 521         }
 522
 523         /* Walls around the room */
 524         for (y = y1 - 1; y <= y2 + 1; y++)
 525         {
 526                 c_ptr = &cave[y][x1 - 1];
 527                 place_outer_grid(c_ptr);
 528                 c_ptr = &cave[y][x2 + 1];
 529                 place_outer_grid(c_ptr);
 530         }
 531         for (x = x1 - 1; x <= x2 + 1; x++)
 532         {
 533                 c_ptr = &cave[y1 - 1][x];
 534                 place_outer_grid(c_ptr);
 535                 c_ptr = &cave[y2 + 1][x];
 536                 place_outer_grid(c_ptr);
 537         }
 538
 539
 540         /* Hack -- Occasional pillar room */
 541         if (one_in_(20))
 542         {
 543                 for (y = y1; y <= y2; y += 2)
 544                 {
 545                         for (x = x1; x <= x2; x += 2)
 546                         {
 547                                 c_ptr = &cave[y][x];
 548                                 place_inner_grid(c_ptr);
 549                         }
 550                 }
 551         }
 552
 553         /* Hack -- Occasional room with four pillars */
 554         else if (one_in_(20))
 555         {
 556                 if ((y1 + 4 < y2) && (x1 + 4 < x2))
 557                 {
 558                         c_ptr = &cave[y1 + 1][x1 + 1];
 559                         place_inner_grid(c_ptr);
 560
 561                         c_ptr = &cave[y1 + 1][x2 - 1];
 562                         place_inner_grid(c_ptr);
 563
 564                         c_ptr = &cave[y2 - 1][x1 + 1];
 565                         place_inner_grid(c_ptr);
 566
 567                         c_ptr = &cave[y2 - 1][x2 - 1];
 568                         place_inner_grid(c_ptr);
 569                 }
 570         }
 571
 572         /* Hack -- Occasional ragged-edge room */
 573         else if (one_in_(50))
 574         {
 575                 for (y = y1 + 2; y <= y2 - 2; y += 2)
 576                 {
 577                         c_ptr = &cave[y][x1];
 578                         place_inner_grid(c_ptr);
 579                         c_ptr = &cave[y][x2];
 580                         place_inner_grid(c_ptr);
 581                 }
 582                 for (x = x1 + 2; x <= x2 - 2; x += 2)
 583                 {
 584                         c_ptr = &cave[y1][x];
 585                         place_inner_grid(c_ptr);
 586                         c_ptr = &cave[y2][x];
 587                         place_inner_grid(c_ptr);
 588                 }
 589         }
 590         /* Hack -- Occasional divided room */
 591         else if (one_in_(50))
 592         {
 593                 if (randint1(100) < 50)
 594                 {
 595                         /* Horizontal wall */
 596                         for (x = x1; x <= x2; x++)
 597                         {
 598                                 place_inner_bold(yval, x);
 599                         }
 600
 601                         /* Prevent edge of wall from being tunneled */
 602                         place_solid_bold(yval, x1 - 1);
 603                         place_solid_bold(yval, x2 + 1);
 604                 }
 605                 else
 606                 {
 607                         /* Vertical wall */
 608                         for (y = y1; y <= y2; y++)
 609                         {
 610                                 place_inner_bold(y, xval);
 611                         }
 612
 613                         /* Prevent edge of wall from being tunneled */
 614                         place_solid_bold(y1 - 1, xval);
 615                         place_solid_bold(y2 + 1, xval);
 616                 }
 617
 618                 place_random_door(yval, xval, TRUE);
 619         }
 620
 621         return TRUE;
 622 }
 623
 624
 625 /*
 626  * Type 2 -- Overlapping rectangular rooms
 627  */
 628 static bool build_type2(void)
 629 {
 630         int                     y, x, xval, yval;
 631         int                     y1a, x1a, y2a, x2a;
 632         int                     y1b, x1b, y2b, x2b;
 633         bool            light;
 634         cave_type   *c_ptr;
 635
 636         /* Find and reserve some space in the dungeon.  Get center of room. */
 637         if (!find_space(&yval, &xval, 11, 25)) return FALSE;
 638
 639         /* Choose lite or dark */
 640         light = ((dun_level <= randint1(25)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS));
 641
 642         /* Determine extents of the first room */
 643         y1a = yval - randint1(4);
 644         y2a = yval + randint1(3);
 645         x1a = xval - randint1(11);
 646         x2a = xval + randint1(10);
 647
 648         /* Determine extents of the second room */
 649         y1b = yval - randint1(3);
 650         y2b = yval + randint1(4);
 651         x1b = xval - randint1(10);
 652         x2b = xval + randint1(11);
 653
 654
 655         /* Place a full floor for room "a" */
 656         for (y = y1a - 1; y <= y2a + 1; y++)
 657         {
 658                 for (x = x1a - 1; x <= x2a + 1; x++)
 659                 {
 660                         c_ptr = &cave[y][x];
 661                         place_floor_grid(c_ptr);
 662                         c_ptr->info |= (CAVE_ROOM);
 663                         if (light) c_ptr->info |= (CAVE_GLOW);
 664                 }
 665         }
 666
 667         /* Place a full floor for room "b" */
 668         for (y = y1b - 1; y <= y2b + 1; y++)
 669         {
 670                 for (x = x1b - 1; x <= x2b + 1; x++)
 671                 {
 672                         c_ptr = &cave[y][x];
 673                         place_floor_grid(c_ptr);
 674                         c_ptr->info |= (CAVE_ROOM);
 675                         if (light) c_ptr->info |= (CAVE_GLOW);
 676                 }
 677         }
 678
 679
 680         /* Place the walls around room "a" */
 681         for (y = y1a - 1; y <= y2a + 1; y++)
 682         {
 683                 c_ptr = &cave[y][x1a - 1];
 684                 place_outer_grid(c_ptr);
 685                 c_ptr = &cave[y][x2a + 1];
 686                 place_outer_grid(c_ptr);
 687         }
 688         for (x = x1a - 1; x <= x2a + 1; x++)
 689         {
 690                 c_ptr = &cave[y1a - 1][x];
 691                 place_outer_grid(c_ptr);
 692                 c_ptr = &cave[y2a + 1][x];
 693                 place_outer_grid(c_ptr);
 694         }
 695
 696         /* Place the walls around room "b" */
 697         for (y = y1b - 1; y <= y2b + 1; y++)
 698         {
 699                 c_ptr = &cave[y][x1b - 1];
 700                 place_outer_grid(c_ptr);
 701                 c_ptr = &cave[y][x2b + 1];
 702                 place_outer_grid(c_ptr);
 703         }
 704         for (x = x1b - 1; x <= x2b + 1; x++)
 705         {
 706                 c_ptr = &cave[y1b - 1][x];
 707                 place_outer_grid(c_ptr);
 708                 c_ptr = &cave[y2b + 1][x];
 709                 place_outer_grid(c_ptr);
 710         }
 711
 712
 713
 714         /* Replace the floor for room "a" */
 715         for (y = y1a; y <= y2a; y++)
 716         {
 717                 for (x = x1a; x <= x2a; x++)
 718                 {
 719                         c_ptr = &cave[y][x];
 720                         place_floor_grid(c_ptr);
 721                 }
 722         }
 723
 724         /* Replace the floor for room "b" */
 725         for (y = y1b; y <= y2b; y++)
 726         {
 727                 for (x = x1b; x <= x2b; x++)
 728                 {
 729                         c_ptr = &cave[y][x];
 730                         place_floor_grid(c_ptr);
 731                 }
 732         }
 733
 734         return TRUE;
 735 }
 736
 737
 738
 739 /*
 740  * Type 3 -- Cross shaped rooms
 741  *
 742  * Builds a room at a row, column coordinate
 743  *
 744  * Room "a" runs north/south, and Room "b" runs east/east
 745  * So the "central pillar" runs from x1a, y1b to x2a, y2b.
 746  *
 747  * Note that currently, the "center" is always 3x3, but I think that
 748  * the code below will work (with "bounds checking") for 5x5, or even
 749  * for unsymetric values like 4x3 or 5x3 or 3x4 or 3x5, or even larger.
 750  */
 751 static bool build_type3(void)
 752 {
 753         int                     y, x, dy, dx, wy, wx;
 754         int                     y1a, x1a, y2a, x2a;
 755         int                     y1b, x1b, y2b, x2b;
 756         int                     yval, xval;
 757         bool            light;
 758         cave_type   *c_ptr;
 759
 760
 761         /* Find and reserve some space in the dungeon.  Get center of room. */
 762         if (!find_space(&yval, &xval, 11, 25)) return FALSE;
 763
 764
 765         /* Choose lite or dark */
 766         light = ((dun_level <= randint1(25)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS));
 767
 768         /* For now, always 3x3 */
 769         wx = wy = 1;
 770
 771         /* Pick max vertical size (at most 4) */
 772         dy = rand_range(3, 4);
 773
 774         /* Pick max horizontal size (at most 15) */
 775         dx = rand_range(3, 11);
 776
 777
 778         /* Determine extents of the north/south room */
 779         y1a = yval - dy;
 780         y2a = yval + dy;
 781         x1a = xval - wx;
 782         x2a = xval + wx;
 783
 784         /* Determine extents of the east/west room */
 785         y1b = yval - wy;
 786         y2b = yval + wy;
 787         x1b = xval - dx;
 788         x2b = xval + dx;
 789
 790
 791         /* Place a full floor for room "a" */
 792         for (y = y1a - 1; y <= y2a + 1; y++)
 793         {
 794                 for (x = x1a - 1; x <= x2a + 1; x++)
 795                 {
 796                         c_ptr = &cave[y][x];
 797                         place_floor_grid(c_ptr);
 798                         c_ptr->info |= (CAVE_ROOM);
 799                         if (light) c_ptr->info |= (CAVE_GLOW);
 800                 }
 801         }
 802
 803         /* Place a full floor for room "b" */
 804         for (y = y1b - 1; y <= y2b + 1; y++)
 805         {
 806                 for (x = x1b - 1; x <= x2b + 1; x++)
 807                 {
 808                         c_ptr = &cave[y][x];
 809                         place_floor_grid(c_ptr);
 810                         c_ptr->info |= (CAVE_ROOM);
 811                         if (light) c_ptr->info |= (CAVE_GLOW);
 812                 }
 813         }
 814
 815
 816         /* Place the walls around room "a" */
 817         for (y = y1a - 1; y <= y2a + 1; y++)
 818         {
 819                 c_ptr = &cave[y][x1a - 1];
 820                 place_outer_grid(c_ptr);
 821                 c_ptr = &cave[y][x2a + 1];
 822                 place_outer_grid(c_ptr);
 823         }
 824         for (x = x1a - 1; x <= x2a + 1; x++)
 825         {
 826                 c_ptr = &cave[y1a - 1][x];
 827                 place_outer_grid(c_ptr);
 828                 c_ptr = &cave[y2a + 1][x];
 829                 place_outer_grid(c_ptr);
 830         }
 831
 832         /* Place the walls around room "b" */
 833         for (y = y1b - 1; y <= y2b + 1; y++)
 834         {
 835                 c_ptr = &cave[y][x1b - 1];
 836                 place_outer_grid(c_ptr);
 837                 c_ptr = &cave[y][x2b + 1];
 838                 place_outer_grid(c_ptr);
 839         }
 840         for (x = x1b - 1; x <= x2b + 1; x++)
 841         {
 842                 c_ptr = &cave[y1b - 1][x];
 843                 place_outer_grid(c_ptr);
 844                 c_ptr = &cave[y2b + 1][x];
 845                 place_outer_grid(c_ptr);
 846         }
 847
 848
 849         /* Replace the floor for room "a" */
 850         for (y = y1a; y <= y2a; y++)
 851         {
 852                 for (x = x1a; x <= x2a; x++)
 853                 {
 854                         c_ptr = &cave[y][x];
 855                         place_floor_grid(c_ptr);
 856                 }
 857         }
 858
 859         /* Replace the floor for room "b" */
 860         for (y = y1b; y <= y2b; y++)
 861         {
 862                 for (x = x1b; x <= x2b; x++)
 863                 {
 864                         c_ptr = &cave[y][x];
 865                         place_floor_grid(c_ptr);
 866                 }
 867         }
 868
 869
 870
 871         /* Special features (3/4) */
 872         switch (randint0(4))
 873         {
 874                 /* Large solid middle pillar */
 875                 case 1:
 876                 {
 877                         for (y = y1b; y <= y2b; y++)
 878                         {
 879                                 for (x = x1a; x <= x2a; x++)
 880                                 {
 881                                         c_ptr = &cave[y][x];
 882                                         place_inner_grid(c_ptr);
 883                                 }
 884                         }
 885                         break;
 886                 }
 887
 888                 /* Inner treasure vault */
 889                 case 2:
 890                 {
 891                         /* Build the vault */
 892                         for (y = y1b; y <= y2b; y++)
 893                         {
 894                                 c_ptr = &cave[y][x1a];
 895                                 place_inner_grid(c_ptr);
 896                                 c_ptr = &cave[y][x2a];
 897                                 place_inner_grid(c_ptr);
 898                         }
 899                         for (x = x1a; x <= x2a; x++)
 900                         {
 901                                 c_ptr = &cave[y1b][x];
 902                                 place_inner_grid(c_ptr);
 903                                 c_ptr = &cave[y2b][x];
 904                                 place_inner_grid(c_ptr);
 905                         }
 906
 907                         /* Place a secret door on the inner room */
 908                         switch (randint0(4))
 909                         {
 910                                 case 0: place_secret_door(y1b, xval); break;
 911                                 case 1: place_secret_door(y2b, xval); break;
 912                                 case 2: place_secret_door(yval, x1a); break;
 913                                 case 3: place_secret_door(yval, x2a); break;
 914                         }
 915
 916                         /* Place a treasure in the vault */
 917                         place_object(yval, xval, 0L);
 918
 919                         /* Let's guard the treasure well */
 920                         vault_monsters(yval, xval, randint0(2) + 3);
 921
 922                         /* Traps naturally */
 923                         vault_traps(yval, xval, 4, 4, randint0(3) + 2);
 924
 925                         break;
 926                 }
 927
 928                 /* Something else */
 929                 case 3:
 930                 {
 931                         /* Occasionally pinch the center shut */
 932                         if (one_in_(3))
 933                         {
 934                                 /* Pinch the east/west sides */
 935                                 for (y = y1b; y <= y2b; y++)
 936                                 {
 937                                         if (y == yval) continue;
 938                                         c_ptr = &cave[y][x1a - 1];
 939                                         place_inner_grid(c_ptr);
 940                                         c_ptr = &cave[y][x2a + 1];
 941                                         place_inner_grid(c_ptr);
 942                                 }
 943
 944                                 /* Pinch the north/south sides */
 945                                 for (x = x1a; x <= x2a; x++)
 946                                 {
 947                                         if (x == xval) continue;
 948                                         c_ptr = &cave[y1b - 1][x];
 949                                         place_inner_grid(c_ptr);
 950                                         c_ptr = &cave[y2b + 1][x];
 951                                         place_inner_grid(c_ptr);
 952                                 }
 953
 954                                 /* Sometimes shut using secret doors */
 955                                 if (one_in_(3))
 956                                 {
 957                                         place_secret_door(yval, x1a - 1);
 958                                         place_secret_door(yval, x2a + 1);
 959                                         place_secret_door(y1b - 1, xval);
 960                                         place_secret_door(y2b + 1, xval);
 961                                 }
 962                         }
 963
 964                         /* Occasionally put a "plus" in the center */
 965                         else if (one_in_(3))
 966                         {
 967                                 c_ptr = &cave[yval][xval];
 968                                 place_inner_grid(c_ptr);
 969                                 c_ptr = &cave[y1b][xval];
 970                                 place_inner_grid(c_ptr);
 971                                 c_ptr = &cave[y2b][xval];
 972                                 place_inner_grid(c_ptr);
 973                                 c_ptr = &cave[yval][x1a];
 974                                 place_inner_grid(c_ptr);
 975                                 c_ptr = &cave[yval][x2a];
 976                                 place_inner_grid(c_ptr);
 977                         }
 978
 979                         /* Occasionally put a pillar in the center */
 980                         else if (one_in_(3))
 981                         {
 982                                 c_ptr = &cave[yval][xval];
 983                                 place_inner_grid(c_ptr);
 984                         }
 985
 986                         break;
 987                 }
 988         }
 989
 990         return TRUE;
 991 }
 992
 993
 994 /*
 995  * Type 4 -- Large room with inner features
 996  *
 997  * Possible sub-types:
 998  *      1 - Just an inner room with one door
 999  *      2 - An inner room within an inner room
1000  *      3 - An inner room with pillar(s)
1001  *      4 - Inner room has a maze
1002  *      5 - A set of four inner rooms
1003  */
1004 static bool build_type4(void)
1005 {
1006         int         y, x, y1, x1;
1007         int         y2, x2, tmp, yval, xval;
1008         bool        light;
1009         cave_type   *c_ptr;
1010
1011
1012         /* Find and reserve some space in the dungeon.  Get center of room. */
1013         if (!find_space(&yval, &xval, 11, 25)) return FALSE;
1014
1015         /* Choose lite or dark */
1016         light = ((dun_level <= randint1(25)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS));
1017
1018         /* Large room */
1019         y1 = yval - 4;
1020         y2 = yval + 4;
1021         x1 = xval - 11;
1022         x2 = xval + 11;
1023
1024         /* Place a full floor under the room */
1025         for (y = y1 - 1; y <= y2 + 1; y++)
1026         {
1027                 for (x = x1 - 1; x <= x2 + 1; x++)
1028                 {
1029                         c_ptr = &cave[y][x];
1030                         place_floor_grid(c_ptr);
1031                         c_ptr->info |= (CAVE_ROOM);
1032                         if (light) c_ptr->info |= (CAVE_GLOW);
1033                 }
1034         }
1035
1036         /* Outer Walls */
1037         for (y = y1 - 1; y <= y2 + 1; y++)
1038         {
1039                 c_ptr = &cave[y][x1 - 1];
1040                 place_outer_grid(c_ptr);
1041                 c_ptr = &cave[y][x2 + 1];
1042                 place_outer_grid(c_ptr);
1043         }
1044         for (x = x1 - 1; x <= x2 + 1; x++)
1045         {
1046                 c_ptr = &cave[y1 - 1][x];
1047                 place_outer_grid(c_ptr);
1048                 c_ptr = &cave[y2 + 1][x];
1049                 place_outer_grid(c_ptr);
1050         }
1051
1052
1053         /* The inner room */
1054         y1 = y1 + 2;
1055         y2 = y2 - 2;
1056         x1 = x1 + 2;
1057         x2 = x2 - 2;
1058
1059         /* The inner walls */
1060         for (y = y1 - 1; y <= y2 + 1; y++)
1061         {
1062                 c_ptr = &cave[y][x1 - 1];
1063                 place_inner_grid(c_ptr);
1064                 c_ptr = &cave[y][x2 + 1];
1065                 place_inner_grid(c_ptr);
1066         }
1067         for (x = x1 - 1; x <= x2 + 1; x++)
1068         {
1069                 c_ptr = &cave[y1 - 1][x];
1070                 place_inner_grid(c_ptr);
1071                 c_ptr = &cave[y2 + 1][x];
1072                 place_inner_grid(c_ptr);
1073         }
1074
1075
1076         /* Inner room variations */
1077         switch (randint1(5))
1078         {
1079                 /* Just an inner room with a monster */
1080                 case 1:
1081                 {
1082                         /* Place a secret door */
1083                         switch (randint1(4))
1084                         {
1085                                 case 1: place_secret_door(y1 - 1, xval); break;
1086                                 case 2: place_secret_door(y2 + 1, xval); break;
1087                                 case 3: place_secret_door(yval, x1 - 1); break;
1088                                 case 4: place_secret_door(yval, x2 + 1); break;
1089                         }
1090
1091                         /* Place a monster in the room */
1092                         vault_monsters(yval, xval, 1);
1093
1094                         break;
1095                 }
1096
1097                 /* Treasure Vault (with a door) */
1098                 case 2:
1099                 {
1100                         /* Place a secret door */
1101                         switch (randint1(4))
1102                         {
1103                                 case 1: place_secret_door(y1 - 1, xval); break;
1104                                 case 2: place_secret_door(y2 + 1, xval); break;
1105                                 case 3: place_secret_door(yval, x1 - 1); break;
1106                                 case 4: place_secret_door(yval, x2 + 1); break;
1107                         }
1108
1109                         /* Place another inner room */
1110                         for (y = yval - 1; y <= yval + 1; y++)
1111                         {
1112                                 for (x = xval -  1; x <= xval + 1; x++)
1113                                 {
1114                                         if ((x == xval) && (y == yval)) continue;
1115                                         c_ptr = &cave[y][x];
1116                                         place_inner_grid(c_ptr);
1117                                 }
1118                         }
1119
1120                         /* Place a locked door on the inner room */
1121                         switch (randint1(4))
1122                         {
1123                                 case 1: place_locked_door(yval - 1, xval); break;
1124                                 case 2: place_locked_door(yval + 1, xval); break;
1125                                 case 3: place_locked_door(yval, xval - 1); break;
1126                                 case 4: place_locked_door(yval, xval + 1); break;
1127                         }
1128
1129                         /* Monsters to guard the "treasure" */
1130                         vault_monsters(yval, xval, randint1(3) + 2);
1131
1132                         /* Object (80%) */
1133                         if (randint0(100) < 80)
1134                         {
1135                                 place_object(yval, xval, 0L);
1136                         }
1137
1138                         /* Stairs (20%) */
1139                         else
1140                         {
1141                                 place_random_stairs(yval, xval);
1142                         }
1143
1144                         /* Traps to protect the treasure */
1145                         vault_traps(yval, xval, 4, 10, 2 + randint1(3));
1146
1147                         break;
1148                 }
1149
1150                 /* Inner pillar(s). */
1151                 case 3:
1152                 {
1153                         /* Place a secret door */
1154                         switch (randint1(4))
1155                         {
1156                                 case 1: place_secret_door(y1 - 1, xval); break;
1157                                 case 2: place_secret_door(y2 + 1, xval); break;
1158                                 case 3: place_secret_door(yval, x1 - 1); break;
1159                                 case 4: place_secret_door(yval, x2 + 1); break;
1160                         }
1161
1162                         /* Large Inner Pillar */
1163                         for (y = yval - 1; y <= yval + 1; y++)
1164                         {
1165                                 for (x = xval - 1; x <= xval + 1; x++)
1166                                 {
1167                                 c_ptr = &cave[y][x];
1168                                 place_inner_grid(c_ptr);
1169                                 }
1170                         }
1171
1172                         /* Occasionally, two more Large Inner Pillars */
1173                         if (one_in_(2))
1174                         {
1175                                 tmp = randint1(2);
1176                                 for (y = yval - 1; y <= yval + 1; y++)
1177                                 {
1178                                         for (x = xval - 5 - tmp; x <= xval - 3 - tmp; x++)
1179                                         {
1180                                         c_ptr = &cave[y][x];
1181                                         place_inner_grid(c_ptr);
1182                                         }
1183                                         for (x = xval + 3 + tmp; x <= xval + 5 + tmp; x++)
1184                                         {
1185                                         c_ptr = &cave[y][x];
1186                                         place_inner_grid(c_ptr);
1187                                         }
1188                                 }
1189                         }
1190
1191                         /* Occasionally, some Inner rooms */
1192                         if (one_in_(3))
1193                         {
1194                                 /* Long horizontal walls */
1195                                 for (x = xval - 5; x <= xval + 5; x++)
1196                                 {
1197                                 c_ptr = &cave[yval - 1][x];
1198                                 place_inner_grid(c_ptr);
1199                                 c_ptr = &cave[yval + 1][x];
1200                                 place_inner_grid(c_ptr);
1201                                 }
1202
1203                                 /* Close off the left/right edges */
1204                                 c_ptr = &cave[yval][xval - 5];
1205                                 place_inner_grid(c_ptr);
1206                                 c_ptr = &cave[yval][xval + 5];
1207                                 place_inner_grid(c_ptr);
1208
1209                                 /* Secret doors (random top/bottom) */
1210                                 place_secret_door(yval - 3 + (randint1(2) * 2), xval - 3);
1211                                 place_secret_door(yval - 3 + (randint1(2) * 2), xval + 3);
1212
1213                                 /* Monsters */
1214                                 vault_monsters(yval, xval - 2, randint1(2));
1215                                 vault_monsters(yval, xval + 2, randint1(2));
1216
1217                                 /* Objects */
1218                                 if (one_in_(3)) place_object(yval, xval - 2, 0L);
1219                                 if (one_in_(3)) place_object(yval, xval + 2, 0L);
1220                         }
1221
1222                         break;
1223                 }
1224
1225                 /* Maze inside. */
1226                 case 4:
1227                 {
1228                         /* Place a secret door */
1229                         switch (randint1(4))
1230                         {
1231                                 case 1: place_secret_door(y1 - 1, xval); break;
1232                                 case 2: place_secret_door(y2 + 1, xval); break;
1233                                 case 3: place_secret_door(yval, x1 - 1); break;
1234                                 case 4: place_secret_door(yval, x2 + 1); break;
1235                         }
1236
1237                         /* Maze (really a checkerboard) */
1238                         for (y = y1; y <= y2; y++)
1239                         {
1240                                 for (x = x1; x <= x2; x++)
1241                                 {
1242                                         if (0x1 & (x + y))
1243                                         {
1244                                                 c_ptr = &cave[y][x];
1245                                                 place_inner_grid(c_ptr);
1246                                         }
1247                                 }
1248                         }
1249
1250                         /* Monsters just love mazes. */
1251                         vault_monsters(yval, xval - 5, randint1(3));
1252                         vault_monsters(yval, xval + 5, randint1(3));
1253
1254                         /* Traps make them entertaining. */
1255                         vault_traps(yval, xval - 3, 2, 8, randint1(3));
1256                         vault_traps(yval, xval + 3, 2, 8, randint1(3));
1257
1258                         /* Mazes should have some treasure too. */
1259                         vault_objects(yval, xval, 3);
1260
1261                         break;
1262                 }
1263
1264                 /* Four small rooms. */
1265                 case 5:
1266                 {
1267                         /* Inner "cross" */
1268                         for (y = y1; y <= y2; y++)
1269                         {
1270                                 c_ptr = &cave[y][xval];
1271                                 place_inner_grid(c_ptr);
1272                         }
1273                         for (x = x1; x <= x2; x++)
1274                         {
1275                                 c_ptr = &cave[yval][x];
1276                                 place_inner_grid(c_ptr);
1277                         }
1278
1279                         /* Doors into the rooms */
1280                         if (randint0(100) < 50)
1281                         {
1282                                 int i = randint1(10);
1283                                 place_secret_door(y1 - 1, xval - i);
1284                                 place_secret_door(y1 - 1, xval + i);
1285                                 place_secret_door(y2 + 1, xval - i);
1286                                 place_secret_door(y2 + 1, xval + i);
1287                         }
1288                         else
1289                         {
1290                                 int i = randint1(3);
1291                                 place_secret_door(yval + i, x1 - 1);
1292                                 place_secret_door(yval - i, x1 - 1);
1293                                 place_secret_door(yval + i, x2 + 1);
1294                                 place_secret_door(yval - i, x2 + 1);
1295                         }
1296
1297                         /* Treasure, centered at the center of the cross */
1298                         vault_objects(yval, xval, 2 + randint1(2));
1299
1300                         /* Gotta have some monsters. */
1301                         vault_monsters(yval + 1, xval - 4, randint1(4));
1302                         vault_monsters(yval + 1, xval + 4, randint1(4));
1303                         vault_monsters(yval - 1, xval - 4, randint1(4));
1304                         vault_monsters(yval - 1, xval + 4, randint1(4));
1305
1306                         break;
1307                 }
1308         }
1309
1310         return TRUE;
1311 }
1312
1313
1314 /*
1315  * The following functions are used to determine if the given monster
1316  * is appropriate for inclusion in a monster nest or monster pit or
1317  * the given type.
1318  *
1319  * None of the pits/nests are allowed to include "unique" monsters.
1320  */
1321
1322
1323 /*
1324  * Monster validation macro
1325  *
1326  * Line 1 -- forbid town monsters
1327  * Line 2 -- forbid uniques
1328  * Line 3 -- forbid aquatic monsters
1329  */
1330 #define vault_monster_okay(I) \
1331         (mon_hook_dungeon(I) && \
1332          !(r_info[I].flags1 & RF1_UNIQUE) && \
1333          !(r_info[I].flags7 & RF7_UNIQUE2) && \
1334          !(r_info[I].flagsr & RFR_RES_ALL) && \
1335          !(r_info[I].flags7 & RF7_AQUATIC))
1336
1337
1338 /* Race index for "monster pit (clone)" */
1339 static int vault_aux_race;
1340
1341 /* Race index for "monster pit (symbol clone)" */
1342 static char vault_aux_char;
1343
1344 /* Breath mask for "monster pit (dragon)" */
1345 static u32b vault_aux_dragon_mask4;
1346
1347
1348 /*
1349  * Helper monster selection function
1350  */
1351 static bool vault_aux_simple(int r_idx)
1352 {
1353         /* Okay */
1354         return (vault_monster_okay(r_idx));
1355 }
1356
1357
1358 /*
1359  * Helper function for "monster nest (jelly)"
1360  */
1361 static bool vault_aux_jelly(int r_idx)
1362 {
1363         monster_race *r_ptr = &r_info[r_idx];
1364
1365         /* Validate the monster */
1366         if (!vault_monster_okay(r_idx)) return (FALSE);
1367
1368         if ((r_ptr->flags2 & RF2_KILL_BODY) && !(r_ptr->flags1 & RF1_NEVER_BLOW)) return (FALSE);
1369
1370         /* Also decline evil jellies (like death molds and shoggoths) */
1371         if (r_ptr->flags3 & (RF3_EVIL)) return (FALSE);
1372
1373         /* Require icky thing, jelly, mold, or mushroom */
1374         if (!strchr("ijm,", r_ptr->d_char)) return (FALSE);
1375
1376         /* Okay */
1377         return (TRUE);
1378 }
1379
1380
1381 /*
1382  * Helper function for "monster nest (animal)"
1383  */
1384 static bool vault_aux_animal(int r_idx)
1385 {
1386         monster_race *r_ptr = &r_info[r_idx];
1387
1388         /* Validate the monster */
1389         if (!vault_monster_okay(r_idx)) return (FALSE);
1390
1391         /* Require "animal" flag */
1392         if (!(r_ptr->flags3 & (RF3_ANIMAL))) return (FALSE);
1393
1394         /* Okay */
1395         return (TRUE);
1396 }
1397
1398
1399 /*
1400  * Helper function for "monster nest (undead)"
1401  */
1402 static bool vault_aux_undead(int r_idx)
1403 {
1404         monster_race *r_ptr = &r_info[r_idx];
1405
1406         /* Validate the monster */
1407         if (!vault_monster_okay(r_idx)) return (FALSE);
1408
1409         /* Require Undead */
1410         if (!(r_ptr->flags3 & (RF3_UNDEAD))) return (FALSE);
1411
1412         /* Okay */
1413         return (TRUE);
1414 }
1415
1416
1417 /*
1418  * Helper function for "monster nest (chapel)"
1419  */
1420 static bool vault_aux_chapel_g(int r_idx)
1421 {
1422         static int chapel_list[] = {
1423                 MON_NOV_PRIEST, MON_NOV_PALADIN, MON_NOV_PRIEST_G, MON_NOV_PALADIN_G,
1424                 MON_PRIEST, MON_JADE_MONK, MON_IVORY_MONK, MON_ULTRA_PALADIN,
1425                 MON_EBONY_MONK, MON_W_KNIGHT, MON_KNI_TEMPLAR, MON_PALADIN,
1426                 MON_TOPAZ_MONK, 0};
1427
1428         int i;
1429
1430         monster_race *r_ptr = &r_info[r_idx];
1431
1432         /* Validate the monster */
1433         if (!vault_monster_okay(r_idx)) return (FALSE);
1434
1435         if (r_ptr->flags3 & (RF3_EVIL)) return (FALSE);
1436         if ((r_idx == MON_A_GOLD) || (r_idx == MON_A_SILVER)) return (FALSE);
1437
1438         /* Require "priest" or Angel */
1439
1440         if (r_ptr->d_char == 'A') return TRUE;
1441
1442         for (i = 0; chapel_list[i]; i++)
1443                 if (r_idx == chapel_list[i]) return TRUE;
1444
1445         return FALSE;
1446 }
1447
1448
1449 /*
1450  * Helper function for "monster nest (kennel)"
1451  */
1452 static bool vault_aux_kennel(int r_idx)
1453 {
1454         monster_race *r_ptr = &r_info[r_idx];
1455
1456         /* Validate the monster */
1457         if (!vault_monster_okay(r_idx)) return (FALSE);
1458
1459         /* Require a Zephyr Hound or a dog */
1460         if (!strchr("CZ", r_ptr->d_char)) return (FALSE);
1461
1462         /* Okay */
1463         return (TRUE);
1464 }
1465
1466
1467 /*
1468  * Helper function for "monster nest (mimic)"
1469  */
1470 static bool vault_aux_mimic(int r_idx)
1471 {
1472         monster_race *r_ptr = &r_info[r_idx];
1473
1474         /* Validate the monster */
1475         if (!vault_monster_okay(r_idx)) return (FALSE);
1476
1477         /* Require mimic */
1478         if (!strchr("!|$?=", r_ptr->d_char)) return (FALSE);
1479
1480         /* Okay */
1481         return (TRUE);
1482 }
1483
1484 /*
1485  * Helper function for "monster nest (clone)"
1486  */
1487 static bool vault_aux_clone(int r_idx)
1488 {
1489         /* Validate the monster */
1490         if (!vault_monster_okay(r_idx)) return (FALSE);
1491
1492         return (r_idx == vault_aux_race);
1493 }
1494
1495
1496 /*
1497  * Helper function for "monster nest (symbol clone)"
1498  */
1499 static bool vault_aux_symbol_e(int r_idx)
1500 {
1501         monster_race *r_ptr = &r_info[r_idx];
1502
1503         /* Validate the monster */
1504         if (!vault_monster_okay(r_idx)) return (FALSE);
1505
1506         if ((r_ptr->flags2 & RF2_KILL_BODY) && !(r_ptr->flags1 & RF1_NEVER_BLOW)) return (FALSE);
1507
1508         if (r_ptr->flags3 & (RF3_GOOD)) return (FALSE);
1509
1510         /* Decline incorrect symbol */
1511         if (r_ptr->d_char != vault_aux_char) return (FALSE);
1512
1513         /* Okay */
1514         return (TRUE);
1515 }
1516
1517
1518 /*
1519  * Helper function for "monster nest (symbol clone)"
1520  */
1521 static bool vault_aux_symbol_g(int r_idx)
1522 {
1523         monster_race *r_ptr = &r_info[r_idx];
1524
1525         /* Validate the monster */
1526         if (!vault_monster_okay(r_idx)) return (FALSE);
1527
1528         if ((r_ptr->flags2 & RF2_KILL_BODY) && !(r_ptr->flags1 & RF1_NEVER_BLOW)) return (FALSE);
1529
1530         if (r_ptr->flags3 & (RF3_EVIL)) return (FALSE);
1531
1532         /* Decline incorrect symbol */
1533         if (r_ptr->d_char != vault_aux_char) return (FALSE);
1534
1535         /* Okay */
1536         return (TRUE);
1537 }
1538
1539
1540 /*
1541  * Helper function for "monster pit (orc)"
1542  */
1543 static bool vault_aux_orc(int r_idx)
1544 {
1545         monster_race *r_ptr = &r_info[r_idx];
1546
1547         /* Validate the monster */
1548         if (!vault_monster_okay(r_idx)) return (FALSE);
1549
1550         /* Require orc */
1551         if (!(r_ptr->flags3 & RF3_ORC)) return (FALSE);
1552
1553         /* Decline undead */
1554         if (r_ptr->flags3 & RF3_UNDEAD) return (FALSE);
1555
1556         /* Okay */
1557         return (TRUE);
1558 }
1559
1560
1561 /*
1562  * Helper function for "monster pit (troll)"
1563  */
1564 static bool vault_aux_troll(int r_idx)
1565 {
1566         monster_race *r_ptr = &r_info[r_idx];
1567
1568         /* Validate the monster */
1569         if (!vault_monster_okay(r_idx)) return (FALSE);
1570
1571         /* Require troll */
1572         if (!(r_ptr->flags3 & RF3_TROLL)) return (FALSE);
1573
1574         /* Decline undead */
1575         if (r_ptr->flags3 & RF3_UNDEAD) return (FALSE);
1576
1577         /* Okay */
1578         return (TRUE);
1579 }
1580
1581
1582 /*
1583  * Helper function for "monster pit (giant)"
1584  */
1585 static bool vault_aux_giant(int r_idx)
1586 {
1587         monster_race *r_ptr = &r_info[r_idx];
1588
1589         /* Validate the monster */
1590         if (!vault_monster_okay(r_idx)) return (FALSE);
1591
1592         /* Require giant */
1593         if (!(r_ptr->flags3 & RF3_GIANT)) return (FALSE);
1594
1595         if (r_ptr->flags3 & RF3_GOOD) return (FALSE);
1596
1597         /* Decline undead */
1598         if (r_ptr->flags3 & RF3_UNDEAD) return (FALSE);
1599
1600         /* Okay */
1601         return (TRUE);
1602 }
1603
1604
1605 /*
1606  * Helper function for "monster pit (dragon)"
1607  */
1608 static bool vault_aux_dragon(int r_idx)
1609 {
1610         monster_race *r_ptr = &r_info[r_idx];
1611
1612         /* Validate the monster */
1613         if (!vault_monster_okay(r_idx)) return (FALSE);
1614
1615         /* Require dragon */
1616         if (!(r_ptr->flags3 & RF3_DRAGON)) return (FALSE);
1617
1618         /* Hack -- Require correct "breath attack" */
1619         if (r_ptr->flags4 != vault_aux_dragon_mask4) return (FALSE);
1620
1621         /* Decline undead */
1622         if (r_ptr->flags3 & RF3_UNDEAD) return (FALSE);
1623
1624         /* Okay */
1625         return (TRUE);
1626 }
1627
1628
1629 /*
1630  * Helper function for "monster pit (demon)"
1631  */
1632 static bool vault_aux_demon(int r_idx)
1633 {
1634         monster_race *r_ptr = &r_info[r_idx];
1635
1636         /* Validate the monster */
1637         if (!vault_monster_okay(r_idx)) return (FALSE);
1638
1639         if ((r_ptr->flags2 & RF2_KILL_BODY) && !(r_ptr->flags1 & RF1_NEVER_BLOW)) return (FALSE);
1640
1641         /* Require demon */
1642         if (!(r_ptr->flags3 & RF3_DEMON)) return (FALSE);
1643
1644         /* Okay */
1645         return (TRUE);
1646 }
1647
1648
1649 /*
1650  * Helper function for "monster pit (lovecraftian)"
1651  */
1652 static bool vault_aux_cthulhu(int r_idx)
1653 {
1654         monster_race *r_ptr = &r_info[r_idx];
1655
1656         /* Validate the monster */
1657         if (!vault_monster_okay(r_idx)) return (FALSE);
1658
1659         if ((r_ptr->flags2 & RF2_KILL_BODY) && !(r_ptr->flags1 & RF1_NEVER_BLOW)) return (FALSE);
1660
1661         /* Require eldritch horror */
1662         if (!(r_ptr->flags2 & (RF2_ELDRITCH_HORROR))) return (FALSE);
1663
1664         /* Okay */
1665         return (TRUE);
1666 }
1667
1668
1669 /*
1670  * Helper function for "monster pit (clone)"
1671  */
1672 static void vault_prep_clone(void)
1673 {
1674         /* Apply the monster restriction */
1675         get_mon_num_prep(vault_aux_simple, NULL);
1676
1677         /* Pick a race to clone */
1678         vault_aux_race = get_mon_num(dun_level + 10);
1679
1680         /* Remove the monster restriction */
1681         get_mon_num_prep(NULL, NULL);
1682 }
1683
1684
1685 /*
1686  * Helper function for "monster pit (symbol clone)"
1687  */
1688 static void vault_prep_symbol(void)
1689 {
1690         int r_idx;
1691
1692         /* Apply the monster restriction */
1693         get_mon_num_prep(vault_aux_simple, NULL);
1694
1695         /* Pick a race to clone */
1696         r_idx = get_mon_num(dun_level + 10);
1697
1698         /* Remove the monster restriction */
1699         get_mon_num_prep(NULL, NULL);
1700
1701         /* Extract the symbol */
1702         vault_aux_char = r_info[r_idx].d_char;
1703 }
1704
1705
1706 /*
1707  * Helper function for "monster pit (dragon)"
1708  */
1709 static void vault_prep_dragon(void)
1710 {
1711         /* Pick dragon type */
1712         switch (randint0(6))
1713         {
1714                 /* Black */
1715                 case 0:
1716                 {
1717                         /* Restrict dragon breath type */
1718                         vault_aux_dragon_mask4 = RF4_BR_ACID;
1719
1720                         /* Done */
1721                         break;
1722                 }
1723
1724                 /* Blue */
1725                 case 1:
1726                 {
1727                         /* Restrict dragon breath type */
1728                         vault_aux_dragon_mask4 = RF4_BR_ELEC;
1729
1730                         /* Done */
1731                         break;
1732                 }
1733
1734                 /* Red */
1735                 case 2:
1736                 {
1737                         /* Restrict dragon breath type */
1738                         vault_aux_dragon_mask4 = RF4_BR_FIRE;
1739
1740                         /* Done */
1741                         break;
1742                 }
1743
1744                 /* White */
1745                 case 3:
1746                 {
1747                         /* Restrict dragon breath type */
1748                         vault_aux_dragon_mask4 = RF4_BR_COLD;
1749
1750                         /* Done */
1751                         break;
1752                 }
1753
1754                 /* Green */
1755                 case 4:
1756                 {
1757                         /* Restrict dragon breath type */
1758                         vault_aux_dragon_mask4 = RF4_BR_POIS;
1759
1760                         /* Done */
1761                         break;
1762                 }
1763
1764                 /* Multi-hued */
1765                 default:
1766                 {
1767                         /* Restrict dragon breath type */
1768                         vault_aux_dragon_mask4 = (RF4_BR_ACID | RF4_BR_ELEC |
1769                                                                                           RF4_BR_FIRE | RF4_BR_COLD |
1770                                                                                           RF4_BR_POIS);
1771
1772                         /* Done */
1773                         break;
1774                 }
1775         }
1776 }
1777
1778
1779 /*
1780  * Helper function for "monster pit (dark elf)"
1781  */
1782 static bool vault_aux_dark_elf(int r_idx)
1783 {
1784         int i;
1785         static int dark_elf_list[] =
1786         {
1787                 MON_D_ELF, MON_D_ELF_MAGE, MON_D_ELF_WARRIOR, MON_D_ELF_PRIEST,
1788                 MON_D_ELF_LORD, MON_D_ELF_WARLOCK, MON_D_ELF_DRUID, MON_NIGHTBLADE,
1789                 MON_D_ELF_SORC, MON_D_ELF_SHADE, 0,
1790         };
1791
1792         /* Validate the monster */
1793         if (!vault_monster_okay(r_idx)) return FALSE;
1794
1795         /* Require dark elves */
1796         for (i = 0; dark_elf_list[i]; i++)
1797                 if (r_idx == dark_elf_list[i]) return TRUE;
1798
1799         /* Assume not */
1800         return FALSE;
1801 }
1802
1803
1804 typedef struct vault_aux_type vault_aux_type;
1805
1806
1807 struct vault_aux_type
1808 {
1809         cptr name;
1810         bool (*hook_func)(int r_idx);
1811         void (*prep_func)(void);
1812         int level;
1813         int chance;
1814 };
1815
1816
1817 static int pick_vault_type(vault_aux_type *l_ptr, s16b allow_flag_mask)
1818 {
1819         int tmp, total, count;
1820
1821         vault_aux_type *n_ptr;
1822
1823         /* Calculate the total possibilities */
1824         for (n_ptr = l_ptr, total = 0, count = 0; TRUE; n_ptr++, count++)
1825         {
1826                 /* Note end */
1827                 if (!n_ptr->name) break;
1828
1829                 /* Ignore excessive depth */
1830                 if (n_ptr->level > dun_level) continue;
1831
1832                 /* Not matched with pit/nest flag */
1833                 if (!(allow_flag_mask & (1L << count))) continue;
1834
1835                 /* Count this possibility */
1836                 total += n_ptr->chance * MAX_DEPTH / (MIN(dun_level, MAX_DEPTH - 1) - n_ptr->level + 5);
1837         }
1838
1839         /* Pick a random type */
1840         tmp = randint0(total);
1841
1842         /* Find this type */
1843         for (n_ptr = l_ptr, total = 0, count = 0; TRUE; n_ptr++, count++)
1844         {
1845                 /* Note end */
1846                 if (!n_ptr->name) break;
1847
1848                 /* Ignore excessive depth */
1849                 if (n_ptr->level > dun_level) continue;
1850
1851                 /* Not matched with pit/nest flag */
1852                 if (!(allow_flag_mask & (1L << count))) continue;
1853
1854                 /* Count this possibility */
1855                 total += n_ptr->chance * MAX_DEPTH / (MIN(dun_level, MAX_DEPTH - 1) - n_ptr->level + 5);
1856
1857                 /* Found the type */
1858                 if (tmp < total) break;
1859         }
1860
1861         return n_ptr->name ? count : -1;
1862 }
1863
1864 static vault_aux_type nest_types[] =
1865 {
1866 #ifdef JP
1867         {"¥¯¥í¡¼¥ó",     vault_aux_clone,    vault_prep_clone,   5, 3},
1868         {"¥¼¥ê¡¼",       vault_aux_jelly,    NULL,               5, 6},
1869         {"¥·¥ó¥Ü¥ë(Á±)", vault_aux_symbol_g, vault_prep_symbol, 25, 2},
1870         {"¥·¥ó¥Ü¥ë(°)", vault_aux_symbol_e, vault_prep_symbol, 25, 2},
1871         {"¥ß¥ß¥Ã¥¯",     vault_aux_mimic,    NULL,              30, 4},
1872         {"¶¸µ¤",         vault_aux_cthulhu,  NULL,              70, 2},
1873         {"¸¤¾®²°",       vault_aux_kennel,   NULL,              45, 4},
1874         {"Æ°Êª±à",       vault_aux_animal,   NULL,              35, 5},
1875         {"¶µ²ñ",         vault_aux_chapel_g, NULL,              75, 4},
1876         {"¥¢¥ó¥Ç¥Ã¥É",   vault_aux_undead,   NULL,              75, 5},
1877         {NULL,           NULL,               NULL,               0, 0},
1878 #else
1879         {"clone",        vault_aux_clone,    vault_prep_clone,   5, 3},
1880         {"jelly",        vault_aux_jelly,    NULL,               5, 6},
1881         {"symbol good",  vault_aux_symbol_g, vault_prep_symbol, 25, 2},
1882         {"symbol evil",  vault_aux_symbol_e, vault_prep_symbol, 25, 2},
1883         {"mimic",        vault_aux_mimic,    NULL,              30, 4},
1884         {"lovecraftian", vault_aux_cthulhu,  NULL,              70, 2},
1885         {"kennel",       vault_aux_kennel,   NULL,              45, 4},
1886         {"animal",       vault_aux_animal,   NULL,              35, 5},
1887         {"chapel",       vault_aux_chapel_g, NULL,              75, 4},
1888         {"undead",       vault_aux_undead,   NULL,              75, 5},
1889         {NULL,           NULL,               NULL,               0, 0},
1890 #endif
1891 };
1892
1893 static vault_aux_type pit_types[] =
1894 {
1895 #ifdef JP
1896         {"¥ª¡¼¥¯",       vault_aux_orc,      NULL,               5, 6},
1897         {"¥È¥í¥ë",       vault_aux_troll,    NULL,              20, 6},
1898         {"¥¸¥ã¥¤¥¢¥ó¥È", vault_aux_giant,    NULL,              50, 6},
1899         {"¶¸µ¤",         vault_aux_cthulhu,  NULL,              80, 2},
1900         {"¥·¥ó¥Ü¥ë(Á±)", vault_aux_symbol_g, vault_prep_symbol, 70, 1},
1901         {"¥·¥ó¥Ü¥ë(°)", vault_aux_symbol_e, vault_prep_symbol, 70, 1},
1902         {"¶µ²ñ",         vault_aux_chapel_g, NULL,              65, 2},
1903         {"¥É¥é¥´¥ó",     vault_aux_dragon,   vault_prep_dragon, 70, 6},
1904         {"¥Ç¡¼¥â¥ó",     vault_aux_demon,    NULL,              80, 6},
1905         {"¥À¡¼¥¯¥¨¥ë¥Õ", vault_aux_dark_elf, NULL,              45, 4},
1906         {NULL,           NULL,               NULL,               0, 0},
1907 #else
1908         {"orc",          vault_aux_orc,      NULL,               5, 6},
1909         {"troll",        vault_aux_troll,    NULL,              20, 6},
1910         {"giant",        vault_aux_giant,    NULL,              50, 6},
1911         {"lovecraftian", vault_aux_cthulhu,  NULL,              80, 2},
1912         {"symbol good",  vault_aux_symbol_g, vault_prep_symbol, 70, 1},
1913         {"symbol evil",  vault_aux_symbol_e, vault_prep_symbol, 70, 1},
1914         {"chapel",       vault_aux_chapel_g, NULL,              65, 2},
1915         {"dragon",       vault_aux_dragon,   vault_prep_dragon, 70, 6},
1916         {"demon",        vault_aux_demon,    NULL,              80, 6},
1917         {"dark elf",     vault_aux_dark_elf, NULL,              45, 4},
1918         {NULL,           NULL,               NULL,               0, 0},
1919 #endif
1920 };
1921
1922
1923 /* Nest types code */
1924 #define NEST_TYPE_CLONE        0
1925 #define NEST_TYPE_JELLY        1
1926 #define NEST_TYPE_SYMBOL_GOOD  2
1927 #define NEST_TYPE_SYMBOL_EVIL  3
1928 #define NEST_TYPE_MIMIC        4
1929 #define NEST_TYPE_LOVECRAFTIAN 5
1930 #define NEST_TYPE_KENNEL       6
1931 #define NEST_TYPE_ANIMAL       7
1932 #define NEST_TYPE_CHAPEL       8
1933 #define NEST_TYPE_UNDEAD       9
1934
1935 /* Pit types code */
1936 #define PIT_TYPE_ORC           0
1937 #define PIT_TYPE_TROLL         1
1938 #define PIT_TYPE_GIANT         2
1939 #define PIT_TYPE_LOVECRAFTIAN  3
1940 #define PIT_TYPE_SYMBOL_GOOD   4
1941 #define PIT_TYPE_SYMBOL_EVIL   5
1942 #define PIT_TYPE_CHAPEL        6
1943 #define PIT_TYPE_DRAGON        7
1944 #define PIT_TYPE_DEMON         8
1945 #define PIT_TYPE_DARK_ELF      9
1946
1947
1948 /*
1949  * Hack -- Get the string describing subtype of pit/nest
1950  * Determined in prepare function (some pit/nest only)
1951  */
1952 static cptr pit_subtype_string(int type, bool nest)
1953 {
1954         static char inner_buf[256] = "";
1955
1956         inner_buf[0] = '\0'; /* Init string */
1957
1958         if (nest) /* Nests */
1959         {
1960                 switch (type)
1961                 {
1962                 case NEST_TYPE_CLONE:
1963                         sprintf(inner_buf, "(%s)", r_name + r_info[vault_aux_race].name);
1964                         break;
1965                 case NEST_TYPE_SYMBOL_GOOD:
1966                 case NEST_TYPE_SYMBOL_EVIL:
1967                         sprintf(inner_buf, "(%c)", vault_aux_char);
1968                         break;
1969                 }
1970         }
1971         else /* Pits */
1972         {
1973                 switch (type)
1974                 {
1975                 case PIT_TYPE_SYMBOL_GOOD:
1976                 case PIT_TYPE_SYMBOL_EVIL:
1977                         sprintf(inner_buf, "(%c)", vault_aux_char);
1978                         break;
1979                 case PIT_TYPE_DRAGON:
1980                         switch (vault_aux_dragon_mask4)
1981                         {
1982 #ifdef JP
1983                         case RF4_BR_ACID: strcpy(inner_buf, "(»À)");   break;
1984                         case RF4_BR_ELEC: strcpy(inner_buf, "(°ðºÊ)"); break;
1985                         case RF4_BR_FIRE: strcpy(inner_buf, "(²Ð±ê)"); break;
1986                         case RF4_BR_COLD: strcpy(inner_buf, "(Îäµ¤)"); break;
1987                         case RF4_BR_POIS: strcpy(inner_buf, "(ÆÇ)");   break;
1988                         case (RF4_BR_ACID | RF4_BR_ELEC | RF4_BR_FIRE | RF4_BR_COLD | RF4_BR_POIS):
1989                                 strcpy(inner_buf, "(Ëü¿§)"); break;
1990                         default: strcpy(inner_buf, "(Ì¤ÄêµÁ)"); break;
1991 #else
1992                         case RF4_BR_ACID: strcpy(inner_buf, "(acid)");      break;
1993                         case RF4_BR_ELEC: strcpy(inner_buf, "(lightning)"); break;
1994                         case RF4_BR_FIRE: strcpy(inner_buf, "(fire)");      break;
1995                         case RF4_BR_COLD: strcpy(inner_buf, "(frost)");     break;
1996                         case RF4_BR_POIS: strcpy(inner_buf, "(poison)");    break;
1997                         case (RF4_BR_ACID | RF4_BR_ELEC | RF4_BR_FIRE | RF4_BR_COLD | RF4_BR_POIS):
1998                                 strcpy(inner_buf, "(multi-hued)"); break;
1999                         default: strcpy(inner_buf, "(undefined)"); break;
2000 #endif
2001                         }
2002                         break;
2003                 }
2004         }
2005
2006         return inner_buf;
2007 }
2008
2009
2010 /* A struct for nest monster information with cheat_hear */
2011 typedef struct
2012 {
2013         s16b r_idx;
2014         bool used;
2015 }
2016 nest_mon_info_type;
2017
2018
2019 /*
2020  * Comp function for sorting nest monster information
2021  */
2022 static bool ang_sort_comp_nest_mon_info(vptr u, vptr v, int a, int b)
2023 {
2024         nest_mon_info_type *nest_mon_info = (nest_mon_info_type *)u;
2025         int w1 = nest_mon_info[a].r_idx;
2026         int w2 = nest_mon_info[b].r_idx;
2027         monster_race *r1_ptr = &r_info[w1];
2028         monster_race *r2_ptr = &r_info[w2];
2029         int z1, z2;
2030
2031         /* Unused */
2032         (void)v;
2033
2034         /* Extract used info */
2035         z1 = nest_mon_info[a].used;
2036         z2 = nest_mon_info[b].used;
2037
2038         /* Compare used status */
2039         if (z1 < z2) return FALSE;
2040         if (z1 > z2) return TRUE;
2041
2042         /* Compare levels */
2043         if (r1_ptr->level < r2_ptr->level) return TRUE;
2044         if (r1_ptr->level > r2_ptr->level) return FALSE;
2045
2046         /* Compare experience */
2047         if (r1_ptr->mexp < r2_ptr->mexp) return TRUE;
2048         if (r1_ptr->mexp > r2_ptr->mexp) return FALSE;
2049
2050         /* Compare indexes */
2051         return w1 <= w2;
2052 }
2053
2054
2055 /*
2056  * Swap function for sorting nest monster information
2057  */
2058 static void ang_sort_swap_nest_mon_info(vptr u, vptr v, int a, int b)
2059 {
2060         nest_mon_info_type *nest_mon_info = (nest_mon_info_type *)u;
2061         nest_mon_info_type holder;
2062
2063         /* Unused */
2064         (void)v;
2065
2066         /* Swap */
2067         holder = nest_mon_info[a];
2068         nest_mon_info[a] = nest_mon_info[b];
2069         nest_mon_info[b] = holder;
2070 }
2071
2072
2073 #define NUM_NEST_MON_TYPE 64
2074
2075 /*
2076  * Type 5 -- Monster nests
2077  *
2078  * A monster nest is a "big" room, with an "inner" room, containing
2079  * a "collection" of monsters of a given type strewn about the room.
2080  *
2081  * The monsters are chosen from a set of 64 randomly selected monster
2082  * races, to allow the nest creation to fail instead of having "holes".
2083  *
2084  * Note the use of the "get_mon_num_prep()" function, and the special
2085  * "get_mon_num_hook()" restriction function, to prepare the "monster
2086  * allocation table" in such a way as to optimize the selection of
2087  * "appropriate" non-unique monsters for the nest.
2088  *
2089  * Note that the "get_mon_num()" function may (rarely) fail, in which
2090  * case the nest will be empty, and will not affect the level rating.
2091  *
2092  * Note that "monster nests" will never contain "unique" monsters.
2093  */
2094 static bool build_type5(void)
2095 {
2096         int y, x, y1, x1, y2, x2, xval, yval;
2097         int i;
2098         nest_mon_info_type nest_mon_info[NUM_NEST_MON_TYPE];
2099
2100         monster_type align;
2101
2102         cave_type *c_ptr;
2103
2104         int cur_nest_type = pick_vault_type(nest_types, d_info[dungeon_type].nest);
2105         vault_aux_type *n_ptr;
2106
2107         /* No type available */
2108         if (cur_nest_type < 0) return FALSE;
2109
2110         n_ptr = &nest_types[cur_nest_type];
2111
2112         /* Process a preparation function if necessary */
2113         if (n_ptr->prep_func) (*(n_ptr->prep_func))();
2114
2115         /* Prepare allocation table */
2116         get_mon_num_prep(n_ptr->hook_func, NULL);
2117
2118         align.sub_align = SUB_ALIGN_NEUTRAL;
2119
2120         /* Pick some monster types */
2121         for (i = 0; i < NUM_NEST_MON_TYPE; i++)
2122         {
2123                 int r_idx = 0, attempts = 100;
2124                 monster_race *r_ptr = NULL;
2125
2126                 while (attempts--)
2127                 {
2128                         /* Get a (hard) monster type */
2129                         r_idx = get_mon_num(dun_level + 10);
2130                         r_ptr = &r_info[r_idx];
2131
2132                         /* Decline incorrect alignment */
2133                         if (monster_has_hostile_align(&align, 0, 0, r_ptr)) continue;
2134
2135                         /* Accept this monster */
2136                         break;
2137                 }
2138
2139                 /* Notice failure */
2140                 if (!r_idx || !attempts) return FALSE;
2141
2142                 /* Note the alignment */
2143                 if (r_ptr->flags3 & RF3_EVIL) align.sub_align |= SUB_ALIGN_EVIL;
2144                 if (r_ptr->flags3 & RF3_GOOD) align.sub_align |= SUB_ALIGN_GOOD;
2145
2146                 nest_mon_info[i].r_idx = r_idx;
2147                 nest_mon_info[i].used = FALSE;
2148         }
2149
2150         /* Find and reserve some space in the dungeon.  Get center of room. */
2151         if (!find_space(&yval, &xval, 11, 25)) return FALSE;
2152
2153         /* Large room */
2154         y1 = yval - 4;
2155         y2 = yval + 4;
2156         x1 = xval - 11;
2157         x2 = xval + 11;
2158
2159         /* Place the floor area */
2160         for (y = y1 - 1; y <= y2 + 1; y++)
2161         {
2162                 for (x = x1 - 1; x <= x2 + 1; x++)
2163                 {
2164                         c_ptr = &cave[y][x];
2165                         place_floor_grid(c_ptr);
2166                         c_ptr->info |= (CAVE_ROOM);
2167                 }
2168         }
2169
2170         /* Place the outer walls */
2171         for (y = y1 - 1; y <= y2 + 1; y++)
2172         {
2173                 c_ptr = &cave[y][x1 - 1];
2174                 place_outer_grid(c_ptr);
2175                 c_ptr = &cave[y][x2 + 1];
2176                 place_outer_grid(c_ptr);
2177         }
2178         for (x = x1 - 1; x <= x2 + 1; x++)
2179         {
2180                 c_ptr = &cave[y1 - 1][x];
2181                 place_outer_grid(c_ptr);
2182                 c_ptr = &cave[y2 + 1][x];
2183                 place_outer_grid(c_ptr);
2184         }
2185
2186
2187         /* Advance to the center room */
2188         y1 = y1 + 2;
2189         y2 = y2 - 2;
2190         x1 = x1 + 2;
2191         x2 = x2 - 2;
2192
2193         /* The inner walls */
2194         for (y = y1 - 1; y <= y2 + 1; y++)
2195         {
2196                 c_ptr = &cave[y][x1 - 1];
2197                 place_inner_grid(c_ptr);
2198                 c_ptr = &cave[y][x2 + 1];
2199                 place_inner_grid(c_ptr);
2200         }
2201
2202         for (x = x1 - 1; x <= x2 + 1; x++)
2203         {
2204                 c_ptr = &cave[y1 - 1][x];
2205                 place_inner_grid(c_ptr);
2206                 c_ptr = &cave[y2 + 1][x];
2207                 place_inner_grid(c_ptr);
2208         }
2209         for (y = y1; y <= y2; y++)
2210         {
2211                 for (x = x1; x <= x2; x++)
2212                 {
2213                         add_cave_info(y, x, CAVE_ICKY);
2214                 }
2215         }
2216
2217         /* Place a secret door */
2218         switch (randint1(4))
2219         {
2220                 case 1: place_secret_door(y1 - 1, xval); break;
2221                 case 2: place_secret_door(y2 + 1, xval); break;
2222                 case 3: place_secret_door(yval, x1 - 1); break;
2223                 case 4: place_secret_door(yval, x2 + 1); break;
2224         }
2225
2226         /* Describe */
2227         if (cheat_room)
2228         {
2229                 /* Room type */
2230 #ifdef JP
2231                 msg_format("¥â¥ó¥¹¥¿¡¼Éô²°(nest)(%s%s)", n_ptr->name, pit_subtype_string(cur_nest_type, TRUE));
2232 #else
2233                 msg_format("Monster nest (%s%s)", n_ptr->name, pit_subtype_string(cur_nest_type, TRUE));
2234 #endif
2235         }
2236
2237         /* Increase the level rating */
2238         rating += 10;
2239
2240         /* (Sometimes) Cause a "special feeling" (for "Monster Nests") */
2241         if ((dun_level <= 40) && (randint1(dun_level * dun_level + 50) < 300))
2242         {
2243                 good_item_flag = TRUE;
2244         }
2245
2246         /* Place some monsters */
2247         for (y = yval - 2; y <= yval + 2; y++)
2248         {
2249                 for (x = xval - 9; x <= xval + 9; x++)
2250                 {
2251                         int r_idx;
2252
2253                         i = randint0(NUM_NEST_MON_TYPE);
2254                         r_idx = nest_mon_info[i].r_idx;
2255
2256                         /* Place that "random" monster (no groups) */
2257                         (void)place_monster_aux(0, y, x, r_idx, 0L);
2258
2259                         nest_mon_info[i].used = TRUE;
2260                 }
2261         }
2262
2263         if (cheat_room && cheat_hear)
2264         {
2265                 ang_sort_comp = ang_sort_comp_nest_mon_info;
2266                 ang_sort_swap = ang_sort_swap_nest_mon_info;
2267                 ang_sort(nest_mon_info, NULL, NUM_NEST_MON_TYPE);
2268
2269                 /* Dump the entries (prevent multi-printing) */
2270                 for (i = 0; i < NUM_NEST_MON_TYPE; i++)
2271                 {
2272                         if (!nest_mon_info[i].used) break;
2273                         for (; i < NUM_NEST_MON_TYPE - 1; i++)
2274                         {
2275                                 if (nest_mon_info[i].r_idx != nest_mon_info[i + 1].r_idx) break;
2276                                 if (!nest_mon_info[i + 1].used) break;
2277                         }
2278                         msg_print(r_name + r_info[nest_mon_info[i].r_idx].name);
2279                 }
2280         }
2281
2282         return TRUE;
2283 }
2284
2285
2286 /*
2287  * Type 6 -- Monster pits
2288  *
2289  * A monster pit is a "big" room, with an "inner" room, containing
2290  * a "collection" of monsters of a given type organized in the room.
2291  *
2292  * The inside room in a monster pit appears as shown below, where the
2293  * actual monsters in each location depend on the type of the pit
2294  *
2295  *   #####################
2296  *   #0000000000000000000#
2297  *   #0112233455543322110#
2298  *   #0112233467643322110#
2299  *   #0112233455543322110#
2300  *   #0000000000000000000#
2301  *   #####################
2302  *
2303  * Note that the monsters in the pit are now chosen by using "get_mon_num()"
2304  * to request 16 "appropriate" monsters, sorting them by level, and using
2305  * the "even" entries in this sorted list for the contents of the pit.
2306  *
2307  * Hack -- all of the "dragons" in a "dragon" pit must be the same "color",
2308  * which is handled by requiring a specific "breath" attack for all of the
2309  * dragons.  This may include "multi-hued" breath.  Note that "wyrms" may
2310  * be present in many of the dragon pits, if they have the proper breath.
2311  *
2312  * Note the use of the "get_mon_num_prep()" function, and the special
2313  * "get_mon_num_hook()" restriction function, to prepare the "monster
2314  * allocation table" in such a way as to optimize the selection of
2315  * "appropriate" non-unique monsters for the pit.
2316  *
2317  * Note that the "get_mon_num()" function may (rarely) fail, in which case
2318  * the pit will be empty, and will not effect the level rating.
2319  *
2320  * Note that "monster pits" will never contain "unique" monsters.
2321  */
2322 static bool build_type6(void)
2323 {
2324         int y, x, y1, x1, y2, x2, xval, yval;
2325         int i, j;
2326
2327         int what[16];
2328
2329         monster_type align;
2330
2331         cave_type *c_ptr;
2332
2333         int cur_pit_type = pick_vault_type(pit_types, d_info[dungeon_type].pit);
2334         vault_aux_type *n_ptr;
2335
2336         /* No type available */
2337         if (cur_pit_type < 0) return FALSE;
2338
2339         n_ptr = &pit_types[cur_pit_type];
2340
2341         /* Process a preparation function if necessary */
2342         if (n_ptr->prep_func) (*(n_ptr->prep_func))();
2343
2344         /* Prepare allocation table */
2345         get_mon_num_prep(n_ptr->hook_func, NULL);
2346
2347         align.sub_align = SUB_ALIGN_NEUTRAL;
2348
2349         /* Pick some monster types */
2350         for (i = 0; i < 16; i++)
2351         {
2352                 int r_idx = 0, attempts = 100;
2353                 monster_race *r_ptr = NULL;
2354
2355                 while (attempts--)
2356                 {
2357                         /* Get a (hard) monster type */
2358                         r_idx = get_mon_num(dun_level + 10);
2359                         r_ptr = &r_info[r_idx];
2360
2361                         /* Decline incorrect alignment */
2362                         if (monster_has_hostile_align(&align, 0, 0, r_ptr)) continue;
2363
2364                         /* Accept this monster */
2365                         break;
2366                 }
2367
2368                 /* Notice failure */
2369                 if (!r_idx || !attempts) return FALSE;
2370
2371                 /* Note the alignment */
2372                 if (r_ptr->flags3 & RF3_EVIL) align.sub_align |= SUB_ALIGN_EVIL;
2373                 if (r_ptr->flags3 & RF3_GOOD) align.sub_align |= SUB_ALIGN_GOOD;
2374
2375                 what[i] = r_idx;
2376         }
2377
2378         /* Find and reserve some space in the dungeon.  Get center of room. */
2379         if (!find_space(&yval, &xval, 11, 25)) return FALSE;
2380
2381         /* Large room */
2382         y1 = yval - 4;
2383         y2 = yval + 4;
2384         x1 = xval - 11;
2385         x2 = xval + 11;
2386
2387         /* Place the floor area */
2388         for (y = y1 - 1; y <= y2 + 1; y++)
2389         {
2390                 for (x = x1 - 1; x <= x2 + 1; x++)
2391                 {
2392                         c_ptr = &cave[y][x];
2393                         place_floor_grid(c_ptr);
2394                         c_ptr->info |= (CAVE_ROOM);
2395                 }
2396         }
2397
2398         /* Place the outer walls */
2399         for (y = y1 - 1; y <= y2 + 1; y++)
2400         {
2401                 c_ptr = &cave[y][x1 - 1];
2402                 place_outer_grid(c_ptr);
2403                 c_ptr = &cave[y][x2 + 1];
2404                 place_outer_grid(c_ptr);
2405         }
2406         for (x = x1 - 1; x <= x2 + 1; x++)
2407         {
2408                 c_ptr = &cave[y1 - 1][x];
2409                 place_outer_grid(c_ptr);
2410                 c_ptr = &cave[y2 + 1][x];
2411                 place_outer_grid(c_ptr);
2412         }
2413
2414         /* Advance to the center room */
2415         y1 = y1 + 2;
2416         y2 = y2 - 2;
2417         x1 = x1 + 2;
2418         x2 = x2 - 2;
2419
2420         /* The inner walls */
2421         for (y = y1 - 1; y <= y2 + 1; y++)
2422         {
2423                 c_ptr = &cave[y][x1 - 1];
2424                 place_inner_grid(c_ptr);
2425                 c_ptr = &cave[y][x2 + 1];
2426                 place_inner_grid(c_ptr);
2427         }
2428         for (x = x1 - 1; x <= x2 + 1; x++)
2429         {
2430                 c_ptr = &cave[y1 - 1][x];
2431                 place_inner_grid(c_ptr);
2432                 c_ptr = &cave[y2 + 1][x];
2433                 place_inner_grid(c_ptr);
2434         }
2435         for (y = y1; y <= y2; y++)
2436         {
2437                 for (x = x1; x <= x2; x++)
2438                 {
2439                         add_cave_info(y, x, CAVE_ICKY);
2440                 }
2441         }
2442
2443         /* Place a secret door */
2444         switch (randint1(4))
2445         {
2446                 case 1: place_secret_door(y1 - 1, xval); break;
2447                 case 2: place_secret_door(y2 + 1, xval); break;
2448                 case 3: place_secret_door(yval, x1 - 1); break;
2449                 case 4: place_secret_door(yval, x2 + 1); break;
2450         }
2451
2452         /* Sort the entries */
2453         for (i = 0; i < 16 - 1; i++)
2454         {
2455                 /* Sort the entries */
2456                 for (j = 0; j < 16 - 1; j++)
2457                 {
2458                         int i1 = j;
2459                         int i2 = j + 1;
2460
2461                         int p1 = r_info[what[i1]].level;
2462                         int p2 = r_info[what[i2]].level;
2463
2464                         /* Bubble */
2465                         if (p1 > p2)
2466                         {
2467                                 int tmp = what[i1];
2468                                 what[i1] = what[i2];
2469                                 what[i2] = tmp;
2470                         }
2471                 }
2472         }
2473
2474         /* Message */
2475         if (cheat_room)
2476         {
2477                 /* Room type */
2478 #ifdef JP
2479                 msg_format("¥â¥ó¥¹¥¿¡¼Éô²°(pit)(%s%s)", n_ptr->name, pit_subtype_string(cur_pit_type, FALSE));
2480 #else
2481                 msg_format("Monster pit (%s%s)", n_ptr->name, pit_subtype_string(cur_pit_type, FALSE));
2482 #endif
2483         }
2484
2485         /* Select the entries */
2486         for (i = 0; i < 8; i++)
2487         {
2488                 /* Every other entry */
2489                 what[i] = what[i * 2];
2490
2491                 if (cheat_hear)
2492                 {
2493                         /* Message */
2494                         msg_print(r_name + r_info[what[i]].name);
2495                 }
2496         }
2497
2498         /* Increase the level rating */
2499         rating += 10;
2500
2501         /* (Sometimes) Cause a "special feeling" (for "Monster Pits") */
2502         if ((dun_level <= 40) && (randint1(dun_level * dun_level + 50) < 300))
2503         {
2504                 good_item_flag = TRUE;
2505         }
2506
2507         /* Top and bottom rows */
2508         for (x = xval - 9; x <= xval + 9; x++)
2509         {
2510                 place_monster_aux(0, yval - 2, x, what[0], PM_NO_KAGE);
2511                 place_monster_aux(0, yval + 2, x, what[0], PM_NO_KAGE);
2512         }
2513
2514         /* Middle columns */
2515         for (y = yval - 1; y <= yval + 1; y++)
2516         {
2517                 place_monster_aux(0, y, xval - 9, what[0], PM_NO_KAGE);
2518                 place_monster_aux(0, y, xval + 9, what[0], PM_NO_KAGE);
2519
2520                 place_monster_aux(0, y, xval - 8, what[1], PM_NO_KAGE);
2521                 place_monster_aux(0, y, xval + 8, what[1], PM_NO_KAGE);
2522
2523                 place_monster_aux(0, y, xval - 7, what[1], PM_NO_KAGE);
2524                 place_monster_aux(0, y, xval + 7, what[1], PM_NO_KAGE);
2525
2526                 place_monster_aux(0, y, xval - 6, what[2], PM_NO_KAGE);
2527                 place_monster_aux(0, y, xval + 6, what[2], PM_NO_KAGE);
2528
2529                 place_monster_aux(0, y, xval - 5, what[2], PM_NO_KAGE);
2530                 place_monster_aux(0, y, xval + 5, what[2], PM_NO_KAGE);
2531
2532                 place_monster_aux(0, y, xval - 4, what[3], PM_NO_KAGE);
2533                 place_monster_aux(0, y, xval + 4, what[3], PM_NO_KAGE);
2534
2535                 place_monster_aux(0, y, xval - 3, what[3], PM_NO_KAGE);
2536                 place_monster_aux(0, y, xval + 3, what[3], PM_NO_KAGE);
2537
2538                 place_monster_aux(0, y, xval - 2, what[4], PM_NO_KAGE);
2539                 place_monster_aux(0, y, xval + 2, what[4], PM_NO_KAGE);
2540         }
2541
2542         /* Above/Below the center monster */
2543         for (x = xval - 1; x <= xval + 1; x++)
2544         {
2545                 place_monster_aux(0, yval + 1, x, what[5], PM_NO_KAGE);
2546                 place_monster_aux(0, yval - 1, x, what[5], PM_NO_KAGE);
2547         }
2548
2549         /* Next to the center monster */
2550         place_monster_aux(0, yval, xval + 1, what[6], PM_NO_KAGE);
2551         place_monster_aux(0, yval, xval - 1, what[6], PM_NO_KAGE);
2552
2553         /* Center monster */
2554         place_monster_aux(0, yval, xval, what[7], PM_NO_KAGE);
2555
2556         return TRUE;
2557 }
2558
2559
2560 /* coordinate translation code */
2561 static void coord_trans(int *x, int *y, int xoffset, int yoffset, int transno)
2562 {
2563         int i;
2564         int temp;
2565
2566         /*
2567          * transno specifies what transformation is required. (0-7)
2568          * The lower two bits indicate by how much the vault is rotated,
2569          * and the upper bit indicates a reflection.
2570          * This is done by using rotation matrices... however since
2571          * these are mostly zeros for rotations by 90 degrees this can
2572          * be expressed simply in terms of swapping and inverting the
2573          * x and y coordinates.
2574          */
2575         for (i = 0; i < transno % 4; i++)
2576         {
2577                 /* rotate by 90 degrees */
2578                 temp = *x;
2579                 *x = -(*y);
2580                 *y = temp;
2581         }
2582
2583         if (transno / 4)
2584         {
2585                 /* Reflect depending on status of 3rd bit. */
2586                 *x = -(*x);
2587         }
2588
2589         /* Add offsets so vault stays in the first quadrant */
2590         *x += xoffset;
2591         *y += yoffset;
2592 }
2593
2594
2595 /*
2596  * Hack -- fill in "vault" rooms
2597  */
2598 static void build_vault(int yval, int xval, int ymax, int xmax, cptr data,
2599                 int xoffset, int yoffset, int transno)
2600 {
2601         int dx, dy, x, y, i, j;
2602
2603         cptr t;
2604
2605         cave_type *c_ptr;
2606
2607
2608         /* Place dungeon features and objects */
2609         for (t = data, dy = 0; dy < ymax; dy++)
2610         {
2611                 for (dx = 0; dx < xmax; dx++, t++)
2612                 {
2613                         /* prevent loop counter from being overwritten */
2614                         i = dx;
2615                         j = dy;
2616
2617                         /* Flip / rotate */
2618                         coord_trans(&i, &j, xoffset, yoffset, transno);
2619
2620                         /* Extract the location */
2621                         if (transno % 2 == 0)
2622                         {
2623                                 /* no swap of x/y */
2624                                 x = xval - (xmax / 2) + i;
2625                                 y = yval - (ymax / 2) + j;
2626                         }
2627                         else
2628                         {
2629                                 /* swap of x/y */
2630                                 x = xval - (ymax / 2) + i;
2631                                 y = yval - (xmax / 2) + j;
2632                         }
2633
2634                         /* Hack -- skip "non-grids" */
2635                         if (*t == ' ') continue;
2636
2637                         /* Access the grid */
2638                         c_ptr = &cave[y][x];
2639
2640                         /* Lay down a floor */
2641                         place_floor_grid(c_ptr);
2642
2643                         /* Remove any mimic */
2644                         c_ptr->mimic = 0;
2645
2646                         /* Part of a vault */
2647                         c_ptr->info |= (CAVE_ROOM | CAVE_ICKY);
2648
2649                         /* Analyze the grid */
2650                         switch (*t)
2651                         {
2652                                 /* Granite wall (outer) */
2653                         case '%':
2654                                 place_outer_noperm_grid(c_ptr);
2655                                 break;
2656
2657                                 /* Granite wall (inner) */
2658                         case '#':
2659                                 place_inner_grid(c_ptr);
2660                                 break;
2661
2662                                 /* Permanent wall (inner) */
2663                         case 'X':
2664                                 c_ptr->feat = FEAT_PERM_INNER;
2665                                 c_ptr->info &= ~(CAVE_MASK);
2666                                 c_ptr->info |= CAVE_INNER;
2667                                 break;
2668
2669                                 /* Treasure/trap */
2670                         case '*':
2671                                 if (randint0(100) < 75)
2672                                 {
2673                                         place_object(y, x, 0L);
2674                                 }
2675                                 else
2676                                 {
2677                                         place_trap(y, x);
2678                                 }
2679                                 break;
2680
2681                                 /* Secret doors */
2682                         case '+':
2683                                 place_secret_door(y, x);
2684                                 break;
2685
2686                                 /* Trap */
2687                         case '^':
2688                                 place_trap(y, x);
2689                                 break;
2690
2691                                 /* Black market in a dungeon */
2692                         case 'S':
2693                                 set_cave_feat(y, x, FEAT_SHOP_HEAD + STORE_BLACK);
2694                                 store_init(NO_TOWN, STORE_BLACK);
2695                                 break;
2696
2697                                 /* The Pattern */
2698                         case 'p':
2699                                 set_cave_feat(y, x, FEAT_PATTERN_START);
2700                                 break;
2701
2702                         case 'a':
2703                                 set_cave_feat(y, x, FEAT_PATTERN_1);
2704                                 break;
2705
2706                         case 'b':
2707                                 set_cave_feat(y, x, FEAT_PATTERN_2);
2708                                 break;
2709
2710                         case 'c':
2711                                 set_cave_feat(y, x, FEAT_PATTERN_3);
2712                                 break;
2713
2714                         case 'd':
2715                                 set_cave_feat(y, x, FEAT_PATTERN_4);
2716                                 break;
2717
2718                         case 'P':
2719                                 set_cave_feat(y, x, FEAT_PATTERN_END);
2720                                 break;
2721
2722                         case 'B':
2723                                 set_cave_feat(y, x, FEAT_PATTERN_XTRA1);
2724                                 break;
2725
2726                         case 'A':
2727                                 /* Reward for Pattern walk */
2728                                 object_level = base_level + 12;
2729                                 place_object(y, x, AM_GOOD | AM_GREAT);
2730                                 object_level = base_level;
2731                                 break;
2732                         }
2733                 }
2734         }
2735
2736
2737         /* Place dungeon monsters and objects */
2738         for (t = data, dy = 0; dy < ymax; dy++)
2739         {
2740                 for (dx = 0; dx < xmax; dx++, t++)
2741                 {
2742                         /* prevent loop counter from being overwritten */
2743                         i = dx;
2744                         j = dy;
2745
2746                         /* Flip / rotate */
2747                         coord_trans(&i, &j, xoffset, yoffset, transno);
2748
2749                         /* Extract the location */
2750                         if (transno % 2 == 0)
2751                         {
2752                                 /* no swap of x/y */
2753                                 x = xval - (xmax / 2) + i;
2754                                 y = yval - (ymax / 2) + j;
2755                         }
2756                         else
2757                         {
2758                                 /* swap of x/y */
2759                                 x = xval - (ymax / 2) + i;
2760                                 y = yval - (xmax / 2) + j;
2761                         }
2762
2763                         /* Hack -- skip "non-grids" */
2764                         if (*t == ' ') continue;
2765
2766                         /* Analyze the symbol */
2767                         switch (*t)
2768                         {
2769                                 /* Monster */
2770                                 case '&':
2771                                 {
2772                                         monster_level = base_level + 5;
2773                                         place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
2774                                         monster_level = base_level;
2775                                         break;
2776                                 }
2777
2778                                 /* Meaner monster */
2779                                 case '@':
2780                                 {
2781                                         monster_level = base_level + 11;
2782                                         place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
2783                                         monster_level = base_level;
2784                                         break;
2785                                 }
2786
2787                                 /* Meaner monster, plus treasure */
2788                                 case '9':
2789                                 {
2790                                         monster_level = base_level + 9;
2791                                         place_monster(y, x, PM_ALLOW_SLEEP);
2792                                         monster_level = base_level;
2793                                         object_level = base_level + 7;
2794                                         place_object(y, x, AM_GOOD);
2795                                         object_level = base_level;
2796                                         break;
2797                                 }
2798
2799                                 /* Nasty monster and treasure */
2800                                 case '8':
2801                                 {
2802                                         monster_level = base_level + 40;
2803                                         place_monster(y, x, PM_ALLOW_SLEEP);
2804                                         monster_level = base_level;
2805                                         object_level = base_level + 20;
2806                                         place_object(y, x, AM_GOOD | AM_GREAT);
2807                                         object_level = base_level;
2808                                         break;
2809                                 }
2810
2811                                 /* Monster and/or object */
2812                                 case ',':
2813                                 {
2814                                         if (randint0(100) < 50)
2815                                         {
2816                                                 monster_level = base_level + 3;
2817                                                 place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
2818                                                 monster_level = base_level;
2819                                         }
2820                                         if (randint0(100) < 50)
2821                                         {
2822                                                 object_level = base_level + 7;
2823                                                 place_object(y, x, 0L);
2824                                                 object_level = base_level;
2825                                         }
2826                                         break;
2827                                 }
2828
2829                         }
2830                 }
2831         }
2832 }
2833
2834
2835 /*
2836  * Type 7 -- simple vaults (see "v_info.txt")
2837  */
2838 static bool build_type7(void)
2839 {
2840         vault_type *v_ptr;
2841         int dummy;
2842         int x, y;
2843         int xval, yval;
2844         int xoffset, yoffset;
2845         int transno;
2846
2847         /* Pick a lesser vault */
2848         for (dummy = 0; dummy < SAFE_MAX_ATTEMPTS; dummy++)
2849         {
2850                 /* Access a random vault record */
2851                 v_ptr = &v_info[randint0(max_v_idx)];
2852
2853                 /* Accept the first lesser vault */
2854                 if (v_ptr->typ == 7) break;
2855         }
2856
2857         /* No lesser vault found */
2858         if (dummy >= SAFE_MAX_ATTEMPTS)
2859         {
2860                 if (cheat_room)
2861                 {
2862 #ifdef JP
2863                         msg_print("·Ù¹ð¡ª¾®¤µ¤ÊÃÏ²¼¼¼¤òÇÛÃÖ¤Ç¤¤Þ¤»¤ó¡ª");
2864 #else
2865                         msg_print("Warning! Could not place lesser vault!");
2866 #endif
2867                 }
2868                 return FALSE;
2869         }
2870
2871         /* pick type of transformation (0-7) */
2872         transno = randint0(8);
2873
2874         /* calculate offsets */
2875         x = v_ptr->wid;
2876         y = v_ptr->hgt;
2877
2878         /* Some huge vault cannot be ratated to fit in the dungeon */
2879         if (x+2 > cur_hgt-2)
2880         {
2881                 /* Forbid 90 or 270 degree ratation */
2882                 transno &= ~1;
2883         }
2884
2885         coord_trans(&x, &y, 0, 0, transno);
2886
2887         if (x < 0)
2888         {
2889                 xoffset = -x - 1;
2890         }
2891         else
2892         {
2893                 xoffset = 0;
2894         }
2895
2896         if (y < 0)
2897         {
2898                 yoffset = -y - 1;
2899         }
2900         else
2901         {
2902                 yoffset = 0;
2903         }
2904
2905         /* Find and reserve some space in the dungeon.  Get center of room. */
2906         if (!find_space(&yval, &xval, abs(y), abs(x))) return FALSE;
2907
2908 #ifdef FORCE_V_IDX
2909         v_ptr = &v_info[2];
2910 #endif
2911
2912         /* Message */
2913 #ifdef JP
2914         if (cheat_room) msg_format("¾®¤µ¤ÊÃÏ²¼¼¼(%s)", v_name + v_ptr->name);
2915 #else
2916         if (cheat_room) msg_format("Lesser vault (%s)", v_name + v_ptr->name);
2917 #endif
2918
2919         /* Boost the rating */
2920         rating += v_ptr->rat;
2921
2922         /* (Sometimes) Cause a special feeling */
2923         if ((dun_level <= 50) ||
2924                 (randint1((dun_level - 40) * (dun_level - 40) + 50) < 400))
2925         {
2926                 good_item_flag = TRUE;
2927         }
2928
2929         /* Hack -- Build the vault */
2930         build_vault(yval, xval, v_ptr->hgt, v_ptr->wid,
2931                     v_text + v_ptr->text, xoffset, yoffset, transno);
2932
2933         return TRUE;
2934 }
2935
2936
2937 /*
2938  * Type 8 -- greater vaults (see "v_info.txt")
2939  */
2940 static bool build_type8(void)
2941 {
2942         vault_type *v_ptr;
2943         int dummy;
2944         int xval, yval;
2945         int x, y;
2946         int transno;
2947         int xoffset, yoffset;
2948
2949         /* Pick a greater vault */
2950         for (dummy = 0; dummy < SAFE_MAX_ATTEMPTS; dummy++)
2951         {
2952                 /* Access a random vault record */
2953                 v_ptr = &v_info[randint0(max_v_idx)];
2954
2955                 /* Accept the first greater vault */
2956                 if (v_ptr->typ == 8) break;
2957         }
2958
2959         /* No greater vault found */
2960         if (dummy >= SAFE_MAX_ATTEMPTS)
2961         {
2962                 if (cheat_room)
2963                 {
2964 #ifdef JP
2965                         msg_print("·Ù¹ð¡ªµðÂç¤ÊÃÏ²¼¼¼¤òÇÛÃÖ¤Ç¤¤Þ¤»¤ó¡ª");
2966 #else
2967                         msg_print("Warning! Could not place greater vault!");
2968 #endif
2969                 }
2970                 return FALSE;
2971         }
2972
2973         /* pick type of transformation (0-7) */
2974         transno = randint0(8);
2975
2976         /* calculate offsets */
2977         x = v_ptr->wid;
2978         y = v_ptr->hgt;
2979
2980         /* Some huge vault cannot be ratated to fit in the dungeon */
2981         if (x+2 > cur_hgt-2)
2982         {
2983                 /* Forbid 90 or 270 degree ratation */
2984                 transno &= ~1;
2985         }
2986
2987         coord_trans(&x, &y, 0, 0, transno);
2988
2989         if (x < 0)
2990         {
2991                 xoffset = - x - 1;
2992         }
2993         else
2994         {
2995                 xoffset = 0;
2996         }
2997
2998         if (y < 0)
2999         {
3000                 yoffset = - y - 1;
3001         }
3002         else
3003         {
3004                 yoffset = 0;
3005         }
3006
3007         /*
3008          * Try to allocate space for room.  If fails, exit
3009          *
3010          * Hack -- Prepare a bit larger space (+2, +2) to
3011          * prevent generation of vaults with no-entrance.
3012          */
3013         /* Find and reserve some space in the dungeon.  Get center of room. */
3014         if (!find_space(&yval, &xval, abs(y) + 2, abs(x) + 2)) return FALSE;
3015
3016 #ifdef FORCE_V_IDX
3017         v_ptr = &v_info[76 + randint1(3)];
3018 #endif
3019
3020         /* Message */
3021 #ifdef JP
3022         if (cheat_room) msg_format("µðÂç¤ÊÃÏ²¼¼¼(%s)", v_name + v_ptr->name);
3023 #else
3024         if (cheat_room) msg_format("Greater vault (%s)", v_name + v_ptr->name);
3025 #endif
3026
3027         /* Boost the rating */
3028         rating += v_ptr->rat;
3029
3030         /* (Sometimes) Cause a special feeling */
3031         if ((dun_level <= 50) ||
3032             (randint1((dun_level - 40) * (dun_level - 40) + 50) < 400))
3033         {
3034                 good_item_flag = TRUE;
3035         }
3036
3037         /* Hack -- Build the vault */
3038         build_vault(yval, xval, v_ptr->hgt, v_ptr->wid,
3039                     v_text + v_ptr->text, xoffset, yoffset, transno);
3040
3041         return TRUE;
3042 }
3043
3044 /*
3045  * Structure to hold all "fill" data
3046  */
3047
3048 typedef struct fill_data_type fill_data_type;
3049
3050 struct fill_data_type
3051 {
3052         /* area size */
3053         int xmin;
3054         int ymin;
3055         int xmax;
3056         int ymax;
3057
3058         /* cutoffs */
3059         int c1;
3060         int c2;
3061         int c3;
3062
3063         /* features to fill with */
3064         int feat1;
3065         int feat2;
3066         int feat3;
3067
3068         int info1;
3069         int info2;
3070         int info3;
3071
3072         /* number of filled squares */
3073         int amount;
3074 };
3075
3076 static fill_data_type fill_data;
3077
3078
3079 /* Store routine for the fractal cave generator */
3080 /* this routine probably should be an inline function or a macro. */
3081 static void store_height(int x, int y, int val)
3082 {
3083         /* if on boundary set val > cutoff so walls are not as square */
3084         if (((x == fill_data.xmin) || (y == fill_data.ymin) ||
3085              (x == fill_data.xmax) || (y == fill_data.ymax)) &&
3086             (val <= fill_data.c1)) val = fill_data.c1 + 1;
3087
3088         /* store the value in height-map format */
3089         cave[y][x].feat = val;
3090
3091         return;
3092 }
3093
3094
3095 /*
3096 * Explanation of the plasma fractal algorithm:
3097 *
3098 * A grid of points is created with the properties of a 'height-map'
3099 * This is done by making the corners of the grid have a random value.
3100 * The grid is then subdivided into one with twice the resolution.
3101 * The new points midway between two 'known' points can be calculated
3102 * by taking the average value of the 'known' ones and randomly adding
3103 * or subtracting an amount proportional to the distance between those
3104 * points.  The final 'middle' points of the grid are then calculated
3105 * by averaging all four of the originally 'known' corner points.  An
3106 * random amount is added or subtracted from this to get a value of the
3107 * height at that point.  The scaling factor here is adjusted to the
3108 * slightly larger distance diagonally as compared to orthogonally.
3109 *
3110 * This is then repeated recursively to fill an entire 'height-map'
3111 * A rectangular map is done the same way, except there are different
3112 * scaling factors along the x and y directions.
3113 *
3114 * A hack to change the amount of correlation between points is done using
3115 * the grd variable.  If the current step size is greater than grd then
3116 * the point will be random, otherwise it will be calculated by the
3117 * above algorithm.  This makes a maximum distance at which two points on
3118 * the height map can affect each other.
3119 *
3120 * How fractal caves are made:
3121 *
3122 * When the map is complete, a cut-off value is used to create a cave.
3123 * Heights below this value are "floor", and heights above are "wall".
3124 * This also can be used to create lakes, by adding more height levels
3125 * representing shallow and deep water/ lava etc.
3126 *
3127 * The grd variable affects the width of passages.
3128 * The roug variable affects the roughness of those passages
3129 *
3130 * The tricky part is making sure the created cave is connected.  This
3131 * is done by 'filling' from the inside and only keeping the 'filled'
3132 * floor.  Walls bounding the 'filled' floor are also kept.  Everything
3133 * else is converted to the normal granite FEAT_WALL_EXTRA.
3134  */
3135
3136
3137 /*
3138  *  Note that this uses the cave.feat array in a very hackish way
3139  *  the values are first set to zero, and then each array location
3140  *  is used as a "heightmap"
3141  *  The heightmap then needs to be converted back into the "feat" format.
3142  *
3143  *  grd=level at which fractal turns on.  smaller gives more mazelike caves
3144  *  roug=roughness level.  16=normal.  higher values make things more convoluted
3145  *    small values are good for smooth walls.
3146  *  size=length of the side of the square cave system.
3147  */
3148 static void generate_hmap(int y0, int x0, int xsiz, int ysiz, int grd, int roug, int cutoff)
3149 {
3150         int xhsize, yhsize, xsize, ysize, maxsize;
3151
3152         /*
3153          * fixed point variables- these are stored as 256 x normal value
3154          * this gives 8 binary places of fractional part + 8 places of normal part
3155          */
3156
3157         u16b xstep, xhstep, ystep, yhstep;
3158         u16b xstep2, xhstep2, ystep2, yhstep2;
3159         u16b i, j, ii, jj, diagsize, xxsize, yysize;
3160
3161         /* Cache for speed */
3162         u16b xm, xp, ym, yp;
3163
3164         /* redefine size so can change the value if out of range */
3165         xsize = xsiz;
3166         ysize = ysiz;
3167
3168         /* Paranoia about size of the system of caves */
3169         if (xsize > 254) xsize = 254;
3170         if (xsize < 4) xsize = 4;
3171         if (ysize > 254) ysize = 254;
3172         if (ysize < 4) ysize = 4;
3173
3174         /* get offsets to middle of array */
3175         xhsize = xsize / 2;
3176         yhsize = ysize / 2;
3177
3178         /* fix rounding problem */
3179         xsize = xhsize * 2;
3180         ysize = yhsize * 2;
3181
3182         /* get limits of region */
3183         fill_data.xmin = x0 - xhsize;
3184         fill_data.ymin = y0 - yhsize;
3185         fill_data.xmax = x0 + xhsize;
3186         fill_data.ymax = y0 + yhsize;
3187
3188         /* Store cutoff in global for quick access */
3189         fill_data.c1 = cutoff;
3190
3191         /*
3192         * Scale factor for middle points:
3193         * About sqrt(2) * 256 - correct for a square lattice
3194         * approximately correct for everything else.
3195          */
3196         diagsize = 362;
3197
3198         /* maximum of xsize and ysize */
3199         maxsize = (xsize > ysize) ? xsize : ysize;
3200
3201         /* Clear the section */
3202         for (i = 0; i <= xsize; i++)
3203         {
3204                 for (j = 0; j <= ysize; j++)
3205                 {
3206                         /* 255 is a flag for "not done yet" */
3207                         cave[(int)(fill_data.ymin + j)][(int)(fill_data.xmin + i)].feat = 255;
3208                         /* Clear icky flag because may be redoing the cave */
3209                         cave[(int)(fill_data.ymin + j)][(int)(fill_data.xmin + i)].info &= ~(CAVE_ICKY);
3210                 }
3211         }
3212
3213         /* Boundaries are walls */
3214         cave[fill_data.ymin][fill_data.xmin].feat = maxsize;
3215         cave[fill_data.ymax][fill_data.xmin].feat = maxsize;
3216         cave[fill_data.ymin][fill_data.xmax].feat = maxsize;
3217         cave[fill_data.ymax][fill_data.xmax].feat = maxsize;
3218
3219         /* Set the middle square to be an open area. */
3220         cave[y0][x0].feat = 0;
3221
3222         /* Initialize the step sizes */
3223         xstep = xhstep = xsize * 256;
3224         ystep = yhstep = ysize * 256;
3225         xxsize = xsize * 256;
3226         yysize = ysize * 256;
3227
3228         /*
3229          * Fill in the rectangle with fractal height data -
3230          * like the 'plasma fractal' in fractint.
3231          */
3232         while ((xhstep > 256) || (yhstep > 256))
3233         {
3234                 /* Halve the step sizes */
3235                 xstep = xhstep;
3236                 xhstep /= 2;
3237                 ystep = yhstep;
3238                 yhstep /= 2;
3239
3240                 /* cache well used values */
3241                 xstep2 = xstep / 256;
3242                 ystep2 = ystep / 256;
3243
3244                 xhstep2 = xhstep / 256;
3245                 yhstep2 = yhstep / 256;
3246
3247                 /* middle top to bottom. */
3248                 for (i = xhstep; i <= xxsize - xhstep; i += xstep)
3249                 {
3250                         for (j = 0; j <= yysize; j += ystep)
3251                         {
3252                                 /* cache often used values */
3253                                 ii = i / 256 + fill_data.xmin;
3254                                 jj = j / 256 + fill_data.ymin;
3255
3256                                 /* Test square */
3257                                 if (cave[jj][ii].feat == 255)
3258                                 {
3259                                         if (xhstep2 > grd)
3260                                         {
3261                                                 /* If greater than 'grid' level then is random */
3262                                                 store_height(ii, jj, randint1(maxsize));
3263                                         }
3264                                         else
3265                                         {
3266                                                 /* Average of left and right points +random bit */
3267                                                 store_height(ii, jj,
3268                                                         (cave[jj][fill_data.xmin + (i - xhstep) / 256].feat
3269                                                          + cave[jj][fill_data.xmin + (i + xhstep) / 256].feat) / 2
3270                                                          + (randint1(xstep2) - xhstep2) * roug / 16);
3271                                         }
3272                                 }
3273                         }
3274                 }
3275
3276
3277                 /* middle left to right. */
3278                 for (j = yhstep; j <= yysize - yhstep; j += ystep)
3279                 {
3280                         for (i = 0; i <= xxsize; i += xstep)
3281                         {
3282                                 /* cache often used values */
3283                                 ii = i / 256 + fill_data.xmin;
3284                                 jj = j / 256 + fill_data.ymin;
3285
3286                                 /* Test square */
3287                                 if (cave[jj][ii].feat == 255)
3288                                 {
3289                                         if (xhstep2 > grd)
3290                                         {
3291                                                 /* If greater than 'grid' level then is random */
3292                                                 store_height(ii, jj, randint1(maxsize));
3293                                         }
3294                                         else
3295                                         {
3296                                                 /* Average of up and down points +random bit */
3297                                                 store_height(ii, jj,
3298                                                         (cave[fill_data.ymin + (j - yhstep) / 256][ii].feat
3299                                                         + cave[fill_data.ymin + (j + yhstep) / 256][ii].feat) / 2
3300                                                         + (randint1(ystep2) - yhstep2) * roug / 16);
3301                                         }
3302                                 }
3303                         }
3304                 }
3305
3306                 /* center. */
3307                 for (i = xhstep; i <= xxsize - xhstep; i += xstep)
3308                 {
3309                         for (j = yhstep; j <= yysize - yhstep; j += ystep)
3310                         {
3311                                 /* cache often used values */
3312                                 ii = i / 256 + fill_data.xmin;
3313                                 jj = j / 256 + fill_data.ymin;
3314
3315                                 /* Test square */
3316                                 if (cave[jj][ii].feat == 255)
3317                                 {
3318                                         if (xhstep2 > grd)
3319                                         {
3320                                                 /* If greater than 'grid' level then is random */
3321                                                 store_height(ii, jj, randint1(maxsize));
3322                                         }
3323                                         else
3324                                         {
3325                                                 /* Cache reused values. */
3326                                                 xm = fill_data.xmin + (i - xhstep) / 256;
3327                                                 xp = fill_data.xmin + (i + xhstep) / 256;
3328                                                 ym = fill_data.ymin + (j - yhstep) / 256;
3329                                                 yp = fill_data.ymin + (j + yhstep) / 256;
3330
3331                                                 /*
3332                                                  * Average over all four corners + scale by diagsize to
3333                                                  * reduce the effect of the square grid on the shape of the fractal
3334                                                  */
3335                                                 store_height(ii, jj,
3336                                                         (cave[ym][xm].feat + cave[yp][xm].feat
3337                                                         + cave[ym][xp].feat + cave[yp][xp].feat) / 4
3338                                                         + (randint1(xstep2) - xhstep2) * (diagsize / 16) / 256 * roug);
3339                                         }
3340                                 }
3341                         }
3342                 }
3343         }
3344 }
3345
3346
3347 static bool hack_isnt_wall(int y, int x, int c1, int c2, int c3, int feat1, int feat2, int feat3, int info1, int info2, int info3)
3348 {
3349         /*
3350          * function used to convert from height-map back to the
3351          *  normal angband cave format
3352          */
3353         if (cave[y][x].info & CAVE_ICKY)
3354         {
3355                 /* already done */
3356                 return FALSE;
3357         }
3358         else
3359         {
3360                 /* Show that have looked at this square */
3361                 cave[y][x].info|= (CAVE_ICKY);
3362
3363                 /* Use cutoffs c1-c3 to allocate regions of floor /water/ lava etc. */
3364                 if (cave[y][x].feat <= c1)
3365                 {
3366                         /* 25% of the time use the other tile : it looks better this way */
3367                         if (randint1(100) < 75)
3368                         {
3369                                 cave[y][x].feat = feat1;
3370                                 cave[y][x].info &= ~(CAVE_MASK);
3371                                 cave[y][x].info |= info1;
3372                                 return TRUE;
3373                         }
3374                         else
3375                         {
3376                                 cave[y][x].feat = feat2;
3377                                 cave[y][x].info &= ~(CAVE_MASK);
3378                                 cave[y][x].info |= info2;
3379                                 return TRUE;
3380                         }
3381                 }
3382                 else if (cave[y][x].feat <= c2)
3383                 {
3384                         /* 25% of the time use the other tile : it looks better this way */
3385                         if (randint1(100) < 75)
3386                         {
3387                                 cave[y][x].feat = feat2;
3388                                 cave[y][x].info &= ~(CAVE_MASK);
3389                                 cave[y][x].info |= info2;
3390                                 return TRUE;
3391                         }
3392                         else
3393                         {
3394                                 cave[y][x].feat = feat1;
3395                                 cave[y][x].info &= ~(CAVE_MASK);
3396                                 cave[y][x].info |= info1;
3397                                 return TRUE;
3398                         }
3399                 }
3400                 else if (cave[y][x].feat <= c3)
3401                 {
3402                         cave[y][x].feat = feat3;
3403                         cave[y][x].info |= info3;
3404                         return TRUE;
3405                 }
3406                 /* if greater than cutoff then is a wall */
3407                 else
3408                 {
3409                         place_outer_bold(y, x);
3410                         return FALSE;
3411                 }
3412         }
3413 }
3414
3415
3416
3417
3418 /*
3419  * Quick and nasty fill routine used to find the connected region
3420  * of floor in the middle of the cave
3421  */
3422 static void cave_fill(byte y, byte x)
3423 {
3424         int i, j, d;
3425         int ty, tx;
3426
3427         int flow_tail = 1;
3428         int flow_head = 0;
3429
3430
3431         /*** Start Grid ***/
3432
3433         /* Enqueue that entry */
3434         temp_y[0] = y;
3435         temp_x[0] = x;
3436
3437
3438         /* Now process the queue */
3439         while (flow_head != flow_tail)
3440         {
3441                 /* Extract the next entry */
3442                 ty = temp_y[flow_head];
3443                 tx = temp_x[flow_head];
3444
3445                 /* Forget that entry */
3446                 if (++flow_head == TEMP_MAX) flow_head = 0;
3447
3448                 /* Add the "children" */
3449                 for (d = 0; d < 8; d++)
3450                 {
3451                         int old_head = flow_tail;
3452
3453                         /* Child location */
3454                         j = ty + ddy_ddd[d];
3455                         i = tx + ddx_ddd[d];
3456
3457                         /* Paranoia Don't leave the cave */
3458                         if (!in_bounds(j, i))
3459                         {
3460                                 /* affect boundary */
3461                                 cave[j][i].info |= CAVE_ICKY;
3462 /*                              return; */
3463                         }
3464
3465                         /* If within bounds */
3466                         else if ((i > fill_data.xmin) && (i < fill_data.xmax)
3467                                 && (j > fill_data.ymin) && (j < fill_data.ymax))
3468                         {
3469                                 /* If not a wall or floor done before */
3470                                 if (hack_isnt_wall(j, i,
3471                                         fill_data.c1, fill_data.c2, fill_data.c3,
3472                                         fill_data.feat1, fill_data.feat2, fill_data.feat3,
3473                                         fill_data.info1, fill_data.info2, fill_data.info3))
3474                                 {
3475                                         /* Enqueue that entry */
3476                                         temp_y[flow_tail] = j;
3477                                         temp_x[flow_tail] = i;
3478
3479                                         /* Advance the queue */
3480                                         if (++flow_tail == TEMP_MAX) flow_tail = 0;
3481
3482                                         /* Hack -- Overflow by forgetting new entry */
3483                                         if (flow_tail == flow_head)
3484                                         {
3485                                                 flow_tail = old_head;
3486                                         }
3487                                         else
3488                                         {
3489                                                 /* keep tally of size of cave system */
3490                                                 (fill_data.amount)++;
3491                                         }
3492                                 }
3493                         }
3494                         else
3495                         {
3496                                 /* affect boundary */
3497                                 cave[j][i].info |= CAVE_ICKY;
3498                         }
3499                 }
3500         }
3501 }
3502
3503
3504 static bool generate_fracave(int y0, int x0, int xsize, int ysize, int cutoff, bool light, bool room)
3505 {
3506         int x, y, i, xhsize, yhsize;
3507
3508
3509         /* offsets to middle from corner */
3510         xhsize = xsize / 2;
3511         yhsize = ysize / 2;
3512
3513
3514         /*
3515          * select region connected to center of cave system
3516          * this gets rid of alot of isolated one-sqaures that
3517          * can make teleport traps instadeaths...
3518          */
3519
3520         /* cutoffs */
3521         fill_data.c1 = cutoff;
3522         fill_data.c2 = 0;
3523         fill_data.c3 = 0;
3524
3525         /* features to fill with */
3526         fill_data.feat1 = floor_type[randint0(100)];
3527         fill_data.feat2 = floor_type[randint0(100)];
3528         fill_data.feat3 = floor_type[randint0(100)];
3529
3530         fill_data.info1 = CAVE_FLOOR;
3531         fill_data.info2 = CAVE_FLOOR;
3532         fill_data.info3 = CAVE_FLOOR;
3533
3534         /* number of filled squares */
3535         fill_data.amount = 0;
3536
3537         cave_fill((byte)y0, (byte)x0);
3538
3539         /* if tally too small, try again */
3540         if (fill_data.amount < 10)
3541         {
3542                 /* too small - clear area and try again later */
3543                 for (x = 0; x <= xsize; ++x)
3544                 {
3545                         for (y = 0; y <= ysize; ++y)
3546                         {
3547                                 place_extra_bold(y0 + y - yhsize, x0 + x - xhsize);
3548                                 cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~(CAVE_ICKY | CAVE_ROOM);
3549                         }
3550                 }
3551                 return FALSE;
3552         }
3553
3554         /*
3555          * Do boundarys-check to see if they are next to a filled region
3556          * If not then they are set to normal granite
3557          * If so then they are marked as room walls.
3558          */
3559         for (i = 0; i <= xsize; ++i)
3560         {
3561                 /* top boundary */
3562                 if ((cave[0 + y0 - yhsize][i + x0 - xhsize].info & CAVE_ICKY) && (room))
3563                 {
3564                         /* Next to a 'filled' region? - set to be room walls */
3565                         place_outer_bold(y0 + 0 - yhsize, x0 + i - xhsize);
3566                         if (light) cave[y0 + 0 - yhsize][x0 + i - xhsize].info |= (CAVE_GLOW);
3567                         cave[y0 + 0 - yhsize][x0 + i - xhsize].info |= (CAVE_ROOM);
3568                         place_outer_bold(y0 + 0 - yhsize, x0 + i - xhsize);
3569                 }
3570                 else
3571                 {
3572                         /* set to be normal granite */
3573                         place_extra_bold(y0 + 0 - yhsize, x0 + i - xhsize);
3574                 }
3575
3576                 /* bottom boundary */
3577                 if ((cave[ysize + y0 - yhsize][i + x0 - xhsize].info & CAVE_ICKY) && (room))
3578                 {
3579                         /* Next to a 'filled' region? - set to be room walls */
3580                         place_outer_bold(y0 + ysize - yhsize, x0 + i - xhsize);
3581                         if (light) cave[y0 + ysize - yhsize][x0 + i - xhsize].info|=(CAVE_GLOW);
3582                         cave[y0 + ysize - yhsize][x0 + i - xhsize].info|=(CAVE_ROOM);
3583                         place_outer_bold(y0 + ysize - yhsize, x0 + i - xhsize);
3584                 }
3585                 else
3586                 {
3587                         /* set to be normal granite */
3588                         place_extra_bold(y0 + ysize - yhsize, x0 + i - xhsize);
3589                 }
3590
3591                 /* clear the icky flag-don't need it any more */
3592                 cave[y0 + 0 - yhsize][x0 + i - xhsize].info &= ~(CAVE_ICKY);
3593                 cave[y0 + ysize - yhsize][x0 + i - xhsize].info &= ~(CAVE_ICKY);
3594         }
3595
3596         /* Do the left and right boundaries minus the corners (done above) */
3597         for (i = 1; i < ysize; ++i)
3598         {
3599                 /* left boundary */
3600                 if ((cave[i + y0 - yhsize][0 + x0 - xhsize].info & CAVE_ICKY) && room)
3601                 {
3602                         /* room boundary */
3603                         place_outer_bold(y0 + i - yhsize, x0 + 0 - xhsize);
3604                         if (light) cave[y0 + i - yhsize][x0 + 0 - xhsize].info |= (CAVE_GLOW);
3605                         cave[y0 + i - yhsize][x0 + 0 - xhsize].info |= (CAVE_ROOM);
3606                         place_outer_bold(y0 + i - yhsize, x0 + 0 - xhsize);
3607                 }
3608                 else
3609                 {
3610                         /* outside room */
3611                         place_extra_bold(y0 + i - yhsize, x0 + 0 - xhsize);
3612                 }
3613                 /* right boundary */
3614                 if ((cave[i + y0 - yhsize][xsize + x0 - xhsize].info & CAVE_ICKY) && room)
3615                 {
3616                         /* room boundary */
3617                         place_outer_bold(y0 + i - yhsize, x0 + xsize - xhsize);
3618                         if (light) cave[y0 + i - yhsize][x0 + xsize - xhsize].info |= (CAVE_GLOW);
3619                         cave[y0 + i - yhsize][x0 + xsize - xhsize].info |= (CAVE_ROOM);
3620                         place_outer_bold(y0 + i - yhsize, x0 + xsize - xhsize);
3621                 }
3622                 else
3623                 {
3624                         /* outside room */
3625                         place_extra_bold(y0 + i - yhsize, x0 + xsize - xhsize);
3626                 }
3627
3628                 /* clear icky flag -done with it */
3629                 cave[y0 + i - yhsize][x0 + 0 - xhsize].info &= ~(CAVE_ICKY);
3630                 cave[y0 + i - yhsize][x0 + xsize - xhsize].info &= ~(CAVE_ICKY);
3631         }
3632
3633
3634         /* Do the rest: convert back to the normal format */
3635         for (x = 1; x < xsize; ++x)
3636         {
3637                 for (y = 1; y < ysize; ++y)
3638                 {
3639                         if (is_floor_bold(y0 + y - yhsize, x0 + x - xhsize) &&
3640                             (cave[y0 + y - yhsize][x0 + x - xhsize].info & CAVE_ICKY))
3641                         {
3642                                 /* Clear the icky flag in the filled region */
3643                                 cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~CAVE_ICKY;
3644
3645                                 /* Set appropriate flags */
3646                                 if (light) cave[y0 + y - yhsize][x0 + x - xhsize].info |= (CAVE_GLOW);
3647                                 if (room) cave[y0 + y - yhsize][x0 + x - xhsize].info |= (CAVE_ROOM);
3648                         }
3649                         else if (is_outer_bold(y0 + y - yhsize, x0 + x - xhsize) &&
3650                                  (cave[y0 + y - yhsize][x0 + x - xhsize].info & CAVE_ICKY))
3651                         {
3652                                 /* Walls */
3653                                 cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~(CAVE_ICKY);
3654                                 if (light) cave[y0 + y - yhsize][x0 + x - xhsize].info |= (CAVE_GLOW);
3655                                 if (room)
3656                                 {
3657                                         cave[y0 + y - yhsize][x0 + x - xhsize].info |= (CAVE_ROOM);
3658                                 }
3659                                 else
3660                                 {
3661
3662                                         place_extra_bold(y0 + y - yhsize, x0 + x - xhsize);
3663                                         cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~(CAVE_ROOM);
3664                                 }
3665                         }
3666                         else
3667                         {
3668                                 /* Clear the unconnected regions */
3669                                 place_extra_bold(y0 + y - yhsize, x0 + x - xhsize);
3670                                 cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~(CAVE_ICKY | CAVE_ROOM);
3671                         }
3672                 }
3673         }
3674
3675         /*
3676          * XXX XXX XXX There is a slight problem when tunnels pierce the caves:
3677          * Extra doors appear inside the system.  (Its not very noticeable though.)
3678          * This can be removed by "filling" from the outside in.  This allows a separation
3679          * from FEAT_WALL_OUTER with FEAT_WALL_INNER.  (Internal walls are  F.W.OUTER instead.)
3680          * The extra effort for what seems to be only a minor thing (even non-existant if you
3681          * think of the caves not as normal rooms, but as holes in the dungeon), doesn't seem
3682          * worth it.
3683          */
3684
3685         return TRUE;
3686 }
3687
3688
3689 /*
3690  * Driver routine to create fractal cave system
3691  */
3692 static bool build_type9(void)
3693 {
3694         int grd, roug, cutoff, xsize, ysize, y0, x0;
3695
3696         bool done, light, room;
3697
3698         /* get size: note 'Evenness'*/
3699         xsize = randint1(22) * 2 + 6;
3700         ysize = randint1(15) * 2 + 6;
3701
3702         /* Find and reserve some space in the dungeon.  Get center of room. */
3703         if (!find_space(&y0, &x0, ysize + 1, xsize + 1)) return FALSE;
3704
3705         light = done = FALSE;
3706         room = TRUE;
3707
3708         if ((dun_level <= randint1(25)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS)) light = TRUE;
3709
3710         while (!done)
3711         {
3712                 /* Note: size must be even or there are rounding problems
3713                 * This causes the tunnels not to connect properly to the room */
3714
3715                 /* testing values for these parameters feel free to adjust */
3716                 grd = 1 << (randint0(4));
3717
3718                 /* want average of about 16 */
3719                 roug = randint1(8) * randint1(4);
3720
3721                 /* about size/2 */
3722                 cutoff = randint1(xsize / 4) + randint1(ysize / 4) +
3723                          randint1(xsize / 4) + randint1(ysize / 4);
3724
3725                 /* make it */
3726                 generate_hmap(y0, x0, xsize, ysize, grd, roug, cutoff);
3727
3728                 /* Convert to normal format + clean up */
3729                 done = generate_fracave(y0, x0, xsize, ysize, cutoff, light, room);
3730         }
3731
3732         return TRUE;
3733 }
3734
3735 #ifdef ALLOW_CAVERNS_AND_LAKES
3736 /*
3737  * Builds a cave system in the center of the dungeon.
3738  */
3739 void build_cavern(void)
3740 {
3741         int grd, roug, cutoff, xsize, ysize, x0, y0;
3742         bool done, light;
3743
3744         light = done = FALSE;
3745         if ((dun_level <= randint1(50)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS)) light = TRUE;
3746
3747         /* Make a cave the size of the dungeon */
3748         xsize = cur_wid - 1;
3749         ysize = cur_hgt - 1;
3750         x0 = xsize / 2;
3751         y0 = ysize / 2;
3752
3753         /* Paranoia: make size even */
3754         xsize = x0 * 2;
3755         ysize = y0 * 2;
3756
3757         while (!done)
3758         {
3759                 /* testing values for these parameters: feel free to adjust */
3760                 grd = randint1(4) + 4;
3761
3762                 /* want average of about 16 */
3763                 roug = randint1(8) * randint1(4);
3764
3765                 /* about size/2 */
3766                 cutoff = xsize / 2;
3767
3768                  /* make it */
3769                 generate_hmap(y0 + 1, x0 + 1, xsize, ysize, grd, roug, cutoff);
3770
3771                 /* Convert to normal format+ clean up */
3772                 done = generate_fracave(y0 + 1, x0 + 1, xsize, ysize, cutoff, light, FALSE);
3773         }
3774 }
3775
3776 static bool generate_lake(int y0, int x0, int xsize, int ysize, int c1, int c2, int c3, int type)
3777 {
3778         int x, y, i, xhsize, yhsize;
3779         int feat1, feat2, feat3;
3780
3781         /* offsets to middle from corner */
3782         xhsize = xsize / 2;
3783         yhsize = ysize / 2;
3784
3785         /* Get features based on type */
3786         switch (type)
3787         {
3788         case LAKE_T_LAVA: /* Lava */
3789                 feat1 = FEAT_DEEP_LAVA;
3790                 feat2 = FEAT_SHAL_LAVA;
3791                 feat3 = floor_type[randint0(100)];
3792                 break;
3793         case LAKE_T_WATER: /* Water */
3794                 feat1 = FEAT_DEEP_WATER;
3795                 feat2 = FEAT_SHAL_WATER;
3796                 feat3 = floor_type[randint0(100)];
3797                 break;
3798         case LAKE_T_CAVE: /* Collapsed cave */
3799                 feat1 = floor_type[randint0(100)];
3800                 feat2 = floor_type[randint0(100)];
3801                 feat3 = FEAT_RUBBLE;
3802                 break;
3803         case LAKE_T_EARTH_VAULT: /* Earth vault */
3804                 feat1 = FEAT_RUBBLE;
3805                 feat2 = floor_type[randint0(100)];
3806                 feat3 = FEAT_RUBBLE;
3807                 break;
3808         case LAKE_T_AIR_VAULT: /* Air vault */
3809                 feat1 = FEAT_GRASS;
3810                 feat2 = FEAT_TREES;
3811                 feat3 = FEAT_GRASS;
3812                 break;
3813         case LAKE_T_WATER_VAULT: /* Water vault */
3814                 feat1 = FEAT_SHAL_WATER;
3815                 feat2 = FEAT_DEEP_WATER;
3816                 feat3 = FEAT_SHAL_WATER;
3817                 break;
3818         case LAKE_T_FIRE_VAULT: /* Fire Vault */
3819                 feat1 = FEAT_SHAL_LAVA;
3820                 feat2 = FEAT_DEEP_LAVA;
3821                 feat3 = FEAT_SHAL_LAVA;
3822                 break;
3823
3824         /* Paranoia */
3825         default: return FALSE;
3826         }
3827
3828         /*
3829          * select region connected to center of cave system
3830          * this gets rid of alot of isolated one-sqaures that
3831          * can make teleport traps instadeaths...
3832          */
3833
3834         /* cutoffs */
3835         fill_data.c1 = c1;
3836         fill_data.c2 = c2;
3837         fill_data.c3 = c3;
3838
3839         /* features to fill with */
3840         fill_data.feat1 = feat1;
3841         fill_data.feat2 = feat2;
3842         fill_data.feat3 = feat3;
3843
3844         fill_data.info1 = 0;
3845         fill_data.info2 = 0;
3846         fill_data.info3 = 0;
3847
3848         /* number of filled squares */
3849         fill_data.amount = 0;
3850
3851         /* select region connected to center of cave system
3852         * this gets rid of alot of isolated one-sqaures that
3853         * can make teleport traps instadeaths... */
3854         cave_fill((byte)y0, (byte)x0);
3855
3856         /* if tally too small, try again */
3857         if (fill_data.amount < 10)
3858         {
3859                 /* too small -clear area and try again later */
3860                 for (x = 0; x <= xsize; ++x)
3861                 {
3862                         for (y = 0; y <= ysize; ++y)
3863                         {
3864                                 place_floor_bold(y0 + y - yhsize, x0 + x - xhsize);
3865                                 cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~(CAVE_ICKY);
3866                         }
3867                 }
3868                 return FALSE;
3869         }
3870
3871         /* Do boundarys- set to normal granite */
3872         for (i = 0; i <= xsize; ++i)
3873         {
3874                 place_extra_bold(y0 + 0 - yhsize, x0 + i - xhsize);
3875                 place_extra_bold(y0 + ysize - yhsize, x0 + i - xhsize);
3876
3877                 /* clear the icky flag-don't need it any more */
3878                 cave[y0 + 0 - yhsize][x0 + i - xhsize].info &= ~(CAVE_ICKY);
3879                 cave[y0 + ysize - yhsize][x0 + i - xhsize].info &= ~(CAVE_ICKY);
3880         }
3881
3882         /* Do the left and right boundaries minus the corners (done above) */
3883
3884         for (i = 1; i < ysize; ++i)
3885         {
3886                 place_extra_bold(y0 + i - yhsize, x0 + 0 - xhsize);
3887                 place_extra_bold(y0 + i - yhsize, x0 + xsize - xhsize);
3888
3889                 /* clear icky flag -done with it */
3890                 cave[y0 + i - yhsize][x0 + 0 - xhsize].info &= ~(CAVE_ICKY);
3891                 cave[y0 + i - yhsize][x0 + xsize - xhsize].info &= ~(CAVE_ICKY);
3892         }
3893
3894
3895         /* Do the rest: convert back to the normal format */
3896         for (x = 1; x < xsize; ++x)
3897         {
3898                 for (y = 1; y < ysize; ++y)
3899                 {
3900                         /* Fill unconnected regions with granite */
3901                         if ((!(cave[y0 + y - yhsize][x0 + x - xhsize].info & CAVE_ICKY)) ||
3902                                 is_outer_bold(y0 + y - yhsize, x0 + x - xhsize))
3903                                 place_extra_bold(y0 + y - yhsize, x0 + x - xhsize);
3904
3905                         /* turn off icky flag (no longer needed.) */
3906                         cave[y0 + y - yhsize][x0 + x - xhsize].info &= ~(CAVE_ICKY | CAVE_ROOM);
3907
3908                         /* Light lava and trees */
3909                         if ((cave[y0 + y - yhsize][x0 + x - xhsize].feat == FEAT_DEEP_LAVA) ||
3910                                 (cave[y0 + y - yhsize][x0 + x - xhsize].feat == FEAT_SHAL_LAVA))
3911                         {
3912                                 if (!(d_info[dungeon_type].flags1 & DF1_DARKNESS)) cave[y0 + y - yhsize][x0 + x - xhsize].info |= CAVE_GLOW;
3913                         }
3914                 }
3915         }
3916
3917         return TRUE;
3918 }
3919
3920
3921 /*
3922  * makes a lake/collapsed cave system in the center of the dungeon
3923  */
3924 void build_lake(int type)
3925 {
3926         int grd, roug, xsize, ysize, x0, y0;
3927         bool done = FALSE;
3928         int c1, c2, c3;
3929
3930         /* paranoia - exit if lake type out of range. */
3931         if ((type < LAKE_T_LAVA) || (type > LAKE_T_FIRE_VAULT))
3932         {
3933                 msg_format("Invalid lake type (%d)", type);
3934                 return;
3935         }
3936
3937         /* Make the size of the dungeon */
3938         xsize = cur_wid - 1;
3939         ysize = cur_hgt - 1;
3940         x0 = xsize / 2;
3941         y0 = ysize / 2;
3942
3943         /* Paranoia: make size even */
3944         xsize = x0 * 2;
3945         ysize = y0 * 2;
3946
3947         while (!done)
3948         {
3949                 /* testing values for these parameters: feel free to adjust */
3950                 grd = randint1(3) + 4;
3951
3952                 /* want average of about 16 */
3953                 roug = randint1(8) * randint1(4);
3954
3955                 /* Make up size of various componants */
3956                 /* Floor */
3957                 c3 = 3 * xsize / 4;
3958
3959                 /* Deep water/lava */
3960                 c1 = randint0(c3 / 2) + randint0(c3 / 2) - 5;
3961
3962                 /* Shallow boundary */
3963                 c2 = (c1 + c3) / 2;
3964
3965                 /* make it */
3966                 generate_hmap(y0 + 1, x0 + 1, xsize, ysize, grd, roug, c3);
3967
3968                 /* Convert to normal format+ clean up */
3969                 done = generate_lake(y0 + 1, x0 + 1, xsize, ysize, c1, c2, c3, type);
3970         }
3971 }
3972 #endif /* ALLOW_CAVERNS_AND_LAKES */
3973
3974
3975 /*
3976  * Routine used by the random vault creators to add a door to a location
3977  * Note that range checking has to be done in the calling routine.
3978  *
3979  * The doors must be INSIDE the allocated region.
3980  */
3981 static void add_door(int x, int y)
3982 {
3983         /* Need to have a wall in the center square */
3984         if (!is_outer_bold(y, x)) return;
3985
3986         /* look at:
3987          *  x#x
3988          *  .#.
3989          *  x#x
3990          *
3991          *  where x=don't care
3992          *  .=floor, #=wall
3993          */
3994
3995         if (is_floor_bold(y-1,x) && is_floor_bold(y+1,x) &&
3996             (is_outer_bold(y, x - 1) && is_outer_bold(y, x + 1)))
3997         {
3998                 /* secret door */
3999                 place_secret_door(y, x);
4000
4001                 /* set boundarys so don't get wide doors */
4002                 place_solid_bold(y, x - 1);
4003                 place_solid_bold(y, x + 1);
4004         }
4005
4006
4007         /* look at:
4008          *  x#x
4009          *  .#.
4010          *  x#x
4011          *
4012          *  where x = don't care
4013          *  .=floor, #=wall
4014          */
4015         if (is_outer_bold(y - 1, x) && is_outer_bold(y + 1, x) &&
4016             is_floor_bold(y,x-1) && is_floor_bold(y,x+1))
4017         {
4018                 /* secret door */
4019                 place_secret_door(y, x);
4020
4021                 /* set boundarys so don't get wide doors */
4022                 place_solid_bold(y - 1, x);
4023                 place_solid_bold(y + 1, x);
4024         }
4025 }
4026
4027
4028 /*
4029  * Routine that fills the empty areas of a room with treasure and monsters.
4030  */
4031 static void fill_treasure(int x1, int x2, int y1, int y2, int difficulty)
4032 {
4033         int x, y, cx, cy, size;
4034         s32b value;
4035
4036         /* center of room:*/
4037         cx = (x1 + x2) / 2;
4038         cy = (y1 + y2) / 2;
4039
4040         /* Rough measure of size of vault= sum of lengths of sides */
4041         size = abs(x2 - x1) + abs(y2 - y1);
4042
4043         for (x = x1; x <= x2; x++)
4044         {
4045                 for (y = y1; y <= y2; y++)
4046                 {
4047                         /* Thing added based on distance to center of vault
4048                          * Difficulty is 1-easy to 10-hard */
4049                         value = ((((s32b)(distance(cx, cy, x, y))) * 100) / size) + randint1(10) - difficulty;
4050
4051                         /* hack- empty square part of the time */
4052                         if ((randint1(100) - difficulty * 3) > 50) value = 20;
4053
4054                          /* if floor, shallow water and lava */
4055                         if (is_floor_bold(y, x) ||
4056                             (cave[y][x].feat == FEAT_SHAL_WATER) ||
4057                             (cave[y][x].feat == FEAT_SHAL_LAVA))
4058                         {
4059                                 /* The smaller 'value' is, the better the stuff */
4060                                 if (value < 0)
4061                                 {
4062                                         /* Meanest monster + treasure */
4063                                         monster_level = base_level + 40;
4064                                         place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
4065                                         monster_level = base_level;
4066                                         object_level = base_level + 20;
4067                                         place_object(y, x, AM_GOOD);
4068                                         object_level = base_level;
4069                                 }
4070                                 else if (value < 5)
4071                                 {
4072                                         /* Mean monster +treasure */
4073                                         monster_level = base_level + 20;
4074                                         place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
4075                                         monster_level = base_level;
4076                                         object_level = base_level + 10;
4077                                         place_object(y, x, AM_GOOD);
4078                                         object_level = base_level;
4079                                 }
4080                                 else if (value < 10)
4081                                 {
4082                                         /* Monster */
4083                                         monster_level = base_level + 9;
4084                                         place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
4085                                         monster_level = base_level;
4086                                 }
4087                                 else if (value < 17)
4088                                 {
4089                                         /* Intentional Blank space */
4090
4091                                         /*
4092                                          * (Want some of the vault to be empty
4093                                          * so have room for group monsters.
4094                                          * This is used in the hack above to lower
4095                                          * the density of stuff in the vault.)
4096                                          */
4097                                 }
4098                                 else if (value < 23)
4099                                 {
4100                                         /* Object or trap */
4101                                         if (randint0(100) < 25)
4102                                         {
4103                                                 place_object(y, x, 0L);
4104                                         }
4105                                         else
4106                                         {
4107                                                 place_trap(y, x);
4108                                         }
4109                                 }
4110                                 else if (value < 30)
4111                                 {
4112                                         /* Monster and trap */
4113                                         monster_level = base_level + 5;
4114                                         place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
4115                                         monster_level = base_level;
4116                                         place_trap(y, x);
4117                                 }
4118                                 else if (value < 40)
4119                                 {
4120                                         /* Monster or object */
4121                                         if (randint0(100) < 50)
4122                                         {
4123                                                 monster_level = base_level + 3;
4124                                                 place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
4125                                                 monster_level = base_level;
4126                                         }
4127                                         if (randint0(100) < 50)
4128                                         {
4129                                                 object_level = base_level + 7;
4130                                                 place_object(y, x, 0L);
4131                                                 object_level = base_level;
4132                                         }
4133                                 }
4134                                 else if (value < 50)
4135                                 {
4136                                         /* Trap */
4137                                         place_trap(y, x);
4138                                 }
4139                                 else
4140                                 {
4141                                         /* Various Stuff */
4142
4143                                         /* 20% monster, 40% trap, 20% object, 20% blank space */
4144                                         if (randint0(100) < 20)
4145                                         {
4146                                                 place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
4147                                         }
4148                                         else if (randint0(100) < 50)
4149                                         {
4150                                                 place_trap(y, x);
4151                                         }
4152                                         else if (randint0(100) < 50)
4153                                         {
4154                                                 place_object(y, x, 0L);
4155                                         }
4156                                 }
4157
4158                         }
4159                 }
4160         }
4161 }
4162
4163
4164 /*
4165  * This function creates a random vault that looks like a collection of bubbles.
4166  * It works by getting a set of coordinates that represent the center of each
4167  * bubble.  The entire room is made by seeing which bubble center is closest. If
4168  * two centers are equidistant then the square is a wall, otherwise it is a floor.
4169  * The only exception is for squares really near a center, these are always floor.
4170  * (It looks better than without this check.)
4171  *
4172  * Note: If two centers are on the same point then this algorithm will create a
4173  *       blank bubble filled with walls. - This is prevented from happening.
4174  */
4175 static void build_bubble_vault(int x0, int y0, int xsize, int ysize)
4176 {
4177         #define BUBBLENUM 10            /* number of bubbles */
4178
4179         /* array of center points of bubbles */
4180         coord center[BUBBLENUM];
4181
4182         int i, j, x, y;
4183         u16b min1, min2, temp;
4184         bool done;
4185
4186         /* Offset from center to top left hand corner */
4187         int xhsize = xsize / 2;
4188         int yhsize = ysize / 2;
4189
4190
4191         if (cheat_room) msg_print("Bubble Vault");
4192
4193         /* Allocate center of bubbles */
4194         center[0].x = randint1(xsize - 3) + 1;
4195         center[0].y = randint1(ysize - 3) + 1;
4196
4197         for (i = 1; i < BUBBLENUM; i++)
4198         {
4199                 done = FALSE;
4200
4201                 /* get center and check to see if it is unique */
4202                 while (!done)
4203                 {
4204                         done = TRUE;
4205
4206                         x = randint1(xsize - 3) + 1;
4207                         y = randint1(ysize - 3) + 1;
4208
4209                         for (j = 0; j < i; j++)
4210                         {
4211                                 /* rough test to see if there is an overlap */
4212                                 if ((x == center[j].x) && (y == center[j].y)) done = FALSE;
4213                         }
4214                 }
4215
4216                 center[i].x = x;
4217                 center[i].y = y;
4218         }
4219
4220
4221         /* Top and bottom boundaries */
4222         for (i = 0; i < xsize; i++)
4223         {
4224                 int x = x0 - xhsize + i;
4225
4226                 place_outer_noperm_bold(y0 - yhsize + 0, x);
4227                 cave[y0 - yhsize + 0][x].info |= (CAVE_ROOM | CAVE_ICKY);
4228                 place_outer_noperm_bold(y0 - yhsize + ysize - 1, x);
4229                 cave[y0 - yhsize + ysize - 1][x].info |= (CAVE_ROOM | CAVE_ICKY);
4230         }
4231
4232         /* Left and right boundaries */
4233         for (i = 1; i < ysize - 1; i++)
4234         {
4235                 int y = y0 - yhsize + i;
4236
4237                 place_outer_noperm_bold(y, x0 - xhsize + 0);
4238                 cave[y][x0 - xhsize + 0].info |= (CAVE_ROOM | CAVE_ICKY);
4239                 place_outer_noperm_bold(y, x0 - xhsize + xsize - 1);
4240                 cave[y][x0 - xhsize + xsize - 1].info |= (CAVE_ROOM | CAVE_ICKY);
4241         }
4242
4243         /* Fill in middle with bubbles */
4244         for (x = 1; x < xsize - 1; x++)
4245         {
4246                 for (y = 1; y < ysize - 1; y++)
4247                 {
4248                         /* Get distances to two closest centers */
4249
4250                         /* initialize */
4251                         min1 = distance(x, y, center[0].x, center[0].y);
4252                         min2 = distance(x, y, center[1].x, center[1].y);
4253
4254                         if (min1 > min2)
4255                         {
4256                                 /* swap if in wrong order */
4257                                 temp = min1;
4258                                 min1 = min2;
4259                                 min2 = temp;
4260                         }
4261
4262                         /* Scan the rest */
4263                         for (i = 2; i < BUBBLENUM; i++)
4264                         {
4265                                 temp = distance(x, y, center[i].x, center[i].y);
4266
4267                                 if (temp < min1)
4268                                 {
4269                                         /* smallest */
4270                                         min2 = min1;
4271                                         min1 = temp;
4272                                 }
4273                                 else if (temp < min2)
4274                                 {
4275                                         /* second smallest */
4276                                         min2 = temp;
4277                                 }
4278                         }
4279                         if (((min2 - min1) <= 2) && (!(min1 < 3)))
4280                         {
4281                                 /* Boundary at midpoint+ not at inner region of bubble */
4282                                 place_outer_noperm_bold(y0 - yhsize + y, x0 - xhsize + x);
4283                         }
4284                         else
4285                         {
4286                                 /* middle of a bubble */
4287                                 place_floor_bold(y0 - yhsize + y, x0 - xhsize + x);
4288                         }
4289
4290                         /* clean up rest of flags */
4291                         cave[y0 - yhsize + y][x0 - xhsize + x].info |= (CAVE_ROOM | CAVE_ICKY);
4292                 }
4293         }
4294
4295         /* Try to add some random doors */
4296         for (i = 0; i < 500; i++)
4297         {
4298                 x = randint1(xsize - 3) - xhsize + x0 + 1;
4299                 y = randint1(ysize - 3) - yhsize + y0 + 1;
4300                 add_door(x, y);
4301         }
4302
4303         /* Fill with monsters and treasure, low difficulty */
4304         fill_treasure(x0 - xhsize + 1, x0 - xhsize + xsize - 2, y0 - yhsize + 1, y0 - yhsize + ysize - 2, randint1(5));
4305 }
4306
4307
4308 /*
4309  * Overlay a rectangular room given its bounds
4310  * This routine is used by build_room_vault
4311  * The area inside the walls is not touched:
4312  * only granite is removed- normal walls stay
4313  */
4314 static void build_room(int x1, int x2, int y1, int y2)
4315 {
4316         int x, y, i, xsize, ysize, temp;
4317
4318         /* Check if rectangle has no width */
4319         if ((x1 == x2) || (y1 == y2)) return;
4320
4321         /* initialize */
4322         if (x1 > x2)
4323         {
4324                 /* Swap boundaries if in wrong order */
4325                 temp = x1;
4326                 x1 = x2;
4327                 x2 = temp;
4328         }
4329
4330         if (y1 > y2)
4331         {
4332                 /* Swap boundaries if in wrong order */
4333                 temp = y1;
4334                 y1 = y2;
4335                 y2 = temp;
4336         }
4337
4338         /* get total widths */
4339         xsize = x2 - x1;
4340         ysize = y2 - y1;
4341
4342
4343         /* Top and bottom boundaries */
4344         for (i = 0; i <= xsize; i++)
4345         {
4346                 place_outer_noperm_bold(y1, x1 + i);
4347                 cave[y1][x1 + i].info |= (CAVE_ROOM | CAVE_ICKY);
4348                 place_outer_noperm_bold(y2, x1 + i);
4349                 cave[y2][x1 + i].info |= (CAVE_ROOM | CAVE_ICKY);
4350         }
4351
4352         /* Left and right boundaries */
4353         for (i = 1; i < ysize; i++)
4354         {
4355                 place_outer_noperm_bold(y1 + i, x1);
4356                 cave[y1 + i][x1].info|=(CAVE_ROOM | CAVE_ICKY);
4357                 place_outer_noperm_bold(y1 + i, x2);
4358                 cave[y1 + i][x2].info|=(CAVE_ROOM | CAVE_ICKY);
4359         }
4360
4361         /* Middle */
4362         for (x = 1; x < xsize; x++)
4363         {
4364                 for (y = 1; y < ysize; y++)
4365                 {
4366                         if (is_extra_bold(y1+y, x1+x))
4367                         {
4368                                 /* clear the untouched region */
4369                                 place_floor_bold(y1 + y, x1 + x);
4370                                 cave[y1 + y][x1 + x].info |= (CAVE_ROOM | CAVE_ICKY);
4371                         }
4372                         else
4373                         {
4374                                 /* make it a room- but don't touch */
4375                                 cave[y1 + y][x1 + x].info |= (CAVE_ROOM | CAVE_ICKY);
4376                         }
4377                 }
4378         }
4379 }
4380
4381
4382 /* Create a random vault that looks like a collection of overlapping rooms */
4383
4384 static void build_room_vault(int x0, int y0, int xsize, int ysize)
4385 {
4386         int i, x1, x2, y1, y2, xhsize, yhsize;
4387
4388         /* get offset from center */
4389         xhsize = xsize / 2;
4390         yhsize = ysize / 2;
4391
4392         if (cheat_room) msg_print("Room Vault");
4393
4394         /* fill area so don't get problems with arena levels */
4395         for (x1 = 0; x1 < xsize; x1++)
4396         {
4397                 int x = x0 - xhsize + x1;
4398
4399                 for (y1 = 0; y1 < ysize; y1++)
4400                 {
4401                         int y = y0 - yhsize + y1;
4402
4403                         place_extra_bold(y, x);
4404                         cave[y][x].info &= (~CAVE_ICKY);
4405                 }
4406         }
4407
4408         /* add ten random rooms */
4409         for (i = 0; i < 10; i++)
4410         {
4411                 x1 = randint1(xhsize) * 2 + x0 - xhsize;
4412                 x2 = randint1(xhsize) * 2 + x0 - xhsize;
4413                 y1 = randint1(yhsize) * 2 + y0 - yhsize;
4414                 y2 = randint1(yhsize) * 2 + y0 - yhsize;
4415                 build_room(x1, x2, y1, y2);
4416         }
4417
4418         /* Add some random doors */
4419         for (i = 0; i < 500; i++)
4420         {
4421                 x1 = randint1(xsize - 3) - xhsize + x0 + 1;
4422                 y1 = randint1(ysize - 3) - yhsize + y0 + 1;
4423                 add_door(x1, y1);
4424         }
4425
4426         /* Fill with monsters and treasure, high difficulty */
4427         fill_treasure(x0 - xhsize + 1, x0 - xhsize + xsize - 2, y0 - yhsize + 1, y0 - yhsize + ysize - 2, randint1(5) + 5);
4428 }
4429
4430
4431 /* Create a random vault out of a fractal cave */
4432 static void build_cave_vault(int x0, int y0, int xsiz, int ysiz)
4433 {
4434         int grd, roug, cutoff, xhsize, yhsize, xsize, ysize, x, y;
4435         bool done, light, room;
4436
4437         /* round to make sizes even */
4438         xhsize = xsiz / 2;
4439         yhsize = ysiz / 2;
4440         xsize = xhsize * 2;
4441         ysize = yhsize * 2;
4442
4443         if (cheat_room) msg_print("Cave Vault");
4444
4445         light = done = FALSE;
4446         room = TRUE;
4447
4448         while (!done)
4449         {
4450                 /* testing values for these parameters feel free to adjust */
4451                 grd = 1 << randint0(4);
4452
4453                 /* want average of about 16 */
4454                 roug = randint1(8) * randint1(4);
4455
4456                 /* about size/2 */
4457                 cutoff = randint1(xsize / 4) + randint1(ysize / 4) +
4458                          randint1(xsize / 4) + randint1(ysize / 4);
4459
4460                 /* make it */
4461                 generate_hmap(y0, x0, xsize, ysize, grd, roug, cutoff);
4462
4463                 /* Convert to normal format+ clean up */
4464                 done = generate_fracave(y0, x0, xsize, ysize, cutoff, light, room);
4465         }
4466
4467         /* Set icky flag because is a vault */
4468         for (x = 0; x <= xsize; x++)
4469         {
4470                 for (y = 0; y <= ysize; y++)
4471                 {
4472                         cave[y0 - yhsize + y][x0 - xhsize + x].info |= CAVE_ICKY;
4473                 }
4474         }
4475
4476         /* Fill with monsters and treasure, low difficulty */
4477         fill_treasure(x0 - xhsize + 1, x0 - xhsize + xsize - 1, y0 - yhsize + 1, y0 - yhsize + ysize - 1, randint1(5));
4478 }
4479
4480 /*
4481  * maze vault -- rectangular labyrinthine rooms
4482  *
4483  * maze vault uses two routines:
4484  *    r_visit - a recursive routine that builds the labyrinth
4485  *    build_maze_vault - a driver routine that calls r_visit and adds
4486  *                   monsters, traps and treasure
4487  *
4488  * The labyrinth is built by creating a spanning tree of a graph.
4489  * The graph vertices are at
4490  *    (x, y) = (2j + x1, 2k + y1)   j = 0,...,m-1    k = 0,...,n-1
4491  * and the edges are the vertical and horizontal nearest neighbors.
4492  *
4493  * The spanning tree is created by performing a suitably randomized
4494  * depth-first traversal of the graph. The only adjustable parameter
4495  * is the randint0(3) below; it governs the relative density of
4496  * twists and turns in the labyrinth: smaller number, more twists.
4497  */
4498 static void r_visit(int y1, int x1, int y2, int x2,
4499                     int node, int dir, int *visited)
4500 {
4501         int i, j, m, n, temp, x, y, adj[4];
4502
4503         /* dimensions of vertex array */
4504         m = (x2 - x1) / 2 + 1;
4505         n = (y2 - y1) / 2 + 1;
4506
4507         /* mark node visited and set it to a floor */
4508         visited[node] = 1;
4509         x = 2 * (node % m) + x1;
4510         y = 2 * (node / m) + y1;
4511         place_floor_bold(y, x);
4512
4513         /* setup order of adjacent node visits */
4514         if (one_in_(3))
4515         {
4516                 /* pick a random ordering */
4517                 for (i = 0; i < 4; i++)
4518                         adj[i] = i;
4519                 for (i = 0; i < 4; i++)
4520                 {
4521                         j = randint0(4);
4522                         temp = adj[i];
4523                         adj[i] = adj[j];
4524                         adj[j] = temp;
4525                 }
4526                 dir = adj[0];
4527         }
4528         else
4529         {
4530                 /* pick a random ordering with dir first */
4531                 adj[0] = dir;
4532                 for (i = 1; i < 4; i++)
4533                         adj[i] = i;
4534                 for (i = 1; i < 4; i++)
4535                 {
4536                         j = 1 + randint0(3);
4537                         temp = adj[i];
4538                         adj[i] = adj[j];
4539                         adj[j] = temp;
4540                 }
4541         }
4542
4543         for (i = 0; i < 4; i++)
4544         {
4545                 switch (adj[i])
4546                 {
4547                         case 0:
4548                                 /* (0,+) - check for bottom boundary */
4549                                 if ((node / m < n - 1) && (visited[node + m] == 0))
4550                                 {
4551                                         place_floor_bold(y + 1, x);
4552                                         r_visit(y1, x1, y2, x2, node + m, dir, visited);
4553                                 }
4554                                 break;
4555                         case 1:
4556                                 /* (0,-) - check for top boundary */
4557                                 if ((node / m > 0) && (visited[node - m] == 0))
4558                                 {
4559                                         place_floor_bold(y - 1, x);
4560                                         r_visit(y1, x1, y2, x2, node - m, dir, visited);
4561                                 }
4562                                 break;
4563                         case 2:
4564                                 /* (+,0) - check for right boundary */
4565                                 if ((node % m < m - 1) && (visited[node + 1] == 0))
4566                                 {
4567                                         place_floor_bold(y, x + 1);
4568                                         r_visit(y1, x1, y2, x2, node + 1, dir, visited);
4569                                 }
4570                                 break;
4571                         case 3:
4572                                 /* (-,0) - check for left boundary */
4573                                 if ((node % m > 0) && (visited[node - 1] == 0))
4574                                 {
4575                                         place_floor_bold(y, x - 1);
4576                                         r_visit(y1, x1, y2, x2, node - 1, dir, visited);
4577                                 }
4578                 } /* end switch */
4579         }
4580 }
4581
4582
4583 void build_maze_vault(int x0, int y0, int xsize, int ysize, bool is_vault)
4584 {
4585         int y, x, dy, dx;
4586         int y1, x1, y2, x2;
4587         int m, n, num_vertices, *visited;
4588         bool light;
4589         cave_type *c_ptr;
4590
4591
4592         if (cheat_room && is_vault) msg_print("Maze Vault");
4593
4594         /* Choose lite or dark */
4595         light = ((dun_level <= randint1(25)) && is_vault && !(d_info[dungeon_type].flags1 & DF1_DARKNESS));
4596
4597         /* Pick a random room size - randomized by calling routine */
4598         dy = ysize / 2 - 1;
4599         dx = xsize / 2 - 1;
4600
4601         y1 = y0 - dy;
4602         x1 = x0 - dx;
4603         y2 = y0 + dy;
4604         x2 = x0 + dx;
4605
4606         /* generate the room */
4607         for (y = y1 - 1; y <= y2 + 1; y++)
4608         {
4609                 for (x = x1 - 1; x <= x2 + 1; x++)
4610                 {
4611                         c_ptr = &cave[y][x];
4612                         c_ptr->info |= CAVE_ROOM;
4613                         if (is_vault) c_ptr->info |= CAVE_ICKY;
4614                         if ((x == x1 - 1) || (x == x2 + 1) || (y == y1 - 1) || (y == y2 + 1))
4615                         {
4616                                 place_outer_grid(c_ptr);
4617                         }
4618                         else if (!is_vault)
4619                         {
4620                                 place_extra_grid(c_ptr);
4621                         }
4622                         else
4623                         {
4624                                 place_inner_grid(c_ptr);
4625                         }
4626                         if (light) c_ptr->info |= (CAVE_GLOW);
4627                 }
4628         }
4629
4630         /* dimensions of vertex array */
4631         m = dx + 1;
4632         n = dy + 1;
4633         num_vertices = m * n;
4634
4635         /* initialize array of visited vertices */
4636         C_MAKE(visited, num_vertices, int);
4637
4638         /* traverse the graph to create a spaning tree, pick a random root */
4639         r_visit(y1, x1, y2, x2, randint0(num_vertices), 0, visited);
4640
4641         /* Fill with monsters and treasure, low difficulty */
4642         if (is_vault) fill_treasure(x1, x2, y1, y2, randint1(5));
4643
4644         C_KILL(visited, num_vertices, int);
4645 }
4646
4647
4648 /* Build a "mini" checkerboard vault
4649  *
4650  * This is done by making a permanent wall maze and setting
4651  * the diagonal sqaures of the checker board to be granite.
4652  * The vault has two entrances on opposite sides to guarantee
4653  * a way to get in even if the vault abuts a side of the dungeon.
4654  */
4655 static void build_mini_c_vault(int x0, int y0, int xsize, int ysize)
4656 {
4657         int dy, dx;
4658         int y1, x1, y2, x2, y, x, total;
4659         int m, n, num_vertices;
4660         int *visited;
4661
4662         if (cheat_room) msg_print("Mini Checker Board Vault");
4663
4664         /* Pick a random room size */
4665         dy = ysize / 2 - 1;
4666         dx = xsize / 2 - 1;
4667
4668         y1 = y0 - dy;
4669         x1 = x0 - dx;
4670         y2 = y0 + dy;
4671         x2 = x0 + dx;
4672
4673
4674         /* generate the room */
4675         for (x = x1 - 2; x <= x2 + 2; x++)
4676         {
4677                 if (!in_bounds(y1-2,x)) break;
4678
4679                 cave[y1-2][x].info |= (CAVE_ROOM | CAVE_ICKY);
4680
4681                 place_outer_noperm_bold(y1-2, x);
4682         }
4683
4684         for (x = x1 - 2; x <= x2 + 2; x++)
4685         {
4686                 if (!in_bounds(y2+2,x)) break;
4687
4688                 cave[y2+2][x].info |= (CAVE_ROOM | CAVE_ICKY);
4689
4690                 place_outer_noperm_bold(y2+2, x);
4691         }
4692
4693         for (y = y1 - 2; y <= y2 + 2; y++)
4694         {
4695                 if (!in_bounds(y,x1-2)) break;
4696
4697                 cave[y][x1-2].info |= (CAVE_ROOM | CAVE_ICKY);
4698
4699                 place_outer_noperm_bold(y, x1-2);
4700         }
4701
4702         for (y = y1 - 2; y <= y2 + 2; y++)
4703         {
4704                 if (!in_bounds(y,x2+2)) break;
4705
4706                 cave[y][x2+2].info |= (CAVE_ROOM | CAVE_ICKY);
4707
4708                 place_outer_noperm_bold(y, x2+2);
4709         }
4710
4711         for (y = y1 - 1; y <= y2 + 1; y++)
4712         {
4713                 for (x = x1 - 1; x <= x2 + 1; x++)
4714                 {
4715                         cave_type *c_ptr = &cave[y][x];
4716
4717                         c_ptr->info |= (CAVE_ROOM | CAVE_ICKY);
4718
4719                         /* Permanent walls */
4720                         c_ptr->feat = FEAT_PERM_INNER;
4721                         c_ptr->info &= ~(CAVE_MASK);
4722                         c_ptr->info |= CAVE_INNER;
4723                 }
4724         }
4725
4726
4727         /* dimensions of vertex array */
4728         m = dx + 1;
4729         n = dy + 1;
4730         num_vertices = m * n;
4731
4732         /* initialize array of visited vertices */
4733         C_MAKE(visited, num_vertices, int);
4734
4735         /* traverse the graph to create a spannng tree, pick a random root */
4736         r_visit(y1, x1, y2, x2, randint0(num_vertices), 0, visited);
4737
4738         /* Make it look like a checker board vault */
4739         for (x = x1; x <= x2; x++)
4740         {
4741                 for (y = y1; y <= y2; y++)
4742                 {
4743                         total = x - x1 + y - y1;
4744                         /* If total is odd- and is a floor then make a wall */
4745                         if ((total % 2 == 1) && is_floor_bold(y, x))
4746                         {
4747                                 place_inner_bold(y, x);
4748                         }
4749                 }
4750         }
4751
4752         /* Make a couple of entrances */
4753         if (one_in_(2))
4754         {
4755                 /* left and right */
4756                 y = randint1(dy) + dy / 2;
4757                 place_inner_bold(y1 + y, x1 - 1);
4758                 place_inner_bold(y1 + y, x2 + 1);
4759         }
4760         else
4761         {
4762                 /* top and bottom */
4763                 x = randint1(dx) + dx / 2;
4764                 place_inner_bold(y1 - 1, x1 + x);
4765                 place_inner_bold(y2 + 1, x1 + x);
4766         }
4767
4768         /* Fill with monsters and treasure, highest difficulty */
4769         fill_treasure(x1, x2, y1, y2, 10);
4770
4771         C_KILL(visited, num_vertices, int);
4772 }
4773
4774
4775 /* Build a town/ castle by using a recursive algorithm.
4776  * Basically divide each region in a probalistic way to create
4777  * smaller regions.  When the regions get too small stop.
4778  *
4779  * The power variable is a measure of how well defended a region is.
4780  * This alters the possible choices.
4781  */
4782 static void build_recursive_room(int x1, int y1, int x2, int y2, int power)
4783 {
4784         int xsize, ysize;
4785         int x, y;
4786         int choice;
4787
4788         /* Temp variables */
4789         int t1, t2, t3, t4;
4790
4791         xsize = x2 - x1;
4792         ysize = y2 - y1;
4793
4794         if ((power < 3) && (xsize > 12) && (ysize > 12))
4795         {
4796                 /* Need outside wall +keep */
4797                 choice = 1;
4798         }
4799         else
4800         {
4801                 if (power < 10)
4802                 {
4803                         /* Make rooms + subdivide */
4804                         if ((randint1(10) > 2) && (xsize < 8) && (ysize < 8))
4805                         {
4806                                 choice = 4;
4807                         }
4808                         else
4809                         {
4810                                 choice = randint1(2) + 1;
4811                         }
4812                 }
4813                 else
4814                 {
4815                         /* Mostly subdivide */
4816                         choice = randint1(3) + 1;
4817                 }
4818         }
4819
4820         /* Based on the choice made above, do something */
4821
4822         switch (choice)
4823         {
4824                 case 1:
4825                 {
4826                         /* Outer walls */
4827
4828                         /* top and bottom */
4829                         for (x = x1; x <= x2; x++)
4830                         {
4831                                 place_outer_bold(y1, x);
4832                                 place_outer_bold(y2, x);
4833                         }
4834
4835                         /* left and right */
4836                         for (y = y1 + 1; y < y2; y++)
4837                         {
4838                                 place_outer_bold(y, x1);
4839                                 place_outer_bold(y, x2);
4840                         }
4841
4842                         /* Make a couple of entrances */
4843                         if (one_in_(2))
4844                         {
4845                                 /* left and right */
4846                                 y = randint1(ysize) + y1;
4847                                 place_floor_bold(y, x1);
4848                                 place_floor_bold(y, x2);
4849                         }
4850                         else
4851                         {
4852                                 /* top and bottom */
4853                                 x = randint1(xsize) + x1;
4854                                 place_floor_bold(y1, x);
4855                                 place_floor_bold(y2, x);
4856                         }
4857
4858                         /* Select size of keep */
4859                         t1 = randint1(ysize / 3) + y1;
4860                         t2 = y2 - randint1(ysize / 3);
4861                         t3 = randint1(xsize / 3) + x1;
4862                         t4 = x2 - randint1(xsize / 3);
4863
4864                         /* Do outside areas */
4865
4866                         /* Above and below keep */
4867                         build_recursive_room(x1 + 1, y1 + 1, x2 - 1, t1, power + 1);
4868                         build_recursive_room(x1 + 1, t2, x2 - 1, y2, power + 1);
4869
4870                         /* Left and right of keep */
4871                         build_recursive_room(x1 + 1, t1 + 1, t3, t2 - 1, power + 3);
4872                         build_recursive_room(t4, t1 + 1, x2 - 1, t2 - 1, power + 3);
4873
4874                         /* Make the keep itself: */
4875                         x1 = t3;
4876                         x2 = t4;
4877                         y1 = t1;
4878                         y2 = t2;
4879                         xsize = x2 - x1;
4880                         ysize = y2 - y1;
4881                         power += 2;
4882
4883                         /* Fall through */
4884                 }
4885                 case 4:
4886                 {
4887                         /* Try to build a room */
4888                         if ((xsize < 3) || (ysize < 3))
4889                         {
4890                                 for (y = y1; y < y2; y++)
4891                                 {
4892                                         for (x = x1; x < x2; x++)
4893                                         {
4894                                                 place_inner_bold(y, x);
4895                                         }
4896                                 }
4897
4898                                 /* Too small */
4899                                 return;
4900                         }
4901
4902                         /* Make outside walls */
4903                         /* top and bottom */
4904                         for (x = x1 + 1; x <= x2 - 1; x++)
4905                         {
4906                                 place_inner_bold(y1 + 1, x);
4907                                 place_inner_bold(y2 - 1, x);
4908                         }
4909
4910                         /* left and right */
4911                         for (y = y1 + 1; y <= y2 - 1; y++)
4912                         {
4913                                 place_inner_bold(y, x1 + 1);
4914                                 place_inner_bold(y, x2 - 1);
4915                         }
4916
4917                         /* Make a door */
4918                         y = randint1(ysize - 3) + y1 + 1;
4919
4920                         if (one_in_(2))
4921                         {
4922                                 /* left */
4923                                 place_floor_bold(y, x1 + 1);
4924                         }
4925                         else
4926                         {
4927                                 /* right */
4928                                 place_floor_bold(y, x2 - 1);
4929                         }
4930
4931                         /* Build the room */
4932                         build_recursive_room(x1 + 2, y1 + 2, x2 - 2, y2 - 2, power + 3);
4933                         break;
4934                 }
4935                 case 2:
4936                 {
4937                         /* Try and divide vertically */
4938                         if (xsize < 3)
4939                         {
4940                                 /* Too small */
4941                                 for (y = y1; y < y2; y++)
4942                                 {
4943                                         for (x = x1; x < x2; x++)
4944                                         {
4945                                                 place_inner_bold(y, x);
4946                                         }
4947                                 }
4948                                 return;
4949                         }
4950
4951                         t1 = randint1(xsize - 2) + x1 + 1;
4952                         build_recursive_room(x1, y1, t1, y2, power - 2);
4953                         build_recursive_room(t1 + 1, y1, x2, y2, power - 2);
4954                         break;
4955                 }
4956                 case 3:
4957                 {
4958                         /* Try and divide horizontally */
4959                         if (ysize < 3)
4960                         {
4961                                 /* Too small */
4962                                 for (y = y1; y < y2; y++)
4963                                 {
4964                                         for (x = x1; x < x2; x++)
4965                                         {
4966                                                 place_inner_bold(y, x);
4967                                         }
4968                                 }
4969                                 return;
4970                         }
4971
4972                         t1 = randint1(ysize - 2) + y1 + 1;
4973                         build_recursive_room(x1, y1, x2, t1, power - 2);
4974                         build_recursive_room(x1, t1 + 1, x2, y2, power - 2);
4975                         break;
4976                 }
4977         }
4978 }
4979
4980
4981 /* Build a castle */
4982
4983 /* Driver routine: clear the region and call the recursive
4984 * room routine.
4985 *
4986 *This makes a vault that looks like a castle/ city in the dungeon.
4987 */
4988 static void build_castle_vault(int x0, int y0, int xsize, int ysize)
4989 {
4990         int dy, dx;
4991         int y1, x1, y2, x2;
4992         int y, x;
4993
4994         /* Pick a random room size */
4995         dy = ysize / 2 - 1;
4996         dx = xsize / 2 - 1;
4997
4998         y1 = y0 - dy;
4999         x1 = x0 - dx;
5000         y2 = y0 + dy;
5001         x2 = x0 + dx;
5002
5003         if (cheat_room) msg_print("Castle Vault");
5004
5005         /* generate the room */
5006         for (y = y1 - 1; y <= y2 + 1; y++)
5007         {
5008                 for (x = x1 - 1; x <= x2 + 1; x++)
5009                 {
5010                         cave[y][x].info |= (CAVE_ROOM | CAVE_ICKY);
5011                         /* Make everything a floor */
5012                         place_floor_bold(y, x);
5013                 }
5014         }
5015
5016         /* Make the castle */
5017         build_recursive_room(x1, y1, x2, y2, randint1(5));
5018
5019         /* Fill with monsters and treasure, low difficulty */
5020         fill_treasure(x1, x2, y1, y2, randint1(3));
5021 }
5022
5023
5024 /*
5025  * Add outer wall to a floored region
5026  * Note: no range checking is done so must be inside dungeon
5027  * This routine also stomps on doors
5028  */
5029 static void add_outer_wall(int x, int y, int light,
5030                                                                         int x1, int y1, int x2, int y2)
5031 {
5032         int i, j;
5033
5034         if (!in_bounds(y, x)) return;
5035
5036         /* hack- check to see if square has been visited before
5037         * if so, then exit (use room flag to do this) */
5038         if (cave[y][x].info & CAVE_ROOM) return;
5039
5040         /* set room flag */
5041         cave[y][x].info |= CAVE_ROOM;
5042
5043         if (is_floor_bold(y, x))
5044         {
5045                 for (i = -1; i <= 1; i++)
5046                 {
5047                         for (j = -1; j <= 1; j++)
5048                         {
5049                                 if ((x + i >= x1) && (x + i <= x2) &&
5050                                          (y + j >= y1) && (y + j <= y2))
5051                                 {
5052                                         add_outer_wall(x + i, y + j, light, x1, y1, x2, y2);
5053                                         if (light) cave[y][x].info |= CAVE_GLOW;
5054                                 }
5055                         }
5056                 }
5057         }
5058         else if (is_extra_bold(y, x))
5059         {
5060                 /* Set bounding walls */
5061                 place_outer_bold(y, x);
5062                 if (light) cave[y][x].info |= CAVE_GLOW;
5063         }
5064         else if (cave[y][x].feat == FEAT_PERM_OUTER)
5065         {
5066                 /* Set bounding walls */
5067                 if (light) cave[y][x].info |= CAVE_GLOW;
5068         }
5069 }
5070
5071
5072 /*
5073  * Hacked distance formula - gives the 'wrong' answer.
5074  * Used to build crypts
5075  */
5076 static int dist2(int x1, int y1, int x2, int y2,
5077                  int h1, int h2, int h3, int h4)
5078 {
5079         int dx, dy;
5080         dx = abs(x2 - x1);
5081         dy = abs(y2 - y1);
5082
5083         /* Basically this works by taking the normal pythagorean formula
5084          * and using an expansion to express this in a way without the
5085          * square root.  This approximate formula is then perturbed to give
5086          * the distorted results.  (I found this by making a mistake when I was
5087          * trying to fix the circular rooms.)
5088          */
5089
5090         /* h1-h4 are constants that describe the metric */
5091         if (dx >= 2 * dy) return (dx + (dy * h1) / h2);
5092         if (dy >= 2 * dx) return (dy + (dx * h1) / h2);
5093         return (((dx + dy) * 128) / 181 +
5094                 (dx * dx / (dy * h3) + dy * dy / (dx * h3)) * h4);
5095         /* 128/181 is approx. 1/sqrt(2) */
5096 }
5097
5098
5099 /*
5100  * Build target vault.
5101  * This is made by two concentric "crypts" with perpendicular
5102  * walls creating the cross-hairs.
5103  */
5104 static void build_target_vault(int x0, int y0, int xsize, int ysize)
5105 {
5106         int rad, x, y;
5107
5108         /* Make a random metric */
5109         int h1, h2, h3, h4;
5110         h1 = randint1(32) - 16;
5111         h2 = randint1(16);
5112         h3 = randint1(32);
5113         h4 = randint1(32) - 16;
5114
5115         if (cheat_room) msg_print("Target Vault");
5116
5117         /* work out outer radius */
5118         if (xsize > ysize)
5119         {
5120                 rad = ysize / 2;
5121         }
5122         else
5123         {
5124                 rad = xsize / 2;
5125         }
5126
5127         /* Make floor */
5128         for (x = x0 - rad; x <= x0 + rad; x++)
5129         {
5130                 for (y = y0 - rad; y <= y0 + rad; y++)
5131                 {
5132                         /* clear room flag */
5133                         cave[y][x].info &= ~(CAVE_ROOM);
5134
5135                         /* Vault - so is "icky" */
5136                         cave[y][x].info |= CAVE_ICKY;
5137
5138                         if (dist2(y0, x0, y, x, h1, h2, h3, h4) <= rad - 1)
5139                         {
5140                                 /* inside- so is floor */
5141                                 place_floor_bold(y, x);
5142                         }
5143                         else
5144                         {
5145                                 /* make granite outside so arena works */
5146                                 place_extra_bold(y, x);
5147                         }
5148
5149                         /* proper boundary for arena */
5150                         if (((y + rad) == y0) || ((y - rad) == y0) ||
5151                             ((x + rad) == x0) || ((x - rad) == x0))
5152                         {
5153                                 place_extra_bold(y, x);
5154                         }
5155                 }
5156         }
5157
5158         /* Find visible outer walls and set to be FEAT_OUTER */
5159         add_outer_wall(x0, y0, FALSE, x0 - rad - 1, y0 - rad - 1,
5160                        x0 + rad + 1, y0 + rad + 1);
5161
5162         /* Add inner wall */
5163         for (x = x0 - rad / 2; x <= x0 + rad / 2; x++)
5164         {
5165                 for (y = y0 - rad / 2; y <= y0 + rad / 2; y++)
5166                 {
5167                         if (dist2(y0, x0, y, x, h1, h2, h3, h4) == rad / 2)
5168                         {
5169                                 /* Make an internal wall */
5170                                 place_inner_bold(y, x);
5171                         }
5172                 }
5173         }
5174
5175         /* Add perpendicular walls */
5176         for (x = x0 - rad; x <= x0 + rad; x++)
5177         {
5178                 place_inner_bold(y0, x);
5179         }
5180
5181         for (y = y0 - rad; y <= y0 + rad; y++)
5182         {
5183                 place_inner_bold(y, x0);
5184         }
5185
5186         /* Make inner vault */
5187         for (y = y0 - 1; y <= y0 + 1; y++)
5188         {
5189                 place_inner_bold(y, x0 - 1);
5190                 place_inner_bold(y, x0 + 1);
5191         }
5192         for (x = x0 - 1; x <= x0 + 1; x++)
5193         {
5194                 place_inner_bold(y0 - 1, x);
5195                 place_inner_bold(y0 + 1, x);
5196         }
5197
5198         place_floor_bold(y0, x0);
5199
5200
5201         /* Add doors to vault */
5202         /* get two distances so can place doors relative to centre */
5203         x = (rad - 2) / 4 + 1;
5204         y = rad / 2 + x;
5205
5206         add_door(x0 + x, y0);
5207         add_door(x0 + y, y0);
5208         add_door(x0 - x, y0);
5209         add_door(x0 - y, y0);
5210         add_door(x0, y0 + x);
5211         add_door(x0, y0 + y);
5212         add_door(x0, y0 - x);
5213         add_door(x0, y0 - y);
5214
5215         /* Fill with stuff - medium difficulty */
5216         fill_treasure(x0 - rad, x0 + rad, y0 - rad, y0 + rad, randint1(3) + 3);
5217 }
5218
5219
5220 #ifdef ALLOW_CAVERNS_AND_LAKES
5221 /*
5222  * This routine uses a modified version of the lake code to make a
5223  * distribution of some terrain type over the vault.  This type
5224  * depends on the dungeon depth.
5225  *
5226  * Miniture rooms are then scattered across the vault.
5227  */
5228 static void build_elemental_vault(int x0, int y0, int xsiz, int ysiz)
5229 {
5230         int grd, roug;
5231         int c1, c2, c3;
5232         bool done = FALSE;
5233         int xsize, ysize, xhsize, yhsize, x, y, i;
5234         int type;
5235
5236
5237         if (cheat_room) msg_print("Elemental Vault");
5238
5239         /* round to make sizes even */
5240         xhsize = xsiz / 2;
5241         yhsize = ysiz / 2;
5242         xsize = xhsize * 2;
5243         ysize = yhsize * 2;
5244
5245         if (dun_level < 25)
5246         {
5247                 /* Earth vault  (Rubble) */
5248                 type = LAKE_T_EARTH_VAULT;
5249         }
5250         else if (dun_level < 50)
5251         {
5252                 /* Air vault (Trees) */
5253                 type = LAKE_T_AIR_VAULT;
5254         }
5255         else if (dun_level < 75)
5256         {
5257                 /* Water vault (shallow water) */
5258                 type = LAKE_T_WATER_VAULT;
5259         }
5260         else
5261         {
5262                 /* Fire vault (shallow lava) */
5263                 type = LAKE_T_FIRE_VAULT;
5264         }
5265
5266         while (!done)
5267         {
5268                 /* testing values for these parameters: feel free to adjust */
5269                 grd = 1 << (randint0(3));
5270
5271                 /* want average of about 16 */
5272                 roug = randint1(8) * randint1(4);
5273
5274                 /* Make up size of various componants */
5275                 /* Floor */
5276                 c3 = 2 * xsize / 3;
5277
5278                 /* Deep water/lava */
5279                 c1 = randint0(c3 / 2) + randint0(c3 / 2) - 5;
5280
5281                 /* Shallow boundary */
5282                 c2 = (c1 + c3) / 2;
5283
5284                 /* make it */
5285                 generate_hmap(y0, x0, xsize, ysize, grd, roug, c3);
5286
5287                 /* Convert to normal format+ clean up */
5288                 done = generate_lake(y0, x0, xsize, ysize, c1, c2, c3, type);
5289         }
5290
5291         /* Set icky flag because is a vault */
5292         for (x = 0; x <= xsize; x++)
5293         {
5294                 for (y = 0; y <= ysize; y++)
5295                 {
5296                         cave[y0 - yhsize + y][x0 - xhsize + x].info |= CAVE_ICKY;
5297                 }
5298         }
5299
5300         /* make a few rooms in the vault */
5301         for (i = 1; i <= (xsize * ysize) / 50; i++)
5302         {
5303                 build_small_room(x0 + randint0(xsize - 4) - xsize / 2 + 2,
5304                                  y0 + randint0(ysize - 4) - ysize / 2 + 2);
5305         }
5306
5307         /* Fill with monsters and treasure, low difficulty */
5308         fill_treasure(x0 - xhsize + 1, x0 - xhsize + xsize - 1,
5309                       y0 - yhsize + 1, y0 - yhsize + ysize - 1, randint1(5));
5310 }
5311 #endif /* ALLOW_CAVERNS_AND_LAKES */
5312
5313
5314 /*
5315  * Random vaults
5316  */
5317 static bool build_type10(void)
5318 {
5319         int y0, x0, xsize, ysize, vtype;
5320
5321         /* Get size */
5322         /* big enough to look good, small enough to be fairly common. */
5323         xsize = randint1(22) + 22;
5324         ysize = randint1(11) + 11;
5325
5326         /* Find and reserve some space in the dungeon.  Get center of room. */
5327         if (!find_space(&y0, &x0, ysize + 1, xsize + 1)) return FALSE;
5328
5329         /* Boost the rating- higher than lesser vaults and lower than greater vaults */
5330         rating += 10;
5331
5332         /* (Sometimes) Cause a special feeling */
5333         if ((dun_level <= 50) ||
5334             (randint1((dun_level - 40) * (dun_level - 40) + 1) < 400))
5335         {
5336                 good_item_flag = TRUE;
5337         }
5338
5339         /* Select type of vault */
5340 #ifdef ALLOW_CAVERNS_AND_LAKES
5341         vtype = randint1(15);
5342 #else /* ALLOW_CAVERNS_AND_LAKES */
5343         vtype = randint1(7);
5344 #endif /* ALLOW_CAVERNS_AND_LAKES */
5345
5346         switch (vtype)
5347         {
5348                 /* Build an appropriate room */
5349                 case 1: case  9: build_bubble_vault(x0, y0, xsize, ysize); break;
5350                 case 2: case 10: build_room_vault(x0, y0, xsize, ysize); break;
5351                 case 3: case 11: build_cave_vault(x0, y0, xsize, ysize); break;
5352                 case 4: case 12: build_maze_vault(x0, y0, xsize, ysize, TRUE); break;
5353                 case 5: case 13: build_mini_c_vault(x0, y0, xsize, ysize); break;
5354                 case 6: case 14: build_castle_vault(x0, y0, xsize, ysize); break;
5355                 case 7: case 15: build_target_vault(x0, y0, xsize, ysize); break;
5356 #ifdef ALLOW_CAVERNS_AND_LAKES
5357                 case 8: build_elemental_vault(x0, y0, xsize, ysize); break;
5358 #endif /* ALLOW_CAVERNS_AND_LAKES */
5359                 /* I know how to add a few more... give me some time. */
5360
5361                 /* Paranoia */
5362                 default: return FALSE;
5363         }
5364
5365         return TRUE;
5366 }
5367
5368
5369 /*
5370  * Build an vertical oval room.
5371  * For every grid in the possible square, check the distance.
5372  * If it's less than the radius, make it a room square.
5373  *
5374  * When done fill from the inside to find the walls,
5375  */
5376 static bool build_type11(void)
5377 {
5378         int rad, x, y, x0, y0;
5379         int light = FALSE;
5380
5381         /* Occasional light */
5382         if ((randint1(dun_level) <= 15) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS)) light = TRUE;
5383
5384         rad = randint0(9);
5385
5386         /* Find and reserve some space in the dungeon.  Get center of room. */
5387         if (!find_space(&y0, &x0, rad * 2 + 1, rad * 2 + 1)) return FALSE;
5388
5389         /* Make circular floor */
5390         for (x = x0 - rad; x <= x0 + rad; x++)
5391         {
5392                 for (y = y0 - rad; y <= y0 + rad; y++)
5393                 {
5394                         if (distance(y0, x0, y, x) <= rad - 1)
5395                         {
5396                                 /* inside- so is floor */
5397                                 place_floor_bold(y, x);
5398                         }
5399                         else if (distance(y0, x0, y, x) <= rad + 1)
5400                         {
5401                                 /* make granite outside so arena works */
5402                                 place_extra_bold(y, x);
5403                         }
5404                 }
5405         }
5406
5407         /* Find visible outer walls and set to be FEAT_OUTER */
5408         add_outer_wall(x0, y0, light, x0 - rad, y0 - rad, x0 + rad, y0 + rad);
5409
5410         return TRUE;
5411 }
5412
5413
5414 /*
5415  * Build crypt room.
5416  * For every grid in the possible square, check the (fake) distance.
5417  * If it's less than the radius, make it a room square.
5418  *
5419  * When done fill from the inside to find the walls,
5420  */
5421 static bool build_type12(void)
5422 {
5423         int rad, x, y, x0, y0;
5424         int light = FALSE;
5425         bool emptyflag = TRUE;
5426
5427         /* Make a random metric */
5428         int h1, h2, h3, h4;
5429         h1 = randint1(32) - 16;
5430         h2 = randint1(16);
5431         h3 = randint1(32);
5432         h4 = randint1(32) - 16;
5433
5434         /* Occasional light */
5435         if ((randint1(dun_level) <= 5) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS)) light = TRUE;
5436
5437         rad = randint1(9);
5438
5439         /* Find and reserve some space in the dungeon.  Get center of room. */
5440         if (!find_space(&y0, &x0, rad * 2 + 3, rad * 2 + 3)) return FALSE;
5441
5442         /* Make floor */
5443         for (x = x0 - rad; x <= x0 + rad; x++)
5444         {
5445                 for (y = y0 - rad; y <= y0 + rad; y++)
5446                 {
5447                         /* clear room flag */
5448                         cave[y][x].info &= ~(CAVE_ROOM);
5449
5450                         if (dist2(y0, x0, y, x, h1, h2, h3, h4) <= rad - 1)
5451                         {
5452                                 /* inside - so is floor */
5453                                 place_floor_bold(y, x);
5454                         }
5455                         else if (distance(y0, x0, y, x) < 3)
5456                         {
5457                                 place_floor_bold(y, x);
5458                         }
5459                         else
5460                         {
5461                                 /* make granite outside so arena works */
5462                                 place_extra_bold(y, x);
5463                         }
5464
5465                         /* proper boundary for arena */
5466                         if (((y + rad) == y0) || ((y - rad) == y0) ||
5467                             ((x + rad) == x0) || ((x - rad) == x0))
5468                         {
5469                                 place_extra_bold(y, x);
5470                         }
5471                 }
5472         }
5473
5474         /* Find visible outer walls and set to be FEAT_OUTER */
5475         add_outer_wall(x0, y0, light, x0 - rad - 1, y0 - rad - 1,
5476                        x0 + rad + 1, y0 + rad + 1);
5477
5478         /* Check to see if there is room for an inner vault */
5479         for (x = x0 - 2; x <= x0 + 2; x++)
5480         {
5481                 for (y = y0 - 2; y <= y0 + 2; y++)
5482                 {
5483                         if (!is_floor_bold(y, x))
5484                         {
5485                                 /* Wall in the way */
5486                                 emptyflag = FALSE;
5487                         }
5488                 }
5489         }
5490
5491         if (emptyflag && one_in_(2))
5492         {
5493                 /* Build the vault */
5494                 build_small_room(x0, y0);
5495
5496                 /* Place a treasure in the vault */
5497                 place_object(y0, x0, 0L);
5498
5499                 /* Let's guard the treasure well */
5500                 vault_monsters(y0, x0, randint0(2) + 3);
5501
5502                 /* Traps naturally */
5503                 vault_traps(y0, x0, 4, 4, randint0(3) + 2);
5504         }
5505
5506         return TRUE;
5507 }
5508
5509
5510 /*
5511  * Helper function for "trapped monster pit"
5512  */
5513 static bool vault_aux_trapped_pit(int r_idx)
5514 {
5515         monster_race *r_ptr = &r_info[r_idx];
5516
5517         /* Validate the monster */
5518         if (!vault_monster_okay(r_idx)) return (FALSE);
5519
5520         /* No wall passing monster */
5521         if (r_ptr->flags2 & (RF2_PASS_WALL | RF2_KILL_WALL)) return (FALSE);
5522
5523         /* Okay */
5524         return (TRUE);
5525 }
5526
5527
5528 /*
5529  * Type 12 -- Trapped monster pits
5530  *
5531  * A trapped monster pit is a "big" room with a straight corridor in
5532  * which wall opening traps are placed, and with two "inner" rooms
5533  * containing a "collection" of monsters of a given type organized in
5534  * the room.
5535  *
5536  * The trapped monster pit appears as shown below, where the actual
5537  * monsters in each location depend on the type of the pit
5538  *
5539  *  #########################
5540  *  #                       #
5541  *  ####################### #
5542  *  #####001123454321100### #
5543  *  ###0012234567654322100# #
5544  *  ####################### #
5545  *  #           ^           #
5546  *  # #######################
5547  *  # #0012234567654322100###
5548  *  # ###001123454321100#####
5549  *  # #######################
5550  *  #                       #
5551  *  #########################
5552  *
5553  * Note that the monsters in the pit are now chosen by using "get_mon_num()"
5554  * to request 16 "appropriate" monsters, sorting them by level, and using
5555  * the "even" entries in this sorted list for the contents of the pit.
5556  *
5557  * Hack -- all of the "dragons" in a "dragon" pit must be the same "color",
5558  * which is handled by requiring a specific "breath" attack for all of the
5559  * dragons.  This may include "multi-hued" breath.  Note that "wyrms" may
5560  * be present in many of the dragon pits, if they have the proper breath.
5561  *
5562  * Note the use of the "get_mon_num_prep()" function, and the special
5563  * "get_mon_num_hook()" restriction function, to prepare the "monster
5564  * allocation table" in such a way as to optimize the selection of
5565  * "appropriate" non-unique monsters for the pit.
5566  *
5567  * Note that the "get_mon_num()" function may (rarely) fail, in which case
5568  * the pit will be empty, and will not effect the level rating.
5569  *
5570  * Note that "monster pits" will never contain "unique" monsters.
5571  */
5572 static bool build_type13(void)
5573 {
5574         static int placing[][3] = {
5575                 {-2, -9, 0}, {-2, -8, 0}, {-3, -7, 0}, {-3, -6, 0},
5576                 {+2, -9, 0}, {+2, -8, 0}, {+3, -7, 0}, {+3, -6, 0},
5577                 {-2, +9, 0}, {-2, +8, 0}, {-3, +7, 0}, {-3, +6, 0},
5578                 {+2, +9, 0}, {+2, +8, 0}, {+3, +7, 0}, {+3, +6, 0},
5579                 {-2, -7, 1}, {-3, -5, 1}, {-3, -4, 1},
5580                 {+2, -7, 1}, {+3, -5, 1}, {+3, -4, 1},
5581                 {-2, +7, 1}, {-3, +5, 1}, {-3, +4, 1},
5582                 {+2, +7, 1}, {+3, +5, 1}, {+3, +4, 1},
5583                 {-2, -6, 2}, {-2, -5, 2}, {-3, -3, 2},
5584                 {+2, -6, 2}, {+2, -5, 2}, {+3, -3, 2},
5585                 {-2, +6, 2}, {-2, +5, 2}, {-3, +3, 2},
5586                 {+2, +6, 2}, {+2, +5, 2}, {+3, +3, 2},
5587                 {-2, -4, 3}, {-3, -2, 3},
5588                 {+2, -4, 3}, {+3, -2, 3},
5589                 {-2, +4, 3}, {-3, +2, 3},
5590                 {+2, +4, 3}, {+3, +2, 3},
5591                 {-2, -3, 4}, {-3, -1, 4},
5592                 {+2, -3, 4}, {+3, -1, 4},
5593                 {-2, +3, 4}, {-3, +1, 4},
5594                 {+2, +3, 4}, {+3, +1, 4},
5595                 {-2, -2, 5}, {-3, 0, 5}, {-2, +2, 5},
5596                 {+2, -2, 5}, {+3, 0, 5}, {+2, +2, 5},
5597                 {-2, -1, 6}, {-2, +1, 6},
5598                 {+2, -1, 6}, {+2, +1, 6},
5599                 {-2, 0, 7}, {+2, 0, 7},
5600                 {0, 0, -1}
5601         };
5602
5603         int y, x, y1, x1, y2, x2, xval, yval;
5604         int i, j;
5605
5606         int what[16];
5607
5608         monster_type align;
5609
5610         cave_type *c_ptr;
5611
5612         int cur_pit_type = pick_vault_type(pit_types, d_info[dungeon_type].pit);
5613         vault_aux_type *n_ptr;
5614
5615         /* Only in Angband */
5616         if (dungeon_type != DUNGEON_ANGBAND) return FALSE;
5617
5618         /* No type available */
5619         if (cur_pit_type < 0) return FALSE;
5620
5621         n_ptr = &pit_types[cur_pit_type];
5622
5623         /* Process a preparation function if necessary */
5624         if (n_ptr->prep_func) (*(n_ptr->prep_func))();
5625
5626         /* Prepare allocation table */
5627         get_mon_num_prep(n_ptr->hook_func, vault_aux_trapped_pit);
5628
5629         align.sub_align = SUB_ALIGN_NEUTRAL;
5630
5631         /* Pick some monster types */
5632         for (i = 0; i < 16; i++)
5633         {
5634                 int r_idx = 0, attempts = 100;
5635                 monster_race *r_ptr = NULL;
5636
5637                 while (attempts--)
5638                 {
5639                         /* Get a (hard) monster type */
5640                         r_idx = get_mon_num(dun_level + 0);
5641                         r_ptr = &r_info[r_idx];
5642
5643                         /* Decline incorrect alignment */
5644                         if (monster_has_hostile_align(&align, 0, 0, r_ptr)) continue;
5645
5646                         /* Accept this monster */
5647                         break;
5648                 }
5649
5650                 /* Notice failure */
5651                 if (!r_idx || !attempts) return FALSE;
5652
5653                 /* Note the alignment */
5654                 if (r_ptr->flags3 & RF3_EVIL) align.sub_align |= SUB_ALIGN_EVIL;
5655                 if (r_ptr->flags3 & RF3_GOOD) align.sub_align |= SUB_ALIGN_GOOD;
5656
5657                 what[i] = r_idx;
5658         }
5659
5660         /* Find and reserve some space in the dungeon.  Get center of room. */
5661         if (!find_space(&yval, &xval, 13, 25)) return FALSE;
5662
5663         /* Large room */
5664         y1 = yval - 5;
5665         y2 = yval + 5;
5666         x1 = xval - 11;
5667         x2 = xval + 11;
5668
5669         /* Fill with inner walls */
5670         for (y = y1 - 1; y <= y2 + 1; y++)
5671         {
5672                 for (x = x1 - 1; x <= x2 + 1; x++)
5673                 {
5674                         c_ptr = &cave[y][x];
5675                         place_inner_grid(c_ptr);
5676                         c_ptr->info |= (CAVE_ROOM);
5677                 }
5678         }
5679
5680         /* Place the floor area 1 */
5681         for (x = x1 + 3; x <= x2 - 3; x++)
5682         {
5683                 c_ptr = &cave[yval-2][x];
5684                 place_floor_grid(c_ptr);
5685                 add_cave_info(yval-2, x, CAVE_ICKY);
5686
5687                 c_ptr = &cave[yval+2][x];
5688                 place_floor_grid(c_ptr);
5689                 add_cave_info(yval+2, x, CAVE_ICKY);
5690         }
5691
5692         /* Place the floor area 2 */
5693         for (x = x1 + 5; x <= x2 - 5; x++)
5694         {
5695                 c_ptr = &cave[yval-3][x];
5696                 place_floor_grid(c_ptr);
5697                 add_cave_info(yval-3, x, CAVE_ICKY);
5698
5699                 c_ptr = &cave[yval+3][x];
5700                 place_floor_grid(c_ptr);
5701                 add_cave_info(yval+3, x, CAVE_ICKY);
5702         }
5703
5704         /* Corridor */
5705         for (x = x1; x <= x2; x++)
5706         {
5707                 c_ptr = &cave[yval][x];
5708                 place_floor_grid(c_ptr);
5709                 c_ptr = &cave[y1][x];
5710                 place_floor_grid(c_ptr);
5711                 c_ptr = &cave[y2][x];
5712                 place_floor_grid(c_ptr);
5713         }
5714
5715         /* Place the outer walls */
5716         for (y = y1 - 1; y <= y2 + 1; y++)
5717         {
5718                 c_ptr = &cave[y][x1 - 1];
5719                 place_outer_grid(c_ptr);
5720                 c_ptr = &cave[y][x2 + 1];
5721                 place_outer_grid(c_ptr);
5722         }
5723         for (x = x1 - 1; x <= x2 + 1; x++)
5724         {
5725                 c_ptr = &cave[y1 - 1][x];
5726                 place_outer_grid(c_ptr);
5727                 c_ptr = &cave[y2 + 1][x];
5728                 place_outer_grid(c_ptr);
5729         }
5730
5731         /* Random corridor */
5732         if (one_in_(2))
5733         {
5734                 for (y = y1; y <= yval; y++)
5735                 {
5736                         place_floor_bold(y, x2);
5737                         place_solid_bold(y, x1-1);
5738                 }
5739                 for (y = yval; y <= y2 + 1; y++)
5740                 {
5741                         place_floor_bold(y, x1);
5742                         place_solid_bold(y, x2+1);
5743                 }
5744         }
5745         else
5746         {
5747                 for (y = yval; y <= y2 + 1; y++)
5748                 {
5749                         place_floor_bold(y, x1);
5750                         place_solid_bold(y, x2+1);
5751                 }
5752                 for (y = y1; y <= yval; y++)
5753                 {
5754                         place_floor_bold(y, x2);
5755                         place_solid_bold(y, x1-1);
5756                 }
5757         }
5758
5759         /* Place the wall open trap */
5760         cave[yval][xval].mimic = cave[yval][xval].feat;
5761         cave[yval][xval].feat = FEAT_TRAP_OPEN;
5762
5763         /* Sort the entries */
5764         for (i = 0; i < 16 - 1; i++)
5765         {
5766                 /* Sort the entries */
5767                 for (j = 0; j < 16 - 1; j++)
5768                 {
5769                         int i1 = j;
5770                         int i2 = j + 1;
5771
5772                         int p1 = r_info[what[i1]].level;
5773                         int p2 = r_info[what[i2]].level;
5774
5775                         /* Bubble */
5776                         if (p1 > p2)
5777                         {
5778                                 int tmp = what[i1];
5779                                 what[i1] = what[i2];
5780                                 what[i2] = tmp;
5781                         }
5782                 }
5783         }
5784
5785         /* Message */
5786         if (cheat_room)
5787         {
5788                 /* Room type */
5789 #ifdef JP
5790                 msg_format("%s%s¤Îæ«¥Ô¥Ã¥È", n_ptr->name, pit_subtype_string(cur_pit_type, FALSE));
5791 #else
5792                 msg_format("Trapped monster pit (%s%s)", n_ptr->name, pit_subtype_string(cur_pit_type, FALSE));
5793 #endif
5794         }
5795
5796         /* Select the entries */
5797         for (i = 0; i < 8; i++)
5798         {
5799                 /* Every other entry */
5800                 what[i] = what[i * 2];
5801
5802                 if (cheat_hear)
5803                 {
5804                         /* Message */
5805                         msg_print(r_name + r_info[what[i]].name);
5806                 }
5807         }
5808
5809         /* Increase the level rating */
5810         rating += 20;
5811
5812         /* (Sometimes) Cause a "special feeling" (for "Monster Pits") */
5813         if ((dun_level <= 40) && (randint1(dun_level * dun_level + 50) < 300))
5814         {
5815                 good_item_flag = TRUE;
5816         }
5817
5818         for (i = 0; placing[i][2] >= 0; i++)
5819         {
5820                 y = yval + placing[i][0];
5821                 x = xval + placing[i][1];
5822                 place_monster_aux(0, y, x, what[placing[i][2]], PM_NO_KAGE);
5823         }
5824
5825         return TRUE;
5826 }
5827
5828
5829 /*
5830  * Type 14 -- trapped rooms
5831  *
5832  * A special trap is placed at center of the room
5833  */
5834 static bool build_type14(void)
5835 {
5836         int y, x, y2, x2, yval, xval;
5837         int y1, x1, xsize, ysize;
5838
5839         bool light;
5840
5841         cave_type *c_ptr;
5842         byte trap;
5843
5844         /* Pick a room size */
5845         y1 = randint1(4);
5846         x1 = randint1(11);
5847         y2 = randint1(3);
5848         x2 = randint1(11);
5849
5850         xsize = x1 + x2 + 1;
5851         ysize = y1 + y2 + 1;
5852
5853         /* Find and reserve some space in the dungeon.  Get center of room. */
5854         if (!find_space(&yval, &xval, ysize + 2, xsize + 2)) return FALSE;
5855
5856         /* Choose lite or dark */
5857         light = ((dun_level <= randint1(25)) && !(d_info[dungeon_type].flags1 & DF1_DARKNESS));
5858
5859
5860         /* Get corner values */
5861         y1 = yval - ysize / 2;
5862         x1 = xval - xsize / 2;
5863         y2 = yval + (ysize - 1) / 2;
5864         x2 = xval + (xsize - 1) / 2;
5865
5866
5867         /* Place a full floor under the room */
5868         for (y = y1 - 1; y <= y2 + 1; y++)
5869         {
5870                 for (x = x1 - 1; x <= x2 + 1; x++)
5871                 {
5872                         c_ptr = &cave[y][x];
5873                         place_floor_grid(c_ptr);
5874                         c_ptr->info |= (CAVE_ROOM);
5875                         if (light) c_ptr->info |= (CAVE_GLOW);
5876                 }
5877         }
5878
5879         /* Walls around the room */
5880         for (y = y1 - 1; y <= y2 + 1; y++)
5881         {
5882                 c_ptr = &cave[y][x1 - 1];
5883                 place_outer_grid(c_ptr);
5884                 c_ptr = &cave[y][x2 + 1];
5885                 place_outer_grid(c_ptr);
5886         }
5887         for (x = x1 - 1; x <= x2 + 1; x++)
5888         {
5889                 c_ptr = &cave[y1 - 1][x];
5890                 place_outer_grid(c_ptr);
5891                 c_ptr = &cave[y2 + 1][x];
5892                 place_outer_grid(c_ptr);
5893         }
5894
5895         if (dun_level < 30 + randint1(30))
5896                 trap = FEAT_TRAP_PIRANHA;
5897         else
5898                 trap = FEAT_TRAP_ARMAGEDDON;
5899
5900         /* Place a special trap */
5901         c_ptr = &cave[rand_spread(yval, ysize/4)][rand_spread(xval, xsize/4)];
5902         c_ptr->mimic = c_ptr->feat;
5903         c_ptr->feat = trap;
5904
5905         /* Message */
5906         if (cheat_room)
5907         {
5908 #ifdef JP
5909                 msg_format("%s¤ÎÉô²°", f_name + f_info[trap].name);
5910 #else
5911                 msg_format("Room of %s", f_name + f_info[trap].name);
5912 #endif
5913         }
5914
5915         return TRUE;
5916 }
5917
5918
5919 /*
5920  * Attempt to build a room of the given type at the given block
5921  *
5922  * Note that we restrict the number of "crowded" rooms to reduce
5923  * the chance of overflowing the monster list during level creation.
5924  */
5925 bool room_build(int typ)
5926 {
5927         /* Build a room */
5928         switch (typ)
5929         {
5930         /* Build an appropriate room */
5931         case ROOM_T_NORMAL:        return build_type1();
5932         case ROOM_T_OVERLAP:       return build_type2();
5933         case ROOM_T_CROSS:         return build_type3();
5934         case ROOM_T_INNER_FEAT:    return build_type4();
5935         case ROOM_T_NEST:          return build_type5();
5936         case ROOM_T_PIT:           return build_type6();
5937         case ROOM_T_LESSER_VAULT:  return build_type7();
5938         case ROOM_T_GREATER_VAULT: return build_type8();
5939         case ROOM_T_FRACAVE:       return build_type9();
5940         case ROOM_T_RANDOM_VAULT:  return build_type10();
5941         case ROOM_T_OVAL:          return build_type11();
5942         case ROOM_T_CRYPT:         return build_type12();
5943         case ROOM_T_TRAP_PIT:      return build_type13();
5944         case ROOM_T_TRAP:          return build_type14();
5945         }
5946
5947         /* Paranoia */
5948         return FALSE;
5949 }
5950
5951
5952 #define MOVE_PLIST(dst, src) (prob_list[dst] += prob_list[src], prob_list[src] = 0)
5953
5954 /*
5955  * [from SAngband (originally from OAngband)]
5956  *
5957  * Generate rooms in dungeon.  Build bigger rooms at first.
5958  */
5959 void generate_rooms(void)
5960 {
5961         int i;
5962         bool remain;
5963         int crowded = 0;
5964         int total_prob;
5965         int prob_list[ROOM_T_MAX];
5966         int rooms_built = 0;
5967         int area_size = 100 * (cur_hgt*cur_wid) / (MAX_HGT*MAX_WID);
5968         int level_index = MIN(10, div_round(dun_level, 10));
5969
5970         /* Number of each type of room on this level */
5971         s16b room_num[ROOM_T_MAX];
5972
5973         /* Limit number of rooms */
5974         int dun_rooms = DUN_ROOMS_MAX * area_size / 100;
5975
5976         /* Assume normal cave */
5977         room_info_type *room_info_ptr = room_info_normal;
5978
5979
5980         /*
5981          * Initialize probability list.
5982          */
5983         for (i = 0; i < ROOM_T_MAX; i++)
5984         {
5985                 /* No rooms allowed above their minimum depth. */
5986                 if (dun_level < room_info_ptr[i].min_level)
5987                 {
5988                         prob_list[i] = 0;
5989                 }
5990                 else
5991                 {
5992                         prob_list[i] = room_info_ptr[i].prob[level_index];
5993                 }
5994         }
5995
5996         /*
5997          * XXX -- Various dungeon types and options.
5998          */
5999
6000         /* Ironman sees only Greater Vaults */
6001         if (ironman_rooms && !((d_info[dungeon_type].flags1 & (DF1_BEGINNER | DF1_CHAMELEON))))
6002         {
6003                 for (i = 0; i < ROOM_T_MAX; i++)
6004                 {
6005                         if (i == ROOM_T_GREATER_VAULT) prob_list[i] = 1;
6006                         else prob_list[i] = 0;
6007                 }
6008         }
6009
6010         /* Forbidden vaults */
6011         else if (d_info[dungeon_type].flags1 & DF1_NO_VAULT)
6012         {
6013                 prob_list[ROOM_T_LESSER_VAULT] = 0;
6014                 prob_list[ROOM_T_GREATER_VAULT] = 0;
6015                 prob_list[ROOM_T_RANDOM_VAULT] = 0;
6016         }
6017
6018
6019         /* NO_CAVE dungeon (Castle)*/
6020         if (d_info[dungeon_type].flags1 & DF1_NO_CAVE)
6021         {
6022                 MOVE_PLIST(ROOM_T_NORMAL, ROOM_T_FRACAVE);
6023                 MOVE_PLIST(ROOM_T_INNER_FEAT, ROOM_T_CRYPT);
6024                 MOVE_PLIST(ROOM_T_INNER_FEAT, ROOM_T_OVAL);
6025         }
6026
6027         /* CAVE dungeon (Orc cave etc.) */
6028         else if (d_info[dungeon_type].flags1 & DF1_CAVE)
6029         {
6030                 MOVE_PLIST(ROOM_T_FRACAVE, ROOM_T_NORMAL);
6031         }
6032
6033         /* No caves when a (random) cavern exists: they look bad */
6034         else if (dun->cavern || dun->empty_level)
6035         {
6036                 prob_list[ROOM_T_FRACAVE] = 0;
6037         }
6038
6039
6040         /*
6041          * Initialize number of rooms,
6042          * And calcurate total probability.
6043          */
6044         for (total_prob = 0, i = 0; i < ROOM_T_MAX; i++)
6045         {
6046                 room_num[i] = 0;
6047                 total_prob += prob_list[i];
6048         }
6049
6050         /*
6051          * Prepare the number of rooms, of all types, we should build
6052          * on this level.
6053          */
6054         for (i = dun_rooms; i > 0; i--)
6055         {
6056                 int room_type;
6057                 int rand = randint0(total_prob);
6058
6059                 /* Get room_type randomly */
6060                 for (room_type = 0; room_type < ROOM_T_MAX; room_type++)
6061                 {
6062                         if (rand < prob_list[room_type]) break;
6063                         else rand -= prob_list[room_type];
6064                 }
6065
6066                 /* Paranoia */
6067                 if (room_type >= ROOM_T_MAX) room_type = ROOM_T_NORMAL;
6068
6069                 /* Increase the number of rooms of that type we should build. */
6070                 room_num[room_type]++;
6071
6072                 switch (room_type)
6073                 {
6074                 case ROOM_T_NEST:
6075                 case ROOM_T_PIT:
6076                 case ROOM_T_LESSER_VAULT:
6077                 case ROOM_T_TRAP_PIT:
6078
6079                         /* Large room */
6080                         i -= 2;
6081                         break;
6082
6083                 case ROOM_T_GREATER_VAULT:
6084                 case ROOM_T_RANDOM_VAULT:
6085
6086                         /* Largest room */
6087                         i -= 3;
6088                         break;
6089                 }
6090         }
6091
6092         /*
6093          * Build each type of room one by one until we cannot build any more.
6094          * [from SAngband (originally from OAngband)]
6095          */
6096         while (TRUE)
6097         {
6098                 /* Assume no remaining rooms */
6099                 remain = FALSE;
6100
6101                 for (i = 0; i < ROOM_T_MAX; i++)
6102                 {
6103                         /* What type of room are we building now? */
6104                         int room_type = room_build_order[i];
6105
6106                         /* Go next if none available */
6107                         if (!room_num[room_type]) continue;
6108
6109                         /* Use up one unit */
6110                         room_num[room_type]--;
6111
6112                         /* Build the room. */
6113                         if (room_build(room_type))
6114                         {
6115                                 /* Increase the room built count. */
6116                                 rooms_built++;
6117
6118                                 /* Mark as there was some remaining rooms */
6119                                 remain = TRUE;
6120
6121                                 switch (room_type)
6122                                 {
6123                                 case ROOM_T_PIT:
6124                                 case ROOM_T_NEST:
6125                                 case ROOM_T_TRAP_PIT:
6126
6127                                         /* Avoid too many monsters */
6128                                         if (++crowded >= 2)
6129                                         {
6130                                                 room_num[ROOM_T_PIT] = 0;
6131                                                 room_num[ROOM_T_NEST] = 0;
6132                                                 room_num[ROOM_T_TRAP_PIT] = 0;
6133                                         }
6134                                 }
6135                         }
6136
6137                         /* Stop building this type on failure. */
6138                         else
6139                         {
6140                                 room_num[room_type] = 0;
6141                         }
6142                 }
6143
6144                 /* End loop if no room remain */
6145                 if (!remain) break;
6146         }
6147
6148         if (cheat_room)
6149         {
6150 #ifdef JP
6151                 msg_format("Éô²°¿ô: %d", rooms_built);
6152 #else
6153                 msg_format("Number of Rooms: %d", rooms_built);
6154 #endif
6155         }
6156 }