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