src/grid.c

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