src/grid.c

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