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