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