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