src/grid.c

   1 /*
   2  * File: grid.c
   3  * Purpose: low-level dungeon creation primitives
   4  */
   5
   6 /*
   7  * Copyright (c) 1989 James E. Wilson, Robert A. Koeneke
   8  *
   9  * This software may be copied and distributed for educational, research, and
  10  * not for profit purposes provided that this copyright and statement are
  11  * included in all such copies.
  12  */
  13
  14 #include "angband.h"
  15 #include "generate.h"
  16 #include "grid.h"
  17
  18
  19 /*
  20  * Returns random co-ordinates for player/monster/object
  21  */
  22 bool new_player_spot(void)
  23 {
  24         int     y, x;
  25         int max_attempts = 5000;
  26
  27         cave_type *c_ptr;
  28
  29         /* Place the player */
  30         while (max_attempts--)
  31         {
  32                 /* Pick a legal spot */
  33                 y = rand_range(1, cur_hgt - 2);
  34                 x = rand_range(1, cur_wid - 2);
  35
  36                 c_ptr = &cave[y][x];
  37
  38                 /* Must be a "naked" floor grid */
  39                 if (!cave_clean_bold(y, x) || c_ptr->m_idx) continue;
  40                 if (!in_bounds(y,x)) continue;
  41
  42                 /* Refuse to start on anti-teleport grids */
  43                 if (c_ptr->info & (CAVE_ICKY)) continue;
  44
  45                 /* Done */
  46                 break;
  47         }
  48
  49         if (max_attempts < 1) /* Should be -1, actually if we failed... */
  50                 return FALSE;
  51
  52         /* Save the new player grid */
  53         py = y;
  54         px = x;
  55
  56         return TRUE;
  57 }
  58
  59
  60 /*
  61  * Place an up/down staircase at given location
  62  */
  63 void place_random_stairs(int y, int x)
  64 {
  65         bool up_stairs = TRUE;
  66         bool down_stairs = TRUE;
  67         cave_type *c_ptr;
  68
  69         /* Paranoia */
  70         c_ptr = &cave[y][x];
  71         if (!is_floor_grid(c_ptr) || c_ptr->o_idx) return;
  72
  73         /* Town */
  74         if (!dun_level)
  75                 up_stairs = FALSE;
  76
  77         /* Ironman */
  78         if (ironman_downward)
  79                 up_stairs = FALSE;
  80
  81         /* Bottom */
  82         if (dun_level >= d_info[dungeon_type].maxdepth)
  83                 down_stairs = FALSE;
  84
  85         /* Quest-level */
  86         if (quest_number(dun_level) && (dun_level > 1))
  87                 down_stairs = FALSE;
  88
  89         /* We can't place both */
  90         if (down_stairs && up_stairs)
  91         {
  92                 /* Choose a staircase randomly */
  93                 if (randint0(100) < 50)
  94                         up_stairs = FALSE;
  95                 else
  96                         down_stairs = FALSE;
  97         }
  98
  99         /* Place the stairs */
 100         if (up_stairs)
 101                 place_up_stairs(y, x);
 102         else if (down_stairs)
 103                 place_down_stairs(y, x);
 104 }
 105
 106
 107 /*
 108  * Place a random type of door at the given location
 109  */
 110 void place_random_door(int y, int x)
 111 {
 112         int tmp;
 113         cave_type *c_ptr = &cave[y][x];
 114
 115         /* Initialize mimic info */
 116         c_ptr->mimic = 0;
 117
 118         if (d_info[dungeon_type].flags1 & DF1_NO_DOORS)
 119         {
 120                 place_floor_bold(y, x);
 121                 return;
 122         }
 123
 124         /* Choose an object */
 125         tmp = randint0(1000);
 126
 127         /* Open doors (300/1000) */
 128         if (tmp < 300)
 129         {
 130                 /* Create open door */
 131                 set_cave_feat(y, x, FEAT_OPEN);
 132         }
 133
 134         /* Broken doors (100/1000) */
 135         else if (tmp < 400)
 136         {
 137                 /* Create broken door */
 138                 set_cave_feat(y, x, FEAT_BROKEN);
 139         }
 140
 141         /* Secret doors (200/1000) */
 142         else if (tmp < 600)
 143         {
 144                 /* Create secret door */
 145                 place_closed_door(y, x);
 146
 147                 /* Hide */
 148                 c_ptr->mimic = fill_type[randint0(100)];
 149         }
 150
 151         /* Closed, locked, or stuck doors (400/1000) */
 152         else place_closed_door(y, x);
 153 }
 154
 155
 156 /*
 157  * Place a random type of normal door at the given location.
 158  */
 159 void place_closed_door(int y, int x)
 160 {
 161         int tmp;
 162
 163         if (d_info[dungeon_type].flags1 & DF1_NO_DOORS)
 164         {
 165                 place_floor_bold(y, x);
 166                 return;
 167         }
 168
 169         /* Choose an object */
 170         tmp = randint0(400);
 171
 172         /* Closed doors (300/400) */
 173         if (tmp < 300)
 174         {
 175                 /* Create closed door */
 176                 cave_set_feat(y, x, FEAT_DOOR_HEAD + 0x00);
 177         }
 178
 179         /* Locked doors (99/400) */
 180         else if (tmp < 399)
 181         {
 182                 /* Create locked door */
 183                 cave_set_feat(y, x, FEAT_DOOR_HEAD + randint1(7));
 184         }
 185
 186         /* Stuck doors (1/400) */
 187         else
 188         {
 189                 /* Create jammed door */
 190                 cave_set_feat(y, x, FEAT_DOOR_HEAD + 0x08 + randint0(8));
 191         }
 192 }
 193
 194
 195 /*
 196  * Make an empty square floor, for the middle of rooms
 197  */
 198 void place_floor(int x1, int x2, int y1, int y2, bool light)
 199 {
 200         int x, y;
 201
 202         /* Place a full floor under the room */
 203         for (y = y1 - 1; y <= y2 + 1; y++)
 204         {
 205                 for (x = x1 - 1; x <= x2 + 1; x++)
 206                 {
 207                         place_floor_bold(y, x);
 208                         add_cave_info(y, x, CAVE_ROOM);
 209                         if (light) add_cave_info(y, x, CAVE_GLOW);
 210                 }
 211         }
 212 }
 213
 214
 215 /*
 216  * Make an empty square room, only floor and wall grids
 217  */
 218 void place_room(int x1, int x2, int y1, int y2, bool light)
 219 {
 220         int y, x;
 221
 222         place_floor(x1, x2, y1, y2, light);
 223
 224         /* Walls around the room */
 225         for (y = y1 - 1; y <= y2 + 1; y++)
 226         {
 227                 place_outer_bold(y, x1 - 1);
 228                 place_outer_bold(y, x2 + 1);
 229         }
 230         for (x = x1 - 1; x <= x2 + 1; x++)
 231         {
 232                 place_outer_bold(y1 - 1, x);
 233                 place_outer_bold(y2 + 1, x);
 234         }
 235 }
 236
 237
 238 /*
 239  * Create up to "num" objects near the given coordinates
 240  * Only really called by some of the "vault" routines.
 241  */
 242 void vault_objects(int y, int x, int num)
 243 {
 244         int dummy = 0;
 245         int i = 0, j = y, k = x;
 246
 247         cave_type *c_ptr;
 248
 249
 250         /* Attempt to place 'num' objects */
 251         for (; num > 0; --num)
 252         {
 253                 /* Try up to 11 spots looking for empty space */
 254                 for (i = 0; i < 11; ++i)
 255                 {
 256                         /* Pick a random location */
 257                         while (dummy < SAFE_MAX_ATTEMPTS)
 258                         {
 259                                 j = rand_spread(y, 2);
 260                                 k = rand_spread(x, 3);
 261                                 dummy++;
 262                                 if (!in_bounds(j, k)) continue;
 263                                 break;
 264                         }
 265
 266
 267                         if (dummy >= SAFE_MAX_ATTEMPTS)
 268                         {
 269                                 if (cheat_room)
 270                                 {
 271 #ifdef JP
 272 msg_print("·Ù¹ð¡ªÃÏ²¼¼¼¤Î¥¢¥¤¥Æ¥à¤òÇÛÃÖ¤Ç¤¤Þ¤»¤ó¡ª");
 273 #else
 274                                         msg_print("Warning! Could not place vault object!");
 275 #endif
 276
 277                                 }
 278                         }
 279
 280
 281                         /* Require "clean" floor space */
 282                         c_ptr = &cave[j][k];
 283                         if (!is_floor_grid(c_ptr) || c_ptr->o_idx) continue;
 284
 285                         /* Place an item */
 286                         if (randint0(100) < 75)
 287                         {
 288                                 place_object(j, k, FALSE, FALSE);
 289                         }
 290
 291                         /* Place gold */
 292                         else
 293                         {
 294                                 place_gold(j, k);
 295                         }
 296
 297                         /* Placement accomplished */
 298                         break;
 299                 }
 300         }
 301 }
 302
 303
 304 /*
 305  * Place a trap with a given displacement of point
 306  */
 307 void vault_trap_aux(int y, int x, int yd, int xd)
 308 {
 309         int count = 0, y1 = y, x1 = x;
 310         int dummy = 0;
 311
 312         cave_type *c_ptr;
 313
 314         /* Place traps */
 315         for (count = 0; count <= 5; count++)
 316         {
 317                 /* Get a location */
 318                 while (dummy < SAFE_MAX_ATTEMPTS)
 319                 {
 320                         y1 = rand_spread(y, yd);
 321                         x1 = rand_spread(x, xd);
 322                         dummy++;
 323                         if (!in_bounds(y1, x1)) continue;
 324                         break;
 325                 }
 326
 327                 if (dummy >= SAFE_MAX_ATTEMPTS)
 328                 {
 329                         if (cheat_room)
 330                         {
 331 #ifdef JP
 332 msg_print("·Ù¹ð¡ªÃÏ²¼¼¼¤Î¥È¥é¥Ã¥×¤òÇÛÃÖ¤Ç¤¤Þ¤»¤ó¡ª");
 333 #else
 334                                 msg_print("Warning! Could not place vault trap!");
 335 #endif
 336
 337                         }
 338                 }
 339
 340                 /* Require "naked" floor grids */
 341                 c_ptr = &cave[y1][x1];
 342                 if (!is_floor_grid(c_ptr) || c_ptr->o_idx || c_ptr->m_idx) continue;
 343
 344                 /* Place the trap */
 345                 place_trap(y1, x1);
 346
 347                 /* Done */
 348                 break;
 349         }
 350 }
 351
 352
 353 /*
 354  * Place some traps with a given displacement of given location
 355  */
 356 void vault_traps(int y, int x, int yd, int xd, int num)
 357 {
 358         int i;
 359
 360         for (i = 0; i < num; i++)
 361         {
 362                 vault_trap_aux(y, x, yd, xd);
 363         }
 364 }
 365
 366
 367 /*
 368  * Hack -- Place some sleeping monsters near the given location
 369  */
 370 void vault_monsters(int y1, int x1, int num)
 371 {
 372         int k, i, y, x;
 373         cave_type *c_ptr;
 374
 375         /* Try to summon "num" monsters "near" the given location */
 376         for (k = 0; k < num; k++)
 377         {
 378                 /* Try nine locations */
 379                 for (i = 0; i < 9; i++)
 380                 {
 381                         int d = 1;
 382
 383                         /* Pick a nearby location */
 384                         scatter(&y, &x, y1, x1, d, 0);
 385
 386                         /* Require "empty" floor grids */
 387                         c_ptr = &cave[y][x];
 388                         if (!cave_empty_grid(c_ptr)) continue;
 389
 390                         /* Place the monster (allow groups) */
 391                         monster_level = base_level + 2;
 392                         (void)place_monster(y, x, (PM_ALLOW_SLEEP | PM_ALLOW_GROUP));
 393                         monster_level = base_level;
 394                 }
 395         }
 396 }
 397
 398
 399 /*
 400  * Count the number of walls adjacent to the given grid.
 401  *
 402  * Note -- Assumes "in_bounds(y, x)"
 403  *
 404  * We count only granite walls and permanent walls.
 405  */
 406 int next_to_walls(int y, int x)
 407 {
 408         int     k = 0;
 409
 410         if (cave_floor_grid(&cave[y + 1][x])) k++;
 411         if (cave_floor_grid(&cave[y - 1][x])) k++;
 412         if (cave_floor_grid(&cave[y][x + 1])) k++;
 413         if (cave_floor_grid(&cave[y][x - 1])) k++;
 414
 415         return (k);
 416 }
 417
 418
 419 /*
 420  * Always picks a correct direction
 421  */
 422 void correct_dir(int *rdir, int *cdir, int y1, int x1, int y2, int x2)
 423 {
 424         /* Extract vertical and horizontal directions */
 425         *rdir = (y1 == y2) ? 0 : (y1 < y2) ? 1 : -1;
 426         *cdir = (x1 == x2) ? 0 : (x1 < x2) ? 1 : -1;
 427
 428         /* Never move diagonally */
 429         if (*rdir && *cdir)
 430         {
 431                 if (randint0(100) < 50)
 432                         *rdir = 0;
 433                 else
 434                         *cdir = 0;
 435         }
 436 }
 437
 438
 439
 440 /*
 441  * Pick a random direction
 442  */
 443 void rand_dir(int *rdir, int *cdir)
 444 {
 445         /* Pick a random direction */
 446         int i = randint0(4);
 447
 448         /* Extract the dy/dx components */
 449         *rdir = ddy_ddd[i];
 450         *cdir = ddx_ddd[i];
 451 }
 452
 453
 454 /* Function that sees if a square is a floor.  (Includes range checking.) */
 455 bool get_is_floor(int x, int y)
 456 {
 457         if (!in_bounds(y, x))
 458         {
 459                 /* Out of bounds */
 460                 return (FALSE);
 461         }
 462
 463         /* Do the real check */
 464         if (is_floor_bold(y, x)) return (TRUE);
 465
 466         return (FALSE);
 467 }
 468
 469
 470 /* Set a square to be floor.  (Includes range checking.) */
 471 void set_floor(int x, int y)
 472 {
 473         if (!in_bounds(y, x))
 474         {
 475                 /* Out of bounds */
 476                 return;
 477         }
 478
 479         if (cave[y][x].info & CAVE_ROOM)
 480         {
 481                 /* A room border don't touch. */
 482                 return;
 483         }
 484
 485         /* Set to be floor if is a wall (don't touch lakes). */
 486         if (is_extra_bold(y, x))
 487                 place_floor_bold(y, x);
 488 }
 489
 490
 491
 492 /*
 493  * Constructs a tunnel between two points
 494  *
 495  * This function must be called BEFORE any streamers are created,
 496  * since we use the special "granite wall" sub-types to keep track
 497  * of legal places for corridors to pierce rooms.
 498  *
 499  * We use "door_flag" to prevent excessive construction of doors
 500  * along overlapping corridors.
 501  *
 502  * We queue the tunnel grids to prevent door creation along a corridor
 503  * which intersects itself.
 504  *
 505  * We queue the wall piercing grids to prevent a corridor from leaving
 506  * a room and then coming back in through the same entrance.
 507  *
 508  * We "pierce" grids which are "outer" walls of rooms, and when we
 509  * do so, we change all adjacent "outer" walls of rooms into "solid"
 510  * walls so that no two corridors may use adjacent grids for exits.
 511  *
 512  * The "solid" wall check prevents corridors from "chopping" the
 513  * corners of rooms off, as well as "silly" door placement, and
 514  * "excessively wide" room entrances.
 515  *
 516  * Useful "feat" values:
 517  *   FEAT_WALL_EXTRA -- granite walls
 518  *   FEAT_WALL_INNER -- inner room walls
 519  *   FEAT_WALL_OUTER -- outer room walls
 520  *   FEAT_WALL_SOLID -- solid room walls
 521  *   FEAT_PERM_EXTRA -- shop walls (perma)
 522  *   FEAT_PERM_INNER -- inner room walls (perma)
 523  *   FEAT_PERM_OUTER -- outer room walls (perma)
 524  *   FEAT_PERM_SOLID -- dungeon border (perma)
 525  */
 526 void build_tunnel(int row1, int col1, int row2, int col2)
 527 {
 528         int y, x;
 529         int tmp_row, tmp_col;
 530         int row_dir, col_dir;
 531         int start_row, start_col;
 532         int main_loop_count = 0;
 533
 534         bool door_flag = FALSE;
 535
 536         cave_type *c_ptr;
 537
 538         /* Save the starting location */
 539         start_row = row1;
 540         start_col = col1;
 541
 542         /* Start out in the correct direction */
 543         correct_dir(&row_dir, &col_dir, row1, col1, row2, col2);
 544
 545         /* Keep going until done (or bored) */
 546         while ((row1 != row2) || (col1 != col2))
 547         {
 548                 /* Mega-Hack -- Paranoia -- prevent infinite loops */
 549                 if (main_loop_count++ > 2000) break;
 550
 551                 /* Allow bends in the tunnel */
 552                 if (randint0(100) < dun_tun_chg)
 553                 {
 554                         /* Acquire the correct direction */
 555                         correct_dir(&row_dir, &col_dir, row1, col1, row2, col2);
 556
 557                         /* Random direction */
 558                         if (randint0(100) < dun_tun_rnd)
 559                         {
 560                                 rand_dir(&row_dir, &col_dir);
 561                         }
 562                 }
 563
 564                 /* Get the next location */
 565                 tmp_row = row1 + row_dir;
 566                 tmp_col = col1 + col_dir;
 567
 568
 569                 /* Extremely Important -- do not leave the dungeon */
 570                 while (!in_bounds(tmp_row, tmp_col))
 571                 {
 572                         /* Acquire the correct direction */
 573                         correct_dir(&row_dir, &col_dir, row1, col1, row2, col2);
 574
 575                         /* Random direction */
 576                         if (randint0(100) < dun_tun_rnd)
 577                         {
 578                                 rand_dir(&row_dir, &col_dir);
 579                         }
 580
 581                         /* Get the next location */
 582                         tmp_row = row1 + row_dir;
 583                         tmp_col = col1 + col_dir;
 584                 }
 585
 586
 587                 /* Access the location */
 588                 c_ptr = &cave[tmp_row][tmp_col];
 589
 590
 591                 /* Avoid the edge of the dungeon */
 592                 if (c_ptr->feat == FEAT_PERM_SOLID) continue;
 593
 594                 /* Avoid the edge of vaults */
 595                 if (c_ptr->feat == FEAT_PERM_OUTER) continue;
 596
 597                 /* Avoid "solid" granite walls */
 598                 if (is_solid_grid(c_ptr)) continue;
 599
 600                 /* Pierce "outer" walls of rooms */
 601                 if (is_outer_grid(c_ptr))
 602                 {
 603                         /* Acquire the "next" location */
 604                         y = tmp_row + row_dir;
 605                         x = tmp_col + col_dir;
 606
 607                         /* Hack -- Avoid outer/solid permanent walls */
 608                         if (cave[y][x].feat == FEAT_PERM_SOLID) continue;
 609                         if (cave[y][x].feat == FEAT_PERM_OUTER) continue;
 610
 611                         /* Hack -- Avoid outer/solid granite walls */
 612                         if (is_outer_bold(y, x)) continue;
 613                         if (is_solid_bold(y, x)) continue;
 614
 615                         /* Accept this location */
 616                         row1 = tmp_row;
 617                         col1 = tmp_col;
 618
 619                         /* Save the wall location */
 620                         if (dun->wall_n < WALL_MAX)
 621                         {
 622                                 dun->wall[dun->wall_n].y = row1;
 623                                 dun->wall[dun->wall_n].x = col1;
 624                                 dun->wall_n++;
 625                         }
 626
 627                         /* Forbid re-entry near this piercing */
 628                         for (y = row1 - 1; y <= row1 + 1; y++)
 629                         {
 630                                 for (x = col1 - 1; x <= col1 + 1; x++)
 631                                 {
 632                                         /* Convert adjacent "outer" walls as "solid" walls */
 633                                         if (is_outer_bold(y, x))
 634                                         {
 635                                                 /* Change the wall to a "solid" wall */
 636                                                 place_solid_noperm_bold(y, x);
 637                                         }
 638                                 }
 639                         }
 640                 }
 641
 642                 /* Travel quickly through rooms */
 643                 else if (c_ptr->info & (CAVE_ROOM))
 644                 {
 645                         /* Accept the location */
 646                         row1 = tmp_row;
 647                         col1 = tmp_col;
 648                 }
 649
 650                 /* Tunnel through all other walls */
 651                 else if (is_extra_grid(c_ptr) || is_inner_grid(c_ptr) || is_solid_grid(c_ptr))
 652                 {
 653                         /* Accept this location */
 654                         row1 = tmp_row;
 655                         col1 = tmp_col;
 656
 657                         /* Save the tunnel location */
 658                         if (dun->tunn_n < TUNN_MAX)
 659                         {
 660                                 dun->tunn[dun->tunn_n].y = row1;
 661                                 dun->tunn[dun->tunn_n].x = col1;
 662                                 dun->tunn_n++;
 663                         }
 664
 665                         /* Allow door in next grid */
 666                         door_flag = FALSE;
 667                 }
 668
 669                 /* Handle corridor intersections or overlaps */
 670                 else
 671                 {
 672                         /* Accept the location */
 673                         row1 = tmp_row;
 674                         col1 = tmp_col;
 675
 676                         /* Collect legal door locations */
 677                         if (!door_flag)
 678                         {
 679                                 /* Save the door location */
 680                                 if (dun->door_n < DOOR_MAX)
 681                                 {
 682                                         dun->door[dun->door_n].y = row1;
 683                                         dun->door[dun->door_n].x = col1;
 684                                         dun->door_n++;
 685                                 }
 686
 687                                 /* No door in next grid */
 688                                 door_flag = TRUE;
 689                         }
 690
 691                         /* Hack -- allow pre-emptive tunnel termination */
 692                         if (randint0(100) >= dun_tun_con)
 693                         {
 694                                 /* Distance between row1 and start_row */
 695                                 tmp_row = row1 - start_row;
 696                                 if (tmp_row < 0) tmp_row = (-tmp_row);
 697
 698                                 /* Distance between col1 and start_col */
 699                                 tmp_col = col1 - start_col;
 700                                 if (tmp_col < 0) tmp_col = (-tmp_col);
 701
 702                                 /* Terminate the tunnel */
 703                                 if ((tmp_row > 10) || (tmp_col > 10)) break;
 704                         }
 705                 }
 706         }
 707 }
 708
 709
 710 /*
 711  * This routine adds the square to the tunnel
 712  * It also checks for SOLID walls - and returns a nearby
 713  * non-SOLID square in (x,y) so that a simple avoiding
 714  * routine can be used. The returned boolean value reflects
 715  * whether or not this routine hit a SOLID wall.
 716  *
 717  * "affectwall" toggles whether or not this new square affects
 718  * the boundaries of rooms. - This is used by the catacomb
 719  * routine.
 720  */
 721 static bool set_tunnel(int *x, int *y, bool affectwall)
 722 {
 723         int feat, i, j, dx, dy;
 724
 725         cave_type *c_ptr = &cave[*y][*x];
 726
 727         if (!in_bounds(*y, *x)) return TRUE;
 728
 729         feat = c_ptr->feat;
 730
 731         if ((feat == FEAT_PERM_OUTER) ||
 732             (feat == FEAT_PERM_INNER) ||
 733             is_inner_grid(c_ptr))
 734         {
 735                 /*
 736                  * Ignore permanent walls - sometimes cannot tunnel around them anyway
 737                  * so don't try - it just complicates things unnecessarily.
 738                  */
 739                 return TRUE;
 740         }
 741
 742         if (is_extra_bold(*y,*x))
 743         {
 744                 /* Save the tunnel location */
 745                 if (dun->tunn_n < TUNN_MAX)
 746                 {
 747                                 dun->tunn[dun->tunn_n].y = *y;
 748                                 dun->tunn[dun->tunn_n].x = *x;
 749                                 dun->tunn_n++;
 750                 }
 751
 752                 return TRUE;
 753         }
 754
 755         if (is_floor_bold(*y, *x))
 756         {
 757                 /* Don't do anything */
 758                 return TRUE;
 759         }
 760
 761         if (is_outer_grid(c_ptr) && affectwall)
 762         {
 763                 /* Save the wall location */
 764                 if (dun->wall_n < WALL_MAX)
 765                 {
 766                         dun->wall[dun->wall_n].y = *y;
 767                         dun->wall[dun->wall_n].x = *x;
 768                         dun->wall_n++;
 769                 }
 770
 771                 /* Forbid re-entry near this piercing */
 772                 for (j = *y - 1; j <= *y + 1; j++)
 773                 {
 774                         for (i = *x - 1; i <= *x + 1; i++)
 775                         {
 776                                 /* Convert adjacent "outer" walls as "solid" walls */
 777                                 if (is_outer_bold(j, i))
 778                                 {
 779                                         /* Change the wall to a "solid" wall */
 780                                         place_solid_noperm_bold(j, i);
 781                                 }
 782                         }
 783                 }
 784                 place_floor_bold(*y, *x);
 785
 786                 return TRUE;
 787         }
 788
 789         if (is_solid_grid(c_ptr) && affectwall)
 790         {
 791                 /* cannot place tunnel here - use a square to the side */
 792
 793                 /* find usable square and return value in (x,y) */
 794
 795                 i = 50;
 796
 797                 dy = 0;
 798                 dx = 0;
 799                 while ((i > 0) && is_solid_bold(*y + dy, *x + dx))
 800                 {
 801                         dy = randint0(3) - 1;
 802                         dx = randint0(3) - 1;
 803
 804                         if (!in_bounds(*y + dy, *x + dx))
 805                         {
 806                                 dx = 0;
 807                                 dy = 0;
 808                         }
 809
 810                         i--;
 811                 }
 812
 813                 if (i == 0)
 814                 {
 815                         /* Failed for some reason: hack - ignore the solidness */
 816                         place_outer_grid(c_ptr);
 817                         dx = 0;
 818                         dy = 0;
 819                 }
 820
 821                 /* Give new, acceptable coordinate. */
 822                 *x = *x + dx;
 823                 *y = *y + dy;
 824
 825                 return FALSE;
 826         }
 827
 828         return TRUE;
 829 }
 830
 831
 832 /*
 833  * This routine creates the catacomb-like tunnels by removing extra rock.
 834  * Note that this routine is only called on "even" squares - so it gives
 835  * a natural checkerboard pattern.
 836  */
 837 static void create_cata_tunnel(int x, int y)
 838 {
 839         int x1, y1;
 840
 841         /* Build tunnel */
 842         x1 = x - 1;
 843         y1 = y;
 844         set_tunnel(&x1, &y1, FALSE);
 845
 846         x1 = x + 1;
 847         y1 = y;
 848         set_tunnel(&x1, &y1, FALSE);
 849
 850         x1 = x;
 851         y1 = y - 1;
 852         set_tunnel(&x1, &y1, FALSE);
 853
 854         x1 = x;
 855         y1 = y + 1;
 856         set_tunnel(&x1, &y1, FALSE);
 857 }
 858
 859
 860 /*
 861  * This routine does the bulk of the work in creating the new types of tunnels.
 862  * It is designed to use very simple algorithms to go from (x1,y1) to (x2,y2)
 863  * It doesn't need to add any complexity - straight lines are fine.
 864  * The SOLID walls are avoided by a recursive algorithm which tries random ways
 865  * around the obstical until it works.  The number of itterations is counted, and it
 866  * this gets too large the routine exits. This should stop any crashes - but may leave
 867  * small gaps in the tunnel where there are too many SOLID walls.
 868  *
 869  * Type 1 tunnels are extremely simple - straight line from A to B.  This is only used
 870  * as a part of the dodge SOLID walls algorithm.
 871  *
 872  * Type 2 tunnels are made of two straight lines at right angles. When this is used with
 873  * short line segments it gives the "cavelike" tunnels seen deeper in the dungeon.
 874  *
 875  * Type 3 tunnels are made of two straight lines like type 2, but with extra rock removed.
 876  * This, when used with longer line segments gives the "catacomb-like" tunnels seen near
 877  * the surface.
 878  */
 879 static void short_seg_hack(int x1, int y1, int x2, int y2, int type, int count, bool *fail)
 880 {
 881         int i, x, y;
 882         int length;
 883
 884         /* Check for early exit */
 885         if (!(*fail)) return;
 886
 887         length = distance(x1, y1, x2, y2);
 888
 889         count++;
 890
 891         if ((type == 1) && (length != 0))
 892         {
 893
 894                 for (i = 0; i <= length; i++)
 895                 {
 896                         x = x1 + i * (x2 - x1) / length;
 897                         y = y1 + i * (y2 - y1) / length;
 898                         if (!set_tunnel(&x, &y, TRUE))
 899                         {
 900                                 if (count > 50)
 901                                 {
 902                                         /* This isn't working - probably have an infinite loop */
 903                                         *fail = FALSE;
 904                                         return;
 905                                 }
 906
 907                                 /* solid wall - so try to go around */
 908                                 short_seg_hack(x, y, x1 + (i - 1) * (x2 - x1) / length, y1 + (i - 1) * (y2 - y1) / length, 1, count, fail);
 909                                 short_seg_hack(x, y, x1 + (i + 1) * (x2 - x1) / length, y1 + (i + 1) * (y2 - y1) / length, 1, count, fail);
 910                         }
 911                 }
 912         }
 913         else if ((type == 2) || (type == 3))
 914         {
 915                 if (x1 < x2)
 916                 {
 917                         for (i = x1; i <= x2; i++)
 918                         {
 919                                 x = i;
 920                                 y = y1;
 921                                 if (!set_tunnel(&x, &y, TRUE))
 922                                 {
 923                                         /* solid wall - so try to go around */
 924                                         short_seg_hack(x, y, i - 1, y1, 1, count, fail);
 925                                         short_seg_hack(x, y, i + 1, y1, 1, count, fail);
 926                                 }
 927                                 if ((type == 3) && ((x + y) % 2))
 928                                 {
 929                                         create_cata_tunnel(i, y1);
 930                                 }
 931                         }
 932                 }
 933                 else
 934                 {
 935                         for (i = x2; i <= x1; i++)
 936                         {
 937                                 x = i;
 938                                 y = y1;
 939                                 if (!set_tunnel(&x, &y, TRUE))
 940                                 {
 941                                         /* solid wall - so try to go around */
 942                                         short_seg_hack(x, y, i - 1, y1, 1, count, fail);
 943                                         short_seg_hack(x, y, i + 1, y1, 1, count, fail);
 944                                 }
 945                                 if ((type == 3) && ((x + y) % 2))
 946                                 {
 947                                         create_cata_tunnel(i, y1);
 948                                 }
 949                         }
 950
 951                 }
 952                 if (y1 < y2)
 953                 {
 954                         for (i = y1; i <= y2; i++)
 955                         {
 956                                 x = x2;
 957                                 y = i;
 958                                 if (!set_tunnel(&x, &y, TRUE))
 959                                 {
 960                                         /* solid wall - so try to go around */
 961                                         short_seg_hack(x, y, x2, i - 1, 1, count, fail);
 962                                         short_seg_hack(x, y, x2, i + 1, 1, count, fail);
 963                                 }
 964                                 if ((type == 3) && ((x + y) % 2))
 965                                 {
 966                                         create_cata_tunnel(x2, i);
 967                                 }
 968                         }
 969                 }
 970                 else
 971                 {
 972                         for (i = y2; i <= y1; i++)
 973                         {
 974                                 x = x2;
 975                                 y = i;
 976                                 if (!set_tunnel(&x, &y, TRUE))
 977                                 {
 978                                         /* solid wall - so try to go around */
 979                                         short_seg_hack(x, y, x2, i - 1, 1, count, fail);
 980                                         short_seg_hack(x, y, x2, i + 1, 1, count, fail);
 981                                 }
 982                                 if ((type == 3) && ((x + y) % 2))
 983                                 {
 984                                         create_cata_tunnel(x2, i);
 985                                 }
 986                         }
 987                 }
 988         }
 989 }
 990
 991
 992 /*
 993  * This routine maps a path from (x1, y1) to (x2, y2) avoiding SOLID walls.
 994  * Permanent rock is ignored in this path finding- sometimes there is no
 995  * path around anyway -so there will be a crash if we try to find one.
 996  * This routine is much like the river creation routine in Zangband.
 997  * It works by dividing a line segment into two.  The segments are divided
 998  * until they are less than "cutoff" - when the corresponding routine from
 999  * "short_seg_hack" is called.
1000  * Note it is VERY important that the "stop if hit another passage" logic
1001  * stays as is.  Without this the dungeon turns into Swiss Cheese...
1002  */
1003 bool build_tunnel2(int x1, int y1, int x2, int y2, int type, int cutoff)
1004 {
1005         int x3, y3, dx, dy;
1006         int changex, changey;
1007         int midval;
1008         int length;
1009         int i;
1010         bool retval, firstsuccede;
1011         cave_type *c_ptr;
1012
1013         length = distance(x1, y1, x2, y2);
1014
1015         if (length > cutoff)
1016         {
1017                 /*
1018                 * Divide path in half and call routine twice.
1019                  */
1020                 dx = (x2 - x1) / 2;
1021                 dy = (y2 - y1) / 2;
1022
1023                 /* perturbation perpendicular to path */
1024                 changex = (randint0(abs(dy) + 2) * 2 - abs(dy) - 1) / 2;
1025
1026                 /* perturbation perpendicular to path */
1027                 changey = (randint0(abs(dx) + 2) * 2 - abs(dx) - 1) / 2;
1028
1029                 /* Work out "mid" ponit */
1030                 x3 = x1 + dx + changex;
1031                 y3 = y1 + dy + changey;
1032
1033                 /* See if in bounds - if not - do not perturb point */
1034                 if (!in_bounds(y3, x3))
1035                 {
1036                         x3 = (x1 + x2) / 2;
1037                         y3 = (y1 + y2) / 2;
1038                 }
1039                 /* cache midvalue */
1040                 c_ptr = &cave[y3][x3];
1041                 midval = cave[y3][x3].feat;
1042                 if (is_solid_grid(c_ptr))
1043                 {
1044                         /* move midpoint a bit to avoid problem. */
1045
1046                         i = 50;
1047
1048                         dy = 0;
1049                         dx = 0;
1050                         while ((i > 0) && is_solid_bold(y3 + dy, x3 + dx))
1051                         {
1052                                 dy = randint0(3) - 1;
1053                                 dx = randint0(3) - 1;
1054                                 if (!in_bounds(y3 + dy, x3 + dx))
1055                                 {
1056                                         dx = 0;
1057                                         dy = 0;
1058                                 }
1059                                 i--;
1060                         }
1061
1062                         if (i == 0)
1063                         {
1064                                 /* Failed for some reason: hack - ignore the solidness */
1065                                 place_outer_bold(y3, x3);
1066                                 dx = 0;
1067                                 dy = 0;
1068                         }
1069                         y3 += dy;
1070                         x3 += dx;
1071                         c_ptr = &cave[y3][x3];
1072                         midval = cave[y3][x3].feat;
1073                 }
1074
1075                 if (is_floor_grid(c_ptr))
1076                 {
1077                         if (build_tunnel2(x1, y1, x3, y3, type, cutoff))
1078                         {
1079                                 if ((cave[y3][x3].info & CAVE_ROOM) || (randint1(100) > 95))
1080                                 {
1081                                         /* do second half only if works + if have hit a room */
1082                                         retval = build_tunnel2(x3, y3, x2, y2, type, cutoff);
1083                                 }
1084                                 else
1085                                 {
1086                                         /* have hit another tunnel - make a set of doors here */
1087                                         retval = FALSE;
1088
1089                                         /* Save the door location */
1090                                         if (dun->door_n < DOOR_MAX)
1091                                         {
1092                                                 dun->door[dun->door_n].y = y3;
1093                                                 dun->door[dun->door_n].x = x3;
1094                                                 dun->door_n++;
1095                                         }
1096                                 }
1097                                 firstsuccede = TRUE;
1098                         }
1099                         else
1100                         {
1101                                 /* false- didn't work all the way */
1102                                 retval = FALSE;
1103                                 firstsuccede = FALSE;
1104                         }
1105                 }
1106                 else
1107                 {
1108                         /* tunnel through walls */
1109                         if (build_tunnel2(x1, y1, x3, y3, type, cutoff))
1110                         {
1111                                 retval = build_tunnel2(x3, y3, x2, y2, type, cutoff);
1112                                 firstsuccede = TRUE;
1113                         }
1114                         else
1115                         {
1116                                 /* false- didn't work all the way */
1117                                 retval = FALSE;
1118                                 firstsuccede = FALSE;
1119                         }
1120                 }
1121                 if (firstsuccede)
1122                 {
1123                         /* only do this if the first half has worked */
1124                         set_tunnel(&x3, &y3, TRUE);
1125                 }
1126                 /* return value calculated above */
1127                 return retval;
1128         }
1129         else
1130         {
1131                 /* Do a short segment */
1132                 retval = TRUE;
1133                 short_seg_hack(x1, y1, x2, y2, type, 0, &retval);
1134
1135                 /* Hack - ignore return value so avoid infinite loops */
1136                 return TRUE;
1137         }
1138 }