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