src/pathfind.c

   1 /*
   2  * File: pathfind.c
   3  * Purpose: Pathfinding algorithm
   4  *
   5  * Copyright (c) 2004 Christophe Cavalaria, Leon Marrick
   6  *
   7  * This work is free software; you can redistribute it and/or modify it
   8  * under the terms of either:
   9  *
  10  * a) the GNU General Public License as published by the Free Software
  11  *    Foundation, version 2, or
  12  *
  13  * b) the "Angband licence":
  14  *    This software may be copied and distributed for educational, research,
  15  *    and not for profit purposes provided that this copyright and statement
  16  *    are included in all such copies.  Other copyrights may also apply.
  17  */
  18 #include "angband.h"
  19
  20
  21 /*** Constants ***/
  22
  23 /* Maximum size around the player to consider in the pathfinder */
  24 #define MAX_PF_RADIUS 50
  25
  26 /* Maximum distance to consider in the pathfinder */
  27 #define MAX_PF_LENGTH 250
  28
  29
  30 /*** Globals ***/
  31
  32 static int terrain[MAX_PF_RADIUS][MAX_PF_RADIUS];
  33 char pf_result[MAX_PF_LENGTH];
  34 int pf_result_index;
  35
  36 static int ox, oy, ex, ey;
  37
  38
  39 /*** Pathfinding code ***/
  40
  41 static bool is_valid_pf(int y, int x)
  42 {
  43         /* Unvisited means allowed */
  44         if (!(cave_info[y][x] & (CAVE_MARK))) return (TRUE);
  45
  46         /* Require open space */
  47         return (cave_floor_bold(y, x));
  48 }
  49
  50 static void fill_terrain_info(void)
  51 {
  52         int i, j;
  53
  54         ox = MAX(p_ptr->px - MAX_PF_RADIUS / 2, 0);
  55         oy = MAX(p_ptr->py - MAX_PF_RADIUS / 2, 0);
  56
  57         ex = MIN(p_ptr->px + MAX_PF_RADIUS / 2 - 1, DUNGEON_WID);
  58         ey = MIN(p_ptr->py + MAX_PF_RADIUS / 2 - 1, DUNGEON_HGT);
  59
  60         for (i = 0; i < MAX_PF_RADIUS * MAX_PF_RADIUS; i++)
  61                 terrain[0][i] = -1;
  62
  63         for (j = oy; j < ey; j++)
  64                 for (i = ox; i < ex; i++)
  65                         if (is_valid_pf(j, i))
  66                                 terrain[j - oy][i - ox] = MAX_PF_LENGTH;
  67
  68         terrain[p_ptr->py - oy][p_ptr->px - ox] = 1;
  69 }
  70
  71 #define MARK_DISTANCE(c,d) if ((c <= MAX_PF_LENGTH) && (c > d)) { c = d; try_again = (TRUE); }
  72
  73 bool findpath(int y, int x)
  74 {
  75         int i, j, dir;
  76         bool try_again;
  77         int cur_distance;
  78
  79         fill_terrain_info();
  80
  81         terrain[p_ptr->py - oy][p_ptr->px - ox] = 1;
  82
  83         if ((x >= ox) && (x < ex) && (y >= oy) && (y < ey))
  84         {
  85                 if ((cave_m_idx[y][x] > 0) && (mon_list[cave_m_idx[y][x]].ml))
  86                 {
  87                         terrain[y - oy][x - ox] = MAX_PF_LENGTH;
  88                 }
  89
  90 #if 0
  91                 else if (terrain[y-oy][x-ox] != MAX_PF_LENGTH)
  92                 {
  93                    bell("Target blocked");
  94                    return (FALSE);
  95                 }
  96 #endif
  97
  98                 terrain[y - oy][x - ox] = MAX_PF_LENGTH;
  99         }
 100         else
 101         {
 102                 bell("Target out of range.");
 103                 return (FALSE);
 104         }
 105
 106         if (terrain[y - oy][x - ox] == -1)
 107         {
 108                 bell("Target space forbidden");
 109                 return (FALSE);
 110         }
 111
 112
 113         /*
 114          * And now starts the very naive and very
 115          * inefficient pathfinding algorithm
 116          */
 117         do
 118         {
 119                 try_again = FALSE;
 120
 121                 for (j = oy + 1; j < ey - 1; j++)
 122                 {
 123                         for (i = ox + 1; i < ex - 1; i++)
 124                         {
 125                                 cur_distance = terrain[j - oy][i - ox] + 1;
 126
 127                                 if ((cur_distance > 0) && (cur_distance < MAX_PF_LENGTH))
 128                                 {
 129                                         for (dir = 1; dir < 10; dir++)
 130                                         {
 131                                                 if (dir == 5)
 132                                                         dir++;
 133
 134                                                 MARK_DISTANCE(terrain[j - oy + ddy[dir]][i - ox + ddx[dir]], cur_distance);
 135                                         }
 136                                 }
 137                         }
 138                 }
 139
 140                 if (terrain[y - oy][x - ox] < MAX_PF_LENGTH)
 141                         try_again = (FALSE);
 142
 143         }
 144         while (try_again);
 145
 146         /* Failure */
 147         if (terrain[y - oy][x - ox] == MAX_PF_LENGTH)
 148         {
 149                 bell("Target space unreachable.");
 150                 return (FALSE);
 151         }
 152
 153         /* Success */
 154         i = x;
 155         j = y;
 156
 157         pf_result_index = 0;
 158
 159         while ((i != p_ptr->px) || (j != p_ptr->py))
 160         {
 161                 cur_distance = terrain[j - oy][i - ox] - 1;
 162                 for (dir = 1; dir < 10; dir++)
 163                 {
 164                         if (terrain[j - oy + ddy[dir]][i - ox + ddx[dir]] == cur_distance)
 165                                 break;
 166                 }
 167
 168                 /* Should never happend */
 169                 if (dir == 10)
 170                 {
 171                         bell("Wtf ?");
 172                         return (FALSE);
 173                 }
 174
 175                 else if (dir == 5)
 176                 {
 177                         bell("Heyyy !");
 178                         return (FALSE);
 179                 }
 180
 181                 pf_result[pf_result_index++] = '0' + (char)(10 - dir);
 182                 i += ddx[dir];
 183                 j += ddy[dir];
 184         }
 185
 186         pf_result_index--;
 187
 188         return (TRUE);
 189 }
 190
 191
 192
 193 /*
 194  * Accept values for y and x (considered as the endpoints of lines) between
 195  * 0 and 40, and return an angle in degrees (divided by two).  -LM-
 196  *
 197  * This table's input and output need some processing:
 198  *
 199  * Because this table gives degrees for a whole circle, up to radius 20, its
 200  * origin is at (x,y) = (20, 20).  Therefore, the input code needs to find
 201  * the origin grid (where the lines being compared come from), and then map
 202  * it to table grid 20,20.  Do not, however, actually try to compare the
 203  * angle of a line that begins and ends at the origin with any other line -
 204  * it is impossible mathematically, and the table will return the value "255".
 205  *
 206  * The output of this table also needs to be massaged, in order to avoid the
 207  * discontinuity at 0/180 degrees.  This can be done by:
 208  *   rotate = 90 - first value
 209  *   this rotates the first input to the 90 degree line)
 210  *   tmp = ABS(second value + rotate) % 180
 211  *   diff = ABS(90 - tmp) = the angular difference (divided by two) between
 212  *   the first and second values.
 213  *
 214  * Note that grids diagonal to the origin have unique angles.
 215  */
 216 byte get_angle_to_grid[41][41] =
 217 {
 218   {  68,  67,  66,  65,  64,  63,  62,  62,  60,  59,  58,  57,  56,  55,  53,  52,  51,  49,  48,  46,  45,  44,  42,  41,  39,  38,  37,  35,  34,  33,  32,  31,  30,  28,  28,  27,  26,  25,  24,  24,  23 },
 219   {  69,  68,  67,  66,  65,  64,  63,  62,  61,  60,  59,  58,  56,  55,  54,  52,  51,  49,  48,  47,  45,  43,  42,  41,  39,  38,  36,  35,  34,  32,  31,  30,  29,  28,  27,  26,  25,  24,  24,  23,  22 },
 220   {  69,  69,  68,  67,  66,  65,  64,  63,  62,  61,  60,  58,  57,  56,  54,  53,  51,  50,  48,  47,  45,  43,  42,  40,  39,  37,  36,  34,  33,  32,  30,  29,  28,  27,  26,  25,  24,  24,  23,  22,  21 },
 221   {  70,  69,  69,  68,  67,  66,  65,  64,  63,  61,  60,  59,  58,  56,  55,  53,  52,  50,  48,  47,  45,  43,  42,  40,  38,  37,  35,  34,  32,  31,  30,  29,  27,  26,  25,  24,  24,  23,  22,  21,  20 },
 222   {  71,  70,  69,  69,  68,  67,  66,  65,  63,  62,  61,  60,  58,  57,  55,  54,  52,  50,  49,  47,  45,  43,  41,  40,  38,  36,  35,  33,  32,  30,  29,  28,  27,  25,  24,  24,  23,  22,  21,  20,  19 },
 223   {  72,  71,  70,  69,  69,  68,  67,  65,  64,  63,  62,  60,  59,  58,  56,  54,  52,  51,  49,  47,  45,  43,  41,  39,  38,  36,  34,  32,  31,  30,  28,  27,  26,  25,  24,  23,  22,  21,  20,  19,  18 },
 224   {  73,  72,  71,  70,  69,  69,  68,  66,  65,  64,  63,  61,  60,  58,  57,  55,  53,  51,  49,  47,  45,  43,  41,  39,  37,  35,  33,  32,  30,  29,  27,  26,  25,  24,  23,  22,  21,  20,  19,  18,  17 },
 225   {  73,  73,  72,  71,  70,  70,  69,  68,  66,  65,  64,  62,  61,  59,  57,  56,  54,  51,  49,  47,  45,  43,  41,  39,  36,  34,  33,  31,  29,  28,  26,  25,  24,  23,  21,  20,  20,  19,  18,  17,  17 },
 226   {  75,  74,  73,  72,  72,  71,  70,  69,  68,  66,  65,  63,  62,  60,  58,  56,  54,  52,  50,  47,  45,  43,  40,  38,  36,  34,  32,  30,  28,  27,  25,  24,  23,  21,  20,  19,  18,  18,  17,  16,  15 },
 227   {  76,  75,  74,  74,  73,  72,  71,  70,  69,  68,  66,  65,  63,  61,  59,  57,  55,  53,  50,  48,  45,  42,  40,  37,  35,  33,  31,  29,  27,  25,  24,  23,  21,  20,  19,  18,  17,  16,  16,  15,  14 },
 228   {  77,  76,  75,  75,  74,  73,  72,  71,  70,  69,  68,  66,  64,  62,  60,  58,  56,  53,  51,  48,  45,  42,  39,  37,  34,  32,  30,  28,  26,  24,  23,  21,  20,  19,  18,  17,  16,  15,  15,  14,  13 },
 229   {  78,  77,  77,  76,  75,  75,  74,  73,  72,  70,  69,  68,  66,  64,  62,  60,  57,  54,  51,  48,  45,  42,  39,  36,  33,  30,  28,  26,  24,  23,  21,  20,  18,  17,  16,  15,  15,  14,  13,  13,  12 },
 230   {  79,  79,  78,  77,  77,  76,  75,  74,  73,  72,  71,  69,  68,  66,  63,  61,  58,  55,  52,  49,  45,  41,  38,  35,  32,  29,  27,  24,  23,  21,  19,  18,  17,  16,  15,  14,  13,  13,  12,  11,  11 },
 231   {  80,  80,  79,  79,  78,  77,  77,  76,  75,  74,  73,  71,  69,  68,  65,  63,  60,  57,  53,  49,  45,  41,  37,  33,  30,  27,  25,  23,  21,  19,  17,  16,  15,  14,  13,  13,  12,  11,  11,  10,  10 },
 232   {  82,  81,  81,  80,  80,  79,  78,  78,  77,  76,  75,  73,  72,  70,  68,  65,  62,  58,  54,  50,  45,  40,  36,  32,  28,  25,  23,  20,  18,  17,  15,  14,  13,  12,  12,  11,  10,  10,   9,   9,   8 },
 233   {  83,  83,  82,  82,  81,  81,  80,  79,  79,  78,  77,  75,  74,  72,  70,  68,  64,  60,  56,  51,  45,  39,  34,  30,  26,  23,  20,  18,  16,  15,  13,  12,  11,  11,  10,   9,   9,   8,   8,   7,   7 },
 234   {  84,  84,  84,  83,  83,  83,  82,  81,  81,  80,  79,  78,  77,  75,  73,  71,  68,  63,  58,  52,  45,  38,  32,  27,  23,  19,  17,  15,  13,  12,  11,  10,   9,   9,   8,   7,   7,   7,   6,   6,   6 },
 235   {  86,  86,  85,  85,  85,  84,  84,  84,  83,  82,  82,  81,  80,  78,  77,  75,  72,  68,  62,  54,  45,  36,  28,  23,  18,  15,  13,  12,  10,   9,   8,   8,   7,   6,   6,   6,   5,   5,   5,   4,   4 },
 236   {  87,  87,  87,  87,  86,  86,  86,  86,  85,  85,  84,  84,  83,  82,  81,  79,  77,  73,  68,  58,  45,  32,  23,  17,  13,  11,   9,   8,   7,   6,   6,   5,   5,   4,   4,   4,   4,   3,   3,   3,   3 },
 237   {  89,  88,  88,  88,  88,  88,  88,  88,  88,  87,  87,  87,  86,  86,  85,  84,  83,  81,  77,  68,  45,  23,  13,   9,   7,   6,   5,   4,   4,   3,   3,   3,   2,   2,   2,   2,   2,   2,   2,   2,   1 },
 238   {  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90,  90, 255,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0 },
 239   {  91,  92,  92,  92,  92,  92,  92,  92,  92,  93,  93,  93,  94,  94,  95,  96,  97,  99, 103, 113, 135, 158, 167, 171, 173, 174, 175, 176, 176, 177, 177, 177, 178, 178, 178, 178, 178, 178, 178, 178, 179 },
 240   {  93,  93,  93,  93,  94,  94,  94,  94,  95,  95,  96,  96,  97,  98,  99, 101, 103, 107, 113, 122, 135, 148, 158, 163, 167, 169, 171, 172, 173, 174, 174, 175, 175, 176, 176, 176, 176, 177, 177, 177, 177 },
 241   {  94,  94,  95,  95,  95,  96,  96,  96,  97,  98,  98,  99, 100, 102, 103, 105, 108, 113, 118, 126, 135, 144, 152, 158, 162, 165, 167, 168, 170, 171, 172, 172, 173, 174, 174, 174, 175, 175, 175, 176, 176 },
 242   {  96,  96,  96,  97,  97,  97,  98,  99,  99, 100, 101, 102, 103, 105, 107, 109, 113, 117, 122, 128, 135, 142, 148, 153, 158, 161, 163, 165, 167, 168, 169, 170, 171, 171, 172, 173, 173, 173, 174, 174, 174 },
 243   {  97,  97,  98,  98,  99,  99, 100, 101, 101, 102, 103, 105, 106, 108, 110, 113, 116, 120, 124, 129, 135, 141, 146, 150, 154, 158, 160, 162, 164, 165, 167, 168, 169, 169, 170, 171, 171, 172, 172, 173, 173 },
 244   {  98,  99,  99, 100, 100, 101, 102, 102, 103, 104, 105, 107, 108, 110, 113, 115, 118, 122, 126, 130, 135, 140, 144, 148, 152, 155, 158, 160, 162, 163, 165, 166, 167, 168, 168, 169, 170, 170, 171, 171, 172 },
 245   { 100, 100, 101, 101, 102, 103, 103, 104, 105, 106, 107, 109, 111, 113, 115, 117, 120, 123, 127, 131, 135, 139, 143, 147, 150, 153, 155, 158, 159, 161, 163, 164, 165, 166, 167, 167, 168, 169, 169, 170, 170 },
 246   { 101, 101, 102, 103, 103, 104, 105, 106, 107, 108, 109, 111, 113, 114, 117, 119, 122, 125, 128, 131, 135, 139, 142, 145, 148, 151, 153, 156, 158, 159, 161, 162, 163, 164, 165, 166, 167, 167, 168, 169, 169 },
 247   { 102, 103, 103, 104, 105, 105, 106, 107, 108, 110, 111, 113, 114, 116, 118, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 152, 154, 156, 158, 159, 160, 162, 163, 164, 165, 165, 166, 167, 167, 168 },
 248   { 103, 104, 105, 105, 106, 107, 108, 109, 110, 111, 113, 114, 116, 118, 120, 122, 124, 127, 129, 132, 135, 138, 141, 143, 146, 148, 150, 152, 154, 156, 158, 159, 160, 161, 162, 163, 164, 165, 165, 166, 167 },
 249   { 104, 105, 106, 106, 107, 108, 109, 110, 111, 113, 114, 115, 117, 119, 121, 123, 125, 127, 130, 132, 135, 138, 140, 143, 145, 147, 149, 151, 153, 155, 156, 158, 159, 160, 161, 162, 163, 164, 164, 165, 166 },
 250   { 105, 106, 107, 108, 108, 109, 110, 111, 113, 114, 115, 117, 118, 120, 122, 124, 126, 128, 130, 133, 135, 137, 140, 142, 144, 146, 148, 150, 152, 153, 155, 156, 158, 159, 160, 161, 162, 162, 163, 164, 165 },
 251   { 107, 107, 108, 109, 110, 110, 111, 113, 114, 115, 116, 118, 119, 121, 123, 124, 126, 129, 131, 133, 135, 137, 139, 141, 144, 146, 147, 149, 151, 152, 154, 155, 156, 158, 159, 160, 160, 161, 162, 163, 163 },
 252   { 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 119, 120, 122, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 148, 150, 151, 153, 154, 155, 156, 158, 159, 159, 160, 161, 162, 163 },
 253   { 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 120, 121, 122, 124, 126, 128, 129, 131, 133, 135, 137, 139, 141, 142, 144, 146, 148, 149, 150, 152, 153, 154, 155, 157, 158, 159, 159, 160, 161, 162 },
 254   { 109, 110, 111, 112, 113, 114, 114, 115, 117, 118, 119, 120, 122, 123, 125, 126, 128, 130, 131, 133, 135, 137, 139, 140, 142, 144, 145, 147, 148, 150, 151, 152, 153, 155, 156, 157, 158, 159, 159, 160, 161 },
 255   { 110, 111, 112, 113, 114, 114, 115, 116, 117, 119, 120, 121, 122, 124, 125, 127, 128, 130, 132, 133, 135, 137, 138, 140, 142, 143, 145, 146, 148, 149, 150, 151, 153, 154, 155, 156, 157, 158, 159, 159, 160 },
 256   { 111, 112, 113, 114, 114, 115, 116, 117, 118, 119, 120, 122, 123, 124, 126, 127, 129, 130, 132, 133, 135, 137, 138, 140, 141, 143, 144, 146, 147, 148, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 159 },
 257   { 112, 113, 114, 114, 115, 116, 117, 118, 119, 120, 121, 122, 124, 125, 126, 128, 129, 131, 132, 133, 135, 137, 138, 139, 141, 142, 144, 145, 146, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159 },
 258   { 113, 114, 114, 115, 116, 117, 118, 118, 120, 121, 122, 123, 124, 125, 127, 128, 129, 131, 132, 134, 135, 136, 138, 139, 141, 142, 143, 145, 146, 147, 148, 149, 150, 152, 152, 153, 154, 155, 156, 157, 158 }
 259 };
 260
 261
 262
 263 /*
 264  * Calculates and returns the angle to the target or in the given
 265  * direction.
 266  *
 267  * Note:  If a compass direction is supplied, we ignore any target.
 268  * Note:  We supply the angle divided by 2.
 269  */
 270 int get_angle_to_target(int y0, int x0, int y1, int x1, int dir)
 271 {
 272         int ny, nx;
 273         int dist_conv;
 274
 275         /* No valid compass direction given */
 276         if ((dir == 0) || (dir == 5) || (dir > 9))
 277         {
 278                 /* Check for a valid target */
 279                 if ((y1) && (x1))
 280                 {
 281                         /* Get absolute distance between source and target */
 282                         int dy = ABS(y1 - y0);
 283                         int dx = ABS(x1 - x0);
 284
 285                         /* Calculate distance conversion factor */
 286                         if ((dy > 20) || (dx > 20))
 287                         {
 288                                 /* Must shrink the distance to avoid illegal table access */
 289                                 if (dy > dx) dist_conv = 1 + (10 * dy / 20);
 290                                 else         dist_conv = 1 + (10 * dx / 20);
 291                         }
 292                         else
 293                         {
 294                                 dist_conv = 10;
 295                         }
 296                         /* Convert and reorient grid for table access */
 297                         ny = 20 + 10 * (y1 - y0) / dist_conv;
 298                         nx = 20 + 10 * (x1 - x0) / dist_conv;
 299
 300                         /* Illegal table access is bad */
 301                         if ((ny < 0) || (ny > 40) || (nx < 0) || (nx > 40))
 302                         {
 303                                 /* Note error */
 304                                 return (-1);
 305                         }
 306                 }
 307
 308                 /* No compass direction and no target --> note error */
 309                 else
 310                 {
 311                         return (-1);
 312                 }
 313         }
 314
 315         /* We have a valid compass direction */
 316         else
 317         {
 318                 /* Step in that direction a bunch of times, get target */
 319                 y1 = y0 + (ddy_ddd[dir] * 10);
 320                 x1 = x0 + (ddx_ddd[dir] * 10);
 321
 322                 /* Convert to table grids */
 323                 ny = 20 + (y1 - y0);
 324                 nx = 20 + (x1 - x0);
 325         }
 326
 327         /* Get angle to target. */
 328         return (get_angle_to_grid[ny][nx]);
 329 }
 330
 331 /*
 332  * Using the angle given, find a grid that is in that direction from the
 333  * origin.
 334  *
 335  * Note:  This function does not yield very good results when the
 336  * character is adjacent to the outer wall of the dungeon and the projection
 337  * heads towards it.
 338  */
 339 void get_grid_using_angle(int angle, int y0, int x0, int *ty, int *tx)
 340 {
 341         int y, x;
 342         int best_y = 0, best_x = 0;
 343
 344         int diff;
 345         int this_angle;
 346         int fudge = 180;
 347
 348
 349         /* Angle must be legal */
 350         if ((angle < 0) || (angle >= 180)) return;
 351
 352         /* Scan the table, get as good a match as possible */
 353         for (y = 0; y < 41; y++)
 354         {
 355                 for (x = 0; x < 41; x++)
 356                 {
 357                         /* Corresponding grid in dungeon must be fully in bounds  XXX */
 358                         if (!in_bounds_fully(y0 - 20 + y, x0 - 20 + x)) continue;
 359
 360                         /* Check this table grid */
 361                         this_angle = get_angle_to_grid[y][x];
 362
 363                         /* Get inaccuracy of this angle */
 364                         diff = ABS(angle - this_angle);
 365
 366                         /* Inaccuracy is lower than previous best */
 367                         if (diff < fudge)
 368                         {
 369                                 /* Note coordinates */
 370                                 best_y = y;
 371                                 best_x = x;
 372
 373                                 /* Save inaccuracy as a new best */
 374                                 fudge = diff;
 375
 376                                 /* Note perfection */
 377                                 if (fudge == 0) break;
 378                         }
 379                 }
 380
 381                 /* Note perfection */
 382                 if (fudge == 0) break;
 383         }
 384
 385         /* We have an unacceptably large fudge factor */
 386         if (fudge >= 30)
 387         {
 388                 /* Set target to original grid */
 389                 *ty = y0;
 390                 *tx = x0;
 391         }
 392
 393         /* Usual case */
 394         else
 395         {
 396                 /* Set target */
 397                 *ty = y0 - 20 + best_y;
 398                 *tx = x0 - 20 + best_x;
 399         }
 400 }
 401