src/grid.c

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