plomlompom.com Git - plomrogue/blob - src/server/field_of_view.c

   1 /* src/server/field_of_view.c */
   2
   3 #include "field_of_view.h"
   4 #include <stdint.h> /* uint8_t, uint16_t, uint32_t, int32_t */
   5 #include <stdlib.h> /* free() */
   6 #include <string.h> /* memset() */
   7 #include "../common/rexit.h" /* exit_trouble() */
   8 #include "../common/try_malloc.h" /* try_malloc() */
   9 #include "map.h" /* yx_to_map_pos() */
  10 #include "things.h" /* Thing */
  11 #include "yx_uint8.h" /* yx_uint8 */
  12 #include "world.h" /* world  */
  13
  14
  15
  16 /* Number of degrees a circle is divided into. The greater it is, the greater
  17  * the angle precision. But make it one whole zero larger and bizarre FOV bugs
  18  * appear on large maps, probably due to value overflows.
  19  */
  20 #define CIRCLE 3600000
  21
  22
  23
  24 /* Values for mv_yx_in_dir_wrap()'s wrapping directory memory. */
  25 enum wraps
  26 {
  27     WRAP_N = 0x01,
  28     WRAP_S = 0x02,
  29     WRAP_E = 0x04,
  30     WRAP_W = 0x08
  31 };
  32
  33
  34
  35 /* Angle of a shadow. */
  36 struct shadow_angle
  37 {
  38     struct shadow_angle * next;
  39     uint32_t left_angle;
  40     uint32_t right_angle;
  41 };
  42
  43
  44
  45 /* Move "yx" into hex direction "d". */
  46 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx);
  47
  48 /* Move "yx" into hex direction "d". If this moves "yx" beyond the minimal (0)
  49  * or maximal (UINT8_MAX) column or row, it wraps to the opposite side. Such
  50  * wrapping is returned as a wraps enum value and stored, so that further calls
  51  * to move "yx" back into the opposite direction may unwrap it again. Pass an
  52  * "unwrap" of !0 to re-set the internal wrap memory to 0.
  53  */
  54 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap);
  55
  56 /* Wrapper to "mv_yx_in_dir_wrap()", returns 1 if the wrapped function moved
  57  * "yx" within the wrap borders and the map size, else 0.
  58  */
  59 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx);
  60
  61 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
  62 static uint32_t correct_angle(int32_t angle);
  63
  64 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
  65  * it meets the shadow from the right or the left. Returns 1 on success, else 0.
  66  */
  67 static uint8_t try_merge(struct shadow_angle * shadow,
  68                          uint32_t left_angle, uint32_t right_angle);
  69
  70 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
  71  * existing shadow angle in "shadows". On success, see if this leads to any
  72  * additional shadow angle overlaps and merge these accordingly. Return 1 on
  73  * success, else 0.
  74  */
  75 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
  76                                   struct shadow_angle ** shadows);
  77
  78 /* If "pos_in_map" in angle between"left_angle" to "right_angle" to the viewing
  79  * actor is in a shadow from the shadow list "shadows", mark it as HIDDEN on the
  80  * "fov_map"; else, if the world map features a viewing obstacle on the world
  81  * map, calculate its shadow angle to the viewer and add it to "shadows".
  82  */
  83 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
  84                        struct shadow_angle ** shadows, uint16_t pos_in_map,
  85                        uint8_t * fov_map);
  86
  87 /* Free shadow angles list "angles". */
  88 static void free_angles(struct shadow_angle * angles);
  89
  90 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
  91  * on the circle of that distance to the origin on hex "hex_i" (as counted from
  92  * the circle's rightmost point), for setting shaded cells in "fov_map" and
  93  * potentially adding a new shadow to linked shadow angle list "shadows".
  94  */
  95 static void eval_position(uint16_t dist, uint16_t hex_i, uint8_t * fov_map,
  96                           struct yx_uint8 * test_pos,
  97                           struct shadow_angle ** shadows);
  98
  99
 100
 101 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx)
 102 {
 103     if     (d == 'e')
 104     {
 105         yx->x = yx->x + (yx->y % 2);
 106         yx->y--;
 107     }
 108     else if (d == 'd')
 109     {
 110         yx->x++;
 111     }
 112     else if (d == 'c')
 113     {
 114         yx->x = yx->x + (yx->y % 2);
 115         yx->y++;
 116     }
 117     else if (d == 'x')
 118     {
 119         yx->x = yx->x - !(yx->y % 2);
 120         yx->y++;
 121     }
 122     else if (d == 's')
 123     {
 124         yx->x--;
 125     }
 126     else if (d == 'w')
 127     {
 128         yx->x = yx->x - !(yx->y % 2);
 129         yx->y--;
 130     }
 131 }
 132
 133
 134
 135 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
 136 {
 137     static uint8_t wrap = 0;
 138     if (unwrap)
 139     {
 140         wrap = 0;
 141         return 0;
 142     }
 143     struct yx_uint8 original;
 144     original.y = yx->y;
 145     original.x = yx->x;
 146     mv_yx_in_hex_dir(d, yx);
 147     if      (strchr("edc", d) && yx->x < original.x)
 148     {
 149         wrap = wrap & WRAP_W ? wrap ^ WRAP_W : wrap | WRAP_E;
 150     }
 151     else if (strchr("xsw", d) && yx->x > original.x)
 152     {
 153         wrap = wrap & WRAP_E ? wrap ^ WRAP_E : wrap | WRAP_W;
 154     }
 155     if      (strchr("we", d) && yx->y > original.y)
 156     {
 157         wrap = wrap & WRAP_S ? wrap ^ WRAP_S : wrap | WRAP_N;
 158     }
 159     else if (strchr("xc", d) && yx->y < original.y)
 160     {
 161         wrap = wrap & WRAP_N ? wrap ^ WRAP_N : wrap | WRAP_S;
 162     }
 163     return wrap;
 164 }
 165
 166
 167
 168 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
 169 {
 170     uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
 171     if (!wraptest && yx->x < world.map.length && yx->y < world.map.length)
 172     {
 173         return 1;
 174     }
 175     return 0;
 176 }
 177
 178
 179
 180 static uint32_t correct_angle(int32_t angle)
 181 {
 182     while (angle < 0)
 183     {
 184         angle = angle + CIRCLE;
 185     }
 186     while (angle > CIRCLE)
 187     {
 188         angle = angle - CIRCLE;
 189     }
 190     return angle;
 191 }
 192
 193
 194
 195 static uint8_t try_merge(struct shadow_angle * shadow,
 196                          uint32_t left_angle, uint32_t right_angle)
 197 {
 198     if      (   shadow->right_angle <= left_angle + 1
 199              && shadow->right_angle >= right_angle)
 200     {
 201         shadow->right_angle = right_angle;
 202     }
 203     else if (   shadow->left_angle + 1 >= right_angle
 204              && shadow->left_angle     <= left_angle)
 205     {
 206         shadow->left_angle = left_angle;
 207     }
 208     else
 209     {
 210         return 0;
 211     }
 212     return 1;
 213 }
 214
 215
 216
 217 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
 218                                   struct shadow_angle ** shadows)
 219 {
 220     uint8_t angle_merge = 0;
 221     struct shadow_angle * shadow;
 222     for (shadow = *shadows; shadow; shadow = shadow->next)
 223     {
 224         if (try_merge(shadow, left_angle, right_angle))
 225         {
 226             angle_merge = 1;
 227         }
 228     }
 229     if (angle_merge)
 230     {
 231         struct shadow_angle * shadow1;
 232         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
 233         {
 234             struct shadow_angle * last_shadow = NULL;
 235             struct shadow_angle * shadow2;
 236             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
 237             {
 238                 if (   shadow1 != shadow2
 239                     && try_merge(shadow1, shadow2->left_angle,
 240                                           shadow2->right_angle))
 241                 {
 242                     struct shadow_angle * to_free = shadow2;
 243                     if (last_shadow)
 244                     {
 245                         last_shadow->next = shadow2->next;
 246                         shadow2 = last_shadow;
 247                     }
 248                     else
 249                     {
 250                         *shadows = shadow2->next;
 251                         shadow2 = *shadows;
 252                     }
 253                     free(to_free);
 254                 }
 255                 last_shadow = shadow2;
 256             }
 257         }
 258     }
 259     return angle_merge;
 260 }
 261
 262
 263
 264 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
 265                        struct shadow_angle ** shadows, uint16_t pos_in_map,
 266                        uint8_t * fov_map)
 267 {
 268     char * f_name = "set_shadow()";
 269     struct shadow_angle * shadow_i;
 270     if (fov_map[pos_in_map] & VISIBLE)
 271     {
 272         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 273         {
 274             if (   left_angle <=  shadow_i->left_angle
 275                 && right_angle >= shadow_i->right_angle)
 276             {
 277                 fov_map[pos_in_map] = HIDDEN;
 278                 return;
 279             }
 280         }
 281     }
 282     if ('X' == world.map.cells[pos_in_map])
 283     {
 284         if (!try_merging_angles(left_angle, right_angle, shadows))
 285         {
 286             struct shadow_angle * shadow;
 287             shadow = try_malloc(sizeof(struct shadow_angle), f_name);
 288             shadow->left_angle  = left_angle;
 289             shadow->right_angle = right_angle;
 290             shadow->next = NULL;
 291             if (*shadows)
 292             {
 293                 for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 294                 {
 295                     if (!shadow_i->next)
 296                     {
 297                         shadow_i->next = shadow;
 298                         return;
 299                     }
 300                 }
 301             }
 302             *shadows = shadow;
 303         }
 304     }
 305 }
 306
 307
 308
 309 static void free_angles(struct shadow_angle * angles)
 310 {
 311     if (angles->next)
 312     {
 313         free_angles(angles->next);
 314     }
 315     free(angles);
 316 }
 317
 318
 319
 320 static void eval_position(uint16_t dist, uint16_t hex_i, uint8_t * fov_map,
 321                           struct yx_uint8 * test_pos,
 322                           struct shadow_angle ** shadows)
 323 {
 324     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
 325                                      - ((hex_i * (CIRCLE / 6)) / dist);
 326     int32_t right_angle_uncorrected =   left_angle_uncorrected
 327                                       - (CIRCLE / (6 * dist));
 328     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
 329     uint32_t right_angle = correct_angle(right_angle_uncorrected);
 330     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
 331     uint16_t pos_in_map = yx_to_map_pos(test_pos);
 332     set_shadow(left_angle, right_angle_1st, shadows, pos_in_map, fov_map);
 333     if (right_angle_1st != right_angle)
 334     {
 335         left_angle = CIRCLE;
 336         set_shadow(left_angle, right_angle, shadows, pos_in_map, fov_map);
 337     }
 338 }
 339
 340
 341
 342 extern uint8_t * build_fov_map(struct Thing * eye)
 343 {
 344     char * f_name = "build_fov_map()";
 345     uint32_t map_size = world.map.length * world.map.length;
 346     uint8_t * fov_map = try_malloc(map_size, f_name);
 347     memset(fov_map, VISIBLE, map_size);
 348     struct yx_uint8 test_pos = eye->pos;
 349     struct shadow_angle * shadows = NULL;
 350     char * circle_dirs = "xswedc";
 351     uint16_t dist;
 352     uint8_t first_round, circle_on_map;
 353     for (first_round = 1, dist = 1, circle_on_map = 1; circle_on_map; dist++)
 354     {
 355         if (!first_round)
 356         {
 357             mv_yx_in_dir_legal('c', &test_pos);
 358         }
 359         char dir = 'd';
 360         uint8_t i_dir = first_round = circle_on_map = 0;
 361         uint16_t i_dist, hex_i;
 362         for (hex_i = 0, i_dist = 1; hex_i < 6 * dist; i_dist++, hex_i++)
 363         {
 364             if (mv_yx_in_dir_legal(dir, &test_pos))
 365             {
 366                 eval_position(dist, hex_i, fov_map, &test_pos, &shadows);
 367                 circle_on_map = 1;
 368             }
 369             dir = circle_dirs[i_dir];
 370             if (dist == i_dist)
 371             {
 372                 i_dist = 0;
 373                 i_dir++;
 374             }
 375         }
 376     }
 377     mv_yx_in_dir_wrap(0, NULL, 1);
 378     free_angles(shadows);
 379     return fov_map;
 380 }