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